Getting That Coveted Technical Interview

I recently decided to apply to few of the tech giants like Microsoft, Amazon and Google. I was at a point in my career where it was almost a “now or never” situation. Applying meant a few uncomfortable things: a very intense and time consuming preparation; the tiring process of getting hold of the recruiter; the nerve-wracking interviews; and if there is an offer, the possibility a cross-country move. At the same time, it also meant other things: working at one of the best companies in the world, alongside the smartest people in the world; working with the latest technologies; being at the heart of world-class innovations; working on projects that impact people at a global scale; immense personal growth; and not to mention, the best perks and compensation packages. For an aspiring software engineer, the pros far outweighed minor cons. The time was just right.

In the process, I read many accounts of people’s experiences of interviewing at various tech-giants. Most of them share their interview experience, but very few share what they did to even get to the interview. I will later cover my interview experiences with Microsoft and Amazon as well, but in this post, I will try to share the steps that enabled me to get the interviews with the best tech companies in the world. I will try to be as thorough as I can. But feel free to comment with questions if you have any. I will do my best to answer them.

Part 1: Initial Steps

Once you make a decision to apply to Microsoft, or Amazon or Google or Yahoo, et al, it is not simply a matter of dropping your resume into their career portal. Well, you could do that, but it is highly unlikely that you will hear back from anyone, except an automated “thank you” note. The top tech companies receive 100s and in certain periods of the year, even thousands of applications a day. Less than 1% make it to the on-site interview, and even less number of applicants actually get an offer. There used to be a time when career portals were the primary method of application. They still exist, but are far from the optimal route to landing an interview, especially at large multinational tech corporations. Although this post is geared towards engineering positions, the initial steps should be the same for any big company in any industry. From talking to various people in the business, and my personal experience, there are only two major ways to get your first interview:

Have an internal employee refer you.
Do things that makes a recruiter notice you.

Internal referral is pretty self-explanatory. The tech-giants invest a lot of money and time in their recruits and hires. So the ones that actually turn into loyal employees are in return trusted by the company as well. Therefore, a referral goes a long-long way. The second option is getting noticed by a recruiter. Rather than being conversational about it, I think this part will be more effective if listed as points (definitely not exhaustive). So here they are:

Revamp your resume.

Organize, and make it simple and clear. Utilize the space. Do not list down your “duties” like a mundane robot. Instead, list your accomplishments in brief and succinct sentences. Include facts and numbers wherever applicable. E.g. of what to write: “Implemented a supervised learning model that achieved accuracy of 90% and helped streamline the process flow.” E.g. of what NOT to write: “Solved complex programming tasks and assisted the team.”

In addition, your resume should be 1-2 pages and recruiters only look at it for 10-30 seconds. Therefore, put the important bits first. And here is another very important part: Remove all things on your resume that you have just listed having done them only once or twice. Unless you are actually good at it and can answer in-depth questions about it, remove it. You are guaranteed to be drilled in-depth on almost everything on your resume. You may get away with stretching the truth, or even lying elsewhere, but not at these companies. So be honest — they would rather work with an honest person who does not know something, but has the potential, than a dishonest person who lies about his/her achievements.

Make sure you have the right things on your resume.

Know the company in accordance with your skillset. It would make little sense for me to apply to hardware-based companies like Intel, or Nokia. Although top tech companies care more about your potential to learn, rather than what you already know, at least in terms of programming language, some basic knowledge is expected. And that “basic” is in fact pretty extensive to be honest. The good thing is that you do not need to know any specific programming language. If a company works with a stack based on object oriented languages, then C++, Java or C# should all be fine. But if the company is functional-heavy, you may not cut the slack. So do your research before wasting time applying to the wrong company.

List out your personal projects.

Well, don’t highlight the fact that you programmed a game of tic-tac-toe in college — make sure it is something more significant and complicated. If you do not have one, work on it. A lot of people advise getting your hands dirty with open-source. But let me tell you, this is easier said than done. Finding the right project, the right skillset and the right interest is pretty hard. Rather, pick something interesting (and significant), and start on your own. If you have friends who are willing, get them on board, too. Who knows, it may eventually turn into an open-source, or even a startup! Regardless, this shows initiative and passion outside of work.

Ask for recommendations.

