Problems solvable using Hashtable

Hashtable are extremely useful data-structure as they provide storage and retrieval in O(1) time (amortized). Several problems of algorithms can be very efficiently solved using hashtables which otherwise turn out to be quite expensive. In this post, we consider some of these problems:

Problem 1: Remove duplicate elements from an unsorted array of size N.
Solution: show

Lets first see the solution without hashtable. Naive solution would be to compare each pair of elements. If they are same then drop one of them. This solution would take O(N^2) time in average case and O(N) time in best case, when all the elements are same. The following code does that:

for i = 1 to N-1
  if a[i] == NaN: continue
  print a[i]
  
  for j = i+1 to N
    if a[i] == a[j]: a[j] = NaN

Above code prints all non-duplicates from the array. Naive solution is average case O(N^2). In practice if you believe that array consists of few numbers duplicated lots of times, say K numbers duplicated N/K times, then the running time of above algorithm is O(KN).

We can do better than worst case O(N^2) time. If we sort the elements in O(N logN) time and compare adjacent elements in O(N), we can solve the above problem in O(N logN) time.

sort(a) // O(N log N) time, O(1) space using Heap Sort

k = a[1]
for i = 2 to N
  if a[i] == k: a[i] = NaN
  else: k = a[i]

Using heap sort, we can make the above algorithm run in O(N log N) time in worst case and it would take O(1) extra space (apart from N for the array). Using hashtable, we can solve this problem in O(N) time (amortized) and O(N) space (for the hash table). The algorithm looks like following:

for i = 1 to N
  if hash.has_key(a[i]) == false:
    print a[i]
    hash.put(a[i])

Above algorithm stores an unseen element in hashtable and ignores the seen element. To check if an element is seen or not, hash table provides storage/retrieval methods in O(1) time.

Problem 2: Find intersection of K unsorted array of N elements each. Intersection consists of elements that appear in all the K arrays.

Problem 3: How to make a linked list support operations in O(1) time. The operations on linked list can be insertion after any arbitrary valued node, deletion of any arbitrary valued node.

Problem 4: Find all unique pairs of element in an array that sum to S. For ex. If array = {2,4,6,4,6} and S = 8 then answer is {<2,6>, <4,4>}

Problem 5: Consider an array containing unique elements. Find a triplet of elements in the array that sum to S (extension of problem 4). Can hashtables improve the running time of your algorithm.

Problem 6: Consider two strings of size M, N. Perform string matching in size O(M+N).

Problem 7: Find top K most frequent elements in an array of size N.

Problem 8: Given a file with N integers. Find top K most frequent integers. Assume N to be very large such that all the N numbers cannot fit into memory. Design for the worst case.

Solution: show

To do

Dragon and Knight

Problem: A dragon and knight live on an island. This island has seven poisoned wells, numbered 1 to 7. If you drink from a well, you can only save yourself by drinking from a higher numbered well. Well 7 is located at the top of a high mountain, so only the dragon can reach it.

One day they decide that the island isn't big enough for the two of them, and they have a duel. Each of them brings a glass of water to the duel, they exchange glasses, and drink. After the duel, the knight lives and the dragon dies.

Why did the knight live? Why did the dragon die?

Solution: show

Dragon knows that knight cant reach well 7. So he thinks that if i give knight water from well 6 or 7, knight would die for sure. So he would get water from well 6 or 7 for knight.

Knight knew that no matter from which well he gives the water, dragon will go and drink from well 7 and live. So he got normal water for dragon and before duel drank water from well 1.

When they exchanged glasses and drank water, dragon rushed to well 7 and drank poison from it, thinking that it would cure the poison he just drank (but he drank normal water), so dragon died. Knight on the other hand already had poison from well 1 so what dragon gave him effectively cured him. So he lived.

Problem: Now consider that Dragon and Knight are equally intelligent then who is expected to die.

Answer: Both survive the battle.

Solution: show

After the battle, dragon drinks from well 1 in order to guarantee that he is poisoned. He then drinks from well 7 to cure himself. Even if knight gets normal water or poison from well 1-6, dragon is now cured and survives.

As for the knight, he drinks from well 1 before the duel. If dragon has got poison for him then he is cured. But if dragon got normal water then he has to ensure that he cures by drinking poison from higher than well 1. So after the battle, knight re-drinks from well 1. This guarantees that he is poisoned from well 1. Then he goes and drinks from well 2 to cure himself.

So both dragon and knight survive the battle.

Number and Age of David's Kids

Problem: The product of the ages of David's children is the square of the sum of their ages. David has less than eight children. None of his children have the same age. None of his children is more than 14 years old. All of his children is at least two years old. How many children does David have, and what are their ages?

Answer: (2,4,6,12)

Solution: show

A way to mathematically analyze this problem is write the general form of equations, differentiate and maximize w.r.t to largest age. That leads to a Fibonacci number series. But after that complex heuristics have to be employed to devise the solution (and we cannot guarantee if that is the unique).

This is a constraint satisfaction problem. The best way to solve it is write the code. The following code solves the problem in general sense:

function TryAll(ageSet, depth)  
  if depth == 0    
    s = sum(ageSet)
    p = product(ageSet)
    if s^2 == p
      print ageSet
    return

  l = length(ageSet)
  x = l ? ageSet[l-1] : 15
  
  for i in 2 to x-1
    ageSet1 = clone(ageSet)
    ageSet1.add(i)
    TryAll(ageSet1, depth-1)

// call
TryAll([],7)
TryAll([],6)
TryAll([],5)
TryAll([],4)
TryAll([],3)

If we change the for loop and make it go from 2 to x then we are solving the problem of age ranging between 2-15 and ages are allowed to be duplicate. Changing 15 to 14, we see the following as the solution as well:

[9, 9, 9]
[4, 4, 4, 4]
[6, 6, 3, 3]
[8, 5, 5, 2]
[12, 6, 4, 2]
[4, 4, 4, 2, 2]
[12, 6, 2, 2, 2]
[4, 4, 2, 2, 2, 2]
[4, 2, 2, 2, 2, 2, 2]

Largest Sum of Consecutive Numbers

Problem: Given an array of N integers (both positive and negative), find the sub-sequence with largest sum.

For ex: Let A = {1 2 -5 4 5 -1 2 -11} then largest sum is 10 (start index = 4, end index = 7)

