Matt Pavelle

Software Development Interview Questions

Below is a compilation of some of the best software developer interview questions I've heard about, discovered, or written and used. Many can be attributed to the famous Microsoft and Google interview processes. Others are basic programming tasks, logic questions, and riddles. If you're stumped and can't find an answer on the web, feel free to contact me.

Basic Computer Science Knowledge

  1. Write an algorithm for integer multiplication.
  2. Merge two sorted linked lists.
  3. Given a set of intervals (time in seconds) find the set of intervals that overlap.
  4. If we had a list of n nodes, what are the maximum number of edges there can be for a directed acyclic graph?
  5. Remove duplicate lines from a large text.
  6. Given a string, find the minimum window containing a given set of characters.
  7. Write a program to compute if one string is a rotation of another.
  8. How many balloons would be required to fill the streets of Manhattan to a depth of 10 meters?
  9. What is the sticky bit and why is it used?
  10. Start with a randomized array of 100 integers from 1 to 100. One integer is randomly removed. Find that integer.
  11. How does a hashtable work?

Algorithmic Questions

  1. Describe advantages and disadvantages of the various stock sorting algorithms.
  2. Give me an algorithm to shuffle a deck of cards, given that the cards are stored in an array of ints.
  3. Given that you are receiving samples from an instrument at a constant rate, and you have constant storage space, how would you design a storage algorithm that would allow me to get a representative readout of data, no matter when I looked at it? In other words, representative of the behavior of the system to date.
  4. How would you find a loop or cycle in a linked list?
  5. How would you print out the data in a binary tree, level by level, starting at the top?
  6. How would you write quicksort? What about a multi-pivot quicksort?
  7. Imagine this scenario: I/O completion ports are communications ports which take handles to files, sockets, or any other I/O. When a Read or Write is submitted to them, they cache the data (if necessary), and attempt to take the request to completion. Upon error or completion, they call a user-supplied function to let the users application know that that particular request has completed. They work asynchronously, and can process an unlimited number of simultaneous requests. Design the implementation and thread models for I/O completion ports. Remember to take into account multi-processor machines.
  8. Implement a linked list. Why did you pick the method you did?
  9. Implement an algorithm that takes two strings as input, and returns the intersection of the two, with each letter represented at most once. Now speed it up. Now test it.
  10. Implement an algorithm to do wild card string matching.
  11. Implement an algorithm to insert a node into a circular linked list without traversing it.
  12. Implement an algorithm to print out all files below a given root node.
  13. Implement an algorithm to reverse a linked list. Now do it without recursion.
  14. Implement an algorithm to sort a linked list. Why did you pick the method you did? Now do it in O(n) time.
  15. Implement an algorithm to sort an array. Why did you pick the method you did?
  16. Implement an algorithm to take an array and return one with only unique elements in it.
  17. Implement malloc.
  18. Implement strstr() (or some other string library function).
  19. Multiple by 8 without using multiplication or addition. Now do the same with 7.
  20. Reverse a string. Optimize for speed. Optimize for space.
  21. Reverse the words in a sentence, i.e. "My name is Chris" becomes "Chris is name My." Optimize for speed. Optimize for space.
  22. Suppose you have an array of 1001 integers. The integers are in random order, but you know each of the integers is between 1 and 1000 (inclusive). In addition, each number appears only once in the array, except for one number, which occurs twice. Assume that you can access each element of the array only once. Describe an algorithm to find the repeated number. If you used auxiliary storage in your algorithm, can you find an algorithm that does not require it?
  23. The asm block: "asm cwd xor ax, dx asm sub ax, dx" performs a common math function, what is it?
  24. What's the difference between a linked list and an array?
  25. Write an algorithm to add numbers in base n (not any common ones like 2, 8, 10, or 16). Now add numbers in base -n.
  26. Write an algorithm to compare two strings using O(n) time with constant space.
  27. Write an algorithm to count the number of set bits in a number. Now optimize for speed. Now optimize for size.
  28. Write an algorithm to find a substring. Optimize it for speed. Optimize it for space.
  29. 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.
  30. Write a function to copy two strings, A and B. The last few bytes of string A overlap the first few bytes of string B.
  31. Write a function to print all of the permutations of a string.
  32. Write a function to print the Fibonacci numbers.
  33. Write routines to manage a heap using an existing array.
  34. Write routines to read and write a bounded buffer.

Application Questions

  1. Define a user interface for indenting selected text in a document. Consider selections ranging from a single sentence up through selections of several pages. Consider selections not currently visible or only partially visible. What are the states of the new UI controls? How will the user know what the controls are for and when to use them?
  2. How can computer technology be integrated in an elevator system for a hundred story office building? How do you optimize for availability? How would variation of traffic over a typical work week or floor or time of day affect this?
  3. How would you build an alarm clock for deaf people?
  4. How would you design a coffee machine for an automobile.
  5. How would you go about building a keyboard for 1 handed users?
  6. How would you implement copy protection on a control which can be embedded in a document and duplicated readily via the Internet?
  7. How would you redesign an ATM?
  8. Suppose we wanted to run a microwave oven from the computer. What kind of software would you write to do this?
  9. What is the difference between a MAC address and an IP address?

