## Some experiences in job hunting for software engineer

Some experiences in job hunting for software engineer

I will present my understanding of job hunting in this short article. I think there are two parts that are both important in job hunting: technique part and non technique part. In the technique part, I mean questions answering, white board coding. In the non technique part, I mean your preparation of resume, communication with friends to get interview opportunities, and interaction with interviewers. I will focus on the technique part. In fact I don’t think I did well in the non technique part.

victorfang.com

In the technique part, you have to prepare for interview questions. It is extremely different for big companies and small companies. For the big companies, the questions are stereotyped. According to my understanding, everyone who prepares for some time should be able to success in one of the following companies: amazon, google, microsoft, facebook, bloomberg. Usually all these companies will ask algorithm questions and coding on whiteboard. But the exact questions that would be asked largely depends on the interviewers.

Personally I think the difficulty of the algorithm questions would be google = facebook > amazon = microsoft > bloomberg. You need to know C++/STL or Java/Containers since most white board coding will use them. It is also less error prone if you used containers. For example, you need to create an array in C++ and initialize it to all 0. Instead of writing new int[] and then initialize in a loop, just vector v(100,0) will do the work. You save 2 lines.

You are expected to know basic language concepts, object oriented programming definitions and os definitions. On the other hand, if you say you specialize in database or networking, then they will ask the related questions. It is very possible that they will find a guy holding Ph.D. in the same area to ask you questions. Thus you must be familiar with your research. For example, one Cisco question: what would happen after you typed the URL in the browser? Explain all the steps and details that you know. If you interview for Cisco, you need to know OS, networking very well.

Google and Facebook are more mysterious because they did not allow ppl to post the problems online. Thus people did not know what exactly the questions are. In fact, you can find similar questions in the problems collections of amazon and microsoft. Algorithm questions of bloomberg are very simple. For all these companies, algorithms related to trees, sorting, hashing are their favorite. In the following I will list some special things about each company.

1. Amazon. It is very likely that they will ask design questions (how to design a parking lot, how to design a zoo). Unfortunately there is no precise answers online. I guess they want to see you use some design patterns. They also ask some pattern matching questions (find all phone numbers from files in the directory). You should have some knowledge of regular expression.

victorfang.com

2. Google questions focus on algorithms. They keep pushing you to save space, time, or sacrifice space for time and vice versa. Thus you should always put the trade off in you mind. (Simple one, when to use hash, and when to use binary search tree?) The other thing is google will ask large scale processing questions. For example, given 1 billion urls, 1M memory, remove duplicates. Thus you need to be familiar with: map-reduce, hashing. There are some hashing concepts in Database that is useful. It is like two steps hashing. I forgot the name. There is also one useful article about large scale problems on jobhunting board which mentions some basic techniques including Bloom filters. Bit manipulations are also asked frequently. Check this link for it: http://graphics.stanford.edu/~seander/bithacks.html

3. Microsoft. There are a lot of questions online. Note that they always ask behavior questions. For behavior questions, there is some instructions on jobhunting board. Basically you create a situation, and show them how you solved the questions under such situations. You are always the hero saving the world as in the Hollywood movies. (Personally I think these questions are stupid! But ms always ask them :< The good thing about google is the rarely ask behavior questions.)

4. Facebook. You can solve some puzzles online to get phone interview opportunites. Note that some questions are NPC : a[j], i < j. Count the number of reverse. (merge sort)

9. Given a sorted array, answer query "is x in A?" If yes, return the interval that contains x.

10. Given a sorted array, cycliclely shift it right. Answer query "is x in A"? For example, 1 2 3 4 5, shifted 2 positions and we have 4 5 1 2 3. (How to do the shifting? There are three algorithms mentioned in Pearls.) Note what will happen if there a lot of equal elements in the array.

11. Given an array containing positive and negative numbers, put negative in left side and positive in right side while keeping original order, i.e, if 3 is before 2 in original array, then 3 is still before 2 in updated array. (D&C)

12. Use two stacks to simulate a queue.

13. Design a stack that can do basic stack operation and also answer query: the largest element of the stack, in const time. (Add extra information to the stack.) Design a queue that can answer the preceding query. (Use 2 stacks designed above.)

