limaye.nikhil
BAN USERWhy wouldn't this work? Please post your comment with an example of a tree, its mirror and INORDER traversals under a case where this doesnt work.
- limaye.nikhil November 29, 2010Step 1: Create a new array containing A[i] - B[i] elements. O(n)
Step 2: k=0, have a variable sum and add the values from i=0 to n from this new array. If the value goes negative at index j, reset k to j+1 and sum to 0. At the end k will be our index. One pass O(n)
Sample example:
A = [ 4 3 9 7 ]
B = [ 6 2 5 10 ]
Diff = [ -2 1 4 -3 ]
sum=0
k=0
sum=sum+Diff[0] = -2
reset k=1 and sum=0
sum=sum+Diff[1] = 1
Keep the sum to be 1 and k=1
sum=sum+Diff[2] = 5
Keep the sum=5 and k=1
sum=sum+Diff[3] = 2
Sum is still +ve, keep it and k=1 as well.
Array ends, we have k=1 --- answer.
Sorry..my bad...didnot read the definition of 'is same' clearly.
Thanks for correcting :)
Inorder is not sufficient to compare.
Need to check Inorder and Preorder traversals. If they are the same then BSTs are similar.
int swapbits(int num, int i, int j)
{
if(((num>>i&1)==1 && (num>>j&1)==1) || ((num>>i&1)==0 && (num>>j&1)==0))
return num;
num ^= 1<<i;
num ^= 1<<j;
return num;
}
In the case where index is invalid, I would assume it is the responsibility of the getword function to handle this scenario. Suppose it handles it by returning an empty string "". Once we get this empty string we can assume that the word is in the lower half of the interval. Applying this logic, a binary search would still work for [1024,2048] interval.
- limaye.nikhil November 21, 2010#include <iostream>
void PrintRobotPaths(std::string path, int row, int column, int totrows, int totcols)
{
if(column == totcols && row == totrows)
{
std::cout << path << std::endl;
return;
}
if(row == totrows)
{
std::string pc = path + " D";
PrintRobotPaths(pc, row, column+1, totrows, totcols);
return;
}
if(column == totcols)
{
std::string pr = path + " R";
PrintRobotPaths(pr, row+1, column, totrows, totcols);
return;
}
std::string pr = path + " R";
std::string pc = path + " D";
PrintRobotPaths(pr, row+1, column, totrows, totcols);
PrintRobotPaths(pc, row, column+1, totrows, totcols);
}
int main(int argc, char** argv)
{
int row=4;
int column=4;
std::string path;
PrintRobotPaths(path,1, 1, row, column);
return 0;
}
If space is a constraint, sort the strings inplace and compare - O(n logn)
If space is *not* a constraint, use a stl map with <chat,count> - O(n)
All this assuming the string lengths are the same or they are not empty, else just return false.
I don't think this can be done in less than O(n). We need to read the element at least once to decide if it is a duplicate. Reading itself will cost O(n).
- limaye.nikhil November 14, 2010std::string DecToBin(int x)
{
std::string bin;
if(!x)
return "0";
while(x)
{
std::ostringstream os;
os << (x&1);
x = x>>1;
bin = os.str() + bin;
}
return bin;
}
Node* merge(Node* n1, Node* n2)
{
if(n1 == NULL) return n2;
if(n2 == NULL) return n1;
Node* head=n1;
while(n1 != NULL && n2 != NULL)
{
Node* temp = n1->next;
if(n2 != NULL)
{
n1->next = n2;
n1 = temp;
}
temp = n2->next;
if(n1!=NULL)
{
n2->next = n1;
n2 = temp;
}
}
return head;
}
Language, location of the server where the pages are kept, meta information present in the web page regarding location like zip codes, area etc.
- limaye.nikhil November 13, 2010I dont think this is correct. You say for the 8th race, run the top cars from the prev 7 races and eliminate the first 6 thinking they will be in top 25. Assume A1...G1 won in this order. Now, all we know is that A1>B1>C1...>G1. There can be a possibility than all cars from A1..A7 to E1..E7 are faster than F1. Then how will F1 be still in the top 25? In this case it will be 36th.
- limaye.nikhil November 13, 2010Solution w/o recursion uses the prev sum to calculate the next level's sum. Recursion solution uses the map to find the prev calculated sums for different levels.
- limaye.nikhil November 12, 2010int fibboNoRecursion(int x)
{
int a=0,b=1,sum=0;
for(int i=0;i<x;++i)
{
sum = a + b;
a = b;
b = sum;
}
return sum;
}
int fibboRecursion(int x, std::map<int,int>& fibboMap)
{
if(fibboMap.find(x-1) != fibboMap.end() && fibboMap.find(x-2) != fibboMap.end())
{
int val = fibboMap.find(x-1)->second + fibboMap.find(x-2)->second;
fibboMap.insert(std::pair<int,int>(x,val));
return val;
}
if(x == 0 || x == 1)
return 1;
return fibboRecursion(x-1,fibboMap) + fibboRecursion(x-2,fibboMap);
}
I don't think this is possible. You need to at least read the elements once to make a decision whether they are duplicates. Reading itself would be O(n).
- limaye.nikhil November 12, 2010
Your first tree is not even a BST. please check that. How can 5 come as the right child of 10 when 5 is less than 10.
- limaye.nikhil December 09, 2010