Interview Criteria

Clarifying the question

There will always be an opportunity to clarify the question. As simple or obvious a question may sound, the interviewer is observing the candidate whether they jump into coding or take time to assess the problem. Companies do this because they already know the candidate can code, but whether they clarify their questions shows how they’ll approach problems in the workplace.

If the question seems so obvious it doesn’t need clarifying, consider the following approaches.

• Provide your own test cases and explain what you think the expected output is.

• Ask how optimal the solution has to be and if they are comfortable with a naive or slow solution.

• Ask if you need to worry about well-formatted input or caching repeated calls. Please clarify each and every coding question. Failing to do this can lead candidates to solve the wrong problem and that always leads to immediate rejection.

Thinking out loud and handling challenges

After clarifying the question, the candidate will start brainstorming algorithms to solve the coding problem. As the candidates is thinking, the interviewer is paying attention to the following details

• If the candidate is visibly stressed or frustrated thinking about this problem

• How the candidate is reasoning about the algorithm out loud and clearly explain where they’re stuck

Candidates that are visibly frustrated tend to overtly frown, let out unnecessary sounds like “grr”, “ugh”, “damn”, or display aggressive body language like clenching their fist. Any examples of the above can lead to quick rejection.

Interviewers aren’t particularly interested in candidates that immediately know the solution but are more interested if they can clearly identify what they are struggling with. If a solution is too slow, can they explain where the bottlenecks are and suggest data structures or algorithms to improve the running time? Thinking out loud will also help the interviewer suggest helpful non-penalty hints to help the candidate.

Outlining an algorithm

When you’re thinking about a solution to the coding problem, explain out loud to the interviewer. If the interviewer does not understand the algorithm, do not proceed to code.

If the algorithm is not simple enough for the interviewer, it’s too complicated to implement and will be assessed as part of communication. In this scenario, explain the algorithm simpler step-by-step. If they do understand the algorithm, explain what the running time of that algorithm is and why. This is absolutely important to determine if your interviewer is satisfied with your algorithm. If not, you will have to consider a more optimal solution.

When the interviewer fully understands the algorithm you intend to implement, outline it as comments at the top of the IDE.

Question: Given an array of integers, return the sum of the array.

# Use a variable to track the running sum
# Iterate through the array from left to right
# Add the value at each index to the running sum
# Return the running sum

Outlining algorithms naturally help candidates by communicating their thought processes and saving candidates time from implementing an algorithm the interviewer was not interested in.

Once you receive the “clear to code” from your interviewer, you may begin coding your algorithm.

Coding quality and speaking out loud

Interviewers will be assessing the following qualities from the candidate’s code

• Code that directly matches the outlined algorithm

• Readable variable names

• Simple and easy to follow code

• Ability to abstract irrelevant or unimportant details

For every line of code, mention which step of the algorithm you’re on and how you’ll be implementing that. If the first step is to use a tracking variable, an example explanation would be:

“I’ll be using an int variable named “runningSum” to track the sum of the array. This will help when we iterate the input array from left to right”.

General clean coding is an enormous topic that can’t be entirely covered in this document. But the general guidelines are to use meaningful variable names that represent its intention as well non-nested functions and functions that are small.

However, the ability to abstract details is important for both the interviewer and beneficial for the candidate. If there are parts of the algorithm that are trivial to understand but tedious to implement, the candidate can abstract that logic to simplify writing code. The interview is also happy to see this because they’re more interested in different parts of the algorithm.

To clarify, “abstracting” away code means using a dummy function to implement the solution for a small part of the algorithm.

# Simple Abstraction Examples
parseStrings(), getLeafNodes(), getMidPoint(), etc...

Proactivity

In each coding interview, an interviewer wants to see the candidate be proactive in the following

• Dry running their code against a test case

• Optimising their code

• Explaining the run time

After implementing their solution, a communicative candidate will first explain the running time of the algorithm and then ask whether the interviewer is interested in dry running or optimising their code.

Dry running code is an opportunity for the candidate to explain their code line-by-line against an example test case. Speaking out loud and referencing the original algorithm will never disappoint the interviewer.

To optimise their code, the candidate will have to identify the bottleneck and think out loud potential solutions. This is the exact same process when outlining their algorithm at the beginning of the interview.

Getting the running time correct

This is the icing on top after solving the coding question. This will never be enough to save a bombed interview or bomb an interview itself. However, this area is important enough when deciding whether to level a candidate as a junior engineer or mid-level software engineer.

What’s expected at the junior level is to determine the running time of their algorithm correctly. A mid-level candidate will solve for the running time and explain exactly where the bottleneck is.

A lot of candidates get confused on what “solving” the running time means. An example is asserting your algorithm runs in O(n log n). Solving for the running time complexity is going through your code line-by-line and identifying the time complexity of each line of code and then showing the interviewer which line is the bottleneck.

# psuedo-code

my_list = [4,3,2,1]

# O(n)
for elem in my_list:
    print(elem)
    
# O(n log n)
sorted_list = sorted(my_list)

Junior engineer: “The running time is O(n log n)”

Mid-level engineer: “Going line-by-line, the for-loop has a linear time complexity of O(n). Depending on the sorting algorithm, we can assume a running time of O(n log n) if it’s implemented using merge sort. Other algorithms like count sort can reduce the time complexity to O(n)”

You are correct in identifying that it's O(log n), but you fail to identify what it is. it is the number of steps it takes to reach the base case. Since each time you are cutting the list in half, each time you call foo, you are working with a list which is half the size of the one you just had. Therefore, it takes O(log n) steps to reach the base case.

The next question is: how much work is done at each step? In the first step, the list is broken in half, which requires n memory copies. In the second step, two lists of size n/2 are broken in half. The amount of work done remains the same! From one step to the next, the size of each list you are cutting halves (due to calling foo(n//2)), but the number of lists you must do this for doubles (since you are calling foo twice recursively). Therefore, for each step, you are always doing O(n) work.

O(log n) steps * O(n) work at each step = O(n log n) in total.

Source: Time complexity of an algorithm in python O(n log n) - Stack Overflow