Let me rephrase: ask for recommendations from people that matter — in the sense that they have directly managed you, or you have taken multiple classes with them — people that can attest your skills in detail with examples. Stay away from asking recommendations from a colleague, a classmate, or your manager from the old odd-job you did in college. While it shows that you are recommendable, it offers little insight to the context, pressure and scale of work you are applying for. Of course, this applies to LinkedIn resumes.

Join groups.

Meet up, LinkedIn, Facebook and other social platforms are all great. But let me warn you, do not be a “serial joiner.” Joining 100 groups related to Java, or even in other fields like CPA, will not make you stand out. As a matter of fact, it clearly shows that you spend no more than a few seconds thinking about which groups you want to join. Be mindful, selective, picky and above all, be involved in what all you join.

Network.

Find friends, of friends of friends of friends … who know a recruiter at the company you are applying to. Buy them beer, food, and pass through the slew of nodes to eventually reach the recruiter. Be nice, friendly and courteous to all of the connects. If all fails, send a nice inquiry email to the recruiter directly. You probably won’t receive a reply, but it is worth a shot.

Part 2: The Preparation (THE MEAT!)

This is one of the most important parts of landing the big-tech job. And sadly, the most overlooked one, as well. You spent hours revamping your resume, you joined groups actively, started a nice project and even got a hold of the recruiter and got setup for an interview. All this means nothing, if your fail the very first phone screen. You need to be prepared, and I am mean technically prepared. Unless you are absolutely sure you are up to it (which you may well be), I would suggest a STRONG commitment to preparation, even if you have had advanced degrees and years of industry experience. I will present to you 6 questions below, so you can gauge your relative competence in solving the interview-type algorithmic questions. Of course, this is not an exhaustive indicator — your questions may be easier, or much more complicated. Regardless, try answering them. If you are able to solve them with ease, then you probably are at a good state. If you have no clue what is going on or haven’t even heard of some of the words used in the questions, then you are almost where I was about a month and a half ago. So don’t fret. If you are prepared to devote a significant amount of hours each day, sacrifice your weekends and hangouts, to almost redo your entire Bachelor’s degree all by yourself, then that attitude and perseverance will undeniably get you through. And at the end, even if you don’t land the job, trust me, you will become a much more competent engineer than you are right now. Of course, you may fall somewhere in between, and even in that case, although you may not have to go into commando-mode, a little brush up will go a long way. Here are the questions:

You are given a histogram of a month’s worth of price predictions (of each day’s high and low) for a particular stock. Provided you can only buy or sell at the start of each day, what is the best stretch of continuous days to buy and sell the stock so that it maximizes your profit? Write an algorithm that does this in linear time with constant space.

A deck of cards is represented by an integer array of size 52, with possible values of 1 – 13 for each position. Design an algorithm to shuffle the deck of cards in linear time, in-place.

Write the algorithm to find the square root of any integer, without using the Math.sqrt() function or any extra space. What is the time complexity of your solution?

Find if a linked list has a cycle. Expectation O(n) time; O(1) space.

Find the lowest common ancestor of two nodes in a Binary Tree. The tree does not have a parent pointer. Your algorithm should run in linear time, without any extra space.

Given a directed graph of 10 cities, each of which may or may not be connected to each other, represented by an adjacency list, write an algorithm to find if there is a route from a city to others, that eventually cycles back to the same city. What is the time complexity of your algorithm? You may use reasonable extra storage, or modify the structure of the graph node class.

(Solution pointers to these problems are at the end of this post)

All of the above questions sound like a piece of cake to you? Well, then you probably are well-prepared. But if you have no clue about what is going on, then it is time to go on commando-mode. Following is a list I have compiled that consists of the bare minimum you should know. But obviously, the more, the better.

Primitive types:

– Which ones are available?
– What are their limits, sizes?
– What do they store?
– You must know integer overflows.
– Any knowledge in binary operations, bitwise operations, bit shifting is great help too.

Arrays:

– How are they stored in memory?
– Time complexity for lookups, search, insertion and removal.
– Pros and cons.
– 2 dimensional arrays, as in matrices.

Dynamic Arrays:

– Pros/cons.
– Time complexity.
– How are they resized and what is the cost?

Linked Lists:

– The idea of Nodes and pointers.
– References.
– Time complexity, storage overhead.
– Insertion, deletions, lookups, search.
– Variations: Singly linked, Doubly linked, Circular, Cyclic?

Hash Maps:

