Random Rants

I have interviewed at many companies including Amazon, Cisco, Motorola, Bloomberg, Microsoft, Yahoo, Flipkart, Brocade, Qualcomm, Google, LinkedIn, and Arista Networks. In this post and few more to come, I share my hard learnt tips & tricks to "hack" programming interviews.

The following is a non exhaustive interview preparation checklist. It should help you organize your interview preparation.The Programming Interview Checklist

• Proficiency in programming language(s) of your choice

Examples
 What would be the implication of two objects that have different hashcode values but object1.equals(object2) (or vice versa) is true? (Java)
 What will happen if a method in a parent class is Public and the overriding method in child class is Private? (Java)
 What is wrong with the following? (Java)

class A {
    public void method1() throws IOException {
    }
}

class B extends A {
    public void method1() throws Exception {
    }
}

What is padding in a structure? (C)

• Programming questions :

Examples
 Print the different words that could be produced by pressing 7,8,9 digits of a touchpad telephone.
 More examples at Coding interview questions and answers and Programming Interview Source Code
 This section includes recursion, arrays, handling corner cases, developing test cases, bit operations, Collections - Java,

• General computer science concepts

operating systems (thread vs process, synchronization, deadlock etc), computer networks (IP packet, IP addressing, routing, TCP packet, protocol - sliding window, three way handshake, congestion control, man in the middle attack, TCP vs UDP, HTTP - pipelining, GET vs POST)

• object oriented design and design patterns

Factory method, Lazy initiation, Object pool, Singleton, Decorator, Publish/Subscribe, State, Monitor
 
 Consider a class Coffee which has a makeCoffee method. This method determines the exact procedure to prepare coffee such as mix with ice, serve hot etc. One obvious method is to make various subclasses of Coffee where each type of Coffee will override its makeCoffee method.

What would you do if you would like to change the makeCoffee method without changing the Coffee object itself. One strategy is when you construct the Coffee class, you pass along a CoffeeRecipie object, that has the procedure to make coffee.

In the example below, it is possible to change the coffee making procedure by changing the CoffeeRecipie object on the fly.

Class Coffee {
  Coffee(CoffeeRecipie recipie) {
   this.recipie = recipie;
    ...}
  makeCoffee() {
     recipie.makeCoffee();
   }
}

• Big-O notations (Unable to guess the complexity of your solution is as bad as not having a solution)
• Sorting (heap, merge, quick. Don't use bubble sort.)
• Data -Structures

Hash
LinkedList
Trees - complexity and use of balanced search tree
 Tries

• Search ~ binary search, Breadth first search, Depth first search and other variants.
• Design questions

How would you design a network of a million nodes such that the data from all these nodes is periodically summed up and stored in a database. Obviously, you are expected to come up with something better than a million connections to the database server

• Fundamental algorithms such as divide and conquer, greedy and dynamic programming and common problems such as Knapsack, Travelling salesman and so on. Here is a specific list of Important Algorithms to master to solve programming puzzles.
• Other Helpful to know topics

Dijkstra, A*
 Heuristic/approximate algorithms for NP hard problems
 basics of randomized algorithms (randomized quick sort, local maxima and related AI concepts)
 Map Reduce
Distributed and parallel computing (and distributed problem solving for large scale problems)

• Miscellaneous

If you are not planning on interviewing in the near future, it would be nice to pursue some advanced courses in the area of your interest. Coursera, EdX and Udacity are some great places to do so. A course in datamining, for example, may not be very relevant for a general programming interview. However, at times you may be able to use one of the strategies that you learnt in your course, to come up with a cool algorithm or a fancy data structure. Needless to mention, it also looks great on your resume.
 If you are planning on interviewing in a networking company, such as Cisco, Brocade, Juniper and so on, try to focus on
 C language and programming skills
LinkedList problems
 Here is an almost exhaustive list of linkedlist problem
 Introduction to computer networks

If you live in Silicon Valley or at least open to relocating here, I strongly recommend trying ‘Hired.com’ for job search. It will save you a lot of time and frustration of seeing your applications go down a black hole.