« Smerity.com

Programming Interview Questions: mind teasers in binary

As part of my preparation for a phone interview with Google Sydney I thought running through some interesting programming interview questions would be a good idea. These problems are either standard algorithms problems, standard interview problems, modified programming competition problems or things I've just thought of that seem to fit the mould.

There are a few important things to remember though:

  1. There's commonly more than one solution - start with the obvious solution and try to improve on it.
  2. In the question description I won't give the optimal Big O complexity - that can give the game away far too easily.
  3. It isn't just about getting the optimal answer, it's also about showing you have the ability to work through a problem. If you come up with a good solution having never heard the problem before that can count as much (or more!) as someone who rattles off the optimal solution from memory.
  4. The Simple, Medium and Hard categories are only a very rough grouping of the problem difficulty. Those in the Medium category could (depending on the programmer's experience) be either too easy or too difficult - especially if the problem assumes you've been exposed to a certain skill or technique.
  5. Remember they're also going to ask about you - it's not all just about programming. Have a friend ask you some general questions about yourself and your career like "what recent projects have you done and what did you learn from it" and so on. I'm not covering those here but they're just as important.

Questions

Simple

Implement a sort of your choice in C/C++/Java/Python/etc

Write a program to reverse the order of all the words in a string. (i.e. "Hello World" => "World Hello")

HINT: There is an O(n) solution using only O(1) space.

Given a list of words how would you find those which are all anagrams of each other? (i.e., if given "tree", "evil", "live" and "god" return "live" and "evil" as anagrams of each other)

Describe Breadth First Search and Depth First Search - are there any advantages to using one over the other?

Given a number multiply it by 7 without using multiplication or addition.

HINT: What if you wanted to multiply the number by 8? How would you modify that for 7?

Given an array, describe an algorithm to identify the subarray with the maximum sum. (i.e., [1,-3,5,-2,9,-8,-6,4] => [5,-2,9])

HINT: You can do this in O(n) time by keeping track of things. If you're really stuck on the O(n) solution have a look for the Maximum Consecutive Subsequence algorithm.

You are told to program on an ancient hardware system and due to some unfortunate design decisions there is no division. Given a list [a,b,c ... z] return a list [b..z, ac..z, to a..y] where you multiply all the other elements in the list together except for the current element. (i.e., [3,5,2] => [10,6,15])

HINT: Even without division it's possible to do this in O(n).

Medium

There is a field filled with gophers and their holes. Occasionally a hawk comes to eat them and the gophers must run for cover. For each gopher you are given a list of possible gopher holes and the time taken to reach there. Unfortunately due to shoddy construction only one gopher can fit in a gopher hole. If the hawk will arrive in X seconds, and eat all the gophers not yet in a hole, how can you maximize the number of gophers saved?

STRONG HINT: Think about how to model this as a bipartite graph and how that could help you.

How would you implement your own set data structure? How does it perform if I wanted to do an intersection? Create a union?

Imagine you have just discovered a previously unknown continent. On this continent there are a large number of people, all belonging to a set of tribes each with a tribe leader. When the Sun God demands it, two tribes merge into one tribe - it doesn't matter who the new leader is as long as all the members end up in the same tribe. What's the best way to find which tribe each person is in after all these merges? You can assume we won't want the tribes split after they're joined.

HINT: You don't want to have to update all of a tribe's members to their new tribe, as that could take a long time. How could you set it up so you only need to update one person per merge?

Given an unsigned integer return if it is a power of two.

HINT: This can be a one liner in C using bitwise operations.

Given an integer L find out how many bits are active.

HINT: Having the previous solution can help you here, so try to solve that first and then move on.

You are given n integers of an unspecified range. Find two integers a and b in n such that a+b = k. What if they were only 8 bit integers?

You have an array of randomly shuffled integers from 1 to n. One integer k has been removed however. How would you find the value of the integer k that was removed?

You have a set of 32 bit integers - find all the numbers that occur exactly once. How would your solution change if the integers were only 8 bit?

If you only have 64 megabytes of RAM, 1 gigabyte of integers to sort and a multi gigabyte hard drive what would your sort algorithm look like?

HINT: What is easy and what is painful to do on a hard drive? What kind of sort can take advantage of this? If you're really stuck, look at external sorting.

Find the median of an array of numbers. What about the kth smallest/largest element?

HINT: It is possible to do this in O(n) time, using only the array of numbers given - no extra space.

Hard

You are given a set of (x,y) co-ordinates - find the minimum spanning tree for these points. What if it was a set of (x,y,z) co-ordinates?

STRONG HINT: The two dimensional co-ordinate problem is an instance of the Euclidean minimum spanning tree and has an optimal solution in O(nlogn) time - this uses the Delaunay triangulation. Extending to three dimensions is not as efficient however.

Given a set of (x,y) co-ordinates, find the closest pair of points.

HINT: This is a painful but standard computational geometry problem - a solution exists in O(nlogn) time. If you've never seen or heard of this problem before I doubt it can be worked out in the course of an interview, but it is a beautiful algorithm, one well worth knowing.

Imagine you had a black box database, storing a large amount of key-value data. Every time you search for a key not in the database this results in a costly series of lookups. You have the set of keys K that the database stores, but they're too large to store in memory or to query efficiently themselves. How would you go about trying to avoid as many non-existent key lookups as possible?

HINT: This problem isn't about preventing any key query not in the set of keys K. You do need to ensure that any key that is in the set of keys K will be queried however. If you're quite stuck, read up on probabilistic set data structures.

Given a deck of cards how would you shuffle them to ensure that it's a completely random shuffle?

HINT: There's a simple solution that will work in a reasonable time complexity and then a more complex linear time algorithm that people commonly get wrong.

Imagine you had a set of people numbered 0 to 1000. You have a list of k money bonuses - for example, anyone > 300 gets $20 each and anyone < 70 get $90 each. Unfortunately k can be a huge number. What sort of data structure would you make to allow you to efficiently query how much a person should get?

HINT: The major issue is adding or subtracting a dollar amount from each person is not feasible for huge values of k if you do it per person. How do you fix that?

If you had a linked list of undefined length and could only pass through it once how would you select a random element in O(1) space?

HINT: How do you select a random element from an array? How can you turn that into something you can apply sequentially?

Given a long string and a given word find out how many times you can write that word using subsets of the string. (i.e., you can create "dog" with "doom dogged" 8 times)

HINT: This can be broken down into sub problems that can then be solved. Dynamic programming can help solve those sub problems efficiently.

The Result

I'll write up how this sort of study paid off after the phone interview. It'll be my first one, so I'm not sure how I'll go, but at least I'll have a story to tell! =]

If there's enough interest I'll also do a follow up post where I'll answer all the questions above in full.