Interview Questions
There are three types of interviews: informationals, phone screens, and onsites.
The informational is the first meeting with a company and it is usually a phone chat with a recruiter.
A screening is a one hour test, by phone or in person, to assess your technical skills.
I also had many “informationals” with hiring managers, and 80+% of the time I was asked technical questions.
Unless their title explicitly says recruiter then you need to expect technical questions.
The onsite is the final stage.
It’s 3 to 6 interview sessions with individual or pairs of interviewers.
And if things will go well, some companies will have you meet with the hiring manager at the end.
Simply knowing memorizing will not help you. It is best to solve these questions on a white board.
Read the section on preparing for an interview for more details.
Here are the questions I have been asked by recruiters.
These are aimed at determining your skill set, interests, and personality.
Similar questions were asked in the later stages too.

Why do you want to work for us?
If you can’t answer this question then you shouldn’t have applied.
Companies want to hear: “I am looking for a challenge.”,
“I love your company’s products and want to work on something I’m passionate about.”,
and “I learned your company culture values x, y, and z. These things are important to me.”
One time I told a .NET shop that I wanted to get away from Microsoft technology and work with open source software.
Unsurprisingly, I did not get a call back. Don’t be stupid. Don’t lie.
Research the company and tell the truth.

Why do you want to leave your current company?
This is similar to question 1.
Be positive. Don't say "I hate my boss" or "They never gave me a raise."
I told a hiring manager that I didn't like the people who did xyz at my company.
His response was "I was a xyz there."
Can you guess if I got an offer afterwards?

Have you used our product? What do you know about our product?
Also similar to question 1.
Companies like candidates who do their research ahead of time.
And it is especially important for companies like Apple and Tableau.
In fact, being familiar with the product is one of Tableau's founding values.

How can you improve our product?
I hear this question often from consumer facing websites/apps.
Answering correctly demonstrates you have done your homework and you can advocate for the end user.

Generic behavioral questions like “tell us a difficult problem you overcame.”
These types of questions are covered in
both
of the
books
as well as sites on the web.
These are more technical, but you can still get asked questions from informationals.
If you have the option to do it in person then go to their office.
Otherwise, get familiar with the webtool ahead of time.
Majority of companies used http://code.stypi.com/.

What is your biggest achievement? Biggest programming challenge?
They want to hear what you can do.
If you are a senior engineer, this is your chance to sell yourself.
Tell them about an ass kicking project you did that saved the company millions of dollars.
Go deep and go big. And this will often be asked during the onsite too.

Implement an arraylist. Need constant time for adding and removing elements.
Implementing an arrayList/vector is generic but I couldn’t figure out a good way to fill up the gaps in the array when elements were removed.
If you figure out a good solution then please share it with us.

Given a maze represented by a grid and a robot. Write code that helps the robot travel from a starting point to the end.
The robot has the following API:
Interface robot
{
CanGo() //checks to see if it can travel in the direction it is facing.
TurnRight() // changes direction
IsAtFinish() //returns true if standing at the end of the maze.
Go() //moves 1 step in the direction it is facing.
}
r  starting point.
X  blocked area.
f  finish.
X 
X 
X 
X 
X 
X 
X 
X 
X 
X 





X 
r 


X 

X 

X 
X 

X 
X 

X 

X 
X 

X 
X 



X 
X 

X 
X 
X 

X 
X 
X 

X 
X 
X 
f 
X 
X 
X 
X 
X 
X 
X 
X 
X 
X 
Hint: the accesible paths have only a width of 1.
Can be solved as generic graph traversal problem. But if you take advanage of the hint then you don't need to remember where you have traveled.

Output the elements of a binary search tree in order. Follow up: Given the root node and another node of the BST, find the next node in order.
Part 1 is basic tree traversal. And Part 2 is a generic BST problem that you should master.

Find the duplicate elements in a string.
This is doable in linear time with a single pass.

Describe abstraction, encapsulation, polymorphism.
I also got asked: isa and hasa?
Abstract class vs interface?
Class vs isntance?
DFS vs BFS?
BST vs array?
These are basic 101 concepts.
And are probably asked to see how well you can communicate a simple idea.
Make sure you have a clear and concise answer for each.

Design an LRU cache.
Standard questions that gets asked a lot. Hint: it requires two data structures.

Given an array of positive and negative integers. Find the starting index and length of subarray with the largest sum.
Can be done in linear time with constant memory.

