recent software engineering interview questions

Hash Table

Write an implementation for a hash table in Java. You may use arrays and the built in int hashCode() method that returns the hash code for all Java objects.

This was a whiteboard question.

Multi-Threading

Write a standard producer / consumer thread implementation in Java. The producer produces integers and sticks them in a queue. The consumer processes integers, one at a time. The consumer should not try and process an empty integer (e.g. it needs to wait until there is something in the queue to consume). You should use the Java 1.5 concurrency package. You should not use the sleep, wait or notify methods.

This was a program-on-the-spot in an IDE question

Design Patterns

Suppose you have a web form that allows users to upload JPG, GIF or PNG images. Before you store the images in your system, you want to convert them all to the JPG format. Design an image converter API. Sketch out all classes and interfaces that are involved. (Note, the actual code necessary to convert a JPG image to a GIF image is not the point. Just write //do conversion for that bit.)

This was a whiteboard question

The Missing Number Question

Suppose you have an array of 99 numbers. The array contains the digits 1 to 100 with one digit missing. Describe four different algorithms to compute the missing number. Two of these should optimize for low storage and two of these should optimize for fast processing.

This was a whiteboard question

The Fibonacci Sequence

Write a program to compute the sum of the digits of the first 3-digit number in the Fibonacci sequence (Interviewee is not expected to know what the Fibonacci sequence is, this is explained.)

This was a program-on-the-spot in an IDE question

Social Graph Estimation

Assume that you have access to an employee's email Inbox, and that you can parse the content of their emails, including the email headers.

1. How can you use this to deduce their first-degree connections?
2. What kind of heuristics can you come up with to quantify the strength of these first-degree connections?
3. How can you use this to deduce their second-degree connections?
4. How can you use this to deduce their third-degree connections?

This was a phone screen question

Social Graph Algorithms

1. Describe how you would store a social graph in a relational database.
2. Describe an efficient algorithm to determine whether or not person X is a 2nd degree connection of person Y.
3. Describe an efficient algorithm to determine whether or not person X is a 3rd degree connection of person Y.
4. How can you make #3 very quick. E.g. how does Linked In compute 3rd degree connections quickly?

This was heard as both a phone screen and a whiteboard question

Probability

Suppose that it is known a priori that in the United States, 2 out of every 100 people has a particular disease. A low-cost screening test for the disease has been developed and this screening test is 99% accurate. You take the test and are told that you have the disease. What is the probability that this result is a false positive?

This was a whiteboard question

More Probability

Suppose that if you stand on a particular street corner for an hour there is an 80% probability that a car will pass. What is the probability that a car will pass in 20 minutes?

This was a phone screen question

Sorting

This time around nobody asked me to actually write out the algorithms for Merge Sort, Partition Sort or Bubble Sort, but I have been asked in the past. I did get asked about the order of these algorithms (e.g. N logN) and the order for various Hash Set operations (e.g. how long to put an item in the hash set, how long to remove an item, etc.).