Solution: show

The naive solution to this problem can be formulated and coded in O(N^3) time. Consider every possible pair of start and end index and calculate sum of the elements within those index and keep track of the max sum. The following code performs that

max = - Inf
imax = jmax = -1
for i = 1 to N
  for j = i to N
    
    // get sum of elements enclosed in index (i,j)
    s = 0
    for k = i to j
      s += A[k]

    if s > max
      max = s
      imax = i
      jmax = j

Clearly the above algorithm is O(N^3). We can definitely improve the running time of the above algorithm. After observing carefully, we can see that an operation that is run several times (O(N^2) times) is computing the sum of elements between indices i,j. Can we do it quickly. Indeed we can.

If we save the cumulative sum of elements in an array CSUM, then CSUM[i] indicates the sum of elements enclosed in indices (1,i), CSUM[j]-CSUM[i-1] would then indicate the sum of elements enclosed in indices (i,j). The following algorithm captures this intuition.

csum[0] = 0
for i = 1 to N
  csum[i] = csum[i-1] + A[i]

max = - Inf
imax = jmax = -1
for i = 1 to N
  for j = i to N
    s = CSUM[j] - CSUM[i-1]
    if s > max 
      max = s
      imax = i 
      jmax = j

This is the best we can do with this approach. This problem can be done in O(N) time using a clever approach. Consider a sub-sequence with sum s > 0. Let the next element n is such that s + n < 0. Clearly this sub-sequence cannot be part of largest subsequence that contains s and n as removing s,n from that sub-sequence we get a larger sum. Easy to prove using contradiction. This idea is captured in the following O(N) algorithm

max = -Inf
imax = jmax = -1
i_temp = -1
s_temp = 0
for i = 1 to N 
  s_temp += A[i]

  if s_temp < 0
    // abort this sub-sequence
    s_temp = 0
    i_temp = i + 1

  if s_temp > max
    // keep track of max so far
    max = s_temp
    imax = i_temp
    jmax = i

Problem: Given an array of N integers (both positive and negative), find the sub-sequence with largest absolute sum. This problem differs from the one at the top as we want the absolute sum (taking mod)

For ex: Let A = {1 2 -5 4 5 -1 2 -11} then largest absolute sum is 11.

Solution: show

Simply keep track of max and min at the same time in the above O(N) solution.

Assuming that we have to use the above algorithm without modification, then we can take these steps to get max absolute sum in O(N) time:

1. Run O(N) algorithm on array A to get the max
2. Create array B by multiply all numbers in A by -1
3. Run O(N) algorithm on array B to get the max
4. Pick the max between the output of two runs of the algorithm

Instead of trying the above two methods, we can try a very nice and simple approach

// build csum matrix as before
csum[0] = 0
for i = 1 to N
  csum[i] = csum[i-1] + A[i]

answer = max(csum) - min(csum)

The answer is maximum element of csum minus the minimum element of csum.

Polynomial Evaluation

Problem: Given a polynomial with degree bound of n=m^r. How do we evaluate the polynomial at n different points such that the polynomial can be recovered from these n points (i.e. the coefficients can be calculated back using the points).

Note: We do not want to recover the coefficients but cleverly choosing the points as that impacts the running time of the algorithm.

Solution: show

Let the polynomial be A(x) = a0 + a1 x + a2 x^2 + ... + a(n-1) x^(n-1).

A(x) has a degree bound of n. Its actual degree can be lower than n-1 if a(n-1) equals zero but that doesn't matter here.

Using Horner's rule, we can compute a polynomial in O(n) time by arranging the terms as follows:

A(x) = a0 + x (a1 + x (a2 + ... + x (a(n-2) + x a(n-1))))

So it will take O(n^2) time to compute polynomial at n different points. But we can use divide and conquer to do better than that i.e. in O(n lg n). We can create "m" different polynomials such that each term of ith polynomial has degree mod m = i.

=> A(x) = [ a0 + a(m) x^m + a(2m) x^2m ... ] +
                   [ a1 + a(m+1) x^(m+1) + a(2m+1) x^(2m+1) ... ] +
                   .
                   .
                   .
                   [ a(m-1) x^(m-1) + a(2m-1) x^(2m-1) + ... ]

=> A(x) = A[0](y) + x A[1](y) + ... + x^i A[i](y) + ... + x^(m-1) A[m-1](y)

where y = x^m, and
            A[i](x) = a(i) + a(m+i) . x + ... + a(n-m+i) . x^(n/m-1)

Still the recurrence for evaluation each point is T(n) = m T(n/m) + O(m) = O(n). So evaluating polynomial at n points leads to O(n^2) which is not great.

Now we can choose the n points cleverly. Lets set w as principal nth root of unity.
=> w^n = 1
=> w = e^(2 . pi . i / n)
          = cos (2 . pi /n) + i . sin(2 . pi / n)

The two interesting properties of w are
1. w^(n/2) = -1
2. [w^(kn/m + p)]^m = w^(kn + mp) = w^(mp)

So the n points on which the polynomial can be evaluated are w^0, w^1, ..., w^(n-1). Now we need to evaluate lower order polynomials of size n/m at only first m powers of w as afterwards it cycles again and we can reuse the computation. This comes from the observation that

A(w^p) = A[0](w^(mp)) + w^p A[1](w^(mp)) + ... + w^(m-1) A[m-1](w^(mp))

Also,
A(m^(kn/m+p)) = A[0](w^(mp)) + w^(kn/m+p) A[1](w^(mp)) + ... + [w^(kn/m+p)]^(m-1) A[m-1](w^(mp))

So A[0], ... A[m-1] are evaluated at p = { 0, 1, ..., m-1 }, and the computation is used for all the other n-m powers of w.

The general recurrence of this algorithm is:

T(n) = m T(n/m) + O(n)
=> T(n) = O(n lg n)

m = 2 works well in practice and is employed by Fast Fourier Transform in order to intrapolate the coefficients of the polynomial. This is generally used for multiplying two polynomials to get higher order polynomial. The steps are to first evaluate the lower order polynomials at n points and then use the multiplication of the point values to generate the coefficients of the higher order polynomial.

Longest Monotone Sequence and Palindromes

Problem: Given an array of integers, find the longest subsequence of elements which monotonically increases. for ex. array = {1 4 8 2 5 7 3 4 6}, the longest subsequence = {1 2 3 4 6}

