Palantir Technologies Software Development Intern Interview Questions & Reviews

Interviewed Nov 2010 (took 2 weeks)

A bit disorganized. First the recruiter called me to ask dumb questions to see whether I could program or not (what is a stack? a queue? a hashtable). She was about an hour and a half late in calling, which was annoying. Then I had two phone interviews.
The first interviewer asked a lot of the same question: How can you efficiently find 3 numbers in an array that sum to 0? 4 numbers? 5 numbers? 6 numbers? My brain was bogged down by so many of the same question... haha. Then he asked how I would find a subarray that summed to zero (elements must be contiguous). After that he asked me to describe a "polynomial" time solution to subset sum (which is just dynamic programming). Interviewer was really interested and helpful.
Second phone interviewer didn't even know it was my second interview. Asked me how I would design an efficient sort for an array, given that every element was at most k positions away from its final sorted position. I didn't know what he was asking at first so I fumbled a lot. I got a good answer in the end but I guess I was too slow.