The nodes in a standard binary tree contain a next pointer that points to NULL.
Change the next pointer to point to the nearest node to the right and on the same level.
Most people solve this using queues, which is O(N) space.
You can really impress your interviewer if you do it with O(1) space.
I giggled like a school girl when two different companies asked this in the same day.

Given an n x m matrix of ints.
Each int/square has a value of 1 or 0.
Two squares are connected if both have a value of 1 and they are next to each other (diagonals do not count).
The area is the sum of all connected squares.
A single square has an area of 1. Calculate the median of all the areas.
n and m are 1024 at most.
0 
1 
0 
0 
0 
0 
0 
0 
1 
1 
0 
0 
0 
1 
1 
0 
0 
0 
0 
0 
0 
1 
1 
0 
0 
0 
0 
0 
0 
0 
0 
1 
The example has three areas with sizes 1, 3, and 4.
The median is 3.
Think about which data structure to use for the median for best performance.
There are also multiple ways to parse the areas.

Databases for Twitter are eventually consistent.
But when a user creates a login it needs to be unique and guaranteed.
Design a system to support this.
Interviewer wanted me to describe paxos.

Given an array of arrays of sorted ints. Returned the kth largest.
Variations of this were asked three times.
Run time should be O(k * log n), where n is the number of arrays.
If n is 2 then it can solved in O(log k).

Class vs instance? Follow up: what is a virtual function and how are they implemented?
http://en.wikipedia.org/wiki/Virtual_method_table

Find all of the phone numbers in 50k files?
Use regular expression.
Know how to do this with command line commands.
Or in a Perl script.

Reverse a null terminated string.
An easy question does not mean the interview is a cupcake.
I assume easy questions are graded harderhow fast and how well did you finish?
Test cases, etc.

Implement binary search to find values from an array of sorted floats.
Same as above. Beaware of cupcakes.

Convert a string to a long.
Standard atoi.

Create the add and delete functions for a trinary search tree. It is like a binary search tree except there is a middle pointer and duplicates are allowed.
This middle pointer points to nodes with identical values.
Not really different from BST.
Mostly a mixture of coding and design questions. But questions from previous sections are also asked during onsite interviews.

Given a N x M sized Boggle board. Find all of the valid words.
This got asked twice.

Make the game asteriods. Code it.
Break the problem into work items and implement it.

Given an nary tree and m number of nodes, how do you find the first common parent? If the nodes had parent pointer, how would you do it?
You can extrapolate from the binary tree case.

topological sort.
Learn it. It gets asked a lot. Make sure you can recognize it and do both implementations.

You have 10MB of data mapping IP range to country code. And 100GB of IP mapping to URL.
Find the 10 countries with the most web traffic.
Find the 10 most visited URLs for each country.
First one is easy. Second requires a bit more thinking.

Given two nodes of a BST, return the least common ancestor. A node cannot be its parent.
(The other variation allows a node to be its own parent.)
Should be pretty simple.

Implement a prefix calculator.
Takes in the string "+ 3 * 3 4" and spits out 15.
Apparently the double stack implementation is impossible. :/

Add two strings. For example ""423" + "99" = "522"
This is a fun and common problem. Try to do it as efficiently as possible. Also, does it matter that it's base 10?

Subtract two strings.
Slightly trickier than adding. They are still both O(n) but subtraction requires more cycles.

Multiply two strings.
This one is pretty hard and it took some thinking.

Divide two strings.
Just kidding! I don't think this is possible in an 1 hour long interview.

Given two integer arrays and a number k. Return all pairs of numbers that sum to k. Each number of the pair has to be from a different array.
What is the best space and time efficient way to do this? You should arrive at an linear algorithm.

Design a hash that can also return a random element in O(1).
Kind of like an LRU cache where you need two data structures.

Design a mobile app for to control Hulu on the Xbox.
API, UI, network protocol.

Given an n x m grid. What is the total number of rectangles?
The sample below is 2 x 3 and contains 18 different rectangles.
If we remove a w x h portion of the grid, what is the total number of rectangles?
First part is really easy. Second part is too if you think about it first, but coding might take a little longer.

Design Twitter. Make sure you include a search function.
Big data, distributed system, system design questions are fun!