Solution: show

Let us construct the solution using the LCS problem. LCS is longest common subsequence, which says that given two string X, Y find the longest common subsequence between them, for ex. if X = {a b c a b c} and Y = {b a c b a c} then a possible LCS(X, Y) = {b c b c}. LCS problem can be solved using dynamic programming in O(n^2).

We can solve the longest monotonically increasing sequence problem using the solution to LCS. Let X = original string. Let Y = sort X (increasing order). LCS(X, Y) gives the desired answer (easy to observe).

Problem: Given a string, find the longest size palindrome in the string. for ex. string = "aaabbccaccbaaa", solution = "bccaccb"

Solution: show

The trivial solution is to check if a palindrom of all possible size starts from a given index. For a index i in array, the possible possitions to test are i < j <= n. Total time taken = O(n^3). We can solve this problem using Longest Common Substring and suffix trees to solve this problem in O(n) time.

Loops in Linked List

Problems with linked lists occur mainly while building or using a bad memory manager. Let us discuss two well known linked list problems.

Problem: Find if two linked lists short at some node. Find the node at which the two lists short.

Solution: show

Subtract the length of smaller list from the larger one. Move a pointer ahead on larger list by the difference of lengths. Now put a pointer on head of smaller list. More two pointers together. The point at which they meet is the point where they short. The following code gives the idea.

d = length(head1) - length(head2)
l1, l2 = head1, head2
if d < 0
  d *= -1 
  l1, l2 = head2, head1

ptr1 = l1
for i <- 1 to d
  ptr1 = ptr1->next

ptr2 = l2
while ptr1 != null
  if ptr2 == ptr1
    return ptr1

ptr1 = ptr1->next
ptr2 = ptr2->next

We can use this idea to find the shorted node to find the solution to next problem.

Problem: A linked list might contain a loop. How do we detect existence of the loop and find the node from which loop starts. Propose an O(n) time algorithm that doesn't take extra space and doesn't modify the linked list.

Solution: show

To find if the linked list contains a loop, run two pointers over the linked list, one that move one node at a time and other that moves two nodes at a time. Both of these pointers meet if the linked list contains a loop, otherwise the pointer moving with twice speed reaches the end while the slower pointer reaches midway.

fastptr = head
slowptr = head

while fastptr != null and fastptr->next != null
  fastptr = fastptr->next->next
  slowptr = slowptr->next
  if fastptr == slowptr
    return "loop exists"
return "loop doesnt exist"

If loop exists, then fast pointer meets the slow pointer before slow pointer completes one rotation of the loop. This fact can be easily proved. Once the pointers meet, we can count the number of nodes in the loop.

loopNodeCount = 0
do 
  loopNodeCount += 1
  slowptr = slowptr->next
while slowptr != fastptr
return loopNodeCount

Now using the trick used in the two linked list shorting problem above, we start two pointers, one from the head and other after advancing "loopNodeCount" nodes ahead. The node at which both the pointers meet is the loop node.

advptr = head
for i in range(1, loopNodeCount)
  advptr = advptr->next

normalptr = head
while normalptr != advptr
  normalptr = normalptr->next
  advptr = advptr->next
return advptr

Monty Hall Problem

This is a very famous probability problem. This problem illustrates that probability is sometimes more convincing than "what we perceive as obvious". I'll post another problem that defeats "obvious reasoning".

Monty Hall problem: Suppose you're on a game show, and you're given the choice of three doors: Behind one door is a car; behind the others, goats. You pick a door, say No. 1, and the host, who knows what's behind the doors, opens another door, say No. 3, which has a goat. He then says to you, "Do you want to pick door No. 2?" Is it to your advantage to switch your choice?

Solution: show

Well for a mathematician stuck on the game show, I would suggest tossing the unbiased coin. The reason being that Game Show host might be clever and seeing that mathematician got the prize behind door 1, would play this card in order to entice the mathematician to switch. Mathematician can be well aware of this trick of Game show host and might not switch. But game show host thought so .. errr. This is a recursive logic and would go to infinity.

Under the assumption that game show host has no hidden motive and performs this step always, the best choice is to switch. That increases the chances by 33.33%. There is a very simple explanation to this. The prize could be behind any doors. Since you pick door 1. Assume game show hosts says that either keep door 1 or take both door 2 and 3, you would go for both door. That doubles up wining chances to 66%. He opens door 3 for you and you open door 2 when you say switch.

Red Green Cards: A box has three cards. First card has both sides green, second card has both sides red, third card has one side green and one side red. A card is picked at random and its one side is observed to be green. What is the probability that the other side of the card is also green.

Solution: show

Well it seems that answer should be 1/2. But its 2/3. For explanation, let us label card 1 as g1|g2, second card as r1|r2, third card as g3|r3. Now since one side of the card is green. It can either be g1, g2, g3. Three events and two point to first card.

Finding Second Smallest Element

Jargon: Order Statistics problem is to find the kth smallest element in an unsorted array A[1..n]. This problem can be solved in O(n) time in average case using randomized select algorithm or in O(n) time in worst case time using an algorithm that chooses the pivot element carefully.

Problem: How to find second smallest element in an array A[1..n] of size n. We would like to do in much less than 2n comparisons.

Answer: Time Complexity = n + lg n - 2

Solution: show

Finding the smallest element is trivial. The following code would find the smallest element using n-1 comparisons.

min = A[1]
for i = 2 to n
  if A[i] < min 
    min = A[i]
return min

The trivial algorithm to find the second minimum is to keep another variable (smin) along with min and if an element knocks out smin then check if it knocks out min and accordingly do the book-keeping. It can be done using 2n-3 comparisons and takes constant space.

A point to observe is that the second smallest element is knocked out by the smallest one at some stage. If we preserve which element is knocked out by whom then finding the second smallest element would just require us to find the smallest amongst the elements knocked out by the smallest element.

But in order to do that we need to build the algorithm in a way that we are playing a pair wise tournament. Lets say we play a tournament and knockout n/2 elements after n/2 comparisons. The recurrence relation looks like this:

T(n) = T(n/2) + n/2

Solving this recurrence gives that T(n) = n - 1. The height of the recurrence tree is lg n. So if we just check these elements knocked by root (min) we get the second minimum.For. E.x.

