akrish

So I’ve been asked by a couple of my friends to give them sample interview questions for computer science internships/jobs (mostly internships). Here are some of the questions that I’ve heard from my own interviews and my friends.

Note: Things in italics are my own notes.

1. A lot more common than you’d think. I have a list of integers that’s sorted. How do I find if a given element is in the list. What’s the running time of your algorithm? I’ve been asked to implement this in the language of my choice as well.

2. I have a 2-D array of integers (say n by n). The rows are sorted and the columns are also sorted (So the smallest element is the top-left element and the largest element is the bottom-right element). How do I efficiently find if a given element is in this matrix? What’s the running time of your algorithm? I’d like to hear people’s answers to this because my interviewer said that I didn’t come up with the best way.

3. Write a function that takes an array of integers and a number (x). This function should find if any two elements in the list add up to x and return those two number (as a list). Analyze your algorithm and explain the running time.

4. Write a function that computes the nth fibonacci number. Write this iteratively and recursively.

5. How many trailing zero’s are in n factorial? I wasn’t asked this one but heard it from someone else.

6. I’m playing a two-player game where there is a tower of n coins. It’s a turn-based game where on each player’s turn he can take either one or two coins from the stack. The person who takes the last coin from the stack is the winner. If I go first, for what values of n am I guaranteed to win? What’s my strategy? Essentially, describe this game in its entirety.

When I get around to it I’ll also link to some other sample interview questions that I’ve found around the web. Also feel free to email me with other questions I should add.