Using this mapping:
"0" > "a"
"1" > "b"
...
"24" > "y"
"25" > "z"
How many possible mappings are there for any numerical string?
For example, "11" can be mapped two different ways: "bb" and "j".
Spoilers: it's like fibonacci...

Given a list of words in an alien language.
If you know the list is sorted in alphabetical order then how do you determine the alphabetical order of the letters?
For example, from the following list of English words we can determine the letter "t" must come after "b".
And "c" is before "z".
list:
cab
cat
zebra
Beep! Beep! Topological sort problem detected.

Given a function f and a number d. I want you to call f after waiting d miliseconds.
People tell me this is a classic question asked by hiring managers for senior positions.
It's basically design a task scheduler.

Return the first n prime numbers.
How do you optimize this? Is it thread safe?

Given two strings a and b. Return true if any substring of a is an anagram of b.
This can be done in linear time with linear space.

Given an array of sorted nonoverlapping intervals.
Insert a random interval i into the array and maintain the array's property.
For example, inserting (3, 6) into {(0,1), (2,4), (5,10)} results in {(0,1), (2,10)}
Understand the array's implementation when designing the optimal solution.

Invert a binary tree. Each child now points to its parent. Return a list of the original leaf nodes.
This is like reversing a linked list, except with a few more if statements.

Invert a graph. If node A pointed to node B then B now points to A instead.
There are many ways to represent a graph. Which one has the best run time and easiest implementation for this problem?
Also, what happens if the graph is cyclical?

Transport a 4GB file between two systems; each with 1GB of RAM. The final output needs to be compeletely randomized.
My lack of filesystem knowledge doomed me.

Design a runner app that calculates miles per minute.
You have a GPS API and one for the UI.

Given a size n array that contains all intergers from 0 to n1. The elements are in random order, how do you sort it?
I feel really dumb not getting this question.

Colors on the web are defined by a three bytes: 0x00 00 00 to 0xFF FF FF.
Implement a lossy compression that maps from three bytes to three half bytes.
For example, 0xFF 01 FE is mapped to 0xF 0 F.
Test all values to make sure it works.

Water fill bar graph column problem.
There has to be a better description of this on the web.

Design a load balancer class.
Code it out. Make sure it can add and remove machines.

Convert an array of strings into one long string. And then convert it back.
What does the long string look like?

Build a class for handling math expressions.
Go fish. This question was very vague. In hindsight I should have asked for more clarifications before coding.

Given an array of unsigned ints and a number s. Return true if a pair in the array sums to s.
Worst case is O(n^2). How do you better?

Count the number of nodes in a binary tree that have only one child.
Recursive tree traversal. Shouldn't be too hard.

"Read and analyze this code. What do you think?"
The interviewer wants you to find bugs in code. It's usually bad abstraction, concurrency issues, memory leaks, or no input sanitation.
The usual stuff you'd discover in a code review.

Design the Maruder's Map from Harry Potter for a tablet.
Features for readibility? Data structures for storing information?

Design the system used by a local rental car agency. It needs to handle: reservations, check out, check in.
How does it handle error conditions? Such as reserved car is not returned by previous owner?
What if user wants a list of all cars available between a certain date?
How do you scale to a national chain like Hertz?

What is the least number of comparisons needed to find the smallest and largest numbers in an array of ints?
Worst case is 2n. How do you do better?

What is the least number of comparisons needed to find the second smallest and second largest numbers in an array of ints?
Try to find the second largest first by itself.

An N sized array contains integerts starting from 1. Find the first missing integer.
For example, in [4, 1, 3, 2, 6] the first missing integer is 5.
You can sort the array and find the missing number in O(n log n). How do you do better?

Describe the excel table problem.
Nag me about this. I need to update it.

The transitive property means if a > b and b > c then a > c. Assume a set of numbers break this property.
If a > b and b > c then a > c, a == c, or a < c. Given an array of such numbers, find the maximum value.
Is there even a guaranteed max?

What is override vs overwritten? Singleton vs Factory? cdecl/c++ calling conventions?
More term definitions. Memorize these.

A musuem's floor space is represented by a N x M matrix.
A square can be a wall, a guard, or empty space.
Given a list of guards, calculate the mahattan distance of all empty space to the nearest guard.
The path cannot go through walls. This is what the output should look like:
G 
1 
2 
2 
3 
4 
5 
6 
1 
2 
2 
1 
2 
3 
4 
5 
2 
2 
1 
G 
1 
2 
3 
4 
3 
3 
2 
1 
2 
3 
4 
5 
W 
W 
W 
W 
W 
4 
W 
W 
G 
1 
2 
3 
4 
5 
6 
7 
Bonus: Given an N x M with one guard. Place a second guard to optmize the coverage.
The bonus part probably has a dynamic programming solution. And you also need to define what is optimal.

