Sibendu Dey
BAN USERPreparing For Google!!
hmm yes may be its an binary tree but the idea is same ,we need to find the LCA and then print the path through LCA
- Sibendu Dey July 18, 2013Just need to find the path from node1 to node 2 throught the LCA of both nodes.
#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<string.h>
using namespace std;
struct node {
int data;
struct node *left;
struct node *right;
};
void printPath(int num,struct node *LCA) {
if(num==LCA->data) {
cout<<LCA->data<<" ";
return;
}
struct node *temp=LCA;
if(num<LCA->data)
LCA=LCA->left;
else
LCA=LCA->right;
printPath(num,LCA);
cout<<temp->data<<" ";
}
void findMaxPath(int num1,int num2,struct node *root) {
struct node *num1LCA=root;
struct node *num2LCA=root;
struct node *LCA=root;
while(num1LCA==num2LCA) {
if(num1 < num1LCA->data)
num1LCA=num1LCA->left;
else
num1LCA=num1LCA->right;
if(num2<num2LCA->data)
num2LCA=num2LCA->left;
else
num2LCA=num2LCA->right;
if(num1LCA==num2LCA)
LCA=num1LCA;
}
cout<<"Path from node1 to root\n";
printPath(num1,LCA);
cout<<"\nAnother path starting from node 2 to root\n";
printPath(num2,LCA);
return;
}
// FUNCTION TO INSERT NODES IN THE BINARY TREE
void insertNode(struct node **root,int data) {
// CREATES THE ROOT NODE
if(*root==NULL) {
(*root)=(struct node*)malloc(sizeof(struct node));
(*root)->data=data;
(*root)->left=NULL;
(*root)->right=NULL;
return;
}
// FOR CREATION OF OTHER NODES
if(data < (*root)->data) {
insertNode((&(*root)->left),data);
}
else {
insertNode((&(*root)->right),data);
}
return;
}
// DRIVER FUNCTION
int main() {
struct node *root=NULL;
// TAKES THE INPUT FOR INSERTION
do {
int data;
scanf("%d",&data);
if(data!=-1) {
insertNode(&root,data);
}
else {
break;
}
}while(1);
findMaxPath(10,14,root);
return 0;
}
Here's an implementation of @Anonymous suggestion in C++
#include<stdio.h>
#include<iostream>
#include<string.h>
#define N 4
#define M 5
using namespace std;
// Prints the nearest bathroom
void printNearestBathroom(int rowPos,int colPos) {
cout<<"The nearest bathroom is at:"<<rowPos<<" "<<colPos;
return;
}
void bfs(int matrix[][M],int startPosRow,int startPosCol) {
int queue[N*M][2];
bool visited[N][M];
for(int i=0;i<N;i++) {
for(int j=0;j<M;j++) {
visited[i][j]=false;
}
}
int front,rear;
front=rear=-1;
queue[++rear][0]=startPosRow;
queue[rear][1]=startPosCol;
visited[startPosRow][startPosCol]=true;
front++;
while(front<=rear) {
int currRow=queue[front][0];
int currCol=queue[front][1];
if(matrix[currRow][currCol]==0) {
printNearestBathroom(currRow,currCol);
return;
}
front++;
if( currRow>0 && visited[currRow-1][currCol]==false ) {
queue[++rear][0]=currRow-1;
queue[rear][1]=currCol;
visited[currRow-1][currCol]=true;
}
if(currCol>0 && visited[currRow][currCol-1]==false ) {
queue[++rear][0]=currRow;
queue[rear][1]=currCol-1;
visited[currRow][currCol-1]=true;
}
if(currCol!=M-1 && visited[currRow][currCol+1]==false ) {
queue[++rear][0]=currRow;
queue[rear][1]=currCol+1;
visited[currRow][currCol+1]=true;
}
if(currRow!=N-1 && visited[currRow+1][currCol]==false ) {
queue[++rear][0]=currRow+1;
queue[rear][1]=currCol;
visited[currRow+1][currCol]=true;
}
}
}
int main() {
int matrix[N][M]={ {1,1,1,1,0}, // 1 denotes a room and 0 denotes a bathroom
{1,1,1,1,1},
{1,1,0,1,0},
{1,1,0,1,0}
};
bfs(matrix,2,1);
return 0;
}
Here is the code in c++
#include<stdio.h>
#include<iostream>
#define ROW 4
#define COL 4
using namespace std;
void printActualCapacity(float actualCapacity[][COL]) {
for(int i=0;i<ROW;i++) {
for(int j=0;j<=i;j++) {
cout<<actualCapacity[i][j]<<" ";
}
cout<<"\n";
}
}
void fillCapacity(int litres) {
float actualCapacity[ROW][COL];
float excessCapacity[ROW][COL];
for(int i=0;i<ROW;i++) {
for(int j=0;j<COL;j++) {
actualCapacity[i][j]=excessCapacity[i][j]=0.0f;
}
}
actualCapacity[0][0]=(litres>=1.0f? 1.0f:litres);
excessCapacity[0][0]=(litres>=1.0f ?litres-1.0f:0.0f);
for(int i=1;i<ROW;i++) {
for(int j=0;j<=i;j++) {
if(excessCapacity[i-1][j]>0) {
actualCapacity[i][j]+=(excessCapacity[i-1][j]/2 >= 1.0f ? 1.0f: excessCapacity[i-1][j]/2 );
excessCapacity[i][j]+=(excessCapacity[i-1][j]/2 >= 1.0f ? excessCapacity[i-1][j]/2 - 1 : 0.0f );
excessCapacity[i-1][j]=excessCapacity[i-1][j]/2;
}
if(j-1>=0 && excessCapacity[i-1][j-1]>0) {
if(actualCapacity[i][j]==1) {
excessCapacity[i][j]+=excessCapacity[i-1][j-1];
excessCapacity[i-1][j-1]=0;
}
else {
excessCapacity[i][j]=excessCapacity[i-1][j-1]+actualCapacity[i][j] > 1 ? excessCapacity[i-1][j-1]+actualCapacity[i][j] -1 : 0;
actualCapacity[i][j]= excessCapacity[i-1][j-1]+actualCapacity[i][j] >=1 ? 1 :excessCapacity[i-1][j-1] + actualCapacity[i][j];
}
}
}
}
printActualCapacity(actualCapacity);
}
int main() {
fillCapacity(6);
}
Well sorry my bad.Haven't read the question properly.
- Sibendu Dey July 17, 2013Can you please tell me if there any restriction on the capacity of glasses after the 1st glass?The capacity above which water will overflow from that glasses??
- Sibendu Dey July 17, 2013Suppose there is a word called dog in the dictionary and and a substring called dea it will return 1 according to your tree but that not a valid word
- Sibendu Dey July 16, 2013Maintain the dictionary in the form of trie and then check for correctness of words.If the sentence is correct,return the words by lookup in the trie or return false if sentence is wrong.
- Sibendu Dey July 16, 2013@varun:im not talking about time complexity .Counting sort takes o(n) extra space which in that case is not allowed by the interviewer.
- Sibendu Dey July 16, 2013Isn't it sorting in o(n) method will take o(n) extra space.???
- Sibendu Dey July 15, 2013@Anonymous:-According to what I said..
first array in increasing order:- -6789 1 34
second array in decreasing order :- 5 1 -6789
minimum value = -6789 * 5 + 1*1 + 34*(-6789)
The idea here is to find the lowest common ancestor of the given nodes and then print the path from first given node to second given node through the LCA.
The code is
#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<string.h>
using namespace std;
struct node {
int data;
struct node *left;
struct node *right;
};
void printPath(int num,struct node *LCA) {
if(num==LCA->data) {
cout<<LCA->data<<" ";
return;
}
struct node *temp=LCA;
if(num<LCA->data)
LCA=LCA->left;
else
LCA=LCA->right;
printPath(num,LCA);
cout<<temp->data<<" ";
}
void findMaxPath(int num1,int num2,struct node *root) {
struct node *num1LCA=root;
struct node *num2LCA=root;
struct node *LCA=root;
while(num1LCA==num2LCA) {
if(num1 < num1LCA->data)
num1LCA=num1LCA->left;
else
num1LCA=num1LCA->right;
if(num2<num2LCA->data)
num2LCA=num2LCA->left;
else
num2LCA=num2LCA->right;
if(num1LCA==num2LCA)
LCA=num1LCA;
}
cout<<"Path from node1 to root\n";
printPath(num1,LCA);
cout<<"\nAnother path starting from node 2 to root\n";
printPath(num2,LCA);
return;
}
// FUNCTION TO INSERT NODES IN THE BINARY TREE
void insertNode(struct node **root,int data) {
// CREATES THE ROOT NODE
if(*root==NULL) {
(*root)=(struct node*)malloc(sizeof(struct node));
(*root)->data=data;
(*root)->left=NULL;
(*root)->right=NULL;
return;
}
// FOR CREATION OF OTHER NODES
if(data < (*root)->data) {
insertNode((&(*root)->left),data);
}
else {
insertNode((&(*root)->right),data);
}
return;
}
// DRIVER FUNCTION
int main() {
struct node *root=NULL;
// TAKES THE INPUT FOR INSERTION
do {
int data;
scanf("%d",&data);
if(data!=-1) {
insertNode(&root,data);
}
else {
break;
}
}while(1);
findMaxPath(10,14,root);
return 0;
}
@bvarghese: Doesn't matter as you have given two arrays.In the first array multiplying the -ve number with the largest number will result in a minimum value.Similarly the largest element from first array get multiplied with the -ve element from second array.
- Sibendu Dey July 13, 2013yes the question seems to be incorrect or incomplete
- Sibendu Dey July 13, 2013Yes I'm searching for that iterative solution but unable to get so.
- Sibendu Dey July 13, 2013This is the implementation of @IM.first idea.
#include<stdio.h>
#include<iostream>
#include<stdlib.h>
using namespace std;
#define N 5
int compare(const void *p1,const void *p2) {
return *(int *)p1-*(int *)p2;
}
int compare2(const void *p1,const void *p2) {
return *(int *)p2-*(int *)p1;
}
int findMinimum(int *arr1,int *arr2) {
qsort(arr1,N,sizeof(int),compare);
qsort(arr2,N,sizeof(int),compare2);
int minimum=0;
for(int i=0;i<N;i++) {
minimum+=arr1[i]*arr2[i];
}
return minimum;
}
int main() {
int arr1[]={3,2,7,4,-1};
int arr2[]={4,12,10,8,9};
cout<<"The minimum value is:"<<findMinimum(arr1,arr2);
return 0;
}
@eugene : Well I need to print them.Oh then you want to say that there is no such solution with time complexity less than what the backtracking problem gives.
- Sibendu Dey July 13, 2013@Anonymous:-Then the question has straight-forward answer..
- Sibendu Dey July 12, 2013@yolo-then we can just check whether the root has children.That itself proves that it contains a subtree.
- Sibendu Dey July 12, 2013Yes when do we say that a tree contains a subTree.I want to say there may be some preconditions.
- Sibendu Dey July 12, 2013Just made use of the basic approach to construction of trees from inorder
and preorder traversals.
#include<stdio.h>
#include<stdlib.h>
#include<iostream>
using namespace std;
struct node {
int data;
struct node *left;
struct node *right;
};
struct node * constructTree(int *preorder,int startPre,int endPre,int *inorder,int startIn,int endIn) {
if( startPre>endPre || startIn>endIn)
return NULL;
int temp=preorder[startPre];
int rootIndex;
for(rootIndex=startIn;rootIndex<=endIn;rootIndex++) {
if(inorder[rootIndex]==temp) {
break;
}
}
struct node *root=(struct node *)malloc(sizeof(struct node));
root->data=inorder[rootIndex];
root->left=constructTree(preorder,startPre+1,startPre+rootIndex-startIn,inorder,startIn,rootIndex-1);
root->right=constructTree(preorder,startPre+rootIndex-startIn+1,endPre,inorder,rootIndex+1,endPre);
return root;
}
void displayTree(struct node *root) {
if(root==NULL)
return;
displayTree(root->left);
cout<<root->data<<" ";
displayTree(root->right);
}
int main() {
int preorder[]={30,13,23,14,25,50,45,40,60};
int inorder[]={13,14,23,25,30,40,45,50,60};
struct node *root=NULL;
root=constructTree(preorder,0,8,inorder,0,8);
displayTree(root);
return 0;
}
#include<stdio.h>
int printDESposition(char [][]matrix,char *word,int i,int j,int trackrow[3],int trackcol[3][3],int indexTrackrow,int indexTrackcol) {
if(i-1 >=0 && j-1>=0 && matrix[i-1][j-1]==word[0]) {
trackrow[indexTrackrow]=i-1;
trackrow[indexTrackcol]=j-1;
if(indexTrackrow==2) {
printPositions(trackrow,trackcol);
}
else {
printDESposition(matrix,++word,i-1,j-1,trackrow,trackcol,++indexTrackrow,++indexTrackcol);
--word;
--indexTrackrow;
--indexTrackcol;
}
// Similarly for the other 7 conditions code needs to be filled up..
}
}
int main() {
char matrix[][] = {{"A","N", "L", "Y", "S"},{"I", "S", "D", "E", "S"},{"I", "G", "N", "D", "E"}};
char *word="DES";
int trackrow[3];
int trackcol[3];
indexTrackrow=0;
indexTrackcol=0;
for(int i=0;i<5;i++) {
for(int j=0;j<5;j++) {
if(matrix[i][j]==word[0]) {
trackrow[indexTrackrow]=i;
trackcol[indexTrackcol]=j;
printDESposition(matrix,++tempWord,i,j,trackrow,trackcol,++indexTrackrow,++indexTrackcol);
}
--word;
--indexTrackrow;
--indexTrackcol;
}
}
}
Trie data structure can be used.IF that word's spelling is wrong then the function returns False.or else True
#include<stdio.h>
struct trie {
struct trie *edges[26];
}
// Initailizes memory for trie t
trie *initializeTrie(struct trie *t) {
t=(trie *)malloc(sizeof(trie));
for(int index=0;index<26;index++) {
t->edges[index]=NULL;
}
return t;
}
// Adds a word to the existing trie
trie *addWord(struct trie *t,char *word) {
if(word[0]=='/0') {
}
else {
int index=t[0]-'a';
if(t->edges[index]==NULL) {
t->edges[index]=initializeTrie(t->edges[index]);
}
t->edges[index]=addWord(t->edges[index],++str);
}
return t;
}
// Checks whether the word's spelling is correct or not
bool spellChecker(trie *t,char *word) {
if(word[0]=='/0')
return true;
else {
int index=word[0]-'a';
if(t->edges[index]!=NULL) {
spellChecker(t->edges[index],++word);
}
else
return false;
}
}
// Driver function to implement Spell Checker
int main() {
Trie *t=(trie *)malloc(sizeof(trie));
// Suppose the dictionary consists of four words
t=addWord(t,"Sibendu");
t=addWord(t,"Hello");
t=addWord(t,"Bhubaneswar");
t=addWord(t,"India");
bool check1=spellChecker(t,"Sibendu"); // Returns true
bool check2=spellChecker(t,"Subendu"); // Returns false
}
Yes it should be the longest..
- Sibendu Dey July 04, 2013Just a little modification to the dynamic approach..I used a LISindex array to keep track of the element that comes before the current element.If any doubts ,Give a reply
#include<stdio.h>
#include<stdlib.h>
int lis( int arr[], int n )
{
int *lisindex=(int *)malloc(sizeof(int) * n);
int *lis, i, j, max = 0;
lis = (int*) malloc ( sizeof( int ) * n );
int lastLISindex;
int check,k=0;
for ( i = 0; i < n; i++ )
lis[i] = 1;
for ( i = 1; i < n; i++ ) {
for ( j = 0; j < i; j++ ) {
if ( arr[i] > arr[j] && lis[i] < lis[j] + 1) {
lis[i] = lis[j] + 1;
lisindex[i]=j;
}
}
}
/* Pick maximum of all LIS values */
for ( i = 0; i < n; i++ ) {
if ( max < lis[i] )
max = lis[i];
lastLISindex=i;
}
int *arrSeq=(int *)malloc(sizeof(int) * max);
for(int index=max-1;index>=0;index--) {
arrSeq[index]=arr[lastLISindex];
lastLISindex=lisindex[lastLISindex];
}
for(int index=0;index<max;index++) {
printf("%d ",arrSeq[index]);
}
/* Free memory to avoid memory leak */
free( lis );
return max;
}
/* Driver program to test above function */
int main()
{
int arr[] = { 10, 22, 9, 33, 21, 50, 41, 60 };
int n = sizeof(arr)/sizeof(arr[0]);
lis( arr, n );
getchar();
return 0;
}
#include<iostream>
using namespace std;
int findStartingPoint(int *arrCapacity,int *arrDistance,const int size) {
int arrSubDistance[size];
for (int index=0;index<size;index++) {
arrSubDistance[index]=arrCapacity[index]-arrDistance[index];
}
int start=0;
int sum=arrSubDistance[start];
int currPetrolPump=start+1;
int count=1;
while(true) {
if(count==size) {
return start;
}
else if(sum<0) {
sum-=arrSubDistance[start];
start=(start+1)%size;
if(start==0)
return -1;
count--;
if(currPetrolPump<start) {
currPetrolPump=start;
}
}
else {
sum+=arrSubDistance[currPetrolPump];
count++;
}
}
}
int main() {
int arrCapacity[]={2,2,2};
int arrDistance[]={4,6,3};
int startPos=findStartingPoint(arrCapacity,arrDistance,3);
cout<<startPos;
return 0;
}
Can be easily done by using binary search
#include<iostream>
#include<stdio.h>
using namespace std;
int findRotation(int *arr,int length) {
int low=0;
int high=length-1;
while(low<=high) {
int mid=(int)(low+high)/2;
if(arr[mid]>arr[mid-1] && arr[mid]>arr[mid+1])
return mid+1;
else if(arr[mid]<arr[mid+1] && arr[mid]>arr[mid-1]) {
high=mid-1;
}
else
low=mid+1;
}
return -1;
}
int main() {
int arr[]={13,20,22,24,2,3,4};
int NRotation=findRotation(arr,7);
cout<<NRotation;
}
How about this??
Store the first line in a string.
Compare first line with second.If not equal then compare third line with first.If they are equal then second is unique else first.
If equal then iterate till you find the unique one.
How about maintaining an array for the pool??
- Sibendu Dey June 28, 2013Consider the unit's digit place,each of 4,3,2,1 appears 6 times each.So at the digit place ,this adds to (4+3+2+1)*6=60.Now 6 gets carried forward to the tens place.Similarly at ten's place,it adds to (4+3+2+1)*6+6(the carry)=66.Now again the 6 is carried forward till we get 66660.
- Sibendu Dey June 26, 20131)Check whether the sender has sufficient balance or not
2)If bal AVL then charge as per applicable plan else deny sending message
3)Check whether the recipient is avl or not
4)If avl then deliver the message to recipient else backup the message and set a time limit of X hours for delivery.
5)If X hours passes then remove the message entry from the back up.
Repjoyceclark, Graphics Programmer at Denmin Group
I am Joyce, a highly talented and passionate writer expert in storytelling. Outside of my writing profession, I’ve hobbies ...
RepI am Susan From Wasilla USA. and my strong interest in yoga and reading historical books. I have a large ...
RepSpent 2001-2004 selling UFOs for the government. Have some experience with Internet Marketing Services New York. Set new standards for ...
@vgeek:Why are you so worried about votes?If you have written the code right,right people will definitely praise you for the effort.Don't think about the votes.By the way thanx for pointing out my mistake.
- Sibendu Dey July 18, 2013