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;
}
use recursion for below triangle
void print(int k,int s){
if(s==1){
return;
}
print(k-1,s-1);
cout<<"*"<<k;
}
main()
{
int i,t,n;
int k=10;
int size=4;
while(size!=0){
print(k,size);
k=k-size+1;
k--;
size--;
cout<<"\n";
}
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";
}
}
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=size-2;
}
else r=size-1;
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;
}
Repgladyskcombs, Personnel at Green Bricks
Hello, I am Gladys. I am a Industrial Photographer. I started off my photographic career as a News photographer based ...
- JerryGoyal May 22, 2015