– Pros, cons.
– Time complexity. Lookup, search, insert, delete.
– Collisions: Chaining vs. Open addressing.
– Hash Functions.
– Compression Functions.
– Variation: TreeMaps.

Queues:

– Pros, cons.
– Time complexity.
– FIFO.
– Implementation: Linked-list vs. array. Enqueue, Dequeue, Peek.
– Variations: Priority Queue, Circular Queue.

Stacks:

– Pros, cons.
– Time complexity.
– LIFO.
– Implementation: Linked-list vs. array. Push, pop, top.

Trees:

– General data structure.
– Definitions, etc.

Binary Trees:

– Traversal (inorder, postorder, preorder, level order).
– Time complexity.
– LCA, Paths. Height/Depth.

Binary Search Tree (BST):

– Traversal.
– BST Property.
– Time Complexity. Insertion, Deletion, Lookup. Min, Max.

Balanced Binary Search Trees:

– Implementation specific property.
– Balancing/Rotations.
– Variations: AVL Tree, Red Black Tree, Splay Tree.

Other Trees:

– Have a general idea about — prefix trees, suffix trees (tries), B-Trees (useful for databases).

Heap:

– Implementation: Tree vs. Array.
– Heap property.
– Insert, Delete, Lookup. Max/Min.
– Heapify.
– Variations: Min-Heap, Max-Heap, Fibonacci heap.

Sorting:

– Insertion
– Selection
– Quick
– Merge
– Counting
– Bucket
– External
– Time complexity, pros/cons, implementation for all.
– Stable sort vs. unstable. Which ones are which?

Searching:

– Linear
– Binary
– DFS
– BFS
– Implementation, Pros/Cons and time complexity for all.

Graphs:

– Nodes? Edges?
– Directed vs. Undirected?
– Implementation: Adjacency matrix vs. adjacency list.
– Search, finding path, distance, cycles, etc.

OOP:

– Inheritance
– Polymorphism
– Composition
– Association
– Aggregation
– Encapsulation
– Method Overriding, Overloading
– Interface, abstract class, virtual class, partial class
– Objects vs. Primitives

Language (Any):

– Constructors/Destructors
– Pass by value, pass be reference, pass reference by value (in Java)
– Basic library functions
– Writing hashcode, equals, toString methods. When, why and how to override?
– Comparable vs. Comparator; Writing compare and compareTo methods. When to use which and why?
– Iterators
– Insertion/Retrieval orders for various data structures
– ADTs
– Final, finally, finalize?
– Exception handling, try-catch
– File handling

Testing (at least glass-box):

– Functional Testing
– Domain Testing
– Code Coverage
– Error handling
– Unit Tests/Boundary Tests/Branch Tests

Design Patterns:

– Singleton
– Builder
– Factory
– Decorator
– Others, at least basic understanding.

Following are books and resources that you can use to prep for the interview — well, at least, this is what I used.

Books:

– Intro to Algorithms (CLRS)
– Algorithm Design Manual (Sienna)
– Programming Pearls (Bentley)
– Programming Interviews Exposed
– Cracking the Coding Interview (Laakmann)
– Elements of Programming Interviews
– Are you smart enough to Work at Google?
– How to move Mt. Fuji?
– The Pragmatic Programmer
– Code Complete
– How We Test at Microsoft
– Code Refactoring
– Head First: Design Patterns
– Gang of Four
– The Productive Programmer

Video Resources by amazing professors:

– Julie Zelenski @ Stanford
– Jonathan Shewchuck @ UC Berkeley
– Erik Demaine @ MIT
– Eric Grimson @ MIT
– Shai Simonson @ Stonehill College
– Richard Buckland @ University of New South Wales

Web Resources:

– TopCoder.com
– LeetCode.com
– Geekforgeeks.com
– CareerCup.com
– GlassDoor.com Interviews Section

Tools:

– Legal Printing Paper (to emulate a wide whiteboard)
– Whiteboard
– Text Editor w/ formatting but no compiler or intellisense (CollabEdit, Sublime Text, etc.)
– IDE to test validity occasionally (language specific)

(You may obviously have to add some depending on whether you are specializing on databases or threading etc.)

This is basically all I have in terms of prep. If you have these down, you should be good. It took me about a month to get through them. Your speed could be different. Good luck!


Here are ideas for the 6 questions I presented above, if you are curious:

