amritaansh123
BAN USERI dont understand why do we need sliding window or any other such complication, its a simple liner traversal algo:
O(n)
void findmax (int a[], int k, int n) {
int count = 0;
int max = Integer.MIN_Value;
int i = 0;
while ( i < n) {
while (count < k && i < n) {
if (a[i] > max) {
max = a[i];
}
count++;
i++;
}
System.out.println(max);
count = 0;
max = Integer.Min_Value;
}
}
I suppose that the question is to construct an expression tree given an infix expression:
Infix: (6*2)/3
Convert this to postfix using the standard method involving a stack:
Postfix: 62*3/
Algo: (Create another empty stack)
1. Scan thpostfix string from left to right, for each element:
-If you encounter a number, create its treenode and pust it onto the stack
-if you encounter an operator(*/+-), create its treenode, pop twp nodes from the stack, and make them this operator node's children, then push the operator node into the stack.
2. Continue till the string is exhausted.
3. the Last node in the stack now is a tree representing the expression.
Here's the complete code, this question is indeed similar to the one for checking if a tree is BST or not but the tricky part is avoiding memory leaks:
node trim (node root, int a, int b) {
if(root == null)
return null;
if(root.data > a && root.data < b) {
root.left = trim(root.left, a, b);
root.right = trim(root.right, a, b);
return root;
} else if(root.data < a){
node temp = root.right;
freeTree(root.left);
free(root)
return trim(temp, a, b);
} else if(root.data > b) {
node temp = root.left;
freeTree(root.right);
free(root);
return trim(temp, a, b);
}
}
//postOrder traversal Deletion
void freeTree (node n) {
if(n == null)
return;
freeTree(n.left);
freeTree(n.right);
free(n)
}
Actually there is no need for the level parameter :
int complete (node root) {
if(root == null)
return -1;
else
return 1 + Math.min(complete(root.left), complete(root.right));
}
Simple code using two queues:
Node clone(Node root) {
if(null == root)
return null;
Queue<Node> q1 = new LinkedList<Node>();
q1.add(root);
Queue<Node> q2 = new LinkedList<Node>();
Node root2 = new Node(root.data);
q2.add(root2);
Node n, fresh;
while(!q1.isEmpty()) {
n=q1.remove();
fresh = q2.remove();
if(null != n.left) {
q1.add(n.left);
fresh.left = new Node(n.left.data);
q2.add(fresh.left);
}
if(null != n.right) {
q1.add(n.right);
fresh.right= new Node(n.right.data);
q2.add(fresh.right);
}
}
return root2;
}
*correction, sum of Y coords must be constant and not zero
- amritaansh123 February 15, 2013The method to store coordinates in each leaf recursively, and extracting them in two arrays is definitely the right way. How ever we need to confim if the trees have to be joined with/without rotation. If the trees have to be joined after rotationg one of them by 180 degrees, then sum of y coordinates of all pairs of leaves is 0. But sum of x coordinates need not be zero, example, We can join a tree of height 2 with a tree of height 100 if they have the same number of leaves properly aligned. So what we should check is that the distance of the leftmost leaf to each other leaf should be the same in both the trees, heres some code, Call assignCoord(root, 0, 0);
void assignCoord (node root, int x, int y) {
if(root == null)
return;
root.x = x;
root.y = y;
assignCoord(root.left, x-1, y+1);
assignCoord(root.right, x+1, y+1);
}
Class Coord {
int x;
int y;
public Cord(int a, int b) { x = a; y = b}
}
ArrayList<Coord> list1 = new ArrayList<Coord> ();
ArrayList<Coord> list2 = new ArrayList<Coord> ();
call addLeaf(root, list1) and addLeaf(root, list2)
void addLeaf (node root, ArrayList<Coord> l) {
if(root == null)
return;
if(root.left == null && root.right == null) {
Coord temp = new Coord(root.x, root.y);
l.add(temp);
addLeaf(root.left, l);
addLeaf(root.right, l);
}
//pseudocode
Boolean check (ArrayList<Coord> l1, ArrayList<Coord> l2) {
if (l1.size() != l2.size())
return false;
//traverse l1 from left to right and l2 from right to left
//sum of y should be constant;
//distance of leftmost leaf in l1 to all other leaves in l1, should be the same as dist of rightmost leaf in l2 to all other leaves in l2
}
Oh, i hadnt' thought of that, sorry, makes sense now. Why dont we hash them by straight away using the key as the 3 letter string?
- amritaansh123 February 13, 2013ascii value of a = 97 e = 101 c = 99 sum = 297
a = 97 d = 100 d = 100, sum is again 297,
so you wont be able to tell them apart.
Wont work as we will have uniqueness issues with encoding 3 chars as an Integer, for example, aec and add will encode to the same ASCII value??
- amritaansh123 February 12, 2013Nope, the algo is correct, it cannot return "abbcd", as as soon as you process 'b', the value of its mapping in the hashmap will reduce below zero and you will discard this substring.
- amritaansh123 February 12, 2013Java code: call checkBST (root, Integer.MIN_Value, Integer, MAX_Value)
Boolean checkBST (node root, int min, int max) {
if(root == null)
return true;
if(min < root.data && root.data < max)
return checkBST(root.left, min, root.data) && checkBST(root.right, root.data, max);
else
return false;
}
Seems like the easiest to understand code, I am not sure if inplace is feasible for this problem?
- amritaansh123 February 11, 2013Scala is so confusing, why would anyone ever want to use this language??
- amritaansh123 February 11, 2013Awesome solution:
Here's the code in C:
Time complexity : O(nlog(n)), as there are n nodes in list, and inserting each node in BST takes O(log(n)), and finding succesor takes O(log(n)).
typedef struct treenode {
int data;
treenode *left;
treenode *right;
} treenode;
void processList (node *head) {
treenode *root = NULL;
node *p, *q;
p = head;
while (p != NULL) {
insertInBst(&root, p->data);
p = p->next;
}
q = head;
while (q != NULL) {
q->next_larger = findSuccesor(root, q->data);
q = q->next;
}
}
treenode* successor (treenode* r, int x) {
treenode* elem = search(r, x);
if (elem == NULL) {
return NULL;
} else if (elem->right != NULL ) {
return minimum(elem->right);
} else {
treenode *p = elem->parent;
while (p != NULL && p->left != elem) {
p = p->parent;
elem = p;
}
if (p == NULL) {
return NULL;
} else {
return p;
}
}
}
treenode* minimum (treenode* t) {
if (t == NULL) {
return NULL;
}
while (t->left != NULL) {
t = t->left;
}
return t;
}
treenode* search (treenode* r, int x) {
if (r == NULL) {
return NULL;
} else if (r->data == x) {
return r;
} else if (r->data > x) {
return search(r->left, x);
} else {
return search(r->right, x);
}
}
- amritaansh123 February 17, 2013