14. Given x, output the number of appearances of 1's from 1 to x. (What is the relation between i-digit number and i+1 digit number? Do it recursively.)

15. Given a stream of different integers coming one at a time, when I say stop, output one of them that each of the numbers appeared before has equal prob of being chosen. (Reservoir algorithm).

16. Given a binary tree, change it to a Dlink list. (DSW algorithm)

17. Find a pattern from a string. (KMP algorithm)

18. Lowest common ancester and range minimus query.

The best reference would be Eric Demaine's lecture notes: http://courses.csail.mit.edu/6.897/spring03/scribe_notes/L11/lecture11.pdf

topcoder notes: http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor

19. BST (binary search tree) with augumented data structures.

20. Generate all permutations of a set of numbers, recursively (how to save space?), nonrecursively (check the source code of STL next_permuation). Extensions: generate all the subsets of {1,2,…,n} in (any) alphabetical order, all 3-subset in (any) alphabetical order.

21. Memory management, i.e, write your own malloc function. victor fang.com

There are several algorithms which are explained in Knuth's bible. However, you can also find reference in: the last chapter of "The c programming language" http://www.amazon.com/Programming-Language-2nd-Brian-Kernighan/dp/0131103628, which use link list

There is another algorithm mentioned in: http://www.amazon.com/Computer-Systems-Programmers-Perspective-Introduction/dp/0582832411/ref=sr_1_2?ie=UTF8&s=books&qid=1273956233&sr=8-2

22. Suffix tree and complex pattern matching. (There is no need to know exactly how suffix tree is constructed. Just need to have an idea that they can be used to solve many problems.) Many applications of it are mentioned in: http://www.amazon.com/dp/0521585198

That is advanced algorithms and are rarely asked.

23. Coin change. (DP related questions.) It is frequently asked. It seems that DP may not always be asked but you still need to prepare for it. The following link is very good: http://people.csail.mit.edu/bdean/6.046/dp/

24. (Probability questions.) Use a fair coin to simulate an unfair coin. (Binary representation.) Use an unfair coin to simulate a fair coin. (von neumann trick)