Logic Questions / Riddles

  1. How many cars are there in the USA?
  2. How many gas stations are there in the USA?
  3. How many manhole covers are there in the USA?
  4. If you had an infinite supply of water and a 5 quart and 3 quart pail, how would you measure exactly 4 quarts?
  5. If you have two buckets, one with red paint and the other with blue paint, and you take one cup from the blue bucket and poor it into the red bucket. Then you take one cup from the red bucket and poor it into the blue bucket. Which bucket has the highest ratio between red and blue? Prove it mathematically.
  6. Imagine a disk spinning like a record player turn table. Half of the disk is black and the other is white. Assume you have an unlimited number of color sensors. How many sensors would you have to place around the disk to determine the direction the disk is spinning? Where would they be placed?
  7. Imagine an analog clock set to 12 o'clock. Note that the hour and minute hands overlap. How many times each day do both the hour and minute hands overlap? How would you determine the exact times of the day that this occurs?
  8. Imagine you are standing in front of a mirror, facing it. Raise your left hand. Raise your right hand. Look at your reflection. When you raise your left hand your reflection raises what appears to be his right hand. But when you tilt your head up, your reflection does too, and does not appear to tilt his/her head down. Why is it that the mirror appears to reverse left and right, but not up and down?
  9. One train leaves Los Angeles at 15mph heading for New York. Another train leaves from New York at 20mph heading for Los Angeles on the same track. If a bird, flying at 25mph, leaves from Los Angeles at the same time as the train and flies back and forth between the two trains until they collide, how far will the bird have traveled?
  10. Pairs of primes separated by a single number are called prime pairs. Examples are 17 and 19. Prove that the number between a prime pair is always divisible by 6 (assuming both numbers in the pair are greater than 6). Now prove that there are no 'prime triples.'
  11. Suppose you had 8 billiard balls, and one of them was slightly heavier, but the only way to tell was by putting it on a scale against another. What's the fewest number of times you'd have to use the scale to find the heavier ball?
  12. The SF Chronicle has a word game where all the letters are scrambled up and you have to figure out what the word is. Imagine that a scrambled word is 5 characters long. How many possible solutions are there? What if we know which 5 letters are being used? Develop an algorithm to solve the word.
  13. There is a room with a closed door and three light bulbs. Outside the room there are three switches, connected to the bulbs. You may manipulate the switches as you wish, but once you open the door you can't change them. Identify each switch with its bulb.
  14. Why is a manhole cover round?
  15. You have 4 jars of pills. Each pill is a certain weight, except for contaminated pills contained in one jar, where each pill is weight + 1. How could you tell which jar had the contaminated pills in just one measurement?
  16. You have a bucket of jelly beans. Some are red, some are blue, and some green. With your eyes closed, pick out 2 of a like color. How many do you have to grab to be sure you have 2 of the same?
  17. You have two jars, 50 red marbles and 50 blue marbles. A jar will be picked at random, and then a marble will be picked from the jar. Placing all of the marbles in the jars, how can you maximize the chances of a red marble being picked? What are the exact odds of getting a red marble using your scheme?
  18. You've got someone working for you for seven days and a gold bar to pay them. The gold bar is segmented into seven connected pieces. You must give them a piece of gold at the end of every day. If you are only allowed to make two breaks in the gold bar, how do you pay your worker?

Thinkers

  1. Explain a scenario for testing a salt shaker.
  2. How are M&Ms made?
  3. How would you explain how to use a compiler to your grandma?
  4. If we told you we were willing to invest $5 million in a start up of your choice, what business would you start? Why?
  5. If you are going to receive an award in 5 years, what is it for and who is the audience?
  6. If you could gather all of the computer manufacturers in the world together into one room and then tell them one thing that they would be compelled to do, what would it be?
  7. If you had a clock with lots of moving mechanical parts, you took it apart piece by piece without keeping track of the method of how it was disassembled, then you put it back together and discovered that 3 important parts were not included; how would you go about reassembling the clock?
  8. If you had to learn a new computer language, how would you go about doing it?
  9. Interviewer hands you a black pen and says nothing but "This pen is red."
  10. Suppose you go home, enter your house or apartment, hit the light switch, and nothing happens - no light floods the room. What exactly, in order, are the steps you would take in determining what the problem was?
  11. What was the hardest question asked of you so far today?
  12. Why do you want to work here?
  13. Why is it that when you turn on the hot water in any hotel, for example, the hot water comes pouring out almost instantaneously?