1   5 2   6  
\ /   \ /  
 1     2
  \   /
    1

As soon as we build the tree using n-1 comparisons, we can check the second largest amongst the number knocked out by 1. i.e. 2, 5. so the second minimum is 2.

This algorithm can be implemented using an auxiliary array B[1..n]. This tree represents a min heap and can be stored in an array easily. There are many divisions performed (ideally they are right shifts) to index the correct elements, so the actual implementation might look a little complicated.

Another algorithm that is very easy to implement but sadly takes 2n - 2logn - 1 in terms of array element comparisons. Simply build a min heap (rooted at 1). Return the smaller of numbers at index 2 or 3 in the array. The cost of min heap building is = 2 * [n/4 + 2n/8 + ...... + (logn - 1) * n / 2^logn]. The solution to this arithmetic - geometric series is 2n - 2logn - 2. Comparing elements at 2nd and 3rd index adds one to the cost. Its very easy to implement though.

String Permutations

Printing all permutations of a string is a very common interview question. We'll discuss this problem and some interesting variations of it. The original problem of string permutation says, "print all permutations of a string". As an example, if the string is "abc" there are 6 permutations {abc, acb, bac, bca, cab, cba}. Assume that string contains no duplicate elements.

Solution: show

There are many ways in which this problem can be solved. The most easiest of the ways is to code it using simple yet powerful recursion technique.

function permute(str, d)
  if d == length(str)
    print str
  else
    for i <- d to length(str)
      swap(str[d] <-> str[i]) // swap the characters for permutation
      permute(str, d + 1)
      swap(str[d] <-> str[i]) // undo the swapping for parent call

Above code performs the swapping operation twice. First time to generate all possible permutations of character at that level and second time to restore to the original string. It is important to restore to the original string (as passed to this call), otherwise the algorithm ends up printing redundant permutations. Additionally, this code assumes that there are no duplicates in the string, else it fails.

There are other ways in which string permutation can be printed that require circular shifting, but it cant get any simpler than above.

Lets us assume that string can contain duplicates. How do we print all non-redundant permutations of the string. For ex. If string is "abab" the permutations are {baab, abba, abab, baba, bbaa, aabb}

Solution: show

Clearly the solution to first problem fails here. This is due to fact that we generate all permutations of the string after the swapping step. Same character could get swapped to dth spot again, leading to redundant permutations. A very simple trick solves the game. The trick is to pre-sort the string on alphabetical order. Now we need to ensure that while we are swapping, to generate permutation for that particular character, if that matches the last swapped character we ignore generating permutations. The following code implements the same:

function permute(str, d)
  if d == length(str)
    print str
  else
    lastSwap = Nil
    for i <- d to length(str)
      if lastSwap == str[i]
        continue
      else
        lastSwap = str[i]

      swap(str[d] <-> str[i]) // swap the characters for permutation
      permute(str, d + 1)
      swap(str[d] <-> str[i]) // undo the swapping for parent call

If the string is pre-sorted alphabetically then the above algorithm works magically. The reason is that sorting ensures that if there are duplicates then the second occurrence of the duplicate element is picked immediately after we finish generating permutations for the first occurrence of the duplicate element.

If sorting is not allowed, then you need to maintain a local hashtable (local to each function call), that maintains characters swapped to dth spot and ensures that duplicate candidates are discarded. Presort and make life simple.

Some other constraints could be added to make the problem more interesting. One such constrain could be of partial ordering of characters. For Ex. 'a' should appear before 'c', and 'b' should appear before 'c' in all permutations. There can exist ordering that leads to no permutation of the string such as 'a' precedes 'b', 'b' precedes 'c', 'c' precedes 'a'. Additionally implementing the permutation algorithm in these cases require checking for ordering violation at each permutation level or just at the leaf of recursion, depending on whether checking for ordering violations is more costly or generating all permutations.

An interesting problem, that talks of special kind of ordering and can be very efficiently computed is as follows: Assume that the string is made up of equal number of '{' and '}'. You need to print all permutations of this string which could satisfy a C compiler i.e. an ending bracket is balanced by an opening bracket. For ex. for '{{}}' the permutations are [{{}}, {}{}].

Solution: show

Permutation problems can be easily solved using recursion. The trick is to formulate all the possible cases at a particular level and code according to the formulation. The steps used below illustrate this approach.

Let's formulate the problem in general sense. Assume that at a given step of recursion, we have n open brackets and m closed brackets that are not used so far. Now we can formuate each and every case for a given (n,m) and code the possible substeps.

Problem Formulation:
(n,m) ---> NOT POSSIBLE,   if m < n
(n,m) ---> PRINT AND DONE, if m = 0 and n = 0
(n,m) ---> (n-1, m)        if n > 0   
              +
           (n, m-1)        if m > 0 and m > n

The above formulation is generic and takes into account all possible input values of (n,m). If we put following constraint on the initial value of n and m such as following, then actual implementation can omit some of the above cases:

Constraints: 
n > 0
m == n

The actual implementation that follows above constraints and problem formuation:

function permute(str, n, m)
  if m == 0
    print str
  else
    if n > 0
      permute (str + '{', n - 1, m);

    if m > n
      permute (str + '}', n, m - 1);

To enforce the above mentioned constraints, permute function should be kept as inner/private function and the actual function that should be exposed is as follows:

function GenerateCStyleBrackets(N)
if N <= 0
return

str = new String[2 * N]
permute(str, N, N) // str is passed as pointer.

The memory cost is O(N). The maximum stack depth is also O(N). So total space cost is O(N). Calculating time cost is an interesting problem and can be worded in a very interesting way, deserving a separate post in itselt. I'll post it later.

Party Friends

Problem: In any party, there exists two people with same number of friends. Is is true or false. Assume that party has more than one people.

Solution: show

Yes, The statement is true. We can prove it by contradiction.

Let there be N people at the party.
Let all the N people have different number of friends.

Since a person can have maximum of N-1 friends and a minimum of 0 friends. Hence the possible number of friends for a person is 0, 1, 2, ..., N-1. Since, we are assuming that there are no two people with same number of friends, so everyone has different number of friends. This means that someone has 0 friend, someone has 1 friend, so on and someone has N-1 friends. But 0 & N-1 cannot coexist. This is because if a person has N-1 friends then that means he is friend with every one, including the one who has 0 friends, which is a contradiction. Hence by pigeon hole principle at least two people should have the same number of friends.

