Preliminary Thoughts

During my earlier years as an engineer, I frequently visited joelonsoftware.com. One article that resonated with me discussed the critical decision of whether to hire a candidate based on their intelligence and ability to execute tasks, all within a limited timeframe. Does the interview provide evidence for both qualities? Why or why not?

I come from an Electrical Engineering background and have limited formal training in Computer Science. My programming experiences, such as developing a maze-solving program for a Micromouse project, don’t reflect traditional CS education. Therefore, I prefer to avoid questions that hinge on specific computer science curricula.

A common joke at Google is that during interviews, candidates are asked to build a compiler, only to later be tasked with a simple button color change. From my experience in application front-end work, much of the role involves reading from and writing to data stores or transforming data formats. While there are numerous roles focused on infrastructure and AI, my expertise lies in evaluating general software engineers and front-end developers.

In coding interviews, my goal is to assess how candidates perform against my team in everyday tasks like coding, testing, and debugging. The approach to problem-solving often reveals more than academic credentials.

Coding Challenge

Given a sorted positive array a = [3, 4, 6, 9, 10, 12, 14, 15, 17, 19, 21], define a function f(a, x) that returns the next smallest number or -1 in case of errors. For example:

• f(a, 12) should return 12
• f(a, 13) should also return 12

The beauty of this question lies in its clarity. It doesn't favor those with formal CS backgrounds or advanced degrees. If an interview question requires extensive explanation, that’s time lost in a limited session.

The selected sorted array is intentional. Negative numbers and zero are irrelevant to the problem and are excluded. With exactly eleven elements, the indices range from 0 to 10, allowing for straightforward binary division. The first test case centers on 12, while the second involves 13, necessitating a directional change in the binary search.

I start by prompting candidates to suggest test cases, like those for x = 12 and x = 13. While this may seem unusual for a coding question, it offers insight into their familiarity with test-driven development and handling edge cases. With some nudging, we typically compile the following list:

• f(a, 12) = 12 // found
• f(a, 13) = 12 // next smallest
• f(a, 2) = -1 // out of bounds too low
• f(a, 22) = 21 // out of bounds too high
• f(a, 3) = 3 // exact left boundary
• f(a, 21) = 21 // exact right boundary
• f([], x) = -1 // empty array
• f(null, x) = -1 // invalid input

Surprisingly, many developers struggle to compile the complete list. Some may overlook edge cases, while others might misunderstand the question entirely. Each of these instances sheds light on their professional coding experience.

Next, we discuss the algorithm. A brute-force solution with a for loop at O(n) is acceptable for the youngest interns. I’ve interviewed students from HBCUs who are just beginning their programming journey; a well-implemented for loop solution can merit a hire for them.

For others, we delve into a binary search solution with O(log n) complexity. I encourage candidates to articulate their thought process, ensuring they're aligned before they begin coding. If you’re up for the challenge, give it a try. Remember to debug it against all eight test cases!

The first video titled "How to: Work at Google — Example Coding/Engineering Interview" showcases effective strategies for handling coding interviews at Google.

Welcome Back

How long did it take you? More than 30 minutes? Did your algorithm function on the first attempt? Did you manage the midpoint calculations effectively? Whether you chose an iterative or recursive solution, did you remember to return the correct values? Don’t worry; I faced challenges in my initial attempts as well.

The Omelet Test

Years ago, I read The Making of a Chef, which explored various paths to becoming a master chef. One route involved passing the Certified Master Chef exam, while another followed chefs like Michael Symon, who built their careers through social connections. Finally, there’s Thomas Keller, who rose from dishwasher to renowned chef under the guidance of French masters.

I believe there are parallels between chefs and programmers. Experienced chefs exhibit specific characteristics: their preparation, cooking, and presentation reflect years of practice. In The Hundred-Foot Journey, the character Hassan Kadam demonstrates this when his omelet is judged after just one bite by Madam Mallory, played by Helen Mirren.

My interview question serves as a coding equivalent of the omelet test. I look for indicators of experienced programmers in how they tackle and resolve this well-known problem.

The Solution

Numerous solutions exist, but the simplest iterative approach could be structured as follows:

function f(a, x) {

if (a == null || a.length == 0) return -1;

var answer = -1;

var low = 0;

var high = a.length - 1;

while(low <= high) {

var mid = Math.floor((low + high) / 2);

if (a[mid] == x) {

return x;

} else if (a[mid] < x) {

answer = a[mid];

low = mid + 1;

} else {

high = mid - 1;

}

}

return answer;

}

In a binary search, the loop continues as long as low is less than or equal to high, effectively bisecting until the item is located. The equality check is critical, especially as the array reduces to a size of one. Adjusting mid by one is also essential to prevent infinite loops.

