Interview Question- String subsequence challenge

kravmaguy · August 3, 2021, 9:03pm

I want to find the minimum subsequence. Have I done this correctly or how can it be better? thank you.

KravMaguy/Technical-interview/blob/master/interview/repeated_subsequence.js

const findSmallestRepeatedSubsequence = (primary, secondary) => {
  const toadd = primary;
  while (primary.length < secondary.length) {
    primary = primary + toadd;
  }
  if (primary === secondary) {
    //it is a subsequence
    let temp;
    let incrementer = 0;
    return slicer(incrementer, primary);
  }
  if (primary.length >= secondary.length) {
    return Number(`-${secondary.length}`);
  }
};

const slicer = (incrementer, primary) => {
  if (incrementer > primary.length) return;
  incrementer += 1;
  temp = primary.slice(0, incrementer);

This file has been truncated. show original

bbsmooth · August 3, 2021, 10:17pm

I’m not sure I completely understand the objective here? Could you give a little more detail on what this function is supposed to be doing?

kravmaguy · August 4, 2021, 7:45pm

determine if primary is a subsequence of secondary

Primary: AB
Secondary: ABC
False

Primary: AB
Secondary: ABAB
True

Primary: ABAB
Secondary: ABABAB
False

If primary is a subsequence of secondary return the minimum of primary that is a subsequence

Primary: ABAB
Secondary: ABABABAB
minimum subsequence: AB

if primary is not a subsequence return negative length of secondary

JeremyLT · August 4, 2021, 8:23pm

Ah, I would try to simplify your code. I see this as two phases

can the second string be made by repeating the first?
is there any substring of the first that can recreate the first?

I think you can use the function itself to check 2.

Here is a guess at what might work

function findSmallestRepeatedSubsequence(first, second) {
  // Check if the second can evenly hold
  //  multiples of the first
  if (second.length % first.length !== 0)
    return false;
  // Check for repetition of first
  for (let i = 0; i < second.length; i += first.length)
    if (second.substring(i, i + first.length) != first)
      return false;
  // Check if smaller subseq will work
  for (let i = 1; i <= first.length/2; i++)
    if (findSmallestRepeatedSubsequence(first.substring(0, i), first))
      return first.substring(0, i);
  // No smaller subseq of first will work
  return first;
}

system · February 3, 2022, 8:23am

This topic was automatically closed 182 days after the last reply. New replies are no longer allowed.