March 26, 2010

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

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 hash-tables improve the running time of your algorithm.

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

March 19, 2010

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

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

Answer: Both survive the battle.

Solution: show

March 18, 2010

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: (12,6,4,2)

Solution: show

Source Code: david_kids_ages.py

March 11, 2010

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 = 4, end = 7)

Solution: show

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

February 3, 2010

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