Count the number of set bits in a byte/int32

Hint: there are atleast 7 solutions each with varying runtime complexities. Popular ones are O(no. of bits), O(no. of set bits), O(no. of unset bits)

10 coins, 1 lighter coin

Out of 10 coins, one weighs less then the others. You have a scale.

• How can you determine which one weighs less in 3 weighs?
• Now how would you do it if you didn't know if the odd coin weighs less or more?

Coins puzzle

There are infinite number of coins in a dark room with exactly 129 coins facing heads.You need to divide the coins into 2 parts such that number of coins facing heads are equal in the 2 parts.

Puzzle Time: 2 egg problem

You have 2 eggs and a multi-storeyed building with you[:) ..yes the building is yours!]
Tolerance level of an egg is defined as the minimum height from which dropping the egg would break it!In other words, if tolerance level of an egg is say 15 it means if the egg is dropped from floor no. >= 15 it would break.
Both the eggs have equal tolerance levels.
What is the minimum number of attempts you need to correctly determine the tolerance level of the eggs.

What if there are 3 eggs?

Linked List

Find whether a circle exists in a Linked List. If yes then find the node where the circle begins. Can be done in O(n) time.

Repeated Number in an array

An array of length n+1 is given which is filled with the numbers 1... n such that only 1 number is repeated. Find the repeated number.

Another variation of the problem asks to find repeated numbers if there are two such repetitions.

Linked List Intersection

Suppose you have 2 Singly Linked List that intersect at a Node.
Find that node in O(n) time complexity and O(1) space.

3 Array Problem

There are 3 unsorted arrays with negative and positive numbers. Find 3 numbers one from each array such that their sum total is 0.
e.g. A, B, C are three arrays
then A[i] + B[j] + C[k] = 0