JavaScript Tech Interview Exercise 2: Binary Gap Exercise in Codility


You might not know about me that I have conducted tech interviews with over 500 software developers from more than twenty countries with the objective of identifying and hiring the best talent. I have also been in the candidate position, interviewing for positions ranging from junior developer to CTO.

In this series, I am exposing the secrets of JavaScript interviewing. You will not only refresh your JavaScript skills, but above all, you will learn the mindset required for solving interview exercises. We will start with simple tasks, and then transition to complex exercises that you could even use to build your portfolio.

Exercise: Suppose a positive integer N is given. Determine the binary representation of N, and find the longest subsequence of form 10*1 in this representation, where 0* stands for any number of zeros in the sequence. Examples: 11, 101, 1001, 10001 etc. Return the number of zeros in the longest sequence you found. If you didn’t find such a sequence, return zero.

You can read the original task description on Codility.

Solution:

Whenever you deal with a riddle, bear in mind, it doesn’t matter what techniques you use as long as your solution is correct. Don’t try to impress your interviewers with fancy techniques, don’t even think about announcing that you are going to use “functional programming” or “recursion” or anything else. Just get the job done.

Do explain your thought process! If you are on the right track, your interviewers will appreciate relating to how you think. If you are on the wrong track, your interviewers will often help you out, because they relate to you, and they want you to succeed.

You can read more interviewing tips in The Developer’s Edge.

Before coding, always plan your solution, and explain how you want to solve your task. Your interviewers may correct you, and best case, they say, you can start coding. In our case, the plan looks as follows:

  1. Convert N into a binary string
  2. Set a sequence counter to zero. Set a maximum sequence counter to zero.
  3. Iterate over each digit of the binary representation
    • If you find a zero, increase the sequence counter by one.
    • If you find a one, compare the sequence counter to the maximum sequence counter, and save the higher value in the maximum sequence counter. Then set the sequence counter to zero to read the upcoming sequence lengths.
  4. Once you finish, return the maximum sequence counter value.

Obtaining the binary representation: You may or may not know that integers have a toString method, and the first argument of toString is the base in which the number should be interpreted. Base 2 is binary, so all you need to do to convert an integer into its binary representation is

Chances are, you don’t know this trick. No problem. In most tech interviews, you can use google. If you formulate the right search expression such as “javascript binary representation of a number”, most of the time, you get a nice, compact StackOverflow page explaining the solution. Be careful with copy-pasting tens of lines of code. Look for deep understanding of the problem, and just implement a compact solution.

Never google for the exact solution of the task, because your interviewers may not know how to handle such an attempt.

In the unlikely case you are not allowed to use Google, nothing is lost. You can still solve the same problem in vanilla JavaScript. How do we convert a decimal number to binary on paper?

Suppose your number is 18.

  • 18 / 2 = 9, and the remainder is 0.
  • 9 / 2 = 4, and the remainder is 1.
  • 4 / 2 = 2, and the remainder is 0.
  • 2 / 2 = 1, and the remainder is 0.
  • 1 / 2 = 0, and the remainder is 1.

Read the digits from bottom-up to get the result: 10010.

Let’s write some code to get the same result:

The % (modulus) operator gives you the remainder of the division. The trunc function truncates the results. For instance, Math.trunc( 9.5 ) becomes 9.

If you can’t come up with this algorithm on your own, think in another way:

First we have to get the largest digit value, which is 16:

Then we divide this digit value by 2 until we get 1 to retrieve the digits of the binary number one by one. Whenever N is greater than or equal to the digit value, our upcoming digit is 1, and we have to subtract digit from N. Otherwise, our upcoming digit value is 0:

Enough said about the integer to binary conversion. Let’s continue with the state space of the solution.

Determining the state space:

We will use N.toString( 2 ) here to get the binary representation of N.

In order to identify a sequence of zeros bounded by ones, we have to know if the sequence has a left border. As every single positive binary number starts with 1, this condition is automatically true.

Side note: if N was allowed to be 0, even then, our function would return the correct result, because the string '0' does not have a trailing 1 in the sequence.

Therefore, the state space is quite simple: we need to know the binary string of the input, the number of zeros currently read in the sequence, and the longest string found so far.

Iteration: We have to read each digit of the solution one by one. The traditional way in most programming languages is a for loop.

We can also use the for..of loop of ES6 that enumerates each character of the string. Strings work as iterators and iterable objects in ES6. For more information, read my article titled ES6 Iterators and Generators in Practice. You can also find six more exercises belonging to this topic in this blogpost.

Reading the digits: Each digit can either be a zero or a one. We will branch off with an if-else statement:

Process the digits: If we read a zero, we have to increment the zero counter by one. If we read a one, we have to determine if we have just read the longest sequence of zeros by taking the maximum of result and zeroCount, and saving this maximum in result. After determining the new result value, we have to make sure to reset zeroCount to 0.

If you execute this algorithm in Codility, you can see that all your tests pass. I encourage you to solve other Codility tasks, as Codility is a great platform to practice coding challenges.

Now that we have solved this exercise together, don’t forget that there are four pillars for a successful tech interview:

  • Tech skills
  • Problem solving skills
  • Soft skills
  • Personal Branding

This blog addresses the first two skills. My other blog, devcareermastery.com addresses soft-skills, and my book The Developer’s Edge – How to Double Your Career Speed with Soft-Skills helps you with soft-skills as well as with your personal brand.

If you are interested in fine-tuning your JavaScript skills as well as your soft skills, I highly recommend that you consider purchasing The JavaScript Developer’s Career Bundle. This bundle contains my book ES6 in Practice, 4.5 hours of JavaScript videos, and The Developer’s Edge. You will not only be fully up-to-date with the latest version of JavaScript, but you will also learn how to build a fulfilling career for yourself.

Learn ES6 in Practice

Sign up below to access an ES6 course with many exercises and reference solutions.