A friend of mine is interviewing for a job. One of the interview questions got me thinking, just wanted some feedback.
There are 2 non-negative integers: i and j. Given the following equation, find an (optimal) solution to iterate over i and j in such a way that the output is sorted.
2^i * 5^j
So the first few rounds would look like this:
2^0 * 5^0 = 1
2^1 * 5^0 = 2
2^2 * 5^0 = 4
2^0 * 5^1 = 5
2^3 * 5^0 = 8
2^1 * 5^1 = 10
2^4 * 5^0 = 16
2^2 * 5^1 = 20
2^0 * 5^2 = 25
Try as I might, I can't see a pattern. Your thoughts?

There is a matrix, m x n. Several groups of people locate at some certain spots. In the following example, there are three groups and the number 4 indicates there are four people in this group. Now we want to find a meeting point in the matrix so that the cost of all groups moving to that point is the minimum. As for how to compute the cost of moving one group to another point, please see the following example.
Group1: (0, 1), 4
Group2: (1, 3), 3
Group3: (2, 0), 5
. 4 . .
. . . 3
5 . . .
If all of these three groups moving to (1, 1), the cost is: 4*((1-0)+(1-1)) + 5*((2-1)+(1-0))+3*((1-1)+(3-1))

Tags: algorithm, boston, interview process, interview |
Posted by Admin on
3/1/2012 12:04 PM |
Comments (1)

There were 3 rounds of interview.In the first round they asked s string related question.1. Given a string and set of characters, find the shortest substring which contains all the characters in the string.In the 2nd round2.Given a 2d sorted matrix (known as tableau) . where rows and cols are sorted, write an algo to find an element.In the 3rd round they asked about garbage collection in java, about my projects and a question related to graphs I dont remeber exactly at this point.
Given 2n points on a circle.find the number of ways to draw n non intersecting chords.

You have 1 to N-1 array and 1 to N numbers, and one number is missing, you need to find the missing the number. Now you have 1 to N-2 numbers, and two numbers missing. Find them.
Solution:The question can be elucidated as follows.Given an array of size N-1 containing numbers less than N and with out any duplicates!! We knew that there is a number missing from the array say K .Let S be the sum of the elements of the array.
Sum of first N natural numbers=N*(N+1)/2
and S=N*(N+1)/2 – K.Now putting this other way around we get K=N*(N+1)/2 -S !!
Now the second part of the question says that there are 2 of the first N numbers missing.Let they be X and Y.
We solve this problem by solving 2 essential equations.
They are X+Y=N*(N+1)/2 -S (1)
X*Y=N!/P (2) where S and P are the cumulative sum and product of the array entries.
You have cycle in linked list. Find it. Prove that time complexity is linear. Also find the node at which looping takes place.
Solution:The problem of checking whether there is a cycle or not can be solved using 2 pointers one moving in increments of 1 and the other in increments of 2.If there is a cycle then these 2 pointers meet at some node say N1 inside the cycle otherwise the fast pointer reaches the end of the list.This is a O(N) solution.
Now coming to the identification of the node at which looping took place.After our identification of cycle ,both the pointers P1 and P2 are at node N1.Now iterate the slow pointer to count the no of nodes in the cycle.(After traversing the whole cycle P1 and P2 shall again be at the same node).Let this size be K.Now take one of the pointers to the head node and count the no of nodes till N1.Let this number be X.Now use one of these pointers to reverse the cycle starting from N1.Only the cycle gets reversed.Now again traverse from head node to N1.Let the number of nodes this time be Y.Let the no of nodes from head to the start node of the cycle be Z
Now X+Y=2*Z+K .Hence solve for K and then having figured out the start node N2 of the cycle.Now as the cycle is reversed having figured out this start node its next node is the looping nodes so set the looping nodes next pointer to NULL and reverse the list further till you reach N2.Questions on my project please be prepare well about your projectHow do you search for a word in a large database.How do you build address bar in say gmail. i.e. if you press ‘r’ then you get all email starting from ‘r’, and if you press ‘ra’ then you will get emails starting from ‘ra’.

Tags: algorithm, graph theory |
Posted by Admin on
1/18/2012 11:34 AM |
Comments (0)

Given an undirected graph, design a O(V+E) algo to detect whether there is a triangle in the graph ot not.
Question: How to find the Least Common Ancestor for 2 nodes of a binary tree?
This sounds like "On finding lowest common ancestors: simplification and parallelization", by Baruch Schieber and Uzi Vishkin, SIAM J. Comput. Vol 17, No 6, December 1988. A google search leads me tohttp://ia700208.us.archive.org/12/items/onfindinglowe00schi/onfindinglowe00schi.pdf.
I actually wrote an implementation of this for fun - it is in a zip file miscellaneous for-fun Java code that you can find off a link from http://www.mcdowella.demon.co.uk/programs.html.
(The algorithm needs linear space and time for pre-processing, then runs at O(1) per query).

Tags: algorithm, software engineer |
Posted by Admin on
1/12/2012 12:45 PM |
Comments (0)

Jim was asked following question in interview recently:
Let suppose you have, following grid on Cartesian coordinate system ( Quadrant I).
o - x - x - x - o
| | | | |
x - x - x - o - x
| | | | |
x - o - o - x - x
where, o => person at intersection and x => no person at intersection
class Point {
int x;
int y;
boolean hasPerson;
}
Point findNearestPointWhereAllPeopleCanMeet(Point[] people) {
}
Implement a routine where given a list of people location (points), find a location(point) such that is closest point to all given point.
How would you solve this problem ?
Tags: algorithm, questions, puzzle, software engineer, tech leader, |
Posted by Admin on
1/26/2011 2:16 PM |
Comments (0)

