LetMyPeopleCode.com

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

Menu
  • About Greg
  • About LMPC
  • Privacy Policy
Menu
"The Coding Interview"

The Coding Interview: Rosetta Code – 100 Doors

Posted on January 31, 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.

In this exercise, we receive a number of doors. It’s 100 in the title, but the function gets passed a number of doors, so it should be able to handle an arbitrary # of doors.

We start with all n doors closed. On the first pass, you toggle every door to the opposite of its state (closed becomes open, open becomes closed). We iterate the toggle n times. Let’s call the iteration count c. Applying the toggle to every cth door on each iteration, until on the final iteration, it’s only applied to door n.

Then return a set with only the numbers of the doors that are open.

Solution Explained

You have to start with an array of n doors. Easy enough to create a 100-element array with Array(100), but filling it… I wanted to see if there was a more efficient way to do this than a loop through. Turns out there’s a fill method on arrays. It’s worth checking Array.protytpe.fill() compatibility, though, since it’s not available on IE or node < 4.0.0.

Then start a loop from 1 to numDoors. Start counting at 1 because it’s used as a step value for the interior loop.

The interior loop starts at i, so when you’re going with every second item, the second loop starts with the second item (i – 1), and so on. It’s one of those lovely parts of the iteration starting from 1 and the index values starting from 0. Somewhere you have to do some mathematical gymnastics to make them work together.

While I was writing the code, I used 0 and 1 to represent closed and open, respectively. I had to take a “bio-break” while writing this description, and during that, I wondered if using a boolean would be more memory efficient than using ‘0’ and ‘1’ as representations of closed and open. A little research later and it seemed they’ll both use the same amount of memory depending on the platform, possibly a little less for the boolean. But it occurred to me that the booleans might make it more readable too, so I refactored with booleans.

In the interior loop, examine door j-1 (first loop: 0, 1, 2, 3…, second loop: 1, 3, 5, 7…). Remember, arrays are zero-indexed. Then using a ternary operator, “flip the bit.” I use that term because a boolean is essentially a representation of the value of a single bit: on or off, 1 or 0, true or false. Since I started programming at 11, I literally “grew up” with that concept and lingo.

When it’s all done, we run a loop through the array to identify the index values of all the open doors. The trick is that the index will be provided to the loop as a string. Add 1 to the integer value of each to get the nth value, and push the value to the array that gets returned.

Solution

function getFinalOpenedDoors(numDoors) {
  let doors = new Array(numDoors).fill(false);
  for(let i = 1; i <= numDoors; i++){
    for(let j = i; j <= numDoors; j += i){
      doors[ j - 1 ] = (doors[ j - 1 ] === false) ? true : false;
    }
  }
  let open = [];
  for(let i in doors){
    if(doors[ i ]) open.push(parseInt( i ) + 1 );
  }
  return(open)
}

 

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

  • My first commute into Seattle since COVID
  • Lenovo P12 Review: A Second Screen – With Caveats
  • Defective Quidel QuickVue COVID Tests
  • The Great American Browser Hunt
  • Chrome’s Usability Crime

Archives

  • April 2022
  • March 2022
  • February 2022
  • January 2022
  • November 2021
  • May 2021
  • April 2020
  • March 2020

Categories

  • Apps
  • Games
  • Hardware
  • JavaScript
  • Mobile
  • Productivity
  • Programming
  • Society & Culture
  • Teaching Code
  • Tech Career
  • Uncategorized
  • WebTech
  • Writing

Tag Cloud

browser hunt code sample commute CX game demo hardware review health interview questions j job hunt diary Mac meta-coding OneNote review Windows

©2022 LetMyPeopleCode.com | Theme by SuperbThemes