## cuppanomics

BAN USER- 0 Answers
**Direct application to Job openings @ UK**Can Indians directly apply for job openings @ UK? If so, is the process straight-forward without going through agents. And would be great if someone could let me know which all companies take Indian s/w professionals directly.

- cuppanomics April 07, 2010

Thanks a lot!| Flag | PURGE

if (FirstCommonParent(x,y) == y) || (FirstCommonParent(y,z) == y)

y lies in the path of x & z

else

y doesn't lie in the path of x & z

The function FirstCommonParent(a,b) is the age-old classic problem. Don't have the link to it right now. Can someone point out common ancestor problem solution link for Binary Trees?

BTW, does the logic work fine?

@gevorgk: "Depth First Search of Binary tree"... Can you please elaborate on which kind of traversal do you intend to do. A pseudo code/algo would be great.. Didn't actually get it completely...

And how are you enlisting all the leaf nodes which differ by >1 level difference?

Thats right. Sorry, its just O(n).. Searching for the character in the auxiliary array is O(1)....

- cuppanomics May 12, 2010Perfect logic @lingrong

- cuppanomics May 11, 20101. Calculate the Payment-Cost, say X

2. Start dividing X with largest denomination and pay the remainder number of denominations. X = X - (Remainder no. * denomination)

3. Repeat step 2 until X == 0

Say cost is 75 cents

Payment done is 10$

X = 9.25

X % 10 = 0 ( 0 * 10)

X % 5 = 1 (1 * 5) X = 9.25 - 5 = 4.25

X % 1 = 4 (4 * 1) X = 4.25 - 4.00 = .25

X % 25 = 1 (1 * .25) X = .25 - .25 = 0

X == 0

@prolific.coder: More or less the logic would be the same, code is fine.

- cuppanomics May 11, 20101. Firstly, we need to enlist all the leaf nodes and their levels in the tree. In order to do this, do a Level order Traversal on the Tree (using queue) and store all leaf node and their levels into a 2d array (by verifying if the node doesn't have child nodes and maintaining a level variable in the recursive level order traversal).

2. Now that we have 2d array of all leaf nodes and its level, we need to find all array elements, wherein difference of levels is 2 or more. O(n square) time complexity we can find all nodes differing by 2 or more. Any better approach, please share.

The level order traversal in binary tree can be brought about by

```
void LevelOrderTraversal(Tree myBinTree) {
Queue myQ = new Queue();
Tree myTree = myBinTree;
int level = 0;
while(myTree != null) {
if(myTree.leftChild == null && myTree.rightChild == null)
Insert <myTree, level> into the 2d array
if(myTree.leftChild != null)
myQ.add(myTree.leftChild);
if(myTree.rightChild != null)
myQ.add(myTree.rightChild);
myTree = q.delete(myTree); //deletes the current node and returns the next node in Q
level++;
}
```

//Have to code the algo to find the nodes differing by >1 levels.

- cuppanomics May 11, 2010As we read on inputs, store the maximum odd int and minimum even int so far in two respective variables. At the end of all the inputs (user enters 0), we have ready the required output.

The company stressed on considering all input values i suppose, more of fuzzing logic (boundary conditions for inputs and stuff).

Discussion of this at the forum link

http[colon]//www[dot]daniweb[dot]com/forums/thread135355.html#

Also, can refer to design of chess game (since its a board game too). Can broadly design Checkers taking hints from Chess game design.

http[colon]//www[dot]nd[dot]edu/~cseprog/proj04_212/Chess_Hopkins_Oehmen_Lictenwalter/Final%20Project%20-%20Chess%20Game/cse212final.pdf

Lets call given input string, T and string that contains characters to be removed as S. 1. Create auxiliary array of 26 size representing the character set (alphabets). Set 1 in chars location if char occurs in S else 0

2. Read string T, if index[char]==1 in auxiliary array, then remove the char from string T.

This will be done in O(n) + O(m) = O(n) time complexity with constant space complexity (26 sized array).

@SachinSaner: Yes, I think so. The simple strategy should be sort each of the list first in O(nlogn) using Quick/Merge sort. And then merge these two sorted arrays in O(n). Any solution better than this?

- cuppanomics April 06, 2010Excellent Neo (for second solution!)

- cuppanomics April 01, 2010perfect Ashutosh. Thats a good mechanism to sort each word and store in hash.

The hash code can be made of primes too! Assign each alphabet a prime no., and then make the multiplication of these numbers a key, for e.g. if A=2, B=3, C=5, then hash key for word 'abc' (supposedly valid word) would be 30. No other combination of any other primes would have key 30, except for 'a', 'b' and 'c'.

Algo:

1. Find the start point of the cycle in the list (can be the first node or any of the middle ones). Pondering over a mechanism to detect this with only O(1) space complexity!!!

2. Delete the two lists separately in the same order below, viz.,

-- (Start point of cycle + 1) to end point of cycle

-- Start of list to start point of cycle

This would effectively help do in O(n)

If the sort order is to be maintained while merging and the two lists are already sorted, then its O(n)

If they are unsorted initially, but the final list needs to be sorted, then it will be O(n square)... Am I right?

Question unclear! Few clarifications requested...

1. Is 'i' given at runtime?

2. Does 'i' indicate the number of false statements below it? or does it signify something else?

**CareerCup**is the world's biggest and best source for software engineering interview preparation. See all our resources.

Open Chat in New Window

Both the solutions, by Ram and by Claudio have O(N^2) time complexity apart from O(N) space complexity. In both cases, iterating through the stack within the outer For Loop results in the O(N^2) time complexity.

- cuppanomics January 11, 2011O(N^2) time without any space complexity can be attained by the naive method of iterating through the array in traditional way (For loop inside For loop). Is there any O(N) solution possible in true way?