Algorithm/Data Structure Design Interview Questions [closed]

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

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.