Algorithm/Data Structure Design Interview Questions [closed]

Question

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

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.

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.

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

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)

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).

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?"