prabu
BAN USER- 0of 0 votes
AnswersGiven a tree with following special property, develop an algorithm to find the LCA of two input nodes. Only O(1) variables can be used.
- prabu in United States
property - all nodes have information only about their parents not their children.| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 0of 0 votes
AnswersGiven a sequence of integers, find the length of the longest ascending or descending sub-sequence.
- prabu in United States
eg : input {3, 5, 8 , 9, 3, -1, -4, -5, -6}
output : length = 6 (corresponding to the descending sequence {9, 3, -1, -4, -5, -6}| Report Duplicate | Flag | PURGE
Socialcam Algorithm
The algo in the blog is cool....
One small change, we dont have to apply it for each row... instead convert the same algorithm to 2D using "summed area table"....
Search "summed area table" and read the wiki page for more details....
1. replace 0's with -1.
2. calculate the summed area table.
3. Hash each value in the table. If it is not in the table "add the 2D index" otherwise check whether the size of the rectangular box is greater than the max_size and update the max_size if necessary.
In worst case, the algorithm is O(mn) excluding the "summed area table" calculation.
- Please correct me if I am wrong
Thank you
another solution to this is to use "deque"
1. odd levels - print the node value from the bottom and push the child nodes to the top
2. even levels - print the node value from the top end and push the child nodes to the bottom
always pop the node after printing its value
also we will have a couple of O(1) memory - one to track the number of elements to print during the current print option and other one is for the number of elements in the next level.
Please correct me if I am wrong
I have tested the code with the given elements. I did not run many tests on it. I believe it will work fine.
- prabu November 29, 2012The algorithm is similar to the one that checks whether the "given tree is a BST".
Let me know your ideas on this.
#include <iostream>
#include <climits>
using namespace std;
struct node {
int val;
node *left;
node *right;
};
int po[]={9,6,4,3,5,7,8,15,13,14,19}; // pre-order elements
int itr=1;
void buildBST(node *r, int min, int max ) {
if ((po[itr]<r->val) && (po[itr]>min)) {
node *temp=new node;
temp->val=po[itr];
r->left=temp;
itr++;
buildBST(temp,min,r->val);
}
if ((po[itr]>r->val) && (po[itr]<max)) {
node *temp=new node;
temp->val=po[itr];
r->right=temp;
itr++;
buildBST(temp,r->val,max);
}
}
node *build (int l) {
node *root=new node;
root->val=po[0];
buildBST (root, INT_MIN, INT_MAX); // call to build tree
return root;
}
void preordertr(node *r) {
if (r!=NULL) {
cout<<r->val<<endl;
preordertr(r->left);
preordertr(r->right);
}
}
int main() {
int l=sizeof(po)/sizeof(int);
node *root=build(l); // build tree
preordertr(root); // check whether tree is correct
return 0;
}