JerryGoyal
BAN USER 1of 1 vote
AnswersFind the shortest path between a start node and end node in a undirected +ve weighted graph.
You are allowed to add at max one edge between any two nodes which are not directly connected to each other.
ex:
From  To  Weight
1 2 2
1 4 4
2 3 1
3 4 3
4 5 1
start node = 1, end node = 5.
extra edge weight = 2.
 JerryGoyal in United States1(2)2     (4) (1)     5(1)4(3)3 In this case answer would be 3 (from 1  > 5  > 4) Solution: 1(2)2 /  /   (2)/ (4) (1) /   /   5(1)4(3)3
 Report Duplicate  Flag  PURGE
Google Software Developer Algorithm  1of 1 vote
Answersgiven 2 strings A and B. generate all possible solutions when B is merged in A.
 JerryGoyal in India
Ex: A = "hey"
B: "sam"
then solutions are :
heysam,hseaym,hesaym,sahemy etc.
notice that order should be the same for both of strings while merging. Report Duplicate  Flag  PURGE
Google Software Developer Algorithm
 0 Answers given 2 strings generate all possible permutation (order should be maintained!)
given 2 strings A and B. generate all possible solutions when B is merged in A.
 JerryGoyal May 22, 2016
Ex: A = "hey"
B: "sam"
then solutions are :
heysam,hseaym,hesaym,sahemy etc.
notice that order should be the same for both of strings while merging. Flag  PURGE  0 Answers Given a complete binary tree find if it is a value balanced tree or not.
A tree is called value balanced tree if for all nodes, sum of values (assume the values are integers) of nodes in left hand side is equal to sum of values in right hand side.
 JerryGoyal May 10, 2015
Given a complete binary tree find if it is a value balanced tree or not.
Test Case 1
3
1 1 1
Tree is value balanced
Test Case 2
7
3 0 1 1 1 2 2
Tree is not value balanced
Test Case 3
15
22 2 4 3 1 0 4 4 4 2 2 2 2 4 4
Tree is value balanced
can it be done without creating tree data structure, solely from array? Flag  PURGE
2 methods to find diameter in O(n)
1. use hashing: store height of every node in hash table > O(2n)
map <node*,int> h;
int height(struct node* node)
{
if(node == NULL)
return 0;
int a=height(node>left);
int b=height(node>right);
h[node]= 1 + max(a,b);
return h[node];
}
int diameter(struct node * tree)
{
if (tree == 0)
return 0;
int lheight = h[tree>left];
int rheight = h[tree>right];
int ldiameter = diameter(tree>left);
int rdiameter = diameter(tree>right);
return max(lheight + rheight + 1, max(ldiameter, rdiameter));
}
2. use postorder traversal in height fuction and keep updating value of diameter to leftheight + rightheight +1 > O(n)
int dia(node* root,int *d){
int lheight, rheight;
if(!root) return 0;
lheight=dia(root>left,d);
rheight=dia(root>right,d);
if(lheight+rheight+1>*d) *d=lheight+rheight+1;
return 1+ max(lheight,rheight);
}
int diameter(node* root){
int d=0;
dia(root,&d);
return d;
}

JerryGoyal
April 19, 2015 use recursion for below triangle
void print(int k,int s){
if(s==1){
return;
}
print(k1,s1);
cout<<"*"<<k;
}
main()
{
int i,t,n;
int k=10;
int size=4;
while(size!=0){
print(k,size);
k=ksize+1;
k;
size;
cout<<"\n";
}

JerryGoyal
April 10, 2015 here's the right code of your logic
void printRow(int n) {
int startNum = n * (n  1) / 2 + 1;
while(n > 0) {
cout << startNum++;
if(n > 1)
cout << " * ";
n;
}
}
void print(int n) {
int i = 1;
while(i <= n){
printRow(i++);
cout<<"\n";
}
i;
while(i > 0){
printRow(i);
cout<<"\n";
}
}

JerryGoyal
April 10, 2015 here's the recursive implementation in C for above approach:
int flag=0;
int search(int list[], int lo, int hi, int key)
{
int mid;
if (lo > hi)
{
return hi;
}
mid = (lo + hi) / 2;
if (list[mid] == key)
{ flag=1;
return mid;
}
else if (list[mid] > key)
{
search(list, lo, mid  1, key);
}
else if (list[mid] < key)
{
search(list, mid + 1, hi, key);
}
}
int search(int list[],int x,int size){
int l=0,r;
if(size%2==0){
r=size2;
}
else r=size1;
int pos=search(list,x,l,r);
if(flag){
return pos;
}
if(list[pos+1]==x){
return pos+1;
}
pos=search(list,list[pos+1],l,r);
if(list[pos+1]==x){
return pos+1;
}
else return 1;
}

JerryGoyal
April 10, 2015 Open Chat in New Window
 JerryGoyal May 22, 2015