Coding Interview

Understanding the Coding Interview – Part 2

0

It has been two years since I published my initial post “Understanding the Coding Interview”, and since then, I’ve had a lot of time to read and reflect on this topic to arrive at more insights. As I emphasized in my first post, preparation is no doubt an essential part of the game. However, what interview-coach books often overlook is the utmost importance of putting yourself into the right mindset for the interview. You could have studied hundreds of questions prior to the interview, but on the big day, standing in-front of the white-board, faced with a tough question from the interviewer, your mind shuts off, like a deer caught in headlights. This effect, as I later found out from reading Charles Duhigg’s book “Smarter, Faster, Better”, is known as “cognitive tunneling”, and can lead to you to make bad decisions in the face of pressure. The key to overcoming “cognitive tunneling” is to build a strong mental model of the task well before you perform it, so your mind will stay focused on the correct objectives during the task. To that end, I have devised a mental model of the “technical interview” that may help you succeed at what is traditionally viewed as an obscure and arbitrary evaluation procedure amounting to nothing more than a coin-toss.

The key idea behind my mental model is to view technical interviews not like job interviews but rather like school exams. Viewing technical interviews as school exams immediately implies several important axioms:

One, you need to study for technical interviews just like school exams. Do practice problems and read solutions to practice problems. No matter how smart you are or how confident you are, you will not do well (or as well as you could) on a school exam if you don’t study for it. This is the focus of my first blog post on this topic, so I won’t go into the details here.

Two, you need to think of technical interviews as grading you on an “A, B, C” scale, as opposed to being pass-fail. It is true that many people who “pass” interviews barely manage to squeak by, and that’s what matters at the end of the day, but “passing” should not be your primary mental focus. If you set “passing” the interview as your goal, you are aiming too low, and a single careless mistake will send you over the edge of the cliff. On the other hand, if you aim to score an “A” on the interview, even if you make some mistakes that hurt your score and put you in the “B” range, you may still pass the interview! One of my favorite sayings is, “Shoot for the moon – if you miss, at least you will land amongst the stars”. It applies to life, it applies to exams, and it applies to technical interviews.

What does this all mean in practice?

First, to elaborate on the “A, B, C” grading scale for technical interviews, here is what each grade roughly amounts to:

“A” is reserved for the top tier candidates who demonstrate deep understanding of algorithms and object-oriented design. These are the candidates who are able to quickly provide an O(n) solution to a tricky array problem (using learned techniques such as “Two Pointers”), and show liberal use of object-oriented design principals such as inheritance and polymorphism in design questions. These are the candidates that all companies are looking to hire.

“B” is reserved for the mid tier candidates who demonstrate good understanding of algorithms and design. These are the candidates who are able to optimize an O(n^2) solution to O(nlogn) after some trial and error, and shows reasonable competency in using classes in design questions. Depending on the company’s hiring-bar, this may be good enough to “pass” the interview, but not always.

“C” is reserved for the low tier candidates who demonstrate barebones knowledge of algorithms and design. They are the ones who are able to cough out an O(n^3) brute force solution to an algorithms problem and implement basic methods in design questions. This is not good enough to pass the interview by any stretch of the imagination.

“F” is reserved for the candidates who shows up to the interview with a hang-over.

Note that I’ve used the word “demonstrate” instead of “possess”, and the reason is as follows: The interviewer doesn’t evaluate you on your raw smarts or the vast array of knowledge you possess, but rather on what you are able to demonstrate or show in one hour. Depending on the candidate, this can be a blessing in disguise because putting on a “show” is something that can be learned and prepared for in a relatively short amount of time, even if you are not the smartest apple in the bunch. The key is to study and prepare!

Finally, another important element of the “school exam mental model” for technical interviews is acclimating to the interview environment. When you are in school, you learn in the same classrooms or lecture halls as where you eventually take your exams, so growing up you have always been taking tests in familiar environments. On the other hand, onsite-interviews often require you to code on the white-board or on a piece of paper, which you would rarely do as a software developer, and this can be a jarring stimuli in an interview. The only way to overcome this cognitive dissonance is to actually simulate this environment while preparing for your interviews - go out and buy a white board if you don’t already have one! Get used to the smell of those dry-erase markers!  Brush up on your handwriting! Only when coding on the white board feels like second nature will you truly be prepared to solve algorithms questions without external interference.

