Algorithm/Data Structure Design Interview Questions

Question

What are some simple algorithm or data structure related "white boarding" problems that you find effective during the candidate screening process?

I have some simple ones that I use to validate problem solving skills and that can be simply expressed but have some opportunity for the application of some heuristics.

One of the basics that I use for junior developers is:

Write a C# method that takes a string which contains a set of words (a sentence) and rotates those words X number of places to the right. When a word in the last position of the sentence is rotated it should show up at the front of the resulting string.

When a candidate answers this question I look to see that they available .NET data structures and methods (string.Join, string.Split, List, etc...) to solve the problem. I also look for them to identify special cases for optimization. Like the number of times that the words need to be rotated isn't really X it's X % number of words.

What are some of the white board problems that you use to interview a candidate and what are some of the things you look for in an answer (do not need to post the actual answer).

Answer 1

1. Write a method that takes a string, and returns true if that string is a number.(anything with regex as the most effective answer for an interview)
2. Please write an abstract factory method, that doesn't contain a switch and returns types with the base type of "X". (Looking for patterns, looking for reflection, looking for them to not side step and use an if else if)
3. Please split the string "every;thing|;|else|;|in|;|he;re" by the token "|;|".(multi character tokens are not allowed at least in .net, so looking for creativity, the best solution is a total hack)

Answer 2

I enjoy the classic "what's the difference between a LinkedList and an ArrayList (or between a linked list and an array/vector) and why would you choose one or the other?"

The kind of answer I hope for is one that includes discussion of:

• insertion performance
• iteration performance
• memory allocation/reallocation impact
• impact of removing elements from the beginning/middle/end
• how knowing (or not knowing) the maximum size of the list can affect the decision

Answer 3

Once when I was interviewing for Microsoft in college, the guy asked me how to detect a cycle in a linked list.

Having discussed in class the prior week the optimal solution to the problem, I started to tell him.

He told me, "No, no, everybody gives me that solution. Give me a different one."

I argued that my solution was optimal. He said, "I know it's optimal. Give me a sub-optimal one."

At the same time, it's a pretty good problem.

Answer 4

I like to go over a code the person actually wrote and have them explain it to me.

Answer 5

When interviewing recently, I was often asked to implement a data structure, usually LinkedList or HashMap. Both of these are easy enough to be doable in a short time, and difficult enough to eliminate the clueless.

Answer 6

Follow up any question like this with: "How could you improve this code so the developer who maintains it can figure out how it works easily?"

Answer 7

Graphs are tough, because most non-trivial graph problems tend to require a decent amount of actual code to implement, if more than a sketch of an algorithm is required. A lot of it tends to come down to whether or not the candidate knows the shortest path and graph traversal algorithms, is familiar with cycle types and detection, and whether they know the complexity bounds. I think a lot of questions about this stuff comes down to trivia more than on the spot creative thinking ability.

I think problems related to trees tend to cover most of the difficulties of graph questions, but without as much code complexity.

I like the Project Euler problem that asks to find the most expensive path down a tree (16/67); common ancestor is a good warm up, but a lot of people have seen it. Asking somebody to design a tree class, perform traversals, and then figure out from which traversals they could rebuild a tree also gives some insight into data structure and algorithm implementation. The Stern-Brocot programming challenge is also interesting and quick to develop on a board (http://online-judge.uva.es/p/v100/10077.html).

Answer 8

A trivial one is to ask them to code up a breadth-first search of a tree from scratch. Yeah, if you know what you're doing it is trivial. But a lot of programmers don't know how to tackle it.

One that I find more useful still is as follows. I've given this in a number of languages, here is a Perl version. First I give them the following code sample:

# @a and @b are two arrays which are already populated.
my @int;
OUTER: for my $x (@a) {
  for my $y (@b) {
    if ($x eq $y) {
      push @int, $x;
      next OUTER;
    }
  }
}

Then I ask them the following questions. I ask them slowly, give people time to think, and am willing to give them nudges:

1. What is in @int when this code is done?
2. This code is put into production and there is a performance problem that is tracked back to this code. Explain the potential performance problem. (If they are struggling I'll ask how many comparisons it takes if @a and @b each have 100,000 elements. I am not looking for specific terminology, just a back of the envelope estimate.)
3. Without code, suggest to make this faster. (If they propose a direction that is easy to code, I'll ask them to code it. If they think of a solution that will result in @int being changed in any way (eg commonly order), I'll push to see whether they realize that they shouldn't code the fix before checking whether that matters.)

If they come up with a slightly (or very) wrong solution, the following silly data set will find most mistakes you run across:

@a = qw(
  hello
  world
  hello
  goodbye
  earthlings
);
@b = qw(
  earthlings
  say
  hello
  earthlings
);

I'd guess that about 2/3 of candidates fail this question. I have yet to encounter a competent programmer who had trouble with it. I've found that people with good common sense and very little programming background do better on this than average programmers with a few years of experience.

I would suggest using these questions as filters. Don't hire someone because they can answer these. But if they can't answer these, then don't hire them.

Answer 9

Asking them to write a recursive algorithm for a well known iterative solution (i.e. Fibonacci etc. -- we give them an iterative function, if needed) and then have them compute the run time for it.

Many times the recursive function involves a tree data structure. The number of times the person has failed to recognize that baffles me. It becomes slightly difficult to calculate the run time until you can see that it's a tree structure...

I find that this problem covers many areas. Namely, their code-reading ability (if they are given an iterative function), code-writing ability (since they write a recursive function), algorithm, data-structure (for run-time)...

Answer 10

Implement a function that, given a linked list that may be circular, swaps the first two elements, the third with the fourth, etc...

Answer 11

This doesn't necessarily touch on OOP capabilities but in our last set of interviews we used a selection of buggy code from the Bug of the Month list. Watching the candidates find the bugs shows their analytical capabilities, shows the know how to interpret somebody elses code