Data Structure Questions

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.

 

 

 

Comment/Reply (w/o sign-up)

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.

Comment/Reply (w/o sign-up)

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....

 

 

 

Comment/Reply (w/o sign-up)

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.

Comment/Reply (w/o sign-up)

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...

Comment/Reply (w/o sign-up)

Replying to varalu Answer to your first question Approch you have used is a "brute force" technique , a better way to do this is by "divide and conquer". First let knows what is inplace algos. It has a memory cost of O(f(and)) it requires extra memory which is of order of some function of and. Any algo using O(1) ie constant amount of memory is inplace algo. Steps I> Sort the array/sequence of numbers using a inplace sorting technique having O(and.Lgn) order . Eg quicksort , heapsort etc Note we can not use merge sort though it has order O(and.Lgn)as it is not inplace sorter ie. Requires auxillary memory of the order O(and). II> Keep two pointers A and B Initially A point to the first element in the array or the sequence of numbers given . B points to the second. III> Then from the element pointed by B to the nth element , do a binary search by moving the B pointer (in the first iteration it will be from 2nd to nth and in third iteration it will be from 3rd to nth element) . This binary search will take at max (approx.) O(lgn) to find An element such that Sum of the element pointed by A and B is equal to the SUM given. IV> If no such element is found in the binary search move the pointer A to next element ie increment it. Now make the B pointer point to element just next to A pointer . Go to step III. This method is inplace algo and has worst case cost = O(and.Lgn) Answer to your first question Approch you have used is a "brute force" technique , a better way to do this is by "divide and conquer". First let knows what is inplace algos. It has a memory cost of O(f(and)) ie requires extra memory which is of order of some function of and. Any algo using O(1) ie constant amount of memory is inplace algo. Steps I> Sort the array/sequence of numbers using a inplace sorting technique having O(and.Lgn) order . Eg quicksort , heapsort etc Note we can not use merge sort though it has order O(and.Lgn)as it is not inplace sorter ie. Requires auxillary memory of the order O(and). II> Keep two pointers A and B Initially A point to the first element in the array or the sequence of numbers given . B points to the second. III> Then from the element pointed by B to the nth element , do a binary search by moving the B pointer (in the first iteration it will be from 2nd to nth and in third iteration it will be from 3rd to nth element) . This binary search will take at max (approx.) O(lgn) to find An element such that Sum of the element pointed by A and B is equal to the SUM given. IV> If no such element is found in the binary search move the pointer A to next element ie increment it. Now make the B pointer point to element just next to A pointer . Go to step III. This method is inplace algo and has worst case cost = O(and.Lgn) Answer to your first question Approch you have used is a "brute force" technique , a better way to do this is by "divide and conquer". First let knows what is inplace algos. It has a memory cost of O(f(and)) ie requires extra memory which is of order of some function of and. Any algo using O(1) ie constant amount of memory is inplace algo. Steps I> Sort the array/sequence of numbers using a inplace sorting technique having O(and.Lgn) order . Eg quicksort , heapsort etc Note we can not use merge sort though it has order O(and.Lgn)as it is not inplace sorter ie. Requires auxillary memory of the order O(and). II> Keep two pointers A and B Initially A point to the first element in the array or the sequence of numbers given . B points to the second. III> Then from the element pointed by B to the nth element , do a binary search by moving the B pointer (in the first iteration it will be from 2nd to nth and in third iteration it will be from 3rd to nth element) . This binary search will take at max (approx.) O(lgn) to find An element such that Sum of the element pointed by A and B is equal to the SUM given. IV> If no such element is found in the binary search move the pointer A to next element ie increment it. Now make the B pointer point to element just next to A pointer . Go to step III. This method is inplace algo and has worst case cost = O(and.Lgn) Answer to your first question Approch you have used is a "brute force" technique , a better way to do this is by "divide and conquer". First let knows what is inplace algos. It has a memory cost of O(f(and)) ie requires extra memory which is of order of some function of and. Any algo using O(1) ie constant amount of memory is inplace algo. Steps I> Sort the array/sequence of numbers using a inplace sorting technique having O(and.Lgn) order . Eg quicksort , heapsort etc Note we can not use merge sort though it has order O(and.Lgn)as it is not inplace sorter ie. Requires auxillary memory of the order O(and). II> Keep two pointers A and B Initially A point to the first element in the array or the sequence of numbers given . B points to the second. III> Then from the element pointed by B to the nth element , do a binary search by moving the B pointer (in the first iteration it will be from 2nd to nth and in third iteration it will be from 3rd to nth element) . This binary search will take at max (approx.) O(lgn) to find An element such that Sum of the element pointed by A and B is equal to the SUM given. IV> If no such element is found in the binary search move the pointer A to next element ie increment it. Now make the B pointer point to element just next to A pointer . Go to step III. This method is inplace algo and has worst case cost = O(and.Lgn) Answer to your first question Approch you have used is a "brute force" technique , a better way to do this is by "divide and conquer". First let knows what is inplace algos. It has a memory cost of O(f(and)) ie requires extra memory which is of order of some function of and. Any algo using O(1) ie constant amount of memory is inplace algo. Steps I> Sort the array/sequence of numbers using a inplace sorting technique having O(and.Lgn) order . Eg quicksort , heapsort etc Note we can not use merge sort though it has order O(and.Lgn)as it is not inplace sorter ie. Requires auxillary memory of the order O(and). II> Keep two pointers A and B Initially A point to the first element in the array or the sequence of numbers given . B points to the second. III> Then from the element pointed by B to the nth element , do a binary search by moving the B pointer (in the first iteration it will be from 2nd to nth and in third iteration it will be from 3rd to nth element) . This binary search will take at max (approx.) O(lgn) to find An element such that Sum of the element pointed by A and B is equal to the SUM given. IV> If no such element is found in the binary search move the pointer A to next element ie increment it. Now make the B pointer point to element just next to A pointer . Go to step III. This method is inplace algo and has worst case cost = O(and.Lgn) Answer to your first question Approch you have used is a "brute force" technique , a better way to do this is by "divide and conquer". First let knows what is inplace algos. It has a memory cost of O(f(and)) ie requires extra memory which is of order of some function of and. Any algo using O(1) ie constant amount of memory is inplace algo. Steps I> Sort the array/sequence of numbers using a inplace sorting technique having O(and.Lgn) order . Eg quicksort , heapsort etc Note we can not use merge sort though it has order O(and.Lgn)as it is not inplace sorter ie. Requires auxillary memory of the order O(and). II> Keep two pointers A and B Initially A point to the first element in the array or the sequence of numbers given . B points to the second. III> Then from the element pointed by B to the nth element , do a binary search by moving the B pointer (in the first iteration it will be from 2nd to nth and in third iteration it will be from 3rd to nth element) . This binary search will take at max (approx.) O(lgn) to find An element such that Sum of the element pointed by A and B is equal to the SUM given. IV> If no such element is found in the binary search move the pointer A to next element ie increment it. Now make the B pointer point to element just next to A pointer . Go to step III. This method is inplace algo and has worst case cost = O(and.Lgn) -reply by angad

Comment/Reply (w/o sign-up)