Here’s a list of 150 Google interview questions. Don't ask us where we got it from...
Product Marketing ManagerWhy do you want to join Google?
What do you know about Google’s product and technology?
If you are Product Manager for Google’s Adwords, how do you plan to market this?
What would you say during an AdWords or AdSense product seminar?
Who are Google’s competitors, and how does Google compete with them?
Have you ever used Google’s products? Gmail?
What’s a creative way of marketing Google’s brand name and product?
If you are the product marketing manager for Google’s Gmail product, how do you plan to market it so as to achieve 100 million customers in 6 months?
How much money you think Google makes daily from Gmail ads?
Name a piece of technology you’ve read about recently. Now tell me your own creative execution for an ad for that product.
Say an advertiser makes $0.10 every time someone clicks on their ad. Only 20% of people who visit the site click on their ad. How many people need to visit the site for the advertiser to make $20?
Estimate the number of students who are college seniors, attend four-year schools, and graduate with a job in the United States every year.
Product ManagerHow would you boost the GMail subscription base?
What is the most efficient way to sort a million integers?
How would you re-position Google’s offerings to counteract competitive threats from Microsoft?
How many golf balls can fit in a school bus?
You are shrunk to the height of a nickel and your mass is proportionally reduced so as to maintain your original density. You are then thrown into an empty glass blender. The blades will start moving in 60 seconds. What do you do?
How much should you charge to wash all the windows in Seattle?
How would you find out if a machine’s stack grows up or down in memory?
Explain a database in three sentences to your eight-year-old nephew.
How many times a day does a clock’s hands overlap?
You have to get from point A to point B. You don’t know if you can get there. What would you do?
Imagine you have a closet full of shirts. It’s very hard to find a shirt. So what can you do to organize your shirts for easy retrieval?
Every man in a village of 100 married couples has cheated on his wife. Every wife in the village instantly knows when a man other than her husband has cheated, but does not know when her own husband has. The village has a law that does not allow for adultery. Any wife who can prove that her husband is unfaithful must kill him that very day. The women of the village would never disobey this law. One day, the queen of the village visits and announces that at least one husband has been unfaithful. What happens?
In a country in which people only want boys, every family continues to have children until they have a boy. If they have a girl, they have another child. If they have a boy, they stop. What is the proportion of boys to girls in the country?
If the probability of observing a car in 30 minutes on a highway is 0.95, what is the probability of observing a car in 10 minutes (assuming constant default probability)?
If you look at a clock and the time is 3:15, what is the angle between the hour and the minute hands? (The answer to this is not zero!)
Four people need to cross a rickety rope bridge to get back to their camp at night. Unfortunately, they only have one flashlight and it only has enough light left for seventeen minutes. The bridge is too dangerous to cross without a flashlight, and it’s only strong enough to support two people at any given time. Each of the campers walks at a different speed. One can cross the bridge in 1 minute, another in 2 minutes, the third in 5 minutes, and the slow poke takes 10 minutes to cross. How do the campers make it across in 17 minutes?
You are at a party with a friend and 10 people are present including you and the friend. your friend makes you a wager that for every person you find that has the same birthday as you, you get $1; for every person he finds that does not have the same birthday as you, he gets $2. would you accept the wager?
How many piano tuners are there in the entire world?
You have eight balls all of the same size. 7 of them weigh the same, and one of them weighs slightly more. How can you find the ball that is heavier by using a balance and only two weighings?
You have five pirates, ranked from 5 to 1 in descending order. The top pirate has the right to propose how 100 gold coins should be divided among them. But the others get to vote on his plan, and if fewer than half agree with him, he gets killed. How should he allocate the gold in order to maximize his share but live to enjoy it? (Hint: One pirate ends up with 98 percent of the gold.)
You are given 2 eggs. You have access to a 100-story building. Eggs can be very hard or very fragile means it may break if dropped from the first floor or may not even break if dropped from 100th floor. Both eggs are identical. You need to figure out the highest floor of a 100-story building an egg can be dropped without breaking. The question is how many drops you need to make. You are allowed to break 2 eggs in the process.
Describe a technical problem you had and how you solved it.
How would you design a simple search engine?
Design an evacuation plan for San Francisco.
There’s a latency problem in South Africa. Diagnose it.
What are three long term challenges facing Google?
Name three non-Google websites that you visit often and like. What do you like about the user interface and design? Choose one of the three sites and comment on what new feature or project you would work on. How would you design it?
If there is only one elevator in the building, how would you change the design? How about if there are only two elevators in the building?
How many vacuum’s are made per year in USA?
Software EngineerWhy are manhole covers round?
What is the difference between a mutex and a semaphore? Which one would you use to protect access to an increment operation?
A man pushed his car to a hotel and lost his fortune. What happened?
Explain the significance of “dead beef”.
Write a C program which measures the the speed of a context switch on a UNIX/Linux system.
Given a function which produces a random integer in the range 1 to 5, write a function which produces a random integer in the range 1 to 7.
Describe the algorithm for a depth-first graph traversal.
Design a class library for writing card games.
You need to check that your friend, Bob, has your correct phone number, but you cannot ask him directly. You must write a the question on a card which and give it to Eve who will take the card to Bob and return the answer to you. What must you write on the card, besides the question, to ensure Bob can encode the message so that Eve cannot read your phone number?
How are cookies passed in the HTTP protocol?
Design the SQL database tables for a car rental database.
Write a regular expression which matches a email address.
Write a function f(a, b) which takes two character string arguments and returns a string containing only the characters found in both strings in the order of a. Write a version which is order N-squared and one which is order N.
You are given a the source to a application which is crashing when run. After running it 10 times in a debugger, you find it never crashes in the same place. The application is single threaded, and uses only the C standard library. What programming errors could be causing this crash? How would you test each one?
Explain how congestion control works in the TCP protocol.
In Java, what is the difference between final, finally, and finalize?
What is multithreaded programming? What is a deadlock?
Write a function (with helper functions if needed) called to Excel that takes an excel column value (A,B,C,D…AA,AB,AC,… AAA..) and returns a corresponding integer value (A=1,B=2,… AA=26..).
You have a stream of infinite queries (ie: real time Google search queries that people are entering). Describe how you would go about finding a good estimate of 1000 samples from this never ending set of data and then write code for it.
Tree search algorithms. Write BFS and DFS code, explain run time and space requirements. Modify the code to handle trees with weighted edges and loops with BFS and DFS, make the code print out path to goal state.
You are given a list of numbers. When you reach the end of the list you will come back to the beginning of the list (a circular list). Write the most efficient algorithm to find the minimum # in this list. Find any given # in the list. The numbers in the list are always increasing but you don’t know where the circular list begins, ie: 38, 40, 55, 89, 6, 13, 20, 23, 36.
Describe the data structure that is used to manage memory. (stack)
What’s the difference between local and global variables?
If you have 1 million integers, how would you sort them efficiently? (modify a specific sorting algorithm to solve this)
In Java, what is the difference between static, final, and const. (if you don’t know Java they will ask something similar for C or C++).
Talk about your class projects or work projects (pick something easy)… then describe how you could make them more efficient (in terms of algorithms).
Suppose you have an NxN matrix of positive and negative integers. Write some code that finds the sub-matrix with the maximum sum of its elements.
Write some code to reverse a string.
Implement division (without using the divide operator, obviously).
Write some code to find all permutations of the letters in a particular string.
What method would you use to look up a word in a dictionary?
Imagine you have a closet full of shirts. It’s very hard to find a shirt. So what can you do to organize your shirts for easy retrieval?
You have eight balls all of the same size. 7 of them weigh the same, and one of them weighs slightly more. How can you fine the ball that is heavier by using a balance and only two weighings?
What is the C-language command for opening a connection with a foreign host over the internet?
Design and describe a system/application that will most efficiently produce a report of the top 1 million Google search requests. These are the particulars: 1) You are given 12 servers to work with. They are all dual-processor machines with 4Gb of RAM, 4x400GB hard drives and networked together.(Basically, nothing more than high-end PC’s) 2) The log data has already been cleaned for you. It consists of 100 Billion log lines, broken down into 12 320 GB files of 40-byte search terms per line. 3) You can use only custom written applications or available free open-source software.
There is an array A[N] of N numbers. You have to compose an array Output[N] such that Output[i] will be equal to multiplication of all the elements of A[N] except A[i]. For example Output[0] will be multiplication of A[1] to A[N-1] and Output[1] will be multiplication of A[0] and from A[2] to A[N-1]. Solve it without division operator and in O(n).
There is a linked list of numbers of length N. N is very large and you don’t know N. You have to write a function that will return k random numbers from the list. Numbers should be completely random. Hint: 1. Use random function rand() (returns a number between 0 and 1) and irand() (return either 0 or 1) 2. It should be done in O(n).
Find or determine non existence of a number in a sorted list of N numbers where the numbers range over M, M>> N and N large enough to span multiple disks. Algorithm to beat O(log n) bonus points for constant time algorithm.
You are given a game of Tic Tac Toe. You have to write a function in which you pass the whole game and name of a player. The function will return whether the player has won the game or not. First you to decide which data structure you will use for the game. You need to tell the algorithm first and then need to write the code. Note: Some position may be blank in the game? So your data structure should consider this condition also.
You are given an array [a1 To an] and we have to construct another array [b1 To bn] where bi = a1*a2*…*an/ai. you are allowed to use only constant space and the time complexity is O(n). No divisions are allowed.
How do you put a Binary Search Tree in an array in a efficient manner. Hint :: If the node is stored at the ith position and its children are at 2i and 2i+1(I mean level order wise)Its not the most efficient way.
How do you find out the fifth maximum element in an Binary Search Tree in efficient manner. Note: You should not use use any extra space. i.e sorting Binary Search Tree and storing the results in an array and listing out the fifth element.
Given a Data Structure having first n integers and next n chars. A = i1 i2 i3 … iN c1 c2 c3 … cN.Write an in-place algorithm to rearrange the elements of the array ass A = i1 c1 i2 c2 … in cn
Given two sequences of items, find the items whose absolute number increases or decreases the most when comparing one sequence with the other by reading the sequence only once.
Given That One of the strings is very very long , and the other one could be of various sizes. Windowing will result in O(N+M) solution but could it be better? May be NlogM or even better?
How many lines can be drawn in a 2D plane such that they are equidistant from 3 non-collinear points?
Let’s say you have to construct Google maps from scratch and guide a person standing on Gateway of India (Mumbai) to India Gate(Delhi). How do you do the same?
Given that you have one string of length N and M small strings of length L. How do you efficiently find the occurrence of each small string in the larger one?
Given a binary tree, programmatically you need to prove it is a binary search tree.
You are given a small sorted list of numbers, and a very very long sorted list of numbers – so long that it had to be put on a disk in different blocks. How would you find those short list numbers in the bigger one?
Suppose you have given N companies, and we want to eventually merge them into one big company. How many ways are theres to merge?
Given a file of 4 billion 32-bit integers, how to find one that appears at least twice?
Write a program for displaying the ten most frequent words in a file such that your program should be efficient in all complexity measures.
Design a stack. We want to push, pop, and also, retrieve the minimum element in constant time.
Given a set of coin denominators, find the minimum number of coins to give a certain amount of change.
Given an array, i) find the longest continuous increasing subsequence. ii) find the longest increasing subsequence.
Suppose we have N companies, and we want to eventually merge them into one big company. How many ways are there to merge?
Write a function to find the middle node of a single link list.
Given two binary trees, write a compare function to check if they are equal or not. Being equal means that they have the same value and same structure.
Implement put/get methods of a fixed size cache with LRU replacement algorithm.
You are given with three sorted arrays ( in ascending order), you are required to find a triplet ( one element from each array) such that distance is minimum.
Distance is defined like this : If a[i], b[j] and c[k] are three elements then distance=max(abs(a[i]-b[j]),abs(a[i]-c[k]),abs(b[j]-c[k]))” Please give a solution in O(n) time complexity
How does C++ deal with constructors and deconstructors of a class and its child class?
Write a function that flips the bits inside a byte (either in C++ or Java). Write an algorithm that take a list of n words, and an integer m, and retrieves the mth most frequent word in that list.
What’s 2 to the power of 64?
Given that you have one string of length N and M small strings of length L. How do you efficiently find the occurrence of each small string in the larger one?
How do you find out the fifth maximum element in an Binary Search Tree in efficient manner.
Suppose we have N companies, and we want to eventually merge them into one big company. How many ways are there to merge?
There is linked list of millions of node and you do not know the length of it. Write a function which will return a random number from the list.
You need to check that your friend, Bob, has your correct phone number, but you cannot ask him directly. You must write a the question on a card which and give it to Eve who will take the card to Bob and return the answer to you. What must you write on the card, besides the question, to ensure Bob can encode the message so that Eve cannot read your phone number?
How long it would take to sort 1 trillion numbers? Come up with a good estimate.
Order the functions in order of their asymptotic performance: 1) 2^n 2) n^100 3) n! 4) n^n
There are some data represented by(x,y,z). Now we want to find the Kth least data. We say (x1, y1, z1) > (x2, y2, z2) when value(x1, y1, z1) > value(x2, y2, z2) where value(x,y,z) = (2^x)*(3^y)*(5^z). Now we can not get it by calculating value(x,y,z) or through other indirect calculations as lg(value(x,y,z)). How to solve it?
How many degrees are there in the angle between the hour and minute hands of a clock when the time is a quarter past three?
Given an array whose elements are sorted, return the index of a the first occurrence of a specific integer. Do this in sub-linear time. I.e. do not just go through each element searching for that element.
Given two linked lists, return the intersection of the two lists: i.e. return a list containing only the elements that occur in both of the input lists.
What’s the difference between a hashtable and a hashmap?
If a person dials a sequence of numbers on the telephone, what possible words/strings can be formed from the letters associated with those numbers?
How would you reverse the image on an n by n matrix where each pixel is represented by a bit?
Create a fast cached storage mechanism that, given a limitation on the amount of cache memory, will ensure that only the least recently used items are discarded when the cache memory is reached when inserting a new item. It supports 2 functions: String get(T t) and void put(String k, T t).
Create a cost model that allows Google to make purchasing decisions on to compare the cost of purchasing more RAM memory for their servers vs. buying more disk space.
Design an algorithm to play a game of Frogger and then code the solution. The object of the game is to direct a frog to avoid cars while crossing a busy road. You may represent a road lane via an array. Generalize the solution for an N-lane road.
What sort would you use if you had a large data set on disk and a small amount of ram to work with?
What sort would you use if you required tight max time bounds and wanted highly regular performance.
How would you store 1 million phone numbers?
Design a 2D dungeon crawling game. It must allow for various items in the maze – walls, objects, and computer-controlled characters. (The focus was on the class structures, and how to optimize the experience for the user as s/he travels through the dungeon.)
What is the size of the C structure below on a 32-bit system? On a 64-bit?
struct foo {
char a;
char* b;
};
Software Engineer in TestEfficiently implement 3 stacks in a single array.
Given an array of integers which is circularly sorted, how do you find a given integer.
Write a program to find depth of binary search tree without using recursion.
Find the maximum rectangle (in terms of area) under a histogram in linear time.
Most phones now have full keyboards. Before there there three letters mapped to a number button. Describe how you would go about implementing spelling and word suggestions as people type.
Describe recursive mergesort and its runtime. Write an iterative version in C++/Java/Python.
How would you determine if someone has won a game of tic-tac-toe on a board of any size?
Given an array of numbers, replace each number with the product of all the numbers in the array except the number itself *without* using division.
Create a cache with fast look up that only stores the N most recently accessed items.
How to design a search engine? If each document contains a set of keywords, and is associated with a numeric attribute, how to build indices?
Given two files that has list of words (one per line), write a program to show the intersection.
What kind of data structure would you use to index annagrams of words? e.g. if there exists the word “top” in the database, the query for “pot” should list that.
Quantitative Compensation AnalystWhat is the yearly standard deviation of a stock given the monthly standard deviation?
How many resumes does Google receive each year for software engineering?
Anywhere in the world, where would you open up a new Google office and how would you figure out compensation for all the employees at this new office?
What is the probability of breaking a stick into 3 pieces and forming a triangle?
Engineering ManagerYou’re the captain of a pirate ship, and your crew gets to vote on how the gold is divided up. If fewer than half of the pirates agree with you, you die. How do you recommend apportioning the gold in such a way that you get a good share of the booty, but still survive?
AdWords AssociateHow would you work with an advertiser who was not seeing the benefits of the AdWords relationship due to poor conversions?
How would you deal with an angry or frustrated advertisers on the phone?
Tags: c++ questions, algorithm, |
Posted by Admin on
5/16/2010 11:19 PM |
Comments (0)

