Problem:FindReverse of a tree.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
/* Linked List Node structure struct Node { int data; struct Node *next; } */ // Should reverse list and return new head. struct Node* reverse(struct Node *head) { // Your code here Node *curr=head; Node *prev=NULL; Node *nxt; while(curr!=NULL) { nxt=curr->next; curr->next=prev; prev=curr; curr=nxt; } head=prev; return head; } |
Problem:Balance check of a binary tree.
A tree is height balanced if difference between heights of left and right subtrees is not more than one for all nodes of tree.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
/* A binary tree node structure struct Node { int data; struct Node* left, * right; }; */ int mx(int a,int b) { if(a>b) return a; return b; } int height(Node *a) { if(a==NULL) return 0; return 1+mx(height(a->left),height(a->right)); } // This function should return tree if passed tree // is balanced, else false. Time complexity should // be O(n) where n is number of nodes in tree bool isBalanced(struct Node *root) { // Your Code here if(root==NULL) return 1; int lh=0,rh=0; lh=height(root->left); rh=height(root->right); if(lh==rh) return 1; else if(lh-rh==1 || lh-rh==-1) return 1; return 0; } |
Problem:Find Maximum Width of Tree.
Maximum width is maximum number of nodes in any level. The problem also given in Flipkartinterview.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 |
/* Structure of a Binary Tree struct Node { int data; struct Node* left, *right; }; */ /* Function to get the maximum width of a binary tree*/ int getMaxWidth(Node* root) { // Your code here if(root==NULL) return 0; int mxWidth; int levelOfNode[1005]; int level[105]; queue<Node*> cue; Node *tmp=root,*a; for(int i=0;i<1005;i++) levelOfNode[i]=-1; for(int i=0;i<105;i++) level[i]=0; levelOfNode[root->data]=0; cue.push(root); level[0]=1; mxWidth=1; while(cue.size()) { tmp=cue.front(); cue.pop(); if(tmp->left) { a=tmp->left; levelOfNode[a->data]=levelOfNode[tmp->data]+1; level[levelOfNode[a->data]]+=1; mxWidth=(mxWidth>level[levelOfNode[a->data]]?mxWidth:level[levelOfNode[a->data]]); cue.push(a); } if(tmp->right) { a=tmp->right; levelOfNode[a->data]=levelOfNode[tmp->data]+1; level[levelOfNode[a->data]]+=1; mxWidth=(mxWidth>level[levelOfNode[a->data]]?mxWidth:level[levelOfNode[a->data]]); cue.push(a); } } return mxWidth; } |
Problem:Find nodes of K distance from root
Print all nodes that are at distance k from root (root is considered at distance 0 from itself).It was given as question in Amazon interview.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 |
/* A binary tree node has data, pointer to left child and a pointer to right child / struct Node { int data; struct Node* left; struct Node* right; }; */ // Recursive function to print right view of a binary tree. void printKdistance(struct Node *root, int k) { // Your code here if(root==NULL) return; Node *tmp=root,*a; queue<Node*> cue; int levelOfNode[1005]; int nodeCountPerLevel[105]; for(int i=0;i<1005;i++) levelOfNode[i]=-1; for(int i=0;i<105;i++) nodeCountPerLevel[i]=0; levelOfNode[root->data]=0; nodeCountPerLevel[0]=1; cue.push(root); while(cue.size()) { tmp=cue.front(); cue.pop(); if(levelOfNode[tmp->data]==k) printf("%d ",tmp->data); if(tmp->left) { a=tmp->left; cue.push(a); levelOfNode[a->data]=levelOfNode[tmp->data]+1; nodeCountPerLevel[levelOfNode[a->data]]+=1; } if(tmp->right) { a=tmp->right; cue.push(a); levelOfNode[a->data]=levelOfNode[tmp->data]+1; nodeCountPerLevel[levelOfNode[a->data]]+=1; } } } |
Problem:Print the words of a given sentence reverse order separated by (.). Sentence will contain words and fullstops(.).
C++ Solution:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
#include <iostream> #include <string> using namespace std; int main() { int t,len; string str="",prev="",cur=""; cin>>t; t+=1; while(t--) { getline(cin,str); len=str.size()-1; if(str[len]=='.') len-=1; for(int i=len;i>=0;i--) { if(str[i]=='.') { cout<<prev<<"."; cur=""; prev=""; } else { cur.append(1u,str[i]); cur.append(prev); prev=cur; cur=""; } } if(prev.size()) cout<<prev<<"\n"; prev=""; } return 0; } |
python Solution:
|
1 2 3 4 5 6 |
t=int(raw_input()) for i in range(t): line=raw_input() mylist = line.split('.') mylist.reverse() print '.'.join(mylist).strip() |