In future posts, I will provide concrete examples of “A”, “B”, “C” grade solutions to further illustrate what to shoot for and what to avoid.

Understanding the Coding Interview

0

Having recently quit my job at Amazon and joined Microsoft, I thought it would be helpful to share my interview experiences so that those in the same shoes can be better prepared and avoid common pitfalls.

First and foremost, the golden rule you need to know about the coding interview:

The coding interview does NOT measure a candidate’s ability to do the job.”

 

In other words, the skills you need to do well on the coding interview is entirely different from the skills you need to do well on the job. And when I say “entirely”, I really mean it – the intersection of the two sets of skills is almost non-existent. It’s the equivalent of asking a firefighter to fix a gas stove because both of them happen to involve fire (or in our case, “code”). In order to fix the gas stove properly, you need training and practice for fixing gas stoves, which you’ll never get on the job as a firefighter. Similarly, in order to pass the coding interview, you need training and practice for solving tricky coding questions, which you’ll never get building apps, frameworks, and backend services as a software engineer. This point should be intuitive, but often times it is overlooked by candidates who believe they can ace coding interviews simply because they are superb coders on the job. Chances are, you’ll never need to balance a BST on the job in your entire career, and as much as I have tried, I’ve only managed to put “recursion” into production code twice.

A couple of myths to dispel right off the bat:

1. “The interviewers are interested in knowing your thought process.” Complete bullshit. For phone screens, the interviewers are most likely not even paying attention to you – they are overwhelmed with work, emails, and meetings and would much rather get the interview over with as quickly as possible. The interviewer already have the solution (or multiple solutions) to the question in mind and is just hoping you would give one of the correct solutions. If your solution deviates from what the interviewer had in mind, he will subconsciously think your solution is wrong or buggy, even if it is correct! And even if you manage to convince the interviewer your solution is correct, you can bet you’ll get a comment in the feedback saying your solution is “suboptimal”. This can be as trivial as applying De Morgan’s law to covert “(not A) and (not B)” to the logically-equivalent “not (A or B)” in an if-statement clause. What is important is not whether your solution is correct, but whether your solution is perceived as correct by the interviewer, who is a biased human, not a machine. Make the job easy for the interviewer and give them the solution they expect – this comes with practice.

2. “We don’t care about syntax and api, just get the logic right.” This is another shameless lie. Don’t let your guard down. I’ve seen lots of candidates get a “not inclined to hire” vote in interview feedbacks simply because they used the incorrect syntax or an api that didn’t exist in the language. For example, the syntax to insert an element into a Queue in Java is “add”, not “push”, not “enqueue”. If you use the wrong api, you are giving the interviewer the impression that you’ve nevered used a Queue before in Java. Don’t rely on the interviewer giving you the benefit of the doubt. You should know the APIs of the common data structures by heart, so you’ll seem sharp to the interviewer when it comes time to code. There is no auto-complete on the white-board!

3. “It’s okay to take hints.” This statement is used to comfort and console candidates. Rather than watching the candidate struggle with the problem, the interviewers are instructed to toss a bone to the interviewee to move them along and put them out of their misery. If you have to take a hint, you’ve already failed the interview. At the end of the day, the company have plenty of candidates to choose from, and they would almost certainly take the candidate who solved the problem without any hints over the candidate who needed hints, regardless of who is a stronger coder in reality. Resist the urge to throw in the towel – you need to figure things out on your own. The trick is to remain calm when you are stuck and think about the problem from different angles.