Innocents and Criminals: Finding Minority Entitybb

Problem: There are two types of people in a particular city, innocents and criminals. All you know is that innocents are in majority and would like to get rid of criminals and criminals would like to protect themselves from persecution. You can ask any number of questions, with yes/no type answer, from any person in the city. Propose an algorithm which requires asking the minimum number of questions.

Hint: Trivial solution requires asking O(n^2) questions. You can do it in less than 2n questions.

Solution: show

The trivial solution is very simple and is in-fact O(n^2) time algorithm. Round up every person and ask him about the status of everyone else. People with majority vote of criminal are criminals and people with minority vote of criminal are innocents. Following code solves it:

for i = 1 to N
  for j = 1 to N
    if person[i].isCriminal(j)  // doesnt matter if i == j
      vote[j] += 1
    else
      vote[j] -= 1

for j <- 1 to n 
  if vote[j] > 0
    person[j].persecute()

The most efficient algorithm requires asking only 2N-2 questions. The key to solution of this problem lies in the solution to the problem of Finding Majority Element. If we can find one innocent person in the city, then he can label everyone else truthfully. We know for sure that an innocent will tell the truth. Criminals can lie or say truth depending on circumstances.

Assume that we formulate the problem this way. Let us consider a pool of people, who claim to be innocents. Also let us say that we declare that we will pick the first person in the pool to be our innocent man and he will reveal the identity of everyone else. Then definitely both innocents and criminals would try their best to capture the first spot in the pool.

Now, we play a game like this. We choose a person randomly to represent the first person in the pool. Now we select a new person randomly and ask him should the last person inducted in the pool is Innocent. If he says Yes, then we add him to the pool. If he says No then we remove him and the last person from the pool and discard them from further selection. If the pool is empty we select a person not selected previously to get the first spot in the pool.

We repeat the process until we don't have anymore people to consider. The intuition is that even if all Criminals join the pool initially (by lying), then innocents would boot them out as they are in majority. If more innocents join the pool initially then criminals will not be able to boot all innocents out. Hence the first person remaining in the pool is indeed an innocent. We can see this argument working inductively as well.

The following code implements above logic with the help of a stack:

stack.push(person[1])
for i <- 2 to N
  if !stack.isEmpty() && person[i].isCriminal(stack.top())
    stack.pop()
  else
    stack.push(person[i])
return stack.bottom()

Finding First Non-Zero Digit of N Factorial

Problem: Find the first non-zero digit of N!. Assume N! to be extremely large.

Solution: show

Taking hint from the solution to previous problem, if we assume that the product doesn't contain 2's and 5's then finding the last digit of product is trivial. Multiply next number to result so far and take mod 10 of the result. The problem is produced by 2's and 5's which lead to trailing zeros.

From any number we can remove 2's and 5's and calculate the answer. Then we can cancel as much 5 as we can with the 2. Then we can multiply remaining 2's to the answer to get the final answer.

For Ex. 7! = 1 * 2 * 3 * 4 * 5 * 6 * 7. We extract 2's and 5's so the product is 1 * 3 * 3 * 7. The trailing digit is 3. We have extracted four 2's and one 5. So we get 3 extra 2's. So multiply to 3 we get 4 as the answer. To check 7! = 5040

The following code implements above logic:

n2 = 0
d = 1
for i <- 1 to n
  j = i

  // remove ending zeros
  while j%10 == 0
    j /= 10

  // add 2's to n2
  while j%2 == 0
    j /= 2
    n2 += 1

  // subtract 5's from n2
  while j%5 ==0
    j /= 5
    n2 -= 1    

  d = (d * j) % 10

// multiply remaining 2's to d
while n2 > 0
  d = (d * 2) % 10
  n2 -= 1
return d

Count Trailing Zeros in N Factorial

Problem: How many trailing zeros does N factorial contain, for ex. 5! = 120 so ans is 1. Propose an algorithm to count trailing zeros. Assume that N! is very large and does not fit into word size of the computer.

Solution: show

This problem is straight forward. N! = 1 * 2 * 3 * 4 * 5 * .... * N. If we count all 5's in this product, then that many trailing zeros are there. This is because a 5 is countered by 2 to produce a zero. Additionally, there are more 2's than 5's so counting 5's gives the right answer. The following pseudo-code does that:

count = 0
i = 5
while i <= n
  j = i
  while j%5 == 0
    j = j/5
    count += 1
  i += 5

return count

This algorithm takes n/5 outer loop iterations and is bounded by log n [base=5] inner loop iterations, hence it takes O(n log n) time. We can clearly do better than this.

Actually, we can solve this problem in O(log n) time. For a given i the term i/5 gives total number of 5's that come before it. For ex. 17/5 is 3, there are 3 numbers that contain fives which are less than 17 i.e. 5, 10, 15. So we count number of 5, then number of 25, then so on.

count = 0
d = r = 1
while r > 0
  d *= 5
  r = [n/d] // [x] is greatest integer less than x
  count += r
return count

This algorithm runs in O(log n) time and an asymptotic improvement on the previous algorithm.

Picking k Elements Randomly from Stream

Problem: Previously, I posted the problem of picking an element randomly from finite stream with unknown size. This problem is generalization of the previous problem. Here, instead of picking an element randomly from the stream, we need to pick k elements randomly from the stream. We can assume that k is less than the actual size of the stream.

Solution: show

We can solve this problem in O(nk) time using O(k) space, where n = size of the stream. Consider an array of size k, we fill it with first k elements of the stream. To remove any kind of element distribution bias of the stream, we randomize the array using the Card Shuffling Algorithm.

We can consider the shuffled array of size k as an ordered tuple. The first element of this tuple can be picked with k ways, second can be picked with (k-1) ways [only k-1 elements remain], third can be picked with (k-2) ways and so on. This gives total number of ways to pick the k elements as k * (k-1) * ... * 1 = k! [k factorial]. This gels well with the fact that total number of permutation of k distinct elements is k!.