Finding the next smallest number adds complexity. A smart approach merges linear and binary search methods, initializing answer with -1 and updating it whenever a[mid] is less than x. If x isn’t found, the answer will represent the next smallest value upon exiting the loop.

For experienced candidates, they might include precondition checks to streamline edge cases:

// Precondition checks

if (a == null || a.length == 0) return -1;

if (x < a[0]) return -1;

if (x == a[0]) return a[0];

if (x >= a[a.length - 1]) return a[a.length - 1];

How did you fare? It wasn’t straightforward, was it? This difficulty is intentional.

Why Binary Search?

Binary search is often regarded as one of the trickiest "simple" coding problems. While the concept seems elementary, implementation can be quite challenging. Jon Bentley, a former professor at CMU, noted that only about 10% of professional programmers could correctly execute it, even among PhD students.

"I was amazed: given ample time, only about ten percent of professional programmers were able to get this small program right."

Bentley highlights that it took 16 years for computer scientists to develop a bug-free version of the algorithm.

In 2006, Joshua Bloch, Google's Chief Java Architect and author of Effective Java, disclosed that the Java implementation had a hidden bug for nine years, stemming from an erroneous midpoint calculation that caused integer overflow for large datasets:

var mid = Math.floor(low + high) / 2; // problematic

var mid = low + Math.floor((high - low) / 2); // correct

Implementing a basic binary search is surprisingly complex. The added challenge of finding the next smallest number amplifies the difficulty. Once candidates dive deep into debugging the binary search, managing the low, high, and mid values can become overwhelming.

An effective solution typically spans 30-40 lines of code, making it manageable within a one-hour interview window, while also allowing for note-taking. This question encapsulates the full journey from test cases to coding and debugging, providing hiring committees with clear insights into a candidate's progress.

(Note: On the Google hiring committee, you have 24 hours to review four interview packets, each containing five interviews. So, you're evaluating 20 interviews alongside your regular job, family commitments, and sleep!)

Hire or No Hire?

There’s no flawless method for assessing candidates. I recognize that I may have been overly strict or lenient with certain individuals. Like the culinary analogy, I look for foundational skills akin to a chef's knife techniques—candidates should be able to code without basic compiler errors.

Key indicators include:

• Appropriate function and variable names (avoid excessively long names)
• Properly closed braces for functions, loops, and conditionals
• Understanding of array indices (0 to length-1)
• Correct variable scoping and initialization
• Appropriate use of equality checks in conditionals
• Clear and readable code structure

Additional aspects I consider:

• Completeness in identifying test cases
• Progress from test cases to code and debugging
• Effective use of the whiteboard for debugging and explaining the binary search
• Overall communication skills and reactions to guidance
• Ability to recognize and recover from mistakes while maintaining forward momentum
• Preference for simplicity over convoluted if/else statements

Setting Expectations

For strong interns or L3 engineers, I expect them to complete the binary search within an hour with some assistance, particularly in test cases and debugging, while demonstrating solid progress and minimal syntax errors.

Mid-level L4 engineers should identify most test cases, implement a functional binary search solution with few bugs, and debug with minimal support. Strong candidates should have enough time left for a second question.

Senior L5 engineers should lead the interview, finishing with sufficient time for a system design question. They are likely to be aware of edge cases and potential integer overflow issues, possibly with minor bugs but showing quick progress.

For Product Managers or Engineering Managers, I adjust expectations based on their level, typically one level lower. While they should know how to code, perfection is not mandatory.

Ultimately, I’m always evaluating whether I would bring this candidate onto my team and how their skills align with my current team members. The best endorsement I can provide in a hiring packet is that the interview felt like a design discussion with a fellow Google engineer.

Post Script

Thank you for reading this far! I hope you found the insights both entertaining and informative. My intention is not to boast about my interview question, but to emphasize that complex questions aren't always necessary for making hiring decisions. Instead, consider how candidates code and debug, as well as the signals their style and pace convey. Does your coding interview question include test cases? Would they enhance the interview and provide clearer signals? Simplified questions can yield more effective evaluations, much to the hiring committee's appreciation!

To my knowledge, one of my former teammates continues to use this question, valuing its simplicity and range for effective hiring recommendations. Best of luck to you if you're interviewing at Google!

Credit

I obtained this interview question from a fellow Googler, whose name I can no longer recall. Thank you!

If you enjoyed this piece, please give it a clap, follow or subscribe to my account, or join Medium as a member through my referral link. Thank you!

What about Front End interviews? Here are my questions.

How I was able to retire from Google.

The second video, "Google Coding Interview With A Normal Software Engineer," offers a realistic perspective on the coding interview process at Google.