## 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

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

Open Chat in New Window

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;

}