Pocket Gems Programmer interview questions

You are given an array with integers between 1 and 1,000,000. One integer is in the array twice. How can you determine which one? Can you think of a way to do it using little extra memory.

Implement a Queue class in C++. Which data structure to use internally? Why? How to notify of errors?

Count the number of set bits in a 32 bit integer.

There are n gas stations positioned along a circular road. Each has a limited supply of gas. You can only drive clockwise around the road. You start with zero gas. Knowing how much gas you need to get from each gas station to the next and how much gas you can get at each station, design an algorithm to find the gas station you need to start at to get all the way around the circle.