Sunday, June 2, 2013

[Amazon Online test] Sort an array containing 0, 1 & 2

Given that an array consists of only 0s 1s and 2s sort the array in one pass.

Approach: 

Lets view the problem if the constraint of one pass wouldn't have been there
Scan over the array and count the number of 0, 1, and 2.
Now initialise the array with the 0, 1, 2 with the number of elements, the idea is similar to the counting sort.

To solve the above problem in one pass we can use the famous Dutch national flag algorithm.
The basic idea is to traverse over the array and keep track of the current 0s and 2s and the read pointers(initialised with -1, n and 0). Now traverse the array and keep swapping the current element in the respective buckets of interest.


[Expedia Interview] Intersection of two link list

Given two link lists intersecting in the following manner


 check whether the two list intersect or not, if it does find the point of intersection.


Saturday, June 1, 2013

Cumulative Sums of elements in an array[Binary Indexed Tree]

Given a array and with below possible operations
Update: Add a value to a index a
Query: Get a cumulative sum from a range a to b
 What is the data structure you would employ and what will be the time complexity of the update and query operations.

Approach:
The basic idea of any of the algorithm is to store/update the sum of the subparts and compute the sum in a range by adding up the relevant subparts.So for e.g a common data structure Segment tree creates a tree where the parent stores the sum of the child elements.