4. “Ask a lot of clarifying questions.” A lot of people give this advice, which is meant to demonstrate that you are a thoughtful coder, but I think it does more harm than good in reality. If you ask too many clarifying questions, it shows that you are not good at dealing with ambiguity. I once followed this advice on a phone screen and asked a lot of questions as I was coding. I thought I did extremely well and finally figured out the interview system. I solved the algorithm question with multiple solutions as well as provided a complete solution to the design question to implement a timer system that can be used in a multi-threaded environment. I received a phone call 20 minutes later from my recruiter saying that they will not proceed with the on-site interview, the reason being the interviewer had to give me too much “hand-holding”. I was extremely disappointed by the outcome – what I perceived as being thoughtful and collaborative is perceived by the interviewer as “hand-holding” – what a joke! My advice here is to make reasonable assumptions (provided the interviewer does not object to the assumptions) and start coding as soon as possible – ask clarification questions only when absolutely necessary, not for the sake of asking.

So what is the coding interview really about? It is about nailing down the coding questions, period. Why? Because at the end of the day, the interviewers need to present legal evidence to the hiring manager on making a hiring decision, and the candidates’ solutions to the coding questions are the most authoritative evidence – if the solutions are not the most efficient and bug free, it’s almost guaranteed to be “not inclined to hire”. There is very little room for subjectivity here - it doesn’t matter how much work experience you have or how many accomplishments you have - if you can’t give them the evidence that you are a good coder, they cannot hire you, legally.

The only way to beat this flawed system is to study extensively on coding problems and hope you get lucky during the interview. It’s an unfortunate reality, but I’ve seen a lot of poorly qualified candidates get through just by memorizing questions while other perfectly qualified candidates get turned down for messing up the coding problem. As a rule of thumb, I recommend spending at least 2 weeks studying coding problems every night in order to prepare for the interview. When you do a coding interview, it is important to remember that you are not competing against other software engineers, but rather against college candidates and unemployed candidates who are able to dedicate all their time to studying and memorizing coding questions. If you are a full-time software engineer, the playing field is rigged against you to begin with, so you must put in a lot of effort to make it even!

Nth Element of a BST

0

This question seems very straight forward on the surface but an efficient solution is tricky to implement in Java due to pass-by-value semantics. Read on to see why!

Question:

Given a BST of integer elements, return the nth element as quickly as possible. Counting starts at 1 (not 0).

Input (input.txt):

4
3
-1
15
2
7
16

Output (stdout):

7

Solution:

A very naive solution is to traverse through the entire tree in-order, adding each element to an ArrayList as you go, and returning the nth element of the resulting ArrayList. This solution is simple to implement but uses extra memory and has a wasteful run-time if n is small compared to the size of the tree (although the run-time can be improved via early termination).

A better idea is to perform the recursive in-order traversal on the tree nodes while keeping a global counter that we can modify across the recursion stack. (Note that we need to define a custom wrapper object for this counter to simulate pass-by-reference of primitive values.) As far as the search logic goes, we can terminate the search and return the result as soon as the counter is fully decremented from n to 0. One final trick: we need to use the Integer primitive wrapper so we can return a null value when the nth element is not found in a substree.

    public static void main (String [] args) throws IOException {
        Scanner in = new Scanner (new FileReader("src/input.txt"));
        int n = in.nextInt();
        BSTNode root = new BSTNode(in.nextInt());
        while(in.hasNext()) {
           root.insert(new BSTNode(in.nextInt()));
        }
        System.out.println(findNthElement(root,new Counter(n)));
    }

    static Integer findNthElement(BSTNode node, Counter counter) {
        //If we reached the end of subtree return null to indicate "not found in subtree"
        if(node==null )  {
            return null;
        }
        //Traverse left subtree
        Integer result = findNthElement(node.left, counter);
        //Return result if found in left subtree
        if (result!=null) {
            return result;
        }
        //In-order visit
        counter.value=counter.value-1;
        //Return node value if found
        if(counter.value == 0) { 
          return node.value;  
        }
        //Traverse right subtree
        result = findNthElement(node.right, counter);
        return result;
    }

    static class Counter {
        int value;
        public Counter(int value) {
            this.value = value;
        }
    }
    
    static class BSTNode {
        BSTNode left;
        BSTNode right;
        int value;

        public BSTNode(int value) {
            this.value = value;
        }

        //Standard BST insertion algorithm
        public void insert(BSTNode node) {
            if(node.value<value) {
                if (left==null) {
                    left = node;
                } else {
                    left.insert(node);
                }
            }
            if(node.value>value) {
                if (right == null) {
                    right = node;
                } else {
                    right.insert(node);
                }
            }
        }
    }

