Question 1
Reply the solutions if you have any so that we can discuss...

Given an array of n elements (containing only positive numbers) and sum, X. Find the first two elements in the array that sum upto X

eg: Array of elements - {2, 3,1000, 200, 51, 88, 29, 49, 65, 40, 98, 12, 3}

Sum - 100.

The answer for the above sample is 51, 49.

There are other possiblities also, but the first two numbers summing upto the given sum, 100 should be taken.
How will you do this with minimal space and time complexities?

---

Question 2

Given two nodes of a binary tree (implemented in a linked list without a parent pointer) and a head pointer, find out the common ancestor of the two nodes with minimal space and time complexities...

Not necessary for an perfect answer...any answer will be appreciated...

Many posts will refine the solution more. Thanks.

---

Question 3

Given two nodes of a Binary Search Tree (implemented using linked list without a parent pointer) and the head pointer, find out the common ancestor of the two nodes with minimal space and time complexities...

All answers will be greatly appreciated...

---

Question 4
This was asked in an interview with GOOGLE.

Given an array (dont consider the data type of the element) of 2n elements with first n integer elements and next n character elements.

i1 i2 i3 ....in c1 c2 c3 ....cn

Write an in-place algorithm to rearrange these elements in the following order.

i1 c1 i2 c2 i3 c3....incn.

in-place algorithm means that the memory used in the algorithm other than the input array should not be dependent on the size of the input.... Also keep this in mind -- Time and space complexity.

This post has been edited by varalu: Oct 23 2007, 01:42 PM

Answer to question 1

1. keep 2 pointers
2. Initially first one points to first element and second one points to the next
3. Calculate the total.
4. If this total < required total, move the second pointer alone to the next one and continue
else if this total> required total, move the first pointer alone to the next one and continue
5. Continue this process until the total equals required total.

Note:

* This can be used in a similar way to find the first 2 elements that differs by a given number
* It works for set with negative numbers also

Please come up with any case that could fail.

PS: Solution suggested by one of my friends.

I have found one combi that fails.... .

Given -- {40, 20, 10, 30, 80}
Sum -- 50

Actual solution shud have been from values 40(1st ele) and 10(3rd ele).
But the algo fails....

Another answer to question 1

Use a hash table
hash function = (X- an element in the array)
This function returns the key value,Array element can be used as index in the hash table stored along with the key value...
Every time a key is calculated it is checked whether the element is present in the table

time complexity O(n)
ya space wise its pooor

working........

Array of elements - {2, 3,1000, 200, 51, 88, 29, 49, 65, 40, 98, 12, 3}

Sum - 100.

X=100

till 51 the hash table values are


2 98
3 97
51 49
200 -100
1000 -900

for 88 and 29

2 98
3 97
29 71
51 49
88 12
200 -100
1000 -900

now when 49 is taken key = (100-49)=51
but 51 is already present as index

Solution suggested by my friend -- Daya.

Answer to Question 3

Was just wondering whats the practical use of this??
http://en.wikipedia.org/wiki/Lowest_common_ancestor

The above wiki link explains things. Also gives applications where the "common ancestor" thing can be used...