Thiyanesh
BAN USERbool start = true;
while (ptr1 != ptr2)
{
if (*ptr1 > 127 && start == true)
{
start = false;
}
else
{
start = true;
}
ptr1++;
}
if (start == false)
{
print "Second byte of 2 byte character";
}
else if (*ptr2 < 128)
{
print "One byte character";
}
else
{
print "First byte of two byte character";
}
Create a doubly linked list.
Do any order(pre, in, or post order) traversal and while we move left in the tree add the value in the current node to the current node in the doubly linked list and move left and vice versa for the right movement.
Now the final values in the doubly linked list will contain the sum values.
Also if we know the width of the tree, we can then create a integer array and then start from the root of the tree and corresponding index of the root in the tree width. then add the value in the root to the array[index]. Now if you move left decrement index or if you move right increment index.
now the final array will have the vertical sum of the tree.
Few questions
1) Is it a singly linked list or doubly linked list?
2) Are we allowed to use extra space?
3) If extra space is not allowed, then is the worst case time complexity less then O(n)?
4) Will this be called repeatedly for random nodes or just one off call?
1)Assume, the equals method is overridden correctly and hashcode is left to default implementation. Now
EqualsOnlyObject o1 = new EqualsOnlyObject();
HashSet hs = new HashSet();
EqualsOnlyObject o2 = o1.clone(); //As per equals, o1 == o2 (but what abt hashcode?)
hs.Add(o1); //Added successfully
hs.Add(o2); //this too is added successfully(default hashcode is unique, as its mostly the memory address of the object)
PRINT hs.Count(); //should print "2"
2)But assume if the hashcode is overridden properly then hs.Add(o2) should not add the object "o2" since they are identical.
- Thiyanesh March 15, 2010Let the two nodes be "A", "B" and "R" be the root.
*With Parent pointers:
1)Start at "A" and traverse to root following the parent pointer.
2)Let "L1" be the total number of nodes in the path "A" to "R".
3)Similarly let "L2" be the total number of nodes in the path "B" to "R".
4)If (L1 > L2), then start from "A" and move up "L1 - L2" nodes, else start from "B" and move up "L2 - L1" nodes.
5)Traverse up simultaneously in both the path until they reach a common node.
6)The common node is the least common ancestor.
*Without parent pointer
en.wikipedia.org/wiki/Tarjan's_off-line_least_common_ancestors_algorithm
@above: you have to store the an extra value to check for duplicates(assuming a number will occur only once in the intersection in case of duplicates on either side)
i = 0;
j = 0;
prev = a[0] < b[0] ? a[0] - 1 : b[0] - 1;
while (i < a.Length && j < b.Length) {
if (a[i] == b[j] && prev != a[i])
{
print a[i];
prev = a[i];
i++;
j++;
}
a[i] < b[j] ? i++ : j++;
}
If its only about alphabets then we can have a array of 26 integers and increment the count for the character each time a character occurs.
But i assume the question is not restricted to alphabets.
Then we have maintain a Dictionary and doubly linked list.(like any simple cache algo)
Declare a Dictionary with words as keys and the count as value.
Also have a min heap of size of 10% words.
Increment the count of a word in the dictionary every time a word occurs.
If the count for the current word is greater than root of the min queue, then replace the key of the root of the queue with the current word.
Hope you meant push 1,2,3,4 and pop 4,3,2,1.(Since we can't pop in the order 1,2,3,4.
This solution requires modification to get second minimum in O(1). Will post the solution tomorrow. But that solution requires a little space overhead. O(n) extra space in worst case.
Assumption: We are allowed to use extra space(there are no duplicates in the input, but this can easily extended to allow duplicates).
Implement a stack(STACK1) normally.
Have an extra stack(STACK2) such that when an element is pushed into the STACK1, check whether the number is lesser than the TOP[STACK2]. If true, then push the number in STACK1 and STACK2. Else push only on STACK1.
While poping an element compare the element with the TOP[STACK2]. If they are equal, the pop the element from STACK2 also.
Minimum element is the TOP[STACK2].
We can split the array into chunks of "x" elements and then store extra one index for storing the previous chunk of the same stack. In this way we can further minimize the storage requirements.(there may be a small subset of unfilled locations in few stacks even when few other stacks overflow.)
- Thiyanesh December 05, 2009First "n" locations in the array can be used as the top pointer of the stacks[1..n] respectively.
We need two index locations to store each element in the stack.
First index stores the element of the stack[i]. Then the next index stores the index of the previous element in the same stack[i].
maxindex = 1;
maxlen = 1;
for(index = 1 to str.length) {
for(cur = 1 to min(index, abs(str.length - index))) {
if(str[index + cur] == str[index - cur]) {
if(cur < maxlen) continue;
maxlen = cur;
maxindex = index;
}
}
}
May fail for the boundary conditions. But this the logic which i can think of for O(n2) complexity.
We need two such code blocks one for even length and one for the odd length.
Hence the time complexity is O(n2). O(1) space complexity
@Kunal
If one of the node is on the left side of the root and other is on the right side of the root, then root will be the LCA as per my above post.
But if the question really meant, "we can't compare two nodes(address)", then i don't have an answer now.("The nodes do not have any key elements or any other data to identify itself." as per the question)
Please do correct if i am missing something.
Let h1, h2 be the levels of the two nodes n1, n2 respectively in the tree(find the level by following the parent pointer)
if (h1 > h2) then follow the parent pointer of node n1 move up (h1 - h2) nodes.
else follow the parent pointer of n2 and move up (h2 - h1) nodes.
Now compare both the nodes n1 and n2 and follow the parent pointers until the common ancestor is found.
@random: When we use a min heap, we don't know when to update the heap or just leave off the incoming number from the stream.
So we need to use a max heap of size "N".
Initially construct a MAX HEAP of the first "N" input numbers from the stream
updateheap(H, num) {
if (H.GetRoot().GetValue() < num) return;
H.DecreaseKey(H.GetRoot(), num);
}
- Thiyanesh February 10, 2013