LetMyPeopleCode.com

A blog about software, schmaltz, and monkey-patches for the soul

Menu
  • About Greg Bulmash
  • Greg Talks Tech
  • Privacy Policy
Menu
"The Coding Interview"

The Coding Interview: No Repeats Please

Posted on February 1, 2022January 30, 2022 by Greg Bulmash

This series answers coding interview questions from the Coding Interview Prep collection at freeCodeCamp. You can find more with the interview questions tag.

This is an algorithm problem. It came in handy in a later exercise.

You get a string like "aab" and have to find all the possible combinations, then remove all the combinations where two characters repeat. The trick is the statement “assume that all characters in the provided string are unique.” That means you have to treat every character as a unique token and base your answer on a set with every possible permutation of those tokens, even if some permutations repeat.

Then from that set provide the number of strings without consecutively repeated characters, even if the strings themselves repeat. So for aab, there are 6 permutations: aab, aab, aba, aba, baa, baa, the only ones without consecutively repeating characters are aba and aba, so the answer is 2. If that felt confusing, think of the two as as a1 and a2 instead. Then aba, aba becomes a1ba2, a2ba1.

Solution explained

I broke it into two functions for manageability, one to generate a set of all combinations, then one to compare them.

The one that generates all the combos is allcombos() and uses recursion. I’ll admit that I had to look up someone else’s answer on how to generate the set, but by describing it, I’m hoping I’m not only helping someone else understand what’s going on, but helping myself work out the logic in a way I not only understand now, but will understand when I re-read this.

So let’s walk through the progress of allcombos() with the simple string of aab. I’ll represent the letters as A(1), A(2), and B.

  • We start our first loop iteration with A(1) as first and A(2)B as rest.
    • A(2)B gets sent to allcombos().
    • A(2) becomes first, B becomes rest.
      • B gets sent to allcombos()
      • B gets returned (because it’s less than 2 in length)
    • A(2)+B gets pushed to full_set in the A(2)B loop’s scope. full_set == ['A(2)B'].
    • Loop iterates and B becomes first, A(2) becomes rest.
      • A(2) gets sent to allcombos()
      • A(2) gets returned (because it’s less than 2 in length)
    • B + A(2) gets pushed to full_set in the A(2)B loop’s scope. full_set == ['A(2)B', 'BA(2)].
    • In the top level loop’s scope A(1) + A(2)B and A(1) + BA(2) get pushed to full_set. full_set == ['A(1)A(2)B', 'A(1)BA(2)]
  • We start our second loop iteration with B as first and A(1)A(2) as rest.
  • …

I’m not a natural at recursion, so it was a little difficult to wrap my head around and still sort of is, but there you have it.

Once we have the full set, then we just loop through the combos and loop through each combo’s letters comparing each to the one before it. For a string of length n, there are n-1 comparisons, since the first letter has nothing before it.

str[1] == str[0]
str[2] == str[1] 

If either one of these matches is true, move onto the next string. If none are, increment the count of qualifying strings by one. For the six strings in aab‘s permutations, the counts are:

  • On the two instances of aab it matches on the first comparison, stops checking, and nothing’s added to the count (0 qualifying, 2 comparisons).
  • On the two of aba, neither of the two comparisons match and one is added to the count for each (2 qualifying, 4 comparisons).
  • On the two of baa, the match happens on the second comparison and zero is added to the count (0 qualifying, 4 comparisons)

For a total of 2 qualifying and 10 comparisons.

I probably need a buddy-edit as a sanity check to see if all that makes sense to anyone but me.

Solution

function allcombos(str){
  if (str.length < 2 ) return str

  let full_set = [] 
    
  for (let i = 0; i < str.length; i++){
    let first = str[i]
    let rest = str.slice(0, i) + str.slice(i + 1, str.length)
    for (let index of allcombos(rest)){
      full_set.push(first + index) 
    }
  }
  return full_set
}

function permAlone(str) {
  let full = allcombos(str);
  let final = 0;
  for(let i in full){
    let isgood = true;
    for(let j = 1; j < full[i].length; j++){
      if(full[i][j] === full[i][j-1]){
        isgood = false;
        break;
      }
    }
    if (isgood) final++;
  }
  return final;
}

Related

Leave a Reply Cancel reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.

Recent Posts

  • Job Hunt Diary 2023: Verizon Is Passive-Aggressive?
  • Job Hunt Diary 2023: Eliciting Responses
  • Job Hunt Diary 2023: And so on, and so on…
  • Job Hunt Diary 2023: Freelancing and warning words
  • Job Hunt Diary 2023: Not all job fairs are created equal

Archives

  • March 2023
  • February 2023
  • January 2023
  • December 2022
  • November 2022
  • September 2022
  • May 2022
  • April 2022
  • March 2022
  • February 2022
  • January 2022
  • November 2021
  • May 2021
  • April 2020
  • March 2020

Categories

  • Apps
  • Computing
  • Frameworks and Libraries
  • Games
  • Hacks
  • Hardware
  • JavaScript
  • Mac
  • Mobile
  • Other Art Projects
  • Productivity
  • Programming
  • Projects
  • Python
  • Society & Culture
  • Teaching Code
  • Tech Career
  • Uncategorized
  • WebTech
  • Writing

Tag Cloud

Adobe advertising bad ads browser hunt clown car code sample comcast commute copy writing CX design Developer Relations dev rel evernote game demo google drive hardware review health home office home studio internet interview questions j job hunt job hunt diary Mac magento meta-coding OneNote PEO productivity review speedtest t-mobile Windows xfinity

©2023 LetMyPeopleCode.com | Theme by SuperbThemes