Given two strings, find the largest common substring.
I have no idea what the optimal solution is but I think this is a well known problem and desribed on wikipedia.

Implement a filesystem that allows multiple readers and one writer.
No readers can read when the writer is writing.
And the writer cannot start writing if a read is in progress.
Concurrency fun!

Design a search engine.
Something about servers, databases, etc.

Given a noncyclical linked list. Each node also contains a random pointer,
which points to null or another node that is already in the list. Copy this list.
There is a layman solution that uses hash tables.
And a trick solution that doesn't need the hash, and I'm not sure how people can actually come up with it instead of the hash solution.

Design a URL crawler using the following APIs:
getURL()  returns a list of all pages linked from the current page.
visit()  process the current page.
Given a starting page, how do you process all pages?
It's a graph traversal problem. But think about DFS vs BFS.
If the average page has 10 links and goes 10 layers deep then how much memory does each take up?

Given an array A. Return array B where B[i] = the product of all elements in A except for A[i].
You cannot use division.
Stupid puzzle problem.

Implement a filesystem that allows multiple readers and one writer.
No readers can read when the writer is writing.
And the writer cannot start writing if a read is in progress.
Concurrency fun!

What is deadlock?
Race condition?
What happens when you add const to the end of a method declaration?
More definitions. Answer these sussinctly.

Given a black and white image. How do you produce the mirror image?
Unlike reversing a string, we know have to reverse the bits in the bytes.
This is actually a complicated problem.

Merge an array strings into one string. Return this string to the clients.
When given back the merged string, separate it into the array of strings again.
This is different from the other problem because the clients can use the intermediatery string.
It's a more open ended question and leads to a discussion about trade offs.

Given two linked lists. Find out if they converge.
Return the node they first converge on.
Edge cases: what if a list is cyclic?

Given a M by N matrix of intergers. If an entry is 0 then set the entire row and column to zero.
How do you make this run faster?

Shift an array by k places.
There is a trick to this.

When playing a game on the Xbox, I want to use the corresponding app on my phone.
Design a robust system to handle this. The phone needs to know the XBox ID/gamertag.
More distributed system design fun!

Given two parameters: n and c. Print out all integers from 1 to n in c columns.
For example, the output for n = 13 and c = 4 looks like this.
1 
5 
9 
13 
2 
6 
10 
3 
7 
11 
4 
8 
12 
This is easy. Part 2 is below.

In the previous problem, notice there are empty spaces in the last column.
Change the algorithm to move the empty spaces in the last row. Like this:
1 
5 
8 
11 
2 
6 
9 
12 
3 
7 
10 
13 
4 
For some reason, I just could not figure out the second part of this problem. Felt so dumb.
Then again, I was exhausted.
It was six hours of straight interviews without any breaksmy lunch buddy decided to turn my lunch into an interview.
Note to companies: please don't do this. Us poor candidates really need our break.

GetXY(), DrawX(), DrawY().
Remind me to update and describe this problem using drawings.

Given a list of lists of strings such as:
{("a1", "a2"),
("b1")
("c1", "c2", "c3")}
Print them in this order: "a1", "b1", "c1", "a2", "c2", "c3"
Again choice of data structure makes or breaks this problem.

What would you do if you had a billion dollars?
Someone asked this immediately after a challenging system design question.
I was totally caught off guard and just mumbled.
Though I am very proud of myself for not blurting out "Hookers and blow."

Do you really want to work for us?
Are we your first choice?
Who else are you looking at?
Are we in the running?
This often get asked at the end of an interview.
Or it's the first question asked when the recruiter calls after an interview.
Companies do this to gage your interest and excitement level.
They don't want to give an offer to someone who doesn't want to work for them.
I told my Hulu referral that I rather go to Google (recruiter told him to ask me).
Then I told my Google interviewers that I want to be at 343 Industries or Redfin.
Guess how many offers I got from Hulu and Google.

Where do you see yourself in 5 years?
Not at this stupid company!
_ Did you read the previous question? In general, try to say things they want to hear until you have an offer.