How to approach a technical interview question ?

TLDR: Ask the right questions.

A technical round is often a face to face round. If you are preparing for a software developer role (or even a lead/engineering manager role) for companies like Google, Amazon or Facebook, this is something you have to be able to crack with flying colours.

The key to answering these questions is to understand the motive behind them. Often the aim is to not just to find if you can arrive at the right answer. Tech giants like Amazon and Google, and increasingly every startup/tech company have complex products and they are not just looking for good coders.

They are looking for engineers who can understand the problems, are good at problem solving and can then write good quality code to solve that problem.

They are also looking to find out what it is working with you on a daily basis.

Some of the common things that Interviewers look at are:

1. Ability to understand the problem
2. Ability to identify when a particular solution would work and when it would not.
3. Ability to convert a solution to quality code.

Lets walk through a real interview question to illustrate this.

Question: Given a Binary Tree, If I start drawing vertical lines through the Nodes of the tree — find the Nodes falling on the same vertical line, from leftmost to rightmost line.

In the diagram below the expected output would be [4], [2,9], [1,5,6], [3,8], [7]

Note: If you are already stumped by the vagueness of the question — don’t be. Its meant to be like this to check your approach.

You can jump to the solution straightaway here.

Step 1: Understand the problem

Here are a few things that could start with, without first jumping to a solution.

• Its a binary tree (Not binary search tree)
• What are vertical lines ?
• What is the significance of left to right ?
• Are there any edge cases you need to consider

Based on the above thoughts, you could perhaps ask to clarify the following:

1. Confirm that it’s not a binary search tree. This would tell the interviewer that you know the difference between a binary tree and a binary search tree. You might even get asked a followup question to this — so win win.
2. As if it a balanced tree? This would indicate that you are already thinking in terms of balanced and unbalanced trees.
3. The output has Nodes falling on single line printed from top to bottom. But none such constraint is given in the question. You can clarify if you have to enforce ordering within nodes falling on same vertical line.

There are many other clarifying questions you could think of that help you understand the problem.

Be aware to not ask a question based on the actual solution you are thinking to implement. As the interviewer would have no idea about it.

Step 2: Think of a solution

You can take a few minutes now to think through a possible solution. If you have found a solution but unsure if it is optimised or not, do not hold back. Think aloud and convey your approach. You could say something like

I am trying to first identify how to traverse the tree

Or

I am trying to think of a way to identify which node falls on which line

Then start by describing your algorithm. Say:

At the root node I start with a line number as zero. As I move left I decrement the line number by 1 and as I move right I increment the line number by 1.

Tip: Provide relevant data structures or pseudo code when you can. If you are conversant in Java you could explain it like this:

I will keep a HashMap<Integer, List<Node>> where key is line number and value is list of nodes on the line. As I traverse the tree I keep adding nodes to the map in respective list.

At the end of it the map would have List of nodes on each line number and I will print the nodes.

If you are confident about complexity of the solution, say that. Example: in this case O(n) to build the map and then to print the values.

As you build your approach — feel free to ask more questions, like:

Can I use extra space? Or

Is there a specific performance you are looking for in the solution.

Idea is to demonstrate that you are not just thinking of the binary tree, but about the larger problem at hand.

Note that the interviewer would like to give you various hints, so keep the conversation going. Try to figure out if there is a hint in the followup questions they are asking. Do not be so overconfident that you ignore these hints.

Step 3: Arrive at your final solution

You should now be able to wrap up and provide the final solution. But wait, we missed something.

The problem wanted the nodes to be printed from left to right line. HashMap doesn’t give us elements in an ordered way. So now either you have to sort it or use a TreeMap (which means cost of adding element is not O(1)).

And sorting also would take O(mlogm) where m is the number of lines. This is not bad at all.

Even better approach would be to use the minimum and maximum values of line number and then just iterate from min to max and print the line numbers. And you would be able to do it in O(m) in addition to O(n) which is the tree traversal time.

Now the solution looks good and you are able to explain time complexity as well. Explaining the pitfalls of your own approach and correcting it shows your ability to think of the right solution that would work in a particular situation.

It does not matter if you were not able to arrive at this solution in the first go. Explain your approach and the reasoning behind every decision you made on the way, and you should be able to get through to the next round !

What next ?

Be prepared for followup questions on the same topic.

Binary trees are the one of the most popular subjects. Read here for more questions that you can expect.

Got a challenge for us ?

If you have some difficult interview questions that you want help with, throw them at us and we will get back to you. We at interviewparrot love solving algorithms.

Email us at: developers@interviewparrot.com