A Simple Regex Matcher

0

This is a classic technical interview question which tests knowledge of string manipulation and recursion.

Question:

Given a regex expression and a string, return true if the regex matches the string. The rules:

  • Strings are composed of alphanumeric characters.
  • Regexes are composed of alphanumeric characters and 2 special characters ‘.’ and ‘*’.
  • A regex matches a string if every character in the regex matches every character in the string.
  • Two single characters match if they are equal.
  • The special character ‘.’ matches with any single character.
  • If the special character ‘*’ appears in the regex, then for our string we can match 0 or more contiguous occurrences of the character preceding the ‘*’. For example, “a*bc” matches “aaabc”.
  • For “.*”, we can match 0 or more contiguous occurrences of any character. For example, “.*bc” matches “xyzbc”.
  • A pair of quotes (“”) denotes an empty string.

Input (input.txt):

a a
abc abc
a.c axc
a*bc aaabc
a*bc bc
.*bc xyzbc
a*aa aaaa
aa aaa
aaa aa
a* “”

Output (stdout):

true
true
true
true
true
true
true
false
false
true

Solution:

The basic idea is to attempt to match the start of the regex with the start of the string and recursively match the remaining regex against the remaining string.

    public static void main(String[] args) throws IOException {
        Scanner in = new Scanner(new FileReader("src/input.txt"));
        while (in.hasNextLine()) {
            String regex = in.next();
            String string = in.next();
            //Special handling of empty strings
            if(regex.equals("\"\"")){
                regex="";
            }
            if(string.equals("\"\"")){
                string="";
            }
            System.out.println(regexMatchesString(regex, string));
        }
    }

    static boolean regexMatchesString (String regex, String string) {
        if(regex.equals("") && string.equals("")) {
            //Base case when regex matches string.
            return true;
        } else if (regex.equals("")) {
            //Base case when string exceeds regex.
            return false;
        } else {
            //Attempt to match start of regex with start of string.
            if(regex.length()>1 && regex.charAt(1)=='*') {
                //Handle wild card:
                //a)Try ignoring wild card.
                boolean matched = regexMatchesString (regex.substring(2), string); 
                if (matched) {
                    return true;
                }
                //b)Try consuming one or more matching characters.
                for (int i=0;i<string.length();i++) { 
                    if (matches(regex.charAt(0), string.charAt(i))) {
                        matched = regexMatchesString (regex.substring(2), string.substring(i+1));
                        if (matched) {
                            return true;
                        }
                    } else {
                        return false;
                    }
                }
                //Remaining regex does not match remaining string.
                return false;
            } else if (string.equals("")) {
                //Base case when regex exceeds string.
                return false;
            } else if (matches(regex.charAt(0), string.charAt(0))) {
                //Try consuming a single character.
                return regexMatchesString (regex.substring(1), string.substring(1));
            } else {
                //Start of regex does not match start of string.
                return false;
            }
        }
    }
    
    //Returns whether a single regex character matches a single string character.
    static boolean matches (char regexChar, char stringChar) {
        return regexChar == '.' || regexChar == stringChar;
    }

The trickiest part of this solution is how the wildcard is handled – we must test all n+1 cases of consuming 0 to n matching characters with our wild card since it not necessarily the case that we want to consume all matching characters. (Ex. “a*ab” should match “aab” – the “a*” only consumes a single “a” in this case.)

Shortest Distance Between Two Nodes

0

What is the shortest distance from point A to point B?

If you’ve taken a CS 101 class in college, this problem should sound very familiar to you. Some of you may even remember that you can solve this problem using something called Dijkstra’s algorithm. You remember that the algorithm is not too hard, so you never bother giving it a second thought. Yet, when it comes time to implement the solution, particularly during a technical interview, you may find yourself at a complete loss as to where to even begin (much like trying to correctly spell “Dijkstra”).

