Data Structure Questions

[varalu 0]

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?

 

[hr=noshade] [/hr]

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.

 

[hr=noshade] [/hr]

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

 

[hr=noshade] [/hr]

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.

Edited October 23, 2007 by varalu (see edit history)

[varalu 0]

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.

[varalu 0]

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

[varalu 0]

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.

[varalu 0]

Answer to Question 3

 

Was just wondering whats the practical use of this??

https://en.wikipedia.org/wiki/Lowest_common_ancestor

 

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

[iGuest 3]

Replying to varaluAnswer to your first questionApproch 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.StepsI> Sort the array/sequence of numbers using a inplace sorting technique having O(and.Lgn) order . Eg quicksort , heapsort etcNote 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 pointersA and BInitially 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 findAn element such thatSum 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 questionApproch 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.StepsI> Sort the array/sequence of numbers using a inplace sorting technique having O(and.Lgn) order . Eg quicksort , heapsort etcNote 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 pointersA and BInitially 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 findAn element such thatSum 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 questionApproch 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.StepsI> Sort the array/sequence of numbers using a inplace sorting technique having O(and.Lgn) order . Eg quicksort , heapsort etcNote 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 pointersA and BInitially 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 findAn element such thatSum 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 questionApproch 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.StepsI> Sort the array/sequence of numbers using a inplace sorting technique having O(and.Lgn) order . Eg quicksort , heapsort etcNote 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 pointersA and BInitially 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 findAn element such thatSum 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 questionApproch 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.StepsI> Sort the array/sequence of numbers using a inplace sorting technique having O(and.Lgn) order . Eg quicksort , heapsort etcNote 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 pointersA and BInitially 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 findAn element such thatSum 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 questionApproch 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.StepsI> Sort the array/sequence of numbers using a inplace sorting technique having O(and.Lgn) order . Eg quicksort , heapsort etcNote 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 pointersA and BInitially 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 findAn element such thatSum 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

[iGuest 3]

source code required.Data Structure QuestionsA source code for Tree is required having following chracteristics.* The node of the Tree should have atmost nine child nodes. The most node will have exactly nine child nodes.The child node of most will have 8 child nodes and number of child nodes will help decreasing down the tree in every level.* In short the node and sub nodes should have 9 child nodes.-question by shahdil

 

[iGuest 3]

Reply to angadData Structure Questions

Angad, your algorithm does not return the FIRST TWO numbers.If you apply your algoirthm to the example input array, it will return (12,88) instead of (49,51)Replying to (G)angad

-reply by vivek