As a CS teacher, it’s enough of a reason to teach this way just because this is how you get Software Engineer jobs. So, this is a collection of problems I do, always starting with the egg problem. Sorry I don’t explain these problems in detail, but Googling them should give you the full problem. I will work on being more detailed when I get a chance.

- Egg problem
- Filling a bar graph with water
- How to store phone numbers
- Given a random nxm matrix of black and white squares, how do you find the largest black square of squares
- How do you know whether a word shares the same characters
- How do you find an integer in a list of integers
- Bit generator/uneven dice
- Flattening an embedded list
- Figuring out whether a set of numbers contains the legs of a triangle

These problems were shared by a Googler coworker of mine:

1. You’re given a list containing the integers(unsorted) 1:n, but one integer is missing. Find out which one it is. What’s the best time complexity? Can you get any clever constant factor speedups?

2. You’re given a list of distinct integers. Find all sets of three which sum to 0. Gotta beat O(n^3).

3. You’re given a list of positive and negative integers. Find the highest sum contiguous subsequence. What’s the best time complexity?

4. You’re given a square tiled space(and a map), n by m. In each square, there are some number of apples. A path from one square to another is a sequence of squares where any two adjacent squares in the sequence are adjacent in the grid. (no diagonals). When you go over a square, you can remove the apples and eat them, leaving the square empty. You are to take 3 paths, one from the top left to bottom right, then turn around and go back to the top left, then go back down to the bottom right. If you MUST take the shortest distance trip, then write an algorithm to get the maximum number of apples.

5. You are given an integer N, and a set S of integers | each s < N. Using only numbers from the set (but you are allowed to re-use numbers), what is an efficient algorithm to find all ways that you can use a sequence of s’s to sum to N. Give one answer for the case where order of the sequence matters, and another for the case where it doesn’t.

CHALLENGE MODE! (I had to look this one up)

1. Devil’s Chessboard – The devil gives you a game. You and your friend can communicate arbitrarily before the game starts, but the devil hears you. First, you enter a room(at this point, your friend waits outside, and communication ceases). Then the devil presents you with a standard chessboard. Each square has a coin that is randomly facing either heads or tails. (or the devil chooses, it actually doesn’t change the outcome) The devil then picks one square, and says “this is the magic square”. He doesn’t change the board at all. You may then flip one coin, anywhere on the board, and leave the room a different way. Your friend then comes in, and has to tell the devil which square is the magic square(the square that the devil chose, not necessarily the one that you flipped). If you lose the devil eats your souls or something. Define an system/algorithm for winning and saving your souls. There are multiple solutions which use fairly different ways of thinking. Some are actually feasible for a human to do(with a pen and paper in under 5min), whereas some would definitely require that the devil give you laptops. Any solution is good!

Advertisements