Question
Come out with an algorithm for getting the column number provided the
column name in a excel sheet and vice versa. Excel has a naming
convention of A,B..Z,AA,AB,AC..ZZ,AAA… This had to be converted to the
column numbers. A will be 1 and AA will 27.. Also the algorithm to find
the name provided column number.
Answer
#include <string>
#include <iostream>
using namespace std;
int ExcelColNum (char *name)
{
int s = 0;
for (int i=strlen(name)-1, e=1; i>=0; –i, e*=26) {
s
+= e*(name[i]-’A'+1);
}
return s;
}
string ExcelColName (int num)
{
string name;
for ( ; num; num/=26) {
name.insert (name.begin(),
‘A’+(num-1)%26);
}
return name;
}
int main(void)
{
cout << "AAA ==> "
<< ExcelColNum ("AAA") << endl;
cout <<
"703 ==> " << ExcelColName (703) << endl;
return 0;
}
Results are,
AAA ==> 703
703 ==> AAA
All the below questions are to be done in O(n) time complexity.
1>Given an array of size n-1 whose entries are integers in the range [1, n], find an integer that is missing. Use only O(1) space and treat the input as read-only.
2>Given an array of size n-2 whose entries are integers in the range [1, n], find two integer that are missing.
3>There is an array A[N] of N integers. You have to compose an array B[N] such that Output[i] will be equal to the product of all the elements of A[] except A[i].
or
Example:
INPUT:[4, 3, 2, 1, 2]
OUTPUT:[12, 16, 24, 48, 24]
Solve it without division operator and in O(n).
Solution :
1>Let the missing number be M. We know that the sum of first
N natural numbers is N*(N+1)/2. Traverse through the array once and
calculate the sum. This is the sum of first N natural numbers – M or
S=N*(N+1)/2 – M. Therefore M = N*(N+1)/2 – S.
2>Similar approach to the first one. Traverse the array once and
calculate its sum and multiplication. Let the sum be S and
multiplication be M. Let the missing numbers be P and Q. From above we
know that P+Q = N*(N+1)/2 – S. Also P*Q = N!/M. So we can get P and Q
from these two equations.
3> Lets first see the C++ solution.
void solution(vector<int> A)
{
int N=A.size(),i,j;
vector<int> L(N,0);
vector<int> R(N,0);
vector<int> B(N,0);
for (i=0,j=N-1; i=0 ;i++, j–)
{
L[i] = i==0? 1 : A[i-1] * L[i-1];
R[j] = j==N-1? 1 : R[j+1] * A[j+1];
}
for (i=0; i
{
B[i] = L[i] * R[i];
printf(“%d “,B[i]);
}
}
Most is clear from the program. Anyways, through the L and R we calculate the multiplication of terms to the left and right of i-th term. then finally we multiply it to get the result.

Tags: java, algorithm, interview process |
Posted by Admin on
11/25/2008 9:24 AM |
Comments (0)

Was removed by author's request. But you can still read original story of BadMagicNumber experience in google interview.
Last time I was interviewed for a software development engineer position, the recruiter asked me some of the classical Microsoft interview questions, such as “How Would You Move Mount Fuji?” or “How many gas station are there in your country?“.
It was the first time for me to be asked such questions but having obtained the job I think my answers were good enough.
After that day, I looked for other well-known interview questions
and I discovered that Google has a totally different approach, focusing
on algorithms, data structures and complexity.
For instance, one of Google interview questions says:
There is an array A[N] of N integers. You have to
compose an array Output[N+1] such that Output[i] will be equal to the
product of all the elements of A[] except A[i].
Example:
INPUT:[4, 3, 2, 1, 2]
OUTPUT:[12, 16, 24, 48, 24]
Solve it without division operator and in O(n).
Without the two constraints at the end of the puzzle it would have been straightforward, but now we have to be smart.
Actually, the product of all elements of A[] except A[i] is equal to the product of all elements before A[i] and those after A[i].
We can traverse A[] twice, once from left to right and once in the opposite way and multiply all the elements we find before A[i].
We’ll pretend to have a new array called Output[] to store the output of the first pass, assigning Output[i] the product of all elements preceding A[i]:
view plaincopy to clipboardprint?
let rec firstpass product input =
match input with
| [] -> []
| x::xs -> product :: firstpass (product * x) xs
let rec firstpass product input =
match input with
| [] -> []
| x::xs -> product :: firstpass (product * x) xs
For the second pass we need to move from right to left, but this can be done by reversing the input arrays and moving as usual:
view plaincopy to clipboardprint?
let secondpass product input arr =
let rev_input = List.rev input
let rev_arr = List.rev arr
let rec rev_secondpass product (input:list<int>) arr =
match arr with
| [] -> []
| x::xs -> rev_secondpass (product * input.Head) input.Tail xs @ [(x * product)]
rev_secondpass product rev_input rev_arr
let secondpass product input arr =
let rev_input = List.rev input
let rev_arr = List.rev arr
let rec rev_secondpass product (input:list<int>) arr =
match arr with
| [] -> []
| x::xs -> rev_secondpass (product * input.Head) input.Tail xs @ [(x * product)]
rev_secondpass product rev_input rev_arr
Both firstpass and secondpass expect an integer argument called product, which will be always be 1 at the beginning and will be used to store the intermediate products during the recursive calls.
With these functions we can just define an input array and apply them to get the result.
The following is the complete F# code:
view plaincopy to clipboardprint?
#light
let input = [ 4; 3; 2; 1; 2 ]
let answer values =
let rec firstpass product input =
match input with
| [] -> []
| x::xs -> product :: firstpass (product * x) xs
let secondpass product input arr =
let rev_input = List.rev input
let rev_arr = List.rev arr
let rec rev_secondpass product (input:list<int>) arr =
match arr with
| [] -> []
| x::xs -> rev_secondpass (product * input.Head) input.Tail xs @ [(x * product)]
rev_secondpass product rev_input rev_arr
values |> firstpass 1 |> secondpass 1 values

Tags: algorithm, questions, answers, c++ questions |
Posted by Admin on
7/29/2008 12:59 AM |
Comments (0)

1. Reverse a singly linked list
//
// iterative version
//
Node* ReverseList( Node ** List )
{
Node *temp1 = *List;
Node * temp2 = NULL;
Node * temp3 = NULL;
while ( temp1 )
{
*List = temp1; //set the head to last node
temp2= temp1->pNext; // save the next ptr in temp2
temp1->pNext = temp3; // change next to privous
temp3 = temp1;
temp1 = temp2;
}
return *List;
}
2. Delete a node in double linked list
void deleteNode(node *n)
{
node *np = n->prev;
node *nn = n->next;
np->next = n->next;
nn->prev = n->prev;
delete n;
}
3. Sort a linked list
//sorting in descending order
struct node
{
int value;
node* NEXT;
}
//Assume HEAD pointer denotes the first element in the //linked list
// only change the values…don’t have to change the //pointers
Sort( Node *Head)
{
node* first,second,temp;
first= Head;
while(first!=null)
{
second=first->NEXT;
while(second!=null)
{
if(first->value < second->value)
{
temp = new node();
temp->value=first->value;
first->value=second->value;
second->value=temp->value;
delete temp;
}
second=second->NEXT;
}
first=first->NEXT;
}
}
4. Reverse a string
void ReverseString (char *String)
{
char *Begin = String;
char *End = String + strlen(String) - 1;
char TempChar = '\0';
while (Begin < End)
{
TempChar = *Begin;
*Begin = *End;
*End = TempChar;
Begin++;
End--;
}
}
5. Insert a node a sorted linked list
void sortedInsert(Node * head, Node* newNode)
{
Node *current = head;
// traverse the list until you find item bigger the // new node value
//
while (current!= NULL && current->data < newNode->data)
{
current = current->next);
}
//
// insert the new node before the big item
//
newNode->next = current->next;
current = newNode;
}
6. Covert a string to upper case
void ToUpper(char * S)
{
while (*S!=0)
{
*S=(*S >= 'a' && *S <= 'z')?(*S-'a'+'A'):*S;
S++;
}
}
7. Multiple a number by 7 without using * and + operator.
NewNum = Num << 3; // mulitplied by 2 ^ 3 = 8
NewNum = NewNum - Num; // 8 – 1 = 7
8.
Write a function that takes in a string parameter and checks to see
whether or not it is an integer, and if it is then return the integer
value.
#include
int strtoint(char *s)
{
int index = 0, flag = 0;
while( *(s+index) != '\0')
{
if( (*(s + index) >= '0') &&
*(s + index) <= '9')
{
flag = 1;
index++;
}
else
{
flag = 0;
break;
}
}
if( flag == 1 )
return atoi(s);
else
return 0;
}
main()
{
printf("%d",strtoint("0123"));
printf("\n%d",strtoint("0123ii"));
}
9. Print a data from a binary tree – In-order(ascending)
//
// recursive version
//
Void PrintTree ( struct * node node )
{
if ( node == NULL )
return;
PrintTree(node->left );
Printf(“%d”, node->data);
PrintTree(node->right );
}
10. print integer using only putchar
//
// recursive version
//
void PrintNum ( int Num )
{
if ( Num == 0 )
return;
PrintNum ( Num / 10 );
Puthcar ( ‘0’+ Num % 10 );
}
11. Find the factorial of number
//
// recursive version
//
int Factorial( int Num )
{
If ( num > 0 )
return Num * Factorial ( Num –1 );
else
return 1;
}
//
// iterative version
//
int Factorial( int Num )
{
int I
int result = 1;
for ( I= Num; I > 0; I-- )
{
result = result * I;
}
return result;
}
12. Generate Fib numbers:
int fib( n ) // recursive version
{
if ( n < 2 )
return 1;
else
return fib ( n –1 ) + fib ( n –2 );
}
int fib( n ) //iterative version
{
int f1 =1, f2 = 1;
if ( n < 2 )
return 1;
for ( i = 1; i < N; i++)
{
f = f1 + f2;
f1= f2;
f = f1;
}
return f;
}
13. Write a function that finds the last instance of a character in a string
char *lastchar(char *String, char ch)
{
char *pStr = NULL;
// traverse the entire string
while( * String ++ != NULL )
{
if( *String == ch )
pStr = String;
}
return pStr;
}
14. Return Nth the node from the end of the linked list in one pass.
Node * GetNthNode ( Node* Head , int NthNode )
{
Node * pNthNode = NULL;
Node * pTempNode = NULL;
int nCurrentElement = 0;
for ( pTempNode = Head; pTempNode != NULL; pTempNode = pTempNode->pNext )
{
nCurrentElement++;
if ( nCurrentElement - NthNode == 0 )
{
pNthNode = Head;
}
else
if ( nCurrentElement - NthNode > 0)
{
pNthNode = pNthNode ->pNext;
}
}
if (pNthNode )
{
return pNthNode;
}
else
return NULL;
}
15. Counting set bits in a number.
First version:
int CoutSetBits(int Num)
{
for(int count=0; Num; Num >>= 1)
{
if (Num & 1)
count++;
}
return count;
}
Optimized version:
int CoutSetBits(int Num)
{
for(int count =0; Num; count++)
{
Num &= Num -1;
}
}
Tags: interview process, algorithm, answers |
Posted by Admin on
3/12/2008 2:25 PM |
Comments (0)

I've been meaning to write up some tips on interviewing at Google for a
good long time now. I keep putting it off, though, because it's going
to make you mad. Probably. For some statistical definition of "you",
it's very likely to upset you.
Why? Because... well, here, I wrote a little ditty about it:
Hey man, I don't know that stuff
Stevey's talking aboooooout
If my boss thinks it's important
I'm gonna get fiiiiiiiiiired
Oooh yeah baaaby baaaay-beeeeee....
I
didn't realize this was such a typical reaction back when I first
started writing about interviewing, way back at other companies.
Boy-o-howdy did I find out in a hurry.
See, it goes like this:
Me: blah blah blah, I like asking question X in interviews, blah blah blah...
You: Question X? Oh man, I haven't heard about X since college! I've never needed it for my job! He asks that in interviews?
But that means someone out there thinks it's important to know, and,
and... I don't know it! If they detect my ignorance, not only will I be
summarily fired for incompetence without so much as a thank-you, I will
also be unemployable by people who ask question X! If people listen to
Stevey, that will be everyone! I will become homeless and destitute!
For not knowing something I've never needed before! This is horrible! I
would attack X itself, except that I do not want to pick up a book and
figure enough out about it to discredit it. Clearly I must yell a lot
about how stupid Stevey is so that nobody will listen to him!
Me: So in conclusion, blah blah... huh? Did you say "fired"? "Destitute?" What are you talking about?
You: Aaaaaaauuuggh!!! *stab* *stab* *stab*
Me: That's it. I'm never talking about interviewing again.
It doesn't matter what X is, either. It's arbitrary. I could say: "I really enjoy asking the candidate (their name)
in interviews", and people would still freak out, on account of
insecurity about either interviewing in general or their knowledge of
their own name, hopefully the former.
But THEN, time passes, and
interview candidates come and go, and we always wind up saying: "Gosh,
we sure wish that obviously smart person had prepared a little better
for his or her interviews. Is there any way we can help future
candidates out with some tips?"
And then nobody actually does anything, because we're all afraid of getting stabbed violently by People Who Don't Know X.
I
considered giving out a set of tips in which I actually use variable
names like X, rather than real subjects, but decided that in the
resultant vacuum, everyone would get upset. Otherwise that approach seemed pretty good, as long as I published under a pseudonym.
In
the end, people really need the tips, regardless of how many feelings
get hurt along the way. So rather than skirt around the issues, I'm
going to give you a few mandatory substitutions for X along with a fair
amount of general interview-prep information.
Caveats and Disclaimers
This
blog is not endorsed by Google. Google doesn't know I'm publishing
these tips. It's just between you and me, OK? Don't tell them I prepped
you. Just go kick ass on your interviews and we'll be square.
I'm only talking about general software engineering positions, and interviews for those positions.
These
tips are actually generic; there's nothing specific to Google vs. any
other software company. I could have been writing these tips about my
first software job 20 years ago. That implies that these tips are also
timeless, at least for the span of our careers.
These tips
obviously won't get you a job on their own. My hope is that by
following them you will perform your very best during the interviews.
Oh, and um, why Google?
Oho! Why Google, you ask? Well let's just have that dialog right up front, shall we?
You: Should I work at Google? Is it all they say it is, and more? Will I be serenely happy there? Should I apply immediately?
Me: Yes.
You: To which ques... wait, what do you mean by "Yes?" I didn't even say who I am!
Me: Dude, the answer is Yes. (You may be a woman, but I'm still calling you Dude.)
You:
But... but... I am paralyzed by inertia! And I feel a certain comfort
level at my current company, or at least I have become relatively
inured to the discomfort. I know people here and nobody at Google! I
would have to learn Google's build system and technology and stuff! I
have no credibility, no reputation there – I would have to start over
virtually from scratch! I waited too long, there's no upside! I'm
afraaaaaaid!
Me: DUDE. The answer is Yes already, OK? It's an invariant. Everyone else who came to Google was in the exact same position
as you are, modulo a handful of famous people with beards that put
Gandalf's to shame, but they're a very tiny minority. Everyone who
applied had the same reasons for not applying as you do. And everyone here says: "GOSH, I SURE AM HAPPY I CAME HERE!" So just apply already. But prep first.
You:
But what if I get a mistrial? I might be smart and qualified, but for
some random reason I may do poorly in the interviews and not get an
offer! That would be a huge blow to my ego! I would rather pass up the
opportunity altogether than have a chance of failure!
Me:
Yeah, that's at least partly true. Heck, I kinda didn't make it in on
my first attempt, but I begged like a street dog until they gave me a
second round of interviews. I caught them in a weak moment. And the
second time around, I prepared, and did much better.
The thing
is, Google has a well-known false negative rate, which means we
sometimes turn away qualified people, because that's considered better
than sometimes hiring unqualified people. This is actually an
industry-wide thing, but the dial gets turned differently at different
companies. At Google the false-negative rate is pretty high. I don't
know what it is, but I do know a lot of smart, qualified people who've
not made it through our interviews. It's a bummer.
But the really important takeaway is this: if you don't get an offer, you may still be qualified to work here. So it needn't be a blow to your ego at all!
As
far as anyone I know can tell, false negatives are completely random,
and are unrelated to your skills or qualifications. They can happen
from a variety of factors, including but not limited to:
you're having an off day
one or more of your interviewers is having an off day
there were communication issues invisible to you and/or one or more of the interviewers
you got unlucky and got an Interview Anti-Loop
Oh no, not the Interview Anti-Loop!
Yes, I'm afraid you have to worry about this.
What
is it, you ask? Well, back when I was at Amazon, we did (and they
undoubtedly still do) a LOT of soul-searching about this exact problem.
We eventually concluded that every single employee E at Amazon has at
least one "Interview Anti-Loop": a set of other employees S who would
not hire E. The root cause is important for you to understand when
you're going into interviews, so I'll tell you a little about what I've
found over the years.
First, you can't tell interviewers what's
important. Not at any company. Not unless they're specifically asking
you for advice. You have a very narrow window of perhaps one year after
an engineer graduates from college to inculcate them in the art of
interviewing, after which the window closes and they believe they are a
"good interviewer" and they don't need to change their questions, their
question styles, their interviewing style, or their feedback style, ever again.
It's a problem. But I've had my hand bitten enough times that I just don't try anymore.
Second
problem: every "experienced" interviewer has a set of pet subjects and
possibly specific questions that he or she feels is an accurate gauge
of a candidate's abilities. The question sets for any two interviewers
can be widely different and even entirely non-overlapping.
A
classic example found everywhere is: Interviewer A always asks about
C++ trivia, filesystems, network protocols and discrete math.
Interviewer B always asks about Java trivia, design patterns, unit
testing, web frameworks, and software project management. For any given
candidate with both A and B on the interview loop, A and B are likely
to give very different votes. A and B would probably not even hire each
other, given a chance, but they both happened to go through interviewer
C, who asked them both about data structures, unix utilities, and
processes versus threads, and A and B both happened to squeak by.
That's
almost always what happens when you get an offer from a tech company.
You just happened to squeak by. Because of the inherently flawed nature
of the interviewing process, it's highly likely that someone
on the loop will be unimpressed with you, even if you are Alan Turing.
Especially if you're Alan Turing, in fact, since it means you obviously
don't know C++.
The bottom line is, if you go to an interview at any
software company, you should plan for the contingency that you might
get genuinely unlucky, and wind up with one or more people from your
Interview Anti-Loop on your interview loop. If this happens, you will
struggle, then be told that you were not a fit at this time, and then
you will feel bad. Just as long as you don't feel meta-bad, everything
is OK. You should feel good that you feel bad after this happens, because hey, it means you're human.
And
then you should wait 6-12 months and re-apply. That's pretty much the
best solution we (or anyone else I know of) could come up with for the
false-negative problem. We wipe the slate clean and start over again.
There are lots of people here who got in on their second or third
attempt, and they're kicking butt.
You can too.
OK, I feel better about potentially not getting hired
Good! So let's get on to those tips, then.
If you've been following along very
closely, you'll have realized that I'm interviewer D. Meaning that my
personal set of pet questions and topics is just my own, and it's no
better or worse than anyone else's. So I can't tell you what it is, no
matter how much I'd like to, because I'll offend interviewers A through
X who have slightly different working sets.
Instead, I want to
prep you for some general topics that I believe are shared by the
majority of tech interviewers at Google-like companies. Roughly
speaking, this means the company builds a lot of their own software and
does a lot of distributed computing. There are other tech-company
footprints, the opposite end of the spectrum being companies that
outsource everything to consultants and try to use as much third-party
software as possible. My tips will be useful only to the extent that
the company resembles Google.
So you might as well make it Google, eh?
First, let's talk about non-technical prep.
The Warm-Up
Nobody
goes into a boxing match cold. Lesson: you should bring your boxing
gloves to the interview. No, wait, sorry, I mean: warm up beforehand!
How do you warm up? Basically there is short-term and long-term warming up, and you should do both.
Long-term
warming up means: study and practice for a week or two before the
interview. You want your mind to be in the general "mode" of problem
solving on whiteboards. If you can do it on a whiteboard, every other
medium (laptop, shared network document, whatever) is a cakewalk. So
plan for the whiteboard.
Short-term warming up means: get lots
of rest the night before, and then do intense, fast-paced warm-ups the
morning of the interview.
The two best long-term warm-ups I know of are:
1) Study a data-structures and algorithms book.
Why? Because it is the most likely to help you beef up on problem
identification. Many interviewers are happy when you understand the
broad class of question they're asking without explanation. For
instance, if they ask you about coloring U.S. states in different
colors, you get major bonus points if you recognize it as a
graph-coloring problem, even if you don't actually remember exactly how
graph-coloring works.
And if you do remember how it works, then
you can probably whip through the answer pretty quickly. So your best
bet, interview-prep wise, is to practice the art of recognizing that
certain problem classes are best solved with certain algorithms and
data structures.
My absolute favorite for this kind of interview preparation is Steven Skiena's The Algorithm Design Manual.
More than any other book it helped me understand just how astonishingly
commonplace (and important) graph problems are – they should be part of
every working programmer's toolkit. The book also covers basic data
structures and sorting algorithms, which is a nice bonus. But the gold
mine is the second half of the book, which is a sort of encyclopedia of
1-pagers on zillions of useful problems and various ways to solve them,
without too much detail. Almost every 1-pager has a simple picture,
making it easy to remember. This is a great way to learn how to
identify hundreds of problem types.
Other interviewers I know recommend Introduction to Algorithms.
It's a true classic and an invaluable resource, but it will probably
take you more than 2 weeks to get through it. But if you want to come
into your interviews prepped, then consider deferring your application until you've made your way through that book.
2) Have a friend interview you.
The friend should ask you a random interview question, and you should
go write it on the board. You should keep going until it is complete,
no matter how tired or lazy you feel. Do this as much as you can
possibly tolerate.
I didn't do these two types of preparation
before my first Google interview, and I was absolutely shocked at how
bad at whiteboard coding I had become since I had last interviewed
seven years prior. It's hard! And I also had forgotten a bunch of
algorithms and data structures that I used to know, or at least had
heard of.
Going through these exercises for a week prepped me
mightily for my second round of Google interviews, and I did way, way
better. It made all the difference.
As for short-term
preparation, all you can really do is make sure you are as alert and
warmed up as possible. Don't go in cold. Solve a few problems and read
through your study books. Drink some coffee: it actually helps you
think faster, believe it or not. Make sure you spend at least
an hour practicing immediately before you walk into the interview.
Treat it like a sports game or a music recital, or heck, an exam: if
you go in warmed up you'll give your best performance.
Mental Prep
So!
You're a hotshot programmer with a long list of accomplishments. Time
to forget about all that and focus on interview survival.
You should go in humble, open-minded, and focused.
If
you come across as arrogant, then people will question whether they
want to work with you. The best way to appear arrogant is to question
the validity of the interviewer's question – it really ticks them off,
as I pointed out earlier on. Remember how I said you can't tell an
interviewer how to interview? Well, that's especially true if you're a candidate.
So
don't ask: "gosh, are algorithms really all that important? do you ever
need to do that kind of thing in real life? I've never had to do that
kind of stuff." You'll just get rejected, so don't say that kind of
thing. Treat every question as legitimate, even if you are frustrated
that you don't know the answer.
Feel free to ask for help or
hints if you're stuck. Some interviewers take points off for that, but
occasionally it will get you past some hurdle and give you a good
performance on what would have otherwise been a horrible stony
half-hour silence.
Don't say "choo choo choo" when you're "thinking".
Don't
try to change the subject and answer a different question. Don't try to
divert the interviewer from asking you a question by telling war
stories. Don't try to bluff your interviewer. You should focus on each problem they're giving you and make your best effort to answer it fully.
Some interviewers will not ask you to write code, but they will expect
you to start writing code on the whiteboard at some point during your
answer. They will give you hints but won't necessarily come right out
and say: "I want you to write some code on the board now." If in doubt,
you should ask them if they would like to see code.
Interviewers
have vastly different expectations about code. I personally don't care
about syntax (unless you write something that could obviously never
work in any programming language, at which point I will dive in and
verify that you are not, in fact, a circus clown and that it was an
honest mistake). But some interviewers are really picky about syntax,
and some will even silently mark you down for missing a semicolon or a
curly brace, without telling you. I think of these
interviewers as – well, it's a technical term that rhymes with "bass
soles", but they think of themselves as brilliant technical evaluators,
and there's no way to tell them otherwise.
So ask. Ask if they
care about syntax, and if they do, try to get it right. Look over your
code carefully from different angles and distances. Pretend it's
someone else's code and you're tasked with finding bugs in it. You'd be
amazed at what you can miss when you're standing 2 feet from a
whiteboard with an interviewer staring at your shoulder blades.
It's
OK (and highly encouraged) to ask a few clarifying questions, and
occasionally verify with the interviewer that you're on the track they
want you to be on. Some interviewers will mark you down if you just
jump up and start coding, even if you get the code right.
They'll say you didn't think carefully first, and you're one of those
"let's not do any design" type cowboys. So even if you think you know
the answer to the problem, ask some questions and talk about the
approach you'll take a little before diving in.
On the flip
side, don't take too long before actually solving the problem, or some
interviewers will give you a delay-of-game penalty. Try to move (and
write) quickly, since often interviewers want to get through more than
one question during the interview, and if you solve the first one too
slowly then they'll be out of time. They'll mark you down because they
couldn't get a full picture of your skills. The benefit of the doubt is
rarely given in interviewing.
One last non-technical tip: bring
your own whiteboard dry-erase markers. They sell pencil-thin ones at
office supply stores, whereas most companies (including Google) tend to
stock the fat kind. The thin ones turn your whiteboard from a 480i
standard-definition tube into a 58-inch 1080p HD plasma screen. You
need all the help you can get, and free whiteboard space is a real
blessing.
You should also practice whiteboard space-management
skills, such as not starting on the right and coding down into the
lower-right corner in Teeny Unreadable Font. Your interviewer will not
be impressed. Amusingly, although it always irks me when people do
this, I did it during my interviews, too. Just be aware of it!
Oh,
and don't let the marker dry out while you're standing there waving it.
I'm tellin' ya: you want minimal distractions during the interview, and
that one is surprisingly common.
OK, that should be good for non-tech tips. On to X, for some value of X! Don't stab me!
Tech Prep Tips
The
best tip is: go get a computer science degree. The more computer
science you have, the better. You don't have to have a CS degree, but
it helps. It doesn't have to be an advanced degree, but that helps too.
However,
you're probably thinking of applying to Google a little sooner than 2
to 8 years from now, so here are some shorter-term tips for you.
Algorithm Complexity:
you need to know Big-O. It's a must. If you struggle with basic big-O
complexity analysis, then you are almost guaranteed not to get hired.
It's, like, one chapter in the beginning of one theory of computation
book, so just go read it. You can do it.
Sorting: know
how to sort. Don't do bubble-sort. You should know the details of at
least one n*log(n) sorting algorithm, preferably two (say, quicksort
and merge sort). Merge sort can be highly useful in situations where
quicksort is impractical, so take a look at it.
For God's sake, don't try sorting a linked list during the interview.
Hashtables: hashtables are arguably the single most important data structure known to mankind. You absolutely have to know how they work.
Again, it's like one chapter in one data structures book, so just go
read about them. You should be able to implement one using only arrays
in your favorite language, in about the space of one interview.
Trees:
you should know about trees. I'm tellin' ya: this is basic stuff, and
it's embarrassing to bring it up, but some of you out there don't know
basic tree construction, traversal and manipulation algorithms. You
should be familiar with binary trees, n-ary trees, and trie-trees at
the very very least. Trees are probably the best source of practice problems for your long-term warmup exercises.
You
should be familiar with at least one flavor of balanced binary tree,
whether it's a red/black tree, a splay tree or an AVL tree. You should
actually know how it's implemented.
You should know about tree traversal algorithms: BFS and DFS, and know the difference between inorder, postorder and preorder.
You
might not use trees much day-to-day, but if so, it's because you're
avoiding tree problems. You won't need to do that anymore once you know
how they work. Study up!
Graphs
Graphs are, like, really really important. More than you think. Even if you already think they're important, it's probably more than you think.
There
are three basic ways to represent a graph in memory (objects and
pointers, matrix, and adjacency list), and you should familiarize
yourself with each representation and its pros and cons.
You
should know the basic graph traversal algorithms: breadth-first search
and depth-first search. You should know their computational complexity,
their tradeoffs, and how to implement them in real code.
You
should try to study up on fancier algorithms, such as Dijkstra and A*,
if you get a chance. They're really great for just about anything, from
game programming to distributed computing to you name it. You should
know them.
Whenever someone gives you a problem, think graphs.
They are the most fundamental and flexible way of representing any kind
of a relationship, so it's about a 50-50 shot that any interesting
design problem has a graph involved in it. Make absolutely sure you
can't think of a way to solve it using graphs before moving on to other
solution types. This tip is important!
Other data structures
You
should study up on as many other data structures and algorithms as you
can fit in that big noggin of yours. You should especially know about
the most famous classes of NP-complete problems, such as traveling
salesman and the knapsack problem, and be able to recognize them when
an interviewer asks you them in disguise.
You should find out what NP-complete means.
Basically, hit that data structures book hard, and try to retain as much of it as you can, and you can't go wrong.
Math
Some
interviewers ask basic discrete math questions. This is more prevalent
at Google than at other places I've been, and I consider it a Good
Thing, even though I'm not particularly good at discrete math. We're
surrounded by counting problems, probability problems, and other
Discrete Math 101 situations, and those innumerate among us blithely
hack around them without knowing what we're doing.
Don't get mad
if the interviewer asks math questions. Do your best. Your best will be
a heck of a lot better if you spend some time before the interview
refreshing your memory on (or teaching yourself) the essentials of
combinatorics and probability. You should be familiar with n-choose-k
problems and their ilk – the more the better.
I know, I know,
you're short on time. But this tip can really help make the difference
between a "we're not sure" and a "let's hire her". And it's actually
not all that bad – discrete math doesn't use much of the high-school
math you studied and forgot. It starts back with elementary-school math
and builds up from there, so you can probably pick up what you need for
interviews in a couple of days of intense study.
Sadly, I don't have a good recommendation for a Discrete Math book, so if you do, please mention it in the comments. Thanks.
Operating Systems
This
is just a plug, from me, for you to know about processes, threads and
concurrency issues. A lot of interviewers ask about that stuff, and
it's pretty fundamental, so you should know it. Know about locks and
mutexes and semaphores and monitors and how they work. Know about
deadlock and livelock and how to avoid them. Know what resources a
processes needs, and a thread needs, and how context switching works,
and how it's initiated by the operating system and underlying hardware.
Know a little about scheduling. The world is rapidly moving towards
multi-core, and you'll be a dinosaur in a real hurry if you don't
understand the fundamentals of "modern" (which is to say, "kinda
broken") concurrency constructs.
The best, most practical book I've ever personally read on the subject is Doug Lea's Concurrent Programming in Java.
It got me the most bang per page. There are obviously lots of other
books on concurrency. I'd avoid the academic ones and focus on the
practical stuff, since it's most likely to get asked in interviews.
Coding
You should know at least one programming language really well, and it should preferably
be C++ or Java. C# is OK too, since it's pretty similar to Java. You
will be expected to write some code in at least some of your
interviews. You will be expected to know a fair amount of detail about
your favorite programming language.
Other Stuff
Because
of the rules I outlined above, it's still possible that you'll get
Interviewer A, and none of the stuff you've studied from these tips
will be directly useful (except being warmed up.) If so, just do your
best. Worst case, you can always come back in 6-12 months, right? Might
seem like a long time, but I assure you it will go by in a flash.
The
stuff I've covered is actually mostly red-flags: stuff that really
worries people if you don't know it. The discrete math is potentially
optional, but somewhat risky if you don't know the first thing about
it. Everything else I've mentioned you should know cold, and then
you'll at least be prepped for the baseline interview level. It could
be a lot harder than that, depending on the interviewer, or it could be
easy.
It just depends on how lucky you are. Are you feeling lucky? Then give it a try!
Send me your resume
I'll
probably batch up any resume submissions people send me and submit them
weekly. In the meantime, study up! You have a lot of warming up to do.
Real-world work makes you rusty.
I hope this was helpful. Let the flames begin, etc. Yawn.
Original story
Tags: algorithm, lessons learned, |
Posted by Admin on
10/14/2007 3:10 PM |
Comments (2)

A
couple years ago, there were some HR trolls or maybe some some resume
bots that figured out that I went to MIT and that I was a software
engineer from my blog (yes, this one). A recruiter from Google emailed
me asking me whether I'd be interested in a position at Google. Um yes,
isn't that every software developer's dream? That initial contact
didn't amount to anything as there was no local office, but they called
again recently when an office opened in Cambridge, MA. My initial phone
interviews went great where I kibitzed with the HR recruiter. But they
sniffed me out as a faker during the technical phone interview. It's
not that I don't know how to program, but having no formal education
(let's just say MIT's first programming class 6.001 made me swear never
to be a SW engineer), I sometimes leave some of the nitty gritty
technical details to magic. Since the software application I'm
currently developing for work looks great and works beautifully, this
is all I need! I have Google for the rest.
I had heard many
about many interesting recruiting techniques that Google uses to get
the best and the brightest. One of them is the billboard for Solve the Equation, Get an Interview.
Yup, way over my head too. Another is the Google Labs Aptitude Test
which is a half-serious spoof with questions like "In your opinion,
what is the most beautiful math equation ever derived?" Geek alert!
Most
of my technical interview went pretty well as we got along fabulously.
The coding sample wasn't too bad, although I was not extremely creative
with my answer (reverse the order of the elements of a array in place).
Luckily, I dodged questions about pointers since I've only done C# in
the last two years and feigned forgetfulness (nothing the feign there,
it was never my strong suit). But then I got tougher questions like how
would you design a smart pointer interface. Yikes! She seemed happy
with my answer, although she corrected me in that the interface must
track the number of instances (seems obvious after the fact). I was
encouraged when she asked if I could go extra time beyond our allotted
hour. The she asked how I would design an assertion class, to which I
responded that I use exceptions and not assertions in .NET. I think
that was the WRONG answer. I could hear the BZZT! buzzer going off in
her head.
Since we got along so well, near the end of the
interview I confided in her that I have had really tough technical
interviews in the past such as with SolidWorks,
where they asked questions about vector geometry as well as
programming. She responded that at Google, they need people able to
solve those kinds problems as well. Oops (reminder to self, never be so
chatty and self-deprecating during interviews in an attempt to be
funny). Suddenly the interview was rushing to a close and I knew I had
flunked. Needless to say, I received the email with "After carefully
reviewing your experience and qualifications, we have determined that
there is not a fit for a position," a few days later. I kicked myself
for weeks afterwards on some of my answers during the interview.
The
one thing that I did get out of this experience was a glimpse into the
life of a Google employee. I had been fascinated by their culture (and
gourmet meals) ever since seeing the Time magazine photo essay Life in the Googleplex.
My interviewer was a woman who has worked at the Google headquarters in
Mountain View, CA for 18 months and previously worked at AOL in
Virginia. She was a technical leader and seemed quite ambitious. She
lived very close to the office and worked long hours although not
everyone is expected to (obviously no kids). The group sizes at Google
are small, around 2-3 people, and the reporting structure is very flat.
They use Agile, Extreme, Scrum and/or Test-driven processes depending
on the group's preference. They test their own programs against the
Google framework, which is like NUnit, and release products whenever
they are ready. It sounded like a really cool, flexible environment,
but I'm not sure how this old fogey would stand up to all the young
whipper snappers who can name the first 10 digit prime found in
consecutive digits of e.