Cracking the Machine Learning Interview — Binary Search

This is a special topic in my machine learning interview preparation series. I have written an overview, which should be very useful if you are preparing for interviews.

This post is about coding interviews. And I will use binary search as an example. In a typical coding interview, you and the interviewer will first give a brief introduction about yourselves. The interviewer may ask a little more about your experience before moving on to the coding question. The time for coding questions is usually 15 min for one problem or 30 min for two problems. The two problems may or may not be related. For example, you are given an array of positive numbers and a random() function which uniformly generates a random number between 0 and 1. Can you write a function to randomly sample a number from the given array with probability proportional to the value.

The description of the problem can be intentionally vague so that you can ask clarification questions. In this example, you may ask what should the function return and the interviewer will let you return the index.

Now you should think aloud by telling the interviewer that you will first normalize the array so that all elements sum up to one. Then you will calculate the cumulative sum of the array, and generate a random number using random() function. After that you will use binary search to find the index of the sampled element by looking for the interval in the cumulative sum array where the random number lies in. Then you start writing the code. An example can be as follows.

There are of course many ways to write the code. I’m choosing a version that’s friendly to non Python programmers and should be good to pass the interview.

A few things to pay attention. It may not be necessary to check if the array is empty. But it’s better to have it. You may find the formula to calculate mid can be simplified. But the current one is safer because start + end may be too large for the system. The hardest part in binary search is to handle boundaries so that it does not fall in endless loops and returns the correct index.

After the coding questions, you will have the opportunity to ask questions about the company, just like the other interview rounds. Be prepared because it is a good opportunity to know more about the team.

Good luck!