This article presents a Java implementation of Dijkstra’s algorithm using breadth-first-search with a PriorityQueue. This is a very useful algorithm to keep in your arsenal. It is also a great starting place for interview prep since the solution touches upon some of the most fundamental CS concepts including:

  • Map (HashMap implementation)
  • PriorityQueue (Heap implementation)
  • Overriding equals and hashCode (when using a custom class in a Map)
  • Overriding compareTo (when using a custom class in a PriorityQueue)

Without further ado, here is the formal question statement:

Question:

Given a set of bi-directional, weighted edges of connected nodes in a graph, compute the shortest distance between a starting node and an ending node. The edge weights are non-negative.

Input (input.txt):

A I
A B 2
B C 3
A D 5
B E 2
C F 1
D E 3
E F 6
D G 2
E H 1
F I 4
G H 8
H I 2

Output (stdout):

7

Solution:

The solution presented below is an end-to-end solution and has three parts: processing the input, implementing Djkstra’s algorithm, and implementing supporting data structure.

1) Process input and construct graph.

The tricky part here is that the nodes can come in any order and must be correctly linked with previous nodes. Thus, a hashmap is needed in order to build the graph in O(n) time since we need to be able to perform look-up on exisiting nodes in O(1) time. Note that a Node data structure is all we need in order to represent our graph – the edges can be stored as a map of weights to adjacent Nodes within the Node data structure – this greatly simplifies our code.

    public static void main (String [] args) throws IOException{

        //Scanner is much more user-friendly than BufferedReader.
        Scanner in = new Scanner(new FileReader("src/input.txt"));

        //Obtain start and end nodes.
        String startLabel = in.next();
        String endLabel = in.next();

        //Construct bi-directional graph (potentially cyclic).
        Map<String,Node> graph = new HashMap<String,Node>();
        while(in.hasNextLine()){

            //Read edge.
            String labelA = in.next();
            String labelB = in.next();
            int weight = in.nextInt();
            Node nodeA;
            Node nodeB;

            //Retrieve or create nodeA.
            if (graph.keySet().contains(labelA)) {
            	nodeA = graph.get(labelA);
            } else {
            	nodeA = new Node(labelA);
            	graph.put(labelA, nodeA);
            }

            //Retrieve or create nodeB.
            if (graph.keySet().contains(labelB)) {
            	nodeB = graph.get(labelB);
            } else {
            	nodeB = new Node(labelB);
            	graph.put(labelB, nodeB);
            }

            //Add bi-drectional edges.
            //(A possible problem variant can use uni-directional edges.)
            nodeA.addEdge(nodeB,weight);
            nodeB.addEdge(nodeA,weight);
        }

        //Invoke algorithm and print solution.
        System.out.println(solve(graph,startLabel,endLabel));
    }

 

2) Implement Djkstra’s algorithm.

The crux of Djkstra’s algorithms lies in a simple loop invariant: Each time we “visit” a node, it is guranteed to possess the minimum distance from the starting node. We maintain this invariant by repeatedly minimizing our tentative distances to unvisited nodes AND always visiting the nodes closest to our starting node first. Under this strategy, it would be impossible to end up in a situation where a current node we visit does not possess the minimum distance from the starting node, since a hypothetical alternative path would necessarily include an intermediary node with a smaller minimum distance from the starting node, in which case we would have visited this intermediary node first and have shrinked our tentative distance to our current node to the minimum, a contradiction.