So we can consider our loop invariant to be that first element stays in its position with probability 1/r, second with probability 1/(r-1), ith with probability 1/(r-i+1), .. so on, where r is total number of elements. Now consider a new element from the stream, to maintain the loop invariant we swap it with element at the first place with probability 1/(r+1). This means that the first element stays with probability r/(r+1) [r/(r+1) * 1/r = 1/(r+1)]. So the first element is chosen in any case by probability 1/(r+1). Whichever element is swapped out is tested with second element with probability 1/r. We continue this process until all k elements are tested. After the end of the loop, the first element is its position with probability 1/(r+1), second with 1/r, so on. This maintains the loop invariant.

The following code observes the above loop invariant:

count = 0
while stream.notEmpty()
  count += 1
  A[count] = stream.element()
  if count == k
    break

while stream.notEmpty()
  count += 1
  e = stream.element()
  for i <- 1 to k
    p = random(1, count - i + 1) // including the end points
    if p == 1
      swap e <-> A[i]

return A[1..k]

Optimal Coin Change Problem

Problem: Given an unlimited supply of coins of denominations C1, C2, ..., CN we wish to make change for a value V. Give an algorithm for producing change with minimum number of coins.

Hint: Depending on denomination of coins, we can either use fast greedy algorithm or dynamic programming.
Solution: show

Consider two specific types of denominations of coins
a) 1, C, C^2, C^3, ..., C^(N-1)
b) 1, C, 2C, 3C, ...., (N-1)C

For both of these arrangements of coins the problem can be solved using the greedy approach. Clearly, we can see that if we first pay with the highest denomination coin, the value (for which change is required) reduces greatest (as compared to any lower denomination). Additionally we can see that optimal solution would require us to use as many highest denomination coin as possible. We can prove this claim using contradiction.

The greedy algorithm that is pretty fast and runs in O(N), is as follows:

change = 0
for j <- N to 1
  change += int(value/C[j])
  value = value % C[j]

assert(value == 0)
return change

The generic problem of coin change cannot be solved using the greedy approach, because the claim that we have to use highest denomination coin as much as possible is wrong here and it could lead to suboptimal or no solutions in some cases. For ex, if coin denomination are 1, 4, 6 and we want change for 8. Using one coin of denomination 6 forces us to use 2 coins of denomination 1, but clearly the optimal solution is to use 2 coin of denomination 4 each.

The key observation to make is the optimal structure of the sub-problem. If we assume for the time being that we have optimal change for all values < i. To produce change for value i, we need to add a coin to some previous solution with value < i.

==> change[i] = change[i - cj] + 1 
// add one coin cj and use optimal solution of i - cj 

we need to choose j that minimizes the value of change[i], the O(V * N) algorithm looks like the following:

change[0] = 0 // no coin required.
for i <- 1 to V
  change[i] = INF
  for j <- 1 to N
    if i >= C[j] and change[i] > change[i - C[j]]
      change[i] = 1 + change[i - C[j]]
return change[V]

For printing the choice of coin, we can keep a separate array to track which coin, cj was chosen for a given i.

Picking an Element Randomly from Stream

Problem: Given a finite stream of data elements, develop an algorithm to pick an element from the stream, randomly. Algorithm should guarantee that, every element of the stream has equal probability of getting picked. Additionally, we don't know the size of the stream until the stream actually finishes. We also have constant space, so all the elements of the stream can not be stored.

Hint: Once we see an element from the stream, we either store it or discard it with some probability, p.

Solution: show

This problem sounds hard due to lack of crucial data. Assume that we know the length of the stream, then the solution is trivial. Simply generate a random number between 1 and stream.length (say r). Then pick the rth element and declare it as the randomly chosen element. Here is the code for the same.

r = random(1, stream.length)
for i <- 1 to r-1
  stream.nextElement()
return stream.nextElement() // this is the randomly picked element

Now, since we don't know the length of the stream, this problem looks difficult. But surprisingly the solution is quite simple. Let us first build the loop invariant property for the solution.

Assuming we have seen n-1 elements and picked one element e, randomly so far with probability 1/(n-1). Now we see another element (say e1) , if we keep e with probability = (n-1)/n and replace it with e1 with probability 1/n, then e contains e1 with probability 1/n or an element from previously seen n-1 elements with probability = 1/(n-1) * (n-1)/n = 1/n.

Bingo, so we made sure that all elements are picked with uniform randomness. This loop invariant is adhered by the following code:

n = 0
e = Nil
while stream.hasElement()
  n += 1
  r = random(1, n) // including 1 and n
  if r == 1
    e = stream.nextElement()
return e

Generating Random Numbers

Problem: How to generate random integer between A and B, using an unbiased coin. For ex. If A = 3 and B = 6 then your algorithm should generate 3, 4, 5, 6 with equal probabilities.

Hint: The solution is non-deterministic.

Solution: show

Without loss of generality, we can generate random number between (and including) 0 and n, where n = B - A. Let r be the random number thus generated, we can then return r + A as the random number between A and B.

The number n can be represented using k bits where k = 1 + [log n] ([x] means greatest integer less than x). Now all the k-bits to code n can be generated randomly using the unbiased coin, this can be done trivially in O(k). If n = 2^k - 1 then the random number, r lies between (and including) 0 and n. Otherwise r could be greater than n with probability = 1 - (n + 1)/2^k. If that happens then repeat the experiment.

Pseudo code for the algorithm looks like the following:-

function random(A, B)
  n = B - A
  k = 1 + int(log n)
  r = 0

  for i = 1 to k
    bit = coin_toss(); // head means 1, tail means 0
    r += bit
    r <<= 1
    if r > n
      return random(A, B)

  return r

This function can go into infinite loop. Let us calculate the expected number of times random(A , B) is called. It is called once by the the actual caller and called again if r > n. Let us assume that the expected number of calls be e.

[note: e can be estimated by using the observation that random variable e - 1 is a geometric distribution]

The probability that r <= n is given as Pr(r <= n) = (n+1)/2^k. If n = 2^k - 1 then Pr(r <= n) = 1.

==> e = 1 * Pr(r <= n) + (1 + e) * Pr(r > n)
==> e = 1 / Pr(r <= n)
==> e = 2^k/(n+1)

Since, k = 1 + [log n]. For worst case analysis we can assume that k-1 lsb bits of n are 0. So n = 2^(k-1) with kth bit 1.