1. You are given a histogram of a month’s worth of price predictions (of each day’s high and low) for a particular stock. Provided you can only buy or sell at the start of each day, what is the best stretch of continuous days to buy and sell the stock so that it maximizes your profit? Write an algorithm that does this in linear time with constant space.

This is a variation of the largest contiguous sub array problem. Search for it.

2. A deck of cards is represented by an integer array of size 52, with possible values of 1 – 13 for each position. Design an algorithm to shuffle the deck of cards in linear time, in-place.

If you are allowed to use Math.Random(), you need to pick a random card from 0 – 51, then swap that card, with the first position i.e. 0. Then pick another random card, but now from 1 – 51, then swap now with 1. Then pick 2 – 51, swap with 2. Repeat until you pick all 52 cards. I think this is the Fisher-Yates algorithm.

3. Write the algorithm to find the square root of any integer, without using the Math.sqrt() function or any extra space. What is the time complexity of your solution?

This is quite tricky. The “aha” moment is to use a binary search, to get close to the square root.

4. Find if a linked list has a cycle. Expectation O(n) time; O(1) space.

Search for the tortoise-hare algorithm.

5. Find the lowest common ancestor of two nodes in a Binary Tree. The tree does not have a parent pointer. Your algorithm should run in linear time, without any extra space.

This can be done many ways, but since we have the constraints, we will have to do this the bottom-up approach.

6. Given a directed graph of 10 cities, each of which may or may not be connected to each other, represented by an adjacency list, write an algorithm to find if there is a write from a city that eventually cycles back to the same city. What is the time complexity of your algorithm? You may use reasonable extra storage, or modify the structure of the graph node class.

This question is disguised by city names and such, but the underlying problem is — find if a Directed Acyclic Graph has a cycle. Use DFS with coloring to find if cycle exists.

 

 

Tags:
Blog Comments

The bottom-up tree approach does use extra space — recursion consumes space.

You are correct! I should probably have mentioned implicit stack as being okay. Thanks for clarifying!

[…] I recently interviewed at Microsoft. If you are interested in the preparation part, read my earlier post. This post is about my interview Experience at Microsoft. I will have another post dedicated to my […]

Hi Utsav

I really cannot recall how I landed up on this page but I’m glad I did.
Thanks for this blog which is detailed and comprehensive to list all what is needed to prepare for technical interview.

Really enjoyed reading your post on Microsoft interview along with great pictures of Redmond city.

I am glad it was useful 🙂

is Question similar to largest contiguous sub array prob?
I thought this comes down to find the largest different in an array while making sure the first one is smaller than the second

Hi utsav,
Thanks for this wonderful article.i am not good at compexity of algorithms.Can you suggest me some good and easy articles to get started with it.

Thanks

Start with these books:
– Intro to Algorithms (CLRS)
– Algorithm Design Manual (Sienna)
– Programming Pearls (Bentley)

Hi Utsav, and thanks for this detailed post.
I have recently prepared and went through a round of on-site interviews at Google, in which I think had a solid performance. The questions included algorithm and coding challenges, data structure and tree questions, system designs and JavaScript (my role is more of a front-end one).
I haven’t heard back from them yet (it’s been only a week) but I was considering interviewing for other companies as well, since I am now in a good shape for interviewing. I was wondering one year later how are you liking Microsoft? Also, what is different when interviewing for a more front-end position?
Thank you!
-Adrian

Hi Adrian,

Congrats on the Google interview, and good luck! I will keep my fingers crossed for you.
It is a great time to be here at Microsoft. Although the news may be full of layoffs and such, it is something we needed to do to trim down years of excess fat, to make the company lean and agile. In little over a year, I have met many passionate individuals who truly believe they are out there to change the world (and are also wicked smart). Biases aside, I am sure Google is a similar place.
I deal mostly with providing software solutions to our internal problems. Although I deal with the entire pipeline, from backend (DB to code) to front-end, I am by no means a competitive front-end developer. Most of that fancy work in my team is handled by the Program Managers.
Feel free to email me your resume and I can try to put you in touch with someone who knows.

Once again, good luck!

Thank you! I sent you my resume yesterday to your gmail address (found it on LinkedIn). Just wanted to confirm if you received it?

Could you highlight your approach on using CLRS book for preparing during the interview? From my understanding, its a huge book and I think you must have studied parts from it (not entirely) in 2 months.

Leave a Comment