Aashish
BAN USER- 0of 0 votes
AnswersGive a good data structure for having n queues ( n not fixed) in a finite memory segment. You can have some data-structure separate for each queue. Try to use at least 90% of the memory space
- Aashish in India| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer - 0of 0 votes
AnswersYou are given many slabs each with a length and a breadth. A slab i can be put on slab j if both dimensions of i are less than that of j. In this similar manner, you can keep on putting slabs on each other. Find the maximum stack possible which you can create out of the given slabs.
- Aashish in India| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer - 0of 0 votes
Answersyou are given a system of passing binary trees among 2 ppl
- Aashish in India
Step1: convert the tree to preorder and inorder strings
Step2:send those strings to the intended person
Step3:get back tree from the strings
whats your strategy of testing?write various test scenarios.---10 marks| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer - 0of 0 votes
AnswersWe have a text editor application where we can choose 1)between 100s of
- Aashish in India
different fonts like arial, calibri, etc.. 2)different text sizes 3) different formatting such as bold, Italics, regular, etc..
Imagine that the application is similar to word(there we will have these options). Now give different test cases to test this application.| Report Duplicate | Flag | PURGE
Microsoft Software Development Manager - 0of 0 votes
AnswersTest cases for finger print reader say in a laptop to login. Here you can swipe your finger to have a secured login. e.g. I will swipe my finger and the system will allow me to login.
- Aashish in India| Report Duplicate | Flag | PURGE
Microsoft Software Engineer in Test Testing - 0of 0 votes
AnswersGiven an array of 32bit unsigned integers in which every number appears exactly twice except three of them, find those three numbers in O(n) time using O(1) extra space. The input array is read-only. What if there are k exceptions instead of 3?
- Aashish in India| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 1of 1 vote
AnswersYou have a stream of bytes from which you can read one byte at a time. You only have enough space to store one byte. After processing those bytes, you have to return a random byte. Note: The probability of picking any one of those bytes should be equal.
- Aashish in United States| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Algorithm - 3of 3 votes
AnswersGiven a circular single linked list.Write a program that deletes every kth node until only one node is left.
- Aashish in India
After kth node is deleted, start the procedure from (k+1)th node.
e.g.list is 1->2->3->4->5->1
k=3
1. You are at 1, delete 3.
List is: 1->2->4->5->1
2. You are at 4, delete 1
List is: 2->4->5->2
3. You are at 2,delete 5
List is: 2->4->2
4. You are at 2, delete 2
List is: 4
Return 4.
How efficient you can do it?| Report Duplicate | Flag | PURGE
Amazon Google Software Engineer / Developer Algorithm - 0of 0 votes
AnswersDesign the Class diagram for vending machine for Tea & Coffee. This machine can generate the diff type of tea like Cardemom, Elichi, Ginger. Same way 3 type of coffee. The thing is when you make the tea or coffee user can add n number of flavors like sugar, honey or etc.
- Aashish in India| Report Duplicate | Flag | PURGE
InMobi Software Engineer / Developer Application / UI Design - 0of 0 votes
AnswersRemove duplicates from min-heap.
- Aashish in India| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 0of 0 votes
AnswersWhat is wrong with the below code?
- Aashish in India#include <iostream> #include <string.h> using namespace std; class A { char *p; public: A(const char* str) { p=new char[strlen(str)+1]; strcpy(p,str); } ~A() { delete p; } }; int main() { A s("Object s"); A t=s; s.~A(); A u("Object u"); u=s; return 0; }
| Report Duplicate | Flag | PURGE
Sap Labs Software Engineer / Developer Algorithm - 0of 0 votes
Answers
- Aashish in Indiavoid freeList( struct node *n ) { while( n ) {????} } Which one of the following can replace the ???? for the function above torelease the memory allocated to a linked list? Choice 1 n = n->next; free( n ); Choice 2 struct node m = n; n = n->next; free( m ); Choice 3 struct node m = n; free( n ); n = m->next; Choice 4 free( n ); n = n->next; Choice 5 struct node m = n; free( m ); n = n->next;
| Report Duplicate | Flag | PURGE
Aricent Software Engineer / Developer Algorithm - 0of 0 votes
Answersvoid *ptr;
- Aashish in United States
myStruct myArray[10];
ptr = myArray;
Which of the following is the correct way to increment the variable "ptr"?
Choice 1 ptr = ptr + sizeof(myStruct);
Choice 2 ++(int*)ptr;
Choice 3 ptr = ptr + sizeof(myArray);
Choice 4 increment(ptr);
Choice 5 ptr = ptr + sizeof(ptr);| Report Duplicate | Flag | PURGE
Aricent Software Engineer / Developer Algorithm - 4of 8 votes
AnswersDesign an algorithm that, given a list of n elements in an array, finds all the elements that appear more than n/3 times in the list. The algorithm should run in linear time ( n >=0 )
- Aashish in India
You are expected to use comparisons and achieve linear time. No hashing/excessive space/ and don't use standard linear time deterministic selection algo| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 0of 0 votes
AnswersIf i type some numbers in my cell, all phone numbers which have these typed nos in any order should appear, tell data structure for this.
- Aashish in United States
eg:if i type 926 then
932678....
92678...
9777726....
should appear.
[EDIT]: It seems you have lot of confusion.
Let me clear it through another example
eg: i enter 321, then
o/p(if they r in book)
9344241..
972153....| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Data Structures - 0of 0 votes
AnswersGiven a set of data ranges (i.e. 2-7, 5-9, 10-20), write a function to determine if there is any overlap within the set. Write test cases. Which data structure would be best to represent the intervals.
- Aashish in India| Report Duplicate | Flag | PURGE
Microsoft Software Engineer in Test - 2of 2 votes
AnswersDoes it always happen that stack always grows downwards & heap grows upwards?
- Aashish in India
If its so, then how does OS keeps the heap area protected from the interference of the stack & vice-versa?
If its not, then what factors affect it? OS version ? Compiler? Anything else??| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Operating System
Time complexity: O(M logN) where M=rows, N=cols
void findMaxOne(int (*M)[COL],int *max,int *r,int row,int l,int h)
{
int mid;
if(row<0 || l>h)
return;
if(l==h)
{
if(M[row][l]==1 && l+1>*max)
{
*max=l+1;
*r=row;
}
findMaxOne(M,max,r,row-1,*max,h);
}
else
{
mid=(l+h)>>1;
if(M[row][mid]==1)
{
if(M[row][mid+1]==0)
{
if(mid+1>*max)
{
*max=mid+1;
*r=row;
}
findMaxOne(M,max,r,row-1,mid+1,h);
}
else
findMaxOne(M,max,r,row,mid+1,h);
}
else
{
if(M[row][mid-1]==1)
{
if(mid>*max)
{
*max=mid;
*r=row;
}
findMaxOne(M,max,r,row-1,mid,h);
}
else
findMaxOne(M,max,r,row,l,mid-1);
}
}
}
Complete code here: ideone.com/b5mLK
- Aashish July 18, 2012next is the pointer to right child.
prev is the pointer to left child.
BST2DLL(root,start)
{
if(root)
{
BST2DLL(root->left);
if(!start)
start=root;
else
{
prevNode->next=root;
root->prev=prevNode;
}
prevNode=root;
BST2DLL(root->right);
}
}
prevNode is static here.
After the execution of the function is over, start will be pointing to the head of the DLL.
0 represents RED & 1 represents GREEN;
c representc color. color[i]==0 indicates ith vertex is colored RED.
int colorGraph(G[][],int c,int source,int color[])
{
color[source]=c;
for each V adj to source
{
if(isColored(V)==c)
return 0;
if(colorGraph(G,1-c,V,color)==0) return 0;
}
return 1;
}
Represent each digit of a number with a bit.
Compare bit-representation of each number with the bit-representation every other number
struct bit
{
unsigned int num:10;
};
void find(int* a,int size)
{
struct bit b[size];
int i,num,j,count=0;
for(i=0;i<size;i++) b[i].num=0;
for(i=0;i<size;i++)
{
num=a[i];
while(num)
{
b[i].num|=1<<(num%10);
num/=10;
}
}
for(i=0;i<size;i++)
{
for(j=i+1;j<size;j++)
{
if(b[i].num&b[j].num)
count++;
}
}
printf("%d ",count);
}
Complete code here: ideone.com/nEeTG
- Aashish July 15, 2012Modified Inorder traversal.
However, it changes the structure of the tree.
void LL(struct node* root,struct node** start)
{
static struct node* tail;
if(root)
{
LL(root->left,start);
if(isLeaf(root))
{
if(!*start)
{
*start=root;
tail=root;
}
else
{ tail->right=root;
tail=tail->right;
}
}
LL(root->right,start);
}
}
start points to the head of the linked list.
Complete code: ideone.com/6WhB3
int isPalindrome(char* s,int l,int h)
{
if(!*s) return 1;
if(l>h) return 0;
return l==h?1:(s[l]==s[h] && isPalindrome(s,l+1,h-1));
}
int main()
{
char s[]="katak",size;
size=sizeof(s)/sizeof(s[0]);
if(isPalindrome(s,0,size-2)) printf("Palindrome");
else printf("Not palindrome");
return 0;
}
If the inorder is given in the form of array, then even if the actual tree is a sparse one, we will end up with making complete binary tree[using property of max heap].
If we are allowed to do so, just call heapify method starting from the last parent[(n-1)/2 if array index starts from 0 to n] to the first parent[0].
Another approach based on DP[Modification of cutting of rod].
This method doesn't require the coin[]={1,3,10} to be sorted.
Say, we know the number of coins required for n-1, we can extend it for n also.
1. Take a minCount array. If minCount[i]==j, then minimum of j number of coins are required for i.
void countCoins(int* coin,int size,int tofind)
{
int minCount[tofind+1],i,j,mintillnow;
for(i=0;i<tofind+1;++i)
minCount[i]=0;
for(i=0;i<size;i++)
if(coin[i]<=tofind)
minCount[coin[i]]=1;
for(i=1;i<=tofind;i++)
{
if(!minCount[i])
{
mintillnow=INT_MAX;
for(j=1;j<i;++j)
{
if(minCount[j]+minCount[i-j]<mintillnow)
mintillnow=minCount[j]+minCount[i-j];
}
minCount[i]=mintillnow;
}
}
printf("Minimum number of coins needed is: %d",minCount[tofind]);
}
The only disadvantage of this method is that it may require large amount of space.
e.g. we may need change of Rs 1 lakh[space required is 1lakh bytes]. However, it can be reduced if we go for bit-vector.
Complete code here: ideone.com/pKEwC
It is the simple one.
Assuming that the coin array is sorted in ascending order[1,3,10].
Time complexity: O(N)
Space complexity: O(1)
Here is the code
// to find the change of k.
int countCoins(int* coin,int size,int value)
{
int i,count,total=0;
for(i=size-1;i>=0;i--)
{
count=value/coin[i];
if(count)
{
value-=count*coin[i];
total+=count;
printf("%d number of Rs %d coins\n",count,coin[i]);
}
}
return total;
}
int main()
{
int coin[]={1,3,10},size,k;
size=sizeof(coin)/sizeof(coin[0]);
scanf("%d",&k);
printf("Minimum pickings: %d",countCoins(coin,size,k));
return 0;
}
ideone.com/Tr69T
- Aashish July 14, 2012Output is:
der 10 func
der 1 func
The explanation goes as follows:
The default argument is a compile-time feature i.e. the substitution of default arguments is done at compile-time.
For this reason, obviously, there's no way the default argument mechanism for member functions can depend on the dynamic (i.e. run-time) type of the object. It always depends on static (i.e. compile-time) type of the object.
The call you wrote in your code sample[bb->func(10)] is immediately interpreted by the compiler as bb->func(10,10) regardless of anything else.
Well, the question needs to be clarified a lot.
1. Are the elements given in the range? If yes, use look up table.
2. else, do sort the array in nlogn, remove duplicates & find the pairs by running the two pointers, low[=0] & high[=n-1].
3. Are the pairs {2,6} & {6,2} considered the same?
Below code is based on: 1 & 3
void findPair(int* a,int n,int k)
{
int hash[10]={0},i;
for(i=0;i<n;i++)
{
if(!hash[a[i]])
{
if(hash[k-a[i]])
printf("%d %d\n",a[i],k-a[i]);
else
hash[a[i]]=1;
}
}
}
complete code here: ideone.com/17w1Z
- Aashish July 14, 2012Corner cases:
1. The number of digits is even or odd.
2. All the digits are 9.
Approach:
1. Take two pointers low[i here] pointing to start & high[j here] pointing t last. Start comparing ith & jth elements.Continue until both are equal or jth element is greater than ith element.
2. In case case 1 holds,Add 1 to the ith element & reflect the changes in elements[due to carry] going downwards from i-1 to 0. Copy elements from i to 0 in the slots from j to n-1.
3. Construct smallest palindrome from i+1 to j-1.
Handle even length & odd length accordingly.
Here is the function:
//if all the digits are 9,simply o/p 1 followed by n-1 0's followed by 1.
void findNextPalindrome(int *arr,int n)
{
int i,j,carry,low,high;
i=0;j=n-1;
while(i<j && arr[j]>=arr[i])
i++,j--;
if(i>=j)
{
if(!(n&1)) //handle even length palindrome
i--,j++;
carry=1;
while(i>=0)
{
arr[i]+=carry;
carry=arr[i]/10;
arr[i]%=10;
arr[j++]=arr[i--];
}
}
else
{
low=i+1;high=j-1;
while(i>=0)
arr[j++]=arr[i--];
while(low<high) // handle the case 8683
{
arr[low]=arr[high]=arr[low]<arr[high]?arr[low]:arr[high];
low++;high--;
}
}
}
Complete code here: ideone.com/t79wb
Please write comments if you find anything wrong here.
A recursive approach:
rev(root)
{
if(!root || !(root->next))
newroot=root;
else
{
rev(root->next);
if(root->next)
{
root->next->next=root;
root->next=NULL;
}
}
return newroot;
}
An iterative one:
iterativerev(root)
{
Node *p,*q,*r;
q=root;
while(q)
{
r=q->next;
q->next=p;
p=q;
q=r;
}
return p;
}
Here is O(N^2) solution.
1. Count all even length palindromes.
2. Count all odd length palindromes.
3.return count.
int countPalindrome(char *str)
{
int i,j,k,count=0;
for(i=0;str[i];i++)
{
k=i-1;j=i+1; //count odd length palindromes
while(k>=0 && str[j] && str[k]==str[j])
{
++count;
k--;j++;
}
k=i;j=i+1; //count even length palindrome
while(k>=0 && str[j] && str[k]==str[j])
{
++count;
k--;j++;
}
}
return count;
}
Can someone post the implementation of suffix array?
- Aashish July 08, 2012We need to handle a few test cases.
1. Both nodes are end nodes.
2. Both nodes are adjacent.
3. Both nodes are somewhere else.
4. Both node are same.
5. kth node doesn't exist.
I prefer swapping the nodes rather than values. It is always advisable to swap the nodes as in general, nodes may contain several data. So, it will be overhead to swap the values.
Steps:
Find the kth node[p] from the beginning. If no kth node, return.
Take another pointer[q] & move it at head. Move it & the kth node one step at a time until kth node is null. q is the kth node from the last.
We need to swap p & q.
The part of linked list found is: t1->p->t2 and t3->q->t4
Just swap the nodes based on links & handle the corner cases mentioned above.
Here is the code:
void swap(struct node **root,int k)
{
int count=1;
struct node *t1,*t2,*t3,*t4,*cur,*p,*q;
if(!(*root) || !k)
return;
cur=*root;
t1=t2=t3=t4=NULL;
while(cur && count++!=k)
{
t1=cur;
cur=cur->next;
}
if(count<=k) //not enough nodes
return;
p=cur;
q=*root;
while(cur && cur->next)
{
t3=q;
q=q->next;
cur=cur->next;
}
t2=p->next;
t4=q->next;
if(p==q) // both nodes are same
return;
if(p->next==q) // adjacent nodes
{
t1->next=q;
q->next=p;
p->next=t4;
}
else if(q->next==p) // adjacent nodes
{
t3->next=p;
p->next=q;
q->next=t2;
}
else if(!t1) // p is the first node
{
*root=(*root)->next;
q->next=*root;
*root=q;
p->next=t4;
t3->next=p;
}
else if(!t3) // q is the last node
{
*root=(*root)->next;
p->next=*root;
*root=p;
q->next=t2;
t1->next=q;
}
else
{
p->next=t4;
t3->next=p;
q->next=t2;
t1->next=q;
}
}
See the complete code here: ideone.com/bUqR3
1. take two pointers fast & slow.
2. Move slow once & fast twice until they do not meet or fast becomes NULL(No cycle)
3. Move slow to root & move slow & fast one step at a time until they do not meet. This is the start of the cycle. Here is pseudo code:
findCycle(root)
{
struct node* slow,*fast;
slow=fast=root;
while(fast && fast->next && fast!=slow)
{
fast=fast->next->next;
slow=slow->next;
}
if(!fast || !(fast->next)) return NULL;
slow=root;
while(fast!=slow)
{
fast=fast->next;
slow=slow->next;
}
return fast;
}
One of the surprising method i would like to share.
However, a prior information must be known which is size of the array to be copied.
Template metaprogramming: The templates must have constant expressions.
Here is the code:
ideone.com/p1cXQ
#include <iostream>
using namespace std;
int size;
template<int n>
void mycopy(int *a,int *b)
{
b[n]=a[n];
mycopy<n+1>(a,b);
}
template<>
void mycopy<3>(int *a,int *b)
{
b[size-1]=a[size-1];
}
int main()
{
int a[4]={1,2,3,4},b[4],i;
size=sizeof(a)/sizeof(a[0]);
mycopy<0>(a,b);
for(i=0;i<4;i++)
printf("%d ",b[i]);
return 0;
}
Use DP.
Say we want to calculate the height of a node p. So, its height is equal to the height of its parent plus 1.
So, while calculating the height of a node, store it somewhere so that we do not need to calculate the height again once we fall in the same path.
Lets take an example of a BST: 1,2,3,4;
For calculating the height of 3, we need height of 2. However its already stored[using DP]
Hope its clear.
#include <stdio.h>
#include <limits.h>
int findheight(int *par,int size)
{
int i,j,height[size],count,maxheight;
for(i=0;i<size;i++)
height[i]=0;
for(i=0;i<size;i++)
{
count=0;j=i;
while(par[j]!=-1 && !height[j])
{
++count;
j=par[j];
}
height[i]=count+(j!=i?height[j]:0);
}
maxheight=INT_MIN;
for(i=0;i<size;i++)
if(maxheight<height[i])
maxheight=height[i];
return maxheight;
}
int main()
{
int par[]={-1,0,1,6,6,0,0,2,7},size;
size=sizeof(par)/sizeof(par[0]);
printf("%d ",findheight(par,size));
return 0;
}
ideone.com/vCLF4
- Aashish July 07, 2012I think this will work. I am first checking whether the previous marked node is the node whose successor is to be found.If yes, just return the current node. Now, What will be the relationship between the previous visited node & the current node. The latter is the successor of the former.
Can you cite an example[a tree] where it fails?
A non-recursive approach which makes use of BST.
Assuming parent pointers are not given.
The space complexity is O(log N)
Time complexity is O(log N)
LOGIC:
1. If the left child r right child exists, return it.
2. Store all the ancestors of the nodes to be found in an array in top down manner.
3. Start searching for the successor among ancestors in bottom up manner. If the right child of the ancestor exists & its right child is the node whose successor is to be found, we will continue following the path upwards.
preorderSuccessor(root,p)
{
if(!root || !p)
return NULL;
if(p->left)
return p->left;
if(p->right)
return p-right;
top=-1;
while(root->data!=p->data)
{
arr[++top]=root;
if(p->data<root->data)
root=root->left;
else
root=root->right;
}
for(i=top;i>=0;i--)
{
if(arr[i]->right)
{
if(p!=arr[i]->right)
return arr[i]->right;
}
p=arr[i];
}
return NULL;
}
I have updated my solution along with the link where i have tried it. Its giving correct output for every input.
See complete code here: ideone.com/18tLJ
A recursive approach:
I don't think in any way, we are benefitted whether the tree is BST or BT.
preorderSuccessor(root,p)
{
static Node* prev;
if(root)
{
if(prev==p)
return root;
prev=root;
preorderSuccessor(root->left,p);
preorderSuccessor(root->right,p);
}
return NULL;
}
Well, the solution depends on what information we have.
If parent pointers are given, here is the pseudo code:
1. If the left child exists, return it
2. If the right child exists, return it.
3. If both children do not exist, we must backtrack to parent. Two conditions arise:
If the node is the left child of its parent or the node is the right child of the parent.
If the node is the right child of its parent,move upwards until it becomes the left child.
If the node is the left child, move upwards until its parent doesn't have right child.
PreorderSuccessor(p)
{
if(p->left)
return p->left
if(p->right)
return p->right;
par=p->parent;
while(par && par->right==p)
{
p=par;
par=p->parent;
}
while(par && par->right==NULL)
par=par->parent;
if(par && par->right)
return par->right;
return NULL:
}
ok, let me explain:
f(n)=2*(f(n-1)+f(n-2))
The recurrence relation would look like : r^2=2*(r+1)
i.e. r^2-2*r-2
r=1+3^0.5 & 1-3^0.5
say r1 & r2
Now, f(n) = a1(r1)^n + a2(r2)^n----------------------original
There are two unknowns a1 & a2.
We have,
f(1)=a1(r1) + a2(r2) = 1----------------------equation 1
f(2)=a1(r1)^2 + a2(r2)^2= 3-------------------equation 2
Solve the two equations, you will get the values of a1 & a2.
Put the values of a1,a2,r1,r2 in the original equation, you will get the result.
Hope its clear.
As the array contains only binary 0 & 1. Use OR & AND operators to swap[Not exactly swap].
void sort(int *arr,int size)
{
int l=0,or,and,h;
h=size-1;
while(l<h)
{
while(arr[l]==0)
l++;
while(arr[h]==1)
h--;
if(l<h)
{
or=arr[l]|arr[h];
and=arr[l]&arr[h];
arr[l]=and;
arr[h]=or;
l++;h--;
}
}
for(l=0;l<size;l++)
printf("%d ",arr[l]);
}
ideone.com/6FEU5
- Aashish July 06, 2012Very rightly said. I would also like to add some food for thought.
The actual values that are being stored are not the one being passed, rather they are stores in the form of exponent & mantissa, they get silently rounded off to the approximated values
because of the recurring nature of the binary form being converted. Also,it depends on the architecture, whether the intermediate values are stored somewhere[more likely to get the approximated or rounded values] or the directly used to get the result. Hence a+b+c is different from a+c+b.
Another approach.
Probably this would be better i the number of duplicates are more.
1. Pick the first element.Find the last occurrence of this element.
2. Increment the pointer to pointer to next unique element. In this way, number of unique elements can be tracked[with the help of count].
3. Anytime if cunt==k, print corresponding element.
As said earlier, if the number of unique elements are duplicated manier times, this approach is efficient[Lets say all elements are duplicated]. However, if all elements are unique, then this will fall into the worst case of nlogn.
I am presenting this idea as it can be used as per the situation.
int findLastOcurrence(int *arr,int item ,int l,int h)
{
int mid;
if(l==h)
return arr[l]==item?l:INT_MAX;
if(l==h-1)
return (arr[h]==item?h:(arr[l]==item?l:INT_MAX));
mid=(l+h)>>1;
if(item>=arr[mid])
return findLastOcurrence(arr,item,mid,h);
else
return findLastOcurrence(arr,item,l,mid-1);
}
void find(int *arr,int size,int k)
{
int count=1,i,last;
for(i=0;i<size;count++)
{
if(count==k)
{
printf("%d ",arr[i]);
return;
}
last=findLastOcurrence(arr,arr[i],i,size-1);
i=last+1;
}
printf("Not found");
}
Complete code: ideone.com/LKtfl
- Aashish July 06, 2012
Well, there are several approaches to solve this problem.
Note that i am only discussing the approaches[corner cases may need to be handled separately] starting from brute force to the best one.
Considering N: number of nodes in first linked list
M: number of nodes in second linked list
Approach 1:
Compare each node of first linked list with every other node of second list. Stop when you find a matching node, this is the merging point.
Time Complexity: O(N*M)
- Aashish July 18, 2012Space Complexity: O(1)
Approach 2:
Maintain two stacks. Push all the nodes of he first linked list to first stack. Repeat he same for second linked list.
Start popping nodes from both the stacks until both popped nodes do not match. The last matching node is the merging point.
Time Complexity: O(N+M)
Space Complexity: O(N+M)
Approach 3:
Make use of hash table. Insert all the nodes of the first linked list into hash.
Search for the first matching node of he second list in the hash.
This is the merging point.
Time Complexity: O(N+M)
Space Complexity: O(N)
Note that the space complexity may vary depending upon the hash function used[talking about C where you are supposed to implement your own hash function].
Approach 4:
Insert all the nodes of first linked list[by nodes, i mean addresses] into an array.
Sort the array with some stable sorting algorithm in O(N logN) time[Merge sort would be better].
Now search for the first matching node from the second linked list.
Time Complexity: O(N logN)
Space Complexity: O(N)
Note that this approach may be better than Approach 3 [in terms of space]as it doesn't use a hash.
Approach 5:
1. Take an array of size M+N.
2. Insert each node from the first linked list, followed by inserting each node from the second linked list.
3. Search for the first repeating element[can be found in one scan in O(M+N) time].
Time Complexity: O(N+M)
Space Complexity: O(N+M)
Approach 6: [A better approach]
1. Modify the first linked list & make it circular.
2. Now starting from the head of the second linked list, find the start of the loop using Floyd- Warshall cycle detection algorithm.
3. Remove the loop[can be easily removed as we know the last node].
Time Complexity: O(N+M)
Space Complexity: O(1)
Approach 7: [Probably the best one]
1. Count the number of nodes in first linked list[say c1].
2. Count the number of nodes in second linked list[say c2].
3. Find the difference[Lets say c1>c2] diff=c1-c2.
4. Take two pointers p1 & p2, p1 pointing to the head of the first linked list & p2 pointing to the head of the second linked list.
5. Move p1 diff times.
6. Move both p1 & p2 each node at a time until both point to the same node.
7. p1 or p2 indicates the merging point.
Time Complexity: O(N+M)
Space Complexity: O(1)