A common setup to this algorithm involves initializing the distance to the starting node to 0 and the distance to all other nodes to infinity. A priority queue is used to provide efficient access to the closest node at all times. (The Java PriorityQueue is a heap-based implementation that offers O(logn) insertion/removal time.)

    public static int solve(Map<String, Node> graph, String startLabel,
            String endLabel) {
        //toVisit queue contains nodes we can reach and visit.
        Queue<Node> toVisit = new PriorityQueue<Node>();

        //Determine start node.
        Node startNode = graph.get(startLabel);

        //Set distance to start node to 0.
        startNode.setDistance(0);

        //Start our search at the start node.
        toVisit.add(startNode);

        //While there are more nodes we can reach and visit...
        while (!toVisit.isEmpty()) {

            //Visit the closest node (Djkstras loop-invariant).
            Node currentNode = toVisit.poll();
            if(currentNode.isVisited()) {
                continue; //See Note A.
            }
            currentNode.setVisited(true);

            //If we reached the end node, return its distance.
            //This must be the shortest distance to the end node.
            if (currentNode.getName().equals(endLabel)) {
                return currentNode.distance;
            }

            //For each neighbor, compute the distance to reach the neighbor
            //through our currentNode, and update shortest distance as needed.
            for (Entry<Integer, Node> edge : currentNode.getEdges().entrySet()) {
                int weight = edge.getKey();
                Node neighbor = edge.getValue();

                //It is unnessary to check on neighbors we already visited
                if (!neighbor.isVisited()) {

                    //Compute new distance
                    int newDistance = currentNode.distance + weight;

                    //Update old distance if new distance is better
                    if (newDistance < neighbor.getDistance()) {
                        neighbor.setDistance(newDistance);
                        //Add neighbor to our toVisit priority queue with the new lower priority. See Note B.
                        toVisit.add(neighbor);
                    }
                }
            }
        }

        return -1; //No path to goal exists.
    }

Note A: Since there can be multiple paths to the same node and we do not remove nodes from our PriorityQueue when we make the path update (for efficiency reasons), it is likely for our PriorityQueue to contain duplicate nodes. We should ignore the nodes we’ve already visited to avoid redundant traversals.

Note B: In light of the above, it is redundant to add a neighbor to our toVisit queue if it doesn’t have a better tentative distance since it will just be discarded when it’s dequeued (it will already have been visited by that time). Of course, since any distance is better than infinity, we will always add a “fresh” neighbor to our toVisit queue.

 

3) Implement supporting data structure.

The Node data structure contains the key fields that support the algorithm including name, distance, and a visited flag. The weighted edges to neighboring nodes are represented by a mapping of edge weights to nodes – this is simply a convenient construct - we are not actually using the map look-up capabilities.

    static class Node implements Comparable<Node> {
        //Always declare fields as private if possible
        private String name;
        private int distance; //distance from starting node.
        private Map<Integer, Node> edges;
        private boolean visited;

        //Each node has a unique name
        public Node(String name) {
            this.name = name;
            //Our algorithm requires distance to be initialized to infinity
            distance = Integer.MAX_VALUE; 
            edges = new HashMap<Integer, Node>();
            visited = false;
        }

        //Add an edge to a neighboring node with the specified weight.
        public void addEdge(Node node, int weight) {
            edges.put(weight, node);
        }

        //equals and hashCode must be overridden for usage in HashMap.
        //We use "name" as our key for this problem.
        @Override
        public boolean equals(Object obj) {
            if (obj == null)
                return false;
            if (obj == this)
                return true;
            if (!(obj instanceof Node))
                return false;

            Node other = (Node) obj;
            return this.getName() == other.getName();
        }

        @Override
        public int hashCode() {
            return name.hashCode();
        }

        //compareTo must be overridden for usage in PriorityQueue.
        //We use "distance" as our comparison value for this problem.
        @Override
        public int compareTo(Node other) {
            if (other == null) {
                return -1;
            }
            if (this.getDistance() == other.getDistance()) {
                return 0;
            }
            return this.getDistance() > other.getDistance() ? 1 : -1;
        }

        //Boiler-plate getter/setters
        public String getName() {
            return name;
        }

        public int getDistance() {
            return distance;
        }

        public void setDistance(int distance) {
            this.distance = distance;
        }

        public Map<Integer, Node> getEdges() {
            return edges;
        }

        public void setVisited(boolean visited) {
            this.visited = visited;
        }

        public boolean isVisited() {
            return visited;
        }
    }

 

Additional Notes:

  • The runtime of this algorithm is O(m * log(n)) time where n is the number of vertices (a.k.a. nodes) and m is the number of edges in the graph.
  • This algorithm does not support negative edge weights since negative edge weights will break the loop-invariant.
  • If all the edge weights are 1, then this algorithm reduces to a plain breadth-first-search. In this scenario, using a FIFO queue will give us an O(m) solution.
Go to Top