25. Mergesort, recursive and bottom up. (Clearly explained in Sedgewick's book) Given array A and B that are both sorted, merge them to A. Suppose A has enough space in the back.

26. Quicksort. Why do we use insertion sort when the size reduce to small? (20 in stl) When should we use O(n^2) time algorithm rather than O(nlgn) time algorithm? (space constraint and the constant before big O) How to choose the partition algorithm? (rand takes 3 and then use the median)

27. Linear selection, i.e, get the i-th largest element in linear time. It is used as a subroutine to solve other problems. For example, given an array where a element has appeared more than n/2 times, find it in linear time. (Any other algorithm?) Given an array of ints, find k of them that is closest to the median.

28. Suppose we use an int array to represent the 800*600 screen where each pixel corresponds to 1 bit (on or off), write code to turn a line segment on. (Pearls, chapter 1)

29. Given a rectangle, starting from the left corner and visiting all elements in spiral order. Write the code to generate the sequence. (There is a mathematical relation between the original order and the spiral order, i.e, (i,j) is the k-th element in the spiral order where i, j, k satisfy certain conditions.)

30. Write your own garbage collector. (The art of c++)

31. Counting sort.

32. Given a rooted binary tree where each edge has a weight, find a path with maximal weight.

33. Given two string, find the edit distance. (DP) Given two set of ints, can we find a subset with sum x? (Note the ints may be negative.)

34. Given an array, find the longest increasing sequence. (Use patience sort which is easy to remember.) victor fang.com

35. Given 4*10^9 integers represented by 32 bits, find a missing one. (Pearls, chap 1)

36. Hash function. (There is one realization of Hash function in last chapter of Pearls. Basically you will use chain hashing.)

Is there any recommendation of algorithm books?

Two books that you must read through: Programming interview exposed.

This book is easy and you can finish reading it in two weeks.

Programming pearls.

This book is very elegant and contain a lot of frequently asked questions. Note that all exercises need to be mastered. There are around 100 problems in the book. Personally I think you can pass phone interviews if you really understand the book.

There are also other books people like:

R. Sedgewick http://www.amazon.com/Algorithms-Parts-1-4-Fundamentals-Structure/dp/0201350882

The good thing about this book is they have versions in c, cpp, java.

Drozdek http://www.amazon.com/Data-Structures-Algorithms-Adam-Drozdek/dp/0534491820/ref=sr_1_1?ie=UTF8&s=books&qid=1273890524&sr=1-1

The author presents severl algorithms that are rarely seen elsewhere: DSW algorithm, nonrecursively inorder (postorder, preorder) traversal.

careercup also edited two small books. One is 150 interview questions with answers (some answers are not complete or not optimal), the other one is about google which is pretty useful for google interview.

Bianchengzhimei

That is a book written in Chinese and has some interesting problems.

Introduction to algorithms by CLRS

A lot of questions are from this book. Or the ideas can be found in this book. The chapters on sorting, binary search tree, heap, hashing, augmented BST are worth reading (not complete). The problem is: the book is huge. My suggestion is tackle Pearls first, and try to read this book when you have time.

How about other directions in interview?

In the preceding part, I focused on algorithm questions. In fact I am not so sure about other directions. But anyway, for Java, C++, OS, networks, database, you have to memorize the concepts and spend time reading the material.

Any quick ways for improvement?

Frankly speaking, it is difficult to get all questions in a short time for normal ppl. Thus you have to start early. The good thing about algorithm questions is: you don't need to remember anything if you know how to do it. If you really understand it, it is hard to forget. The bad thing is algorithm questions are too tricky and if you did not see them before, you may not figure them out in a short time. But note that during the interview, you can ask interviewer questions and he will give you hint. Thus communication skills are important. I strongly suggest you write notes for the questions in your own words without referring to book. Usually it would be very effective to talk with others and share the idea.

Where can I find answers for a question?

google, friends, and jobhunting board. Turn to others when you get stuck. Sure you need to think it for some time before hand. victorfang.com

Is not this a waste of life to study the stupid algorithm questions that you will never meet during work?

Yes, I agree it is stupid. But it is not decided by you. Several years ago, a cse phd may easily find a job after one month preparation. But it is not the case now. Especially Chinese students are not good at showing off while In…

Other information that I think useful:

1. job website: indeed, monster, dice, linkedin, phds.org You can post your resume there and recruiters will contact you.

2. question collections: careercup, spellscroll (there are many interesting questions in this website without solutions)

3. general questions including H1B, opt, interview questions: jobhunting board at mitbbs.com. This is a Chinese website and contain many useful information. Bad thing is the contents are not well organized. The good thing is you can find answers for nearly all questions, meet new friends who are on the same boat, share job hunting information.

4. internal refer is more useful than submitting resume blindly.

5. It is better to have interview on campus. Bloomberg comes twice a year, ms at least once a year. And intern opportunity at big companies would be very helpful.

6. Share your interview experiences with others. Sometimes you thought you got the solution, but it may not be optimal or complete.

7. Try to get all the interview details of one onsite. In this way, you can figure out what the company wants. That's why I think the careercup book for google is very good. It contains all questions of several onsite interviews.

8. If your English is not good, do not talk too much. Try to hit the target whenever you open your mouth.

9. To present your ideas clearly: draw graphs, mention first what you are doing and what you are going to do and why you do it, practice with friends for some mock interviews so that you can find problems early. victorfang.com

10. Form a learning group. It always takes more time to read by yourself than listen to other's explanations.

11. Websites for book downloading: ebookee, and csdn. csdn is a Chinese website that contains nearlly all books you want. You can also buy books from dangdang while use your credit cards in America for payments. Note it may take 2 month for shipping.

12. The university has services for resume checking. Pay some attention to Indian students. They are usally good at English and you can also get some useful information from them.

For the non technique part, I do not have much to say but refer you to some books:

acing the interview

victorfang.com

cover letter magic

resume magic resume for dummies

101 dynamic answers to interview questions

nail the job interviewer

how would you move the mountain fuji