==> e = 2^k/(2^(k-1) + 1)
==> e = 2 - 2 / (2^(k-1)
==> e <= 2

So expected number of internal calls is at-most 1. This gives a good assurance against going into infinite loops.

Another way to reach above conclusion is by observing probability of failure, p = 1 - (n+1)/2^k < 1/2. Since the probability of failure is less than 1/2, the chances that we run into infinite loop is quite low.

The above solution can be explained in simpler terms as well. Assume that we have people numbered A to B and we are playing a tournament. In each round of the tournament, two players are paired up, they call on the coin toss, player who wins goes to next level. In case if pairs can not be formed we add dummies to form pairs. If a normal player wins we are done, but if dummy wins we repeat the experiment again.

So for example if we have 3, 4, 5, 6, 7 as initial number, and we add 'd' as dummy. Then a possible tournament could be as follows:

round 1: (3 vs 4) , (5 vs 6) , (7 vs d) --- winner --> 3, 5, d
round 2: (3 vs 5), (d vs d) -- winner --> 5, d
round 3: (5 vs d) -- winner --> 5

If d wins the last round, we repeat the experiment. This algorithm is just the same as earlier algorithm.

Finding Majority Element

Jargon: Majority Element is an element of an array that occurs more than half the number of times in the array. Also, [x] means smallest integer greater than x.

Easy Problem: Assume that an integer array A[1..n] has a majority element and elements other than majority element are distinct. How to find majority element. What's the space and time complexity of the algorithm ?

Answer: Time Complexity = n/2(comparisons), Space Complexity = O(1)

Solution: show

We will use pigeonhole principle to make our clever observations. There can be a maximum of [n/2]-1 elements that are distinct, remaining [n/2] element have to be same (as majority element exists in the array). We can consider that the [n/2]-1 distinct elements to be laid out and the space between two laid out elements to be a basket of infinite size. So we will have [n/2] baskets. If we try to distribute [n/2] majority element to these baskets, then in only one permutation will each basket get one element. Otherwise, some baskets would get more than one element and some baskets would remain empty.

Using this observation, we can claim that to find majority element we need to check adjacent elements for equality or two hop neighbor (adjacent to neighbor) for equality. That requires two comparison per element and the algorithm would look like this:

for i <- 1 to n-2
  if A[i] == A[i+1] or A[i] == A[i+2]
    return A[i]

A quick observation tells that this algorithm's for loop would stop when i=[3n/4]+1 even in worst case and the number of comparisons done will be ~ 3n/2. Now, we can make another clever observation that is, if we do not find two adjacent elements to be equal after complete scanning of array, then first element has to be majority element by pigeonhole principle.

for i <- 1 to n-1
  if A[i] == A[i+1]
    return A[i]
return A[1]

In Worst case this algorithms stops at i=n+1 and the number of comparisons done is = n-1. Even though this looks better than the first solution but it could be worse in practice. On a highly pipelined architecture with branch prediction, first one is much better than the second one, even though it does more comparisons per loop. So testing for large array sizes with random shuffling of elements will give clear insight into which algorithm is faster. Now an extremely clever solution which is based on observation that if we pair array elements and strike out a pair if its both the elements are distinct or else return the pair element as majority element. If all pair are striked out then what ever element is left has to be majority element.

i = 1
while i <= n 
  if A[i] == A[i+1]: return A[i]
  i+= 2

return A[n]

Worst case analysis tells that algorithms would stop when i=n-1 and the number of comparisons done is ~ n/2. This is indeed the best in worst case that we can do. Cheers

Hard Problem: Assume that an integer array A[1..n] has a majority element and elements other than majority element need NOT be distinct. How to find majority element. What's the space and time complexity of the algorithm?

Answer: Time Complexity=n(comparison), Space Complexity=O(1).

Solution: show

This algorithm uses an observation that if we consider our array to be list of voters and array value is the candidate to whom they are voting, then majority element is the winning candidate. Additionally, if all other candidates are merged to form one candidate then still it will fail to defeat the majority element candidate (hence the name majority element). So we can think of it this way. Assuming a negative vote decrease the count of majority element then still the count of majority element would be atleast 1. This algorithm implements the above idea.

element = A[1]
votes = 1
for i <- 2 to n:
  if A[i] == element
    votes += 1
  else if votes > 0
    votes -= 1
  else:
    element = A[i]
    votes = 1

return element

This algorithm takes n-1 steps in all cases. In worst case this algorithm performs n comparisons.

Note: Comparisons in this context means comparison between the actual array elements. Comparisons such as votes > 0 don't count as they are integer variable comparison.

Tip: Algorithms must be designed while keeping input into account. Additionally, if an algorithm performs many complex calculations then it doesn't necessarily is worse due to pipeline execution of instructions and branch predictions, pre-fetching and other advances in hardware.

Airplane Seating Problem

Problem: 100 passengers are boarding an airplane with 100 seats. Everyone has a ticket with his seat number. These 100 passengers boards the airplane in order. However, the first passenger lost his ticket so he just take a random seat. For any subsequent passenger, he either sits on his own seat or, if the seat is taken, he takes a random empty seat. What's the probability that the last passenger would sit on his own seat?

Answer: 1/2

Solution: show

Let us say that everyone is sitting except for the 100th passenger. Where can he sit. He can sit in either seat numbered 100 or 1. There cannot be any other seat vacant for him.

We can prove this using contradiction. Lets say that a seat numbered n=55 is vacant for 100th passenger. Since passenger 55 came earlier he should be sitting in his seat if its vacant. So seat 55 cant be vacant. This logic can be applied to all seats except for seat 1 and 100.

So all permutations of the seating arrangement would result in last person sitting in either seat 1 or seat 100. Both the options are equi-likely.

Tip: Some problems on probability can be easily solved for small values. Based on the observation of small values, it can be extended to large values.We can solve this problem for small value of n such as n=3 or n=4

Assume that there are 3 passengers only labeled p1, p2, p3. p1 can sit in seat 1 with probability = 1/3. In this case p3 sits in seat 3. p1 can sit in seat 2 with probability = 1/3, p2 can sit in either seat 1 or 3. so p3 gets to sit in his seat with probability = 1/3 * 1/2 = 1/6. p1 can sit in seat 3 with probability 1/3. In this case p3 can sit in seat 3 with probability = 0. ==> total probability for p3 to sit in his seat = 1/3 + 1/6 = 1/2

Tic Tac Toe

Source: Petr Mitrichev's Blog

Problem: Two players are playing a game and take alternating turns. There are 9 cards on the table with numbers from 1 to 9. On each turn, a player picks one card from the table. The first player to have 3 cards that total a sum of 15 wins. If no one can after all cards are distributed, then it's a draw. Can you tell who wins, assume both players are highly and equally intelligent and what is the winning strategy ?

Answer: Draw

Solution: show

If player 1 picks any card except for 5 then there are three ways he can pick second card in order to total 15. Player 2 will block one way in his following turn. Leaving two options for player 1. For any way that player 1 chooses, he has just one way now to total 15. Player 2 will block that way. Player 2 has blocked all ways of player 1 so far. But in the two moves so far player 2 has one way to reach 15. Player 1's next turn can block that. But, This analysis is hard to follow and unclear to see for all the possible combination.

This problem can be modeled in form of tic-tac-toe by constructing a 3 x 3 magic square, as follows:

4  9  2
3  5  7
8  1  6

Now all rows, diagonals, columns sum to 15. So the problem is reducible to playing a tic-tac-toe. Its easy to see that if two players are highly and equally intelligent then the game would result in a draw.

Math Magician

Source: International Maths Olympiad 2000

Problem: A magician has one hundred cards numbered 1 to 100. He puts them into three boxes, a red one, a white one and a blue one, such that each box contains atleast one card. A member of audience draws two cards from two different boxes and announces the sum of the number on those cards. Given this information magician locates the box from which no card has been drawn. How many ways are there to put the cards in the boxes so that the trick works.

Answer: 12

Solution: show

We split the possible arrangements into two different cases.

Case1: Assume that there exists an i such that i, i+1, i+2 go in different box (say wrb). Since, (i+1) + (i+2) = i + (i+3) => (i+3) should go in white box. Similarly i-1 should go in blue box. Since the pattern repeats without much choice so it boils down to assigning different boxes to first three cards. Total of 6 ways.

Case2: Assume that no three neighbours are put in different boxes. Let card 1 be in white box. Let i be the smallest card to go in red box (such that i > 2). Let j be the smallest card to go in blue box (such that j < 100). Let j > i.

==> i-1 is in white box.
==> i + j = (i-1) + (j+1)
==> j+1 is in white box.

==> i + (j+1) = (i+1) + j
==> i+1 is in blue box
==> j = i+1

This violates the main assumption from both ends i-1, i, i+1 are in different boxes and also i, i+1, i+2, hence j = 100. so that j+1 doesnt exist and both 99 and 98 belong to same box other than blue.

also (i-1) + 100 = i + 99 => card 99 is in red box => card 98 is in red box

but 2 + 99 = 1 + 100 => 2 is red. in general assume that there exists a card c (>1) and it belongs to white box and also c-1 to white box. => c + 99 = (c-1) + 100. which leads to failure of the trick. Assuming cards surrounding c are red. c + 99 = c-1 + 100 => failure of trick. Hence no such c exists and c=1 is the only card in white box.

hence the combination looks like wrrrr.........rrrrrb i.e. one card (value 1) in white box, one card (value 100) in blue box and rest all cards in red box. There are six ways of such arrangements.

Unbiased Coin Tossing

Given a biased coin, with probability of Heads equal to x. How to do unbiased coin tossing?

show

Lets define an event, E as tossing the biased coin twice. The possible outcomes with probabilities is as follows

P(h,h) = x^2
P(h,t) = x(1-x)
P(t,h) = x(1-x)
P(t,t) = (1-x)^2

The event h,t or t,h are equi-likely, without any bias we can call that if Event h,t occurs it means head, t,h means tails but if h,h or t,t occurs we repeat the experiment.

Try to find the expected number of coin toss that would be required to call heads or tails?

show

Let expected coin toss be e.

Probability that we get outcome in 1st event is 2x(1-x)
Total number of coin toss would be 2
Probability that we get no outcome in 1st event is [1 - 2x(1-x)]
Total number of coin toss would be 2 + e (we wasted 2 coin toss and still we expect e)

==> e = 2 * 2x(1-x) + (2+e) * [1 - 2x(1-x)]
==> e = 4x(1-x) + 2 - 4x(1-x) + e - 2ex(1-x)
==> e = 1/ [x(1-x)]

so for x = 1/2, e = 4
for x=2/3, e = 4.5
for x=1, e = INF (as expected, because all we get is chain of h h h h h)

What is the probability that there wont be any outcome in e coin tosses (expected outcomes)?

show

p = prob of e heads + prob of e tail
==> p = x^e + (1-x)^e

To find a bound on this p in polynomial terms can be done by using binomial expansion and Newtonian series is out of the scope of this blog. But some number crunching is.

For x = 1/2, e = 4, p = 0.125
For x = 2/3, e = 4.5, p = 0.168
For x = 3/4, e = 5.33, p = 0.216
For x = 0.99, e = 101, p = 0.362

This tells us that probability that outcome comes is quite good even for high coin biases.

How can we improve on the expected number of coin tosses?

show

In above method, we say that HT or TH terminates experiment. and continue the experiment a fresh when the outcome is HH or TT.

We can further combine outcome of two such events to increase the probability of outcome e.g. say HH TT => heads and TT HH means tails.

How much expected coin tosses are we doing in this case?

show

try

Cards Shuffling Problem

A common algorithmic problem of interest is Cards Shuffling Problem, which states that given a deck of cards shuffle it randomly. A naive algorithm for this problem can be written as:

for i <- 0 to cardLen
  r = random (0, cardsLen)
  exchange card[i] <-> card[r]

Assume there are two cards, we can see 4 possible combination of (i,r) namely (0,0), (0,1), (1,0), (1,1) leading to 2^2 outputs. If the two cards are {1,2} then probability of {1,2} after shuffling is 1/2 and of {2,1} is 1/2. Even though this algorithm looks correct, it is logically incorrect.

Actually there is a little bug in the above algorithm because of which it's incorrect. For N cards it generates N^N permutations, where as a card shuffle must generate N! permutations. Also N^N is not divisible by N!, hence a bias. A small change in above code makes it correct:

for i <- 0 to cardLen
  r = random (i, cardsLen)
  exchange card[i] <-> card[r]

Generating r randomly from between i and cardsLen ensures that once a card is swapped to a given i, it's position is fixed. Above algorithm, with iteration on cards in reverse order is Knuth-Fisher-Yates shuffle algorithm.