## sumeet.kukkar

BAN USERNumber of one' s present in 'n'

- sumeet.kukkar January 26, 2014Code: this is not very elegant code but it works.

static void findPivot()

{

int low = 0;

int index = 3;

int high = index + 1;

int []input = { -2, 3, 5, 0, -3, 7, -1};

while(low < index && high < input.length)

{

while(input[low] < 0 && low < input.length)

low++;

while(high < input.length && input[high] > 0)

high++;

if(low < high && high <input.length)

{

int temp = input[low];

input[low] = input[high];

input[high] = temp;

}

}

for(int i =0; i < input.length; i++)

{

System.out.println(input[i]);

}

}

Using the idea of quick sort but with small tweak. In order to maintain the order, starting low pointer from 0th element and high pointer from index of element with value zero + 1. And doing normal partition of quicksort.

- sumeet.kukkar January 25, 2014'n' is number of children of root.

- sumeet.kukkar November 19, 2012@Anjana, We can introduce another parameter like while calculating hash-function by Abhishek.

New function hash-count look like:

h = 31*h*count+ascii(char(i));

for calculating h1 -> increment count from 1 to half of the list i.e. 6 in this case.

And for calculating h2-> decrease count from 6 to 1. This way hash function will start considering order of the character in the string.

I think the answer is segment trees... a segment tree is a tree data structure for storing intervals, or segments. It allows querying which of the stored segments contain a given point. It is, in principle, a static structure; that is, its content cannot be modified once the structure is built

- sumeet.kukkar October 15, 2012**CareerCup**is the world's biggest and best source for software engineering interview preparation. See all our resources.

Open Chat in New Window

Approach: It is stated that node has child and parent properties. We can make use of parent property.

- sumeet.kukkar January 27, 20141. Start traversing from both the nodes using parent pointers'

2. For any one node, start pushing the nodes traveled in a hashtable. For another node traversal, keep check the node is present or not in hashtable. If node is present the found which is LCA of two nodes.

Probably have to work out the details where one traversal finishes before the other one but that can be easilly handled in the code.

If we want to avoid using any extra memory, we can treat this two list with one merging point. Which can be easily solved in O(h).