/* The structure of a BST node is as follows:
struct node
{
int data;
struct node * right, * left;
}; */
void printNearNodes(node *root, int l, int h)
{
// your code goes here
node *p=root;
if(p->data>=l && p->data<=h)
{
if(p->left)
printNearNodes(p->left,l,h);
printf("%d ",p->data);
if(p->right)
printNearNodes(p->right,l,h);
}
else
{
if(p->left)
printNearNodes(p->left,l,h);
if(p->right)
printNearNodes(p->right,l,h);
}
}
/* A binary tree node
struct Node
{
int data;
struct Node* left, * right;
}; */
/*you are required to
complete this function */
bool hasPathSum(Node *node, int sum)
{
//Your code here
Node *tmp=node;
if(node->left==NULL && node->right==NULL && sum==node->data)
return true;
if(sum<node->data)
return false;
if(sum>node->data)
{
bool res=false;
if(node->left)
{
res=hasPathSum(node->left,sum-node->data);
}
if(res)
return res;
if(node->right)
{
res=hasPathSum(node->right,sum-node->data);
}
return res;
}
return false;
}
//The Celebrity Problem(microsoft)
// The task is to complete this function
int getId(int M[MAX][MAX], int n)
{
//Your code here
int arr[45];
for(int i=0;i<45;i++)
arr[i]=0;
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
if(i!=j && M[j][i]==1)
arr[i]+=1;
}
if(arr[i]==n-1)
return i;
}
return -1;
}
Solution Hints: LIFO and FIFO property of queue and stack is used respectively.
/* A tree node has data, pointer to left child
and a pointer to right child
struct node
{
int data;
struct node* left;
struct node* right;
}; */
void reversePrint(struct node *root)
{
node *tmp;
queue<node *> cue;
stack<node *> st;
cue.push(root);
while(cue.size())
{
tmp=cue.front();
cue.pop();
st.push(tmp);
if(tmp->right)
cue.push(tmp->right);
if(tmp->left)
cue.push(tmp->left);
}
while(!st.empty())
{
tmp=st.top();
printf("%d ",tmp->data);
st.pop();
}
}
Problem Description:
Given a Binary Tree, your task is to print its level order traversal where each level is separated by $
For the below tree the output will be 1 $ 2 3 $ 4 5 6 7 $ 8 $
1
/ \
2 3
/ \ / \
4 5 6 7
\
8
Input:
The task is to complete the method which takes one argument, root of Binary Tree. The struct Node has a data part which stores the data, pointer to left child and pointer to right child.
There are multiple test cases. For each test case, this method will be called individually.
Output:
The function should print the level order traversal of the tree as specified in the problem statement.
Approach:
used 2 arrays alternating to store the next level nodes.There should be a better way using queue and/or stack.
void levelOrder(struct Node* node)
{
//Your code here
Node *prev[2005];
Node *prev2[2005];
bool found=0;
int alt=0;
int edx=1;
int idx;
prev[0]=node;
while(1)
{
idx=0;
found=0;
if(alt==0)
{
for(int i=0;i<edx;i++)
{
if(prev[i])
{
printf("%d ",prev[i]->data);
if(prev[i]->left)
{
prev2[idx]=prev[i]->left;
idx+=1;
found=1;
}
if(prev[i]->right)
{
prev2[idx]=prev[i]->right;
idx+=1;
found=1;
}
}
}
edx=idx;
}
else
{
for(int i=0;i<edx;i++)
{
if(prev2[i])
{
printf("%d ",prev2[i]->data);
if(prev2[i]->left)
{
prev[idx]=prev2[i]->left;
idx+=1;
found=1;
}
if(prev2[i]->right)
{
prev[idx]=prev2[i]->right;
idx+=1;
found=1;
}
}
}
edx=idx;
}
alt=1-alt;
if(found==0)
break;
printf("$ ");
}
printf("$");
}
Problem Description:
check if 2 given binary trees are identical.
/* A binary tree node
struct node
{
int data;
struct Node* left, * right;
}; */
/* Should return true if trees with roots as r1 and
r2 are identical */
bool isIdentical(Node *r1, Node *r2)
{
//Your Code here
if(r1==NULL && r2==NULL)
return 1;
if(r1==NULL)
return 0;
if(r2==NULL)
return 0;
if(r1 && r2 && r1->data!=r2->data)
return 0;
if(r1 && r2 && r1->data==r2->data)
{
if(isIdentical(r1->left,r2->left)==0)
return 0;
if(isIdentical(r1->right,r2->right)==0)
return 0;
return 1;
}
//return 0;
}
Problem Description:
Given a Binary Tree and 2 nodes value n1 and n2 , your task is to find the lowest common ancestor of the two nodes . You are required to complete the function LCA . You should not read any input from stdin/console. There are multiple test cases. For each test case, this method will be called individually.
/* A binary tree node
struct node
{
int data;
struct Node* left, * right;
}; */
/*you are required to
complete this function */
Node * LCA(Node* root ,int n1 ,int n2 )
{
//Your code here
vector<int>path;
vector<int>path2;
Node* a;
Node* b;
Node* res;
Node* tmp=root;
int par[1005];
int nodes[1005];
int t;
for(int i=0;i<1005;i++)
{
par[i]=0;
nodes[i]=0;
}
queue<Node*> cue;
cue.push(root);
nodes[root->data]=root->data;
while(cue.size())
{
tmp=cue.front();
cue.pop();
if(tmp->left)
{
a=tmp->left;
par[a->data]=tmp->data;
nodes[a->data]=a->data;
cue.push(a);
}
if(tmp->right)
{
a=tmp->right;
par[a->data]=tmp->data;
nodes[a->data]=a->data;
cue.push(a);
}
}
path.clear();
t=n1;
path.push_back(t);
while(t!=root->data)
{
t=par[t];
path.push_back(t);
}
path.push_back(t);
path2.clear();
t=n2;
path2.push_back(t);
while(t!=root->data)
{
t=par[t];
path2.push_back(t);
}
path2.push_back(t);
int len1=path.size();
int len2=path2.size();
int len;
if(len1<=len2)
len=len1;
else
len=len2;
// res=new Node;
// res->data=path2[len-2];
// return res;
int i=len1-1;
int j=len2-1;
//for(i=len-1;i>=0;i--)
while(i>=0 && j>=0)
{
if(path[i]!=path2[j])
{
break;
}
else
{
i--;
j--;
}
}
res=new Node;
res->data=path[i+1];
return res;
}
Insert A Node:
/* The structure of a BST node is as follows:
struct node {
int data;
struct node * right, * left;
}; */
//Inserts an element with value val to the BST
void insert(node ** root, int val)
{
// Your code here
node *tmp=(*root);
if(tmp==NULL)
{
tmp=new node;
tmp->data=val;
(*root)=tmp;
return;
}
node *a;
if(tmp->data>val)
{
if(tmp->left)
{
insert(&(tmp->left),val);
}
else
{
node *n=new node;
n->data=val;
tmp->left=n;
}
}
else if(tmp->data<val)
{
if(tmp->right)
{
insert(&(tmp->right),val);
}
else
{
node *n=new node;
n->data=val;
tmp->right=n;
}
}
}
BFS Problem:
/* You have to complete this function
which prints out the breadth first level traversal of the
graph starting from node s
the vector<int> g[i] represent the adjacency
list of the ith node of the graph
*/
void bfs(int s, vector<int> g[], bool vis[])
{
queue<int> cue;
cue.push(s);
int a;
while(!cue.empty())
{
a = cue.front();
vis[a]=1;
printf("%d ",a);
cue.pop();
for(int i=0;i<g[a].size();i++)
{
if(vis[g[a][i]]==0)
{
cue.push(g[a][i]);
vis[g[a][i]]=1;
}
}
}
}
Problem Description:
Implement a queue using two stacks.
/* The structure of the class is
class StackQueue{
private:
// These are STL stacks ( http://goo.gl/LxlRZQ )
stack<int> s1;
stack<int> s2;
public:
void push(int);
int pop();
}; */
/* The method push to push element into the queue */
void StackQueue :: push(int x)
{
// Your Code
s1.push(x);
}
/*The method pop which return the element poped out of the queue*/
int StackQueue :: pop()
{
// Your Code
int a;
if(s2.size()==0)
{
while(s1.size())
{
a=s1.top();
s1.pop();
s2.push(a);
}
if(s2.size())
{
a=s2.top();
s2.pop();
return a;
}
else
return -1;
}
a=s2.top();
s2.pop();
return a;
}
Problem description:
A sorted array A[ ] with distinct elements is rotated at some unknown point, the task is to find the minimum element in it.
Expected Time Complexity: O(Log n)
Solution approach: using binary search
#include <stdio.h>
int main() {
//code
int t,n,i;
int lw,hi,mid,prev_mid,mid_next;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
int arr[n];
for(i=0;i<n;i++)
scanf("%d",&arr[i]);
lw=0;
hi=n-1;
while(lw<=hi)
{
mid=(lw+hi)/2;
prev_mid=(n-1+mid-1)%(n-1);
mid_next=(n-1+mid+1)%(n-1);
if(arr[mid]<=arr[prev_mid] && arr[mid]<=arr[mid_next])
{
hi=mid;
lw=mid;
break;
}
else if(arr[mid]>arr[hi])
lw=mid+1;
else
hi=mid;
}
printf("%d\n",arr[mid]);
}
return 0;
}
Find Diameter Of a Binary Tree:
/* Tree node structure used in the program
struct Node
{
int data;
struct Node* left, *right;
}; */
int height(struct Node* root)
{
if(root == NULL) return 0;
else {
int l = height(root->left);
int r = height(root->right);
return (l>r)?(l+1):(r+1);
}
}
/* Computes the diameter of binary tree with given root. */
int diameter(struct Node* node)
{
if(node == NULL)
return 0;
else
{
int lh = height(node->left);
int rh = height(node->right);
int ld = diameter(node->left);
int rd = diameter(node->right);
int mx = (rd>ld?rd:ld);
return ((lh + rh+1) > mx)? (lh + rh+ 1):mx;
}
}