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
Use a finite automata [DFA] & keep changing the states. At the end of the stream, if final state is reached, it is a divisible by 5.
Here is the complete code.
#include <stdio.h>
int getState(int state,char bit)
{
if(state==0)
return bit==0?0:1;
else if(state==1)
return bit==0?2:3;
else if(state==2)
return bit==0?4:0;
else if(state==3)
return bit==0?1:2;
else if(state==4)
return bit==0?3:4;
}
int isDivisible(char *seq)
{
int state=0,i;
for(i=0;seq[i];++i)
{
state=getState(state,seq[i]);
}
return state==0?1:0;
}
int main()
{
char seq[20];
fgets(seq,20,stdin);
isDivisible(seq)?printf("Yes"):printf("No");
return 0;
}
It is better than the above approaches because it works on bits & we do not require any arithmetic(modulo & + to calculate the remainder)
- Aashish June 25, 20121. Make a TRIE of all the words to be searched.
2. Now, find the first segment which contains all the words.Mark its length
3. Take two pointers, one pointing to the start of the above segment & other pointing to the end.
4. Increment the end pointer to point to the next word. Check whether both start & end pointer point to the same word. If yes, increment the start pointer to point to next word.[We will also perform the same while findin the first segment]
Now, remove all the extra words from the starting that are not in the TRIE.
5. Proceed above steps until EOF is not encountered, meanwhile also keep updating the minlength if length of the newly found segment is less.
If there are any issues, let me know.
Because characters are stored in ASCII format. i.e. 1 is stored as 49. We do not need the ascii values rather need the exact values. So, 48 is subtracted. Since,two characters are being extracted, so rather than subtracting 48 two times, 96 is subtracted directly.
Hope this is clear.
void calExpr(char *str,int *Op1,char *Op2,int top1,int top2)
{
int i=0;
char c;
for(;str[i];i++)
{
c=str[i];
if(c=='(' || c=='+' || c=='-' || c=='*' || c=='/')
Op2[++top2]=c;
else if(c==')')
{
if(Op2[top2]=='(')
top2--;
else
{
cout<<"Invalid Expression ";
return;
}
}
else
{
if(Op2[top2]=='+' || Op2[top2]=='-' || Op2[top2]=='*' || Op2[top2]=='/')
{
int y=atoi(&c);
int x=Op1[top1--];
char ch=Op2[top2--];
if(ch=='+')
Op1[++top1]=x+y;
else if(ch=='-')
Op1[++top1]=x-y;
else if(ch=='*')
Op1[++top1]=x*y;
else if(ch=='/')
Op1[++top1]=x/y;
}
else
Op1[++top1]=atoi(&c);
}
}
while(top2>=0)
{
if(Op2[top2]=='+' || Op2[top2]=='-' || Op2[top2]=='*' || Op2[top2]=='/')
{
int y=Op1[top1--];
int x=Op1[top1--];
char ch=Op2[top2--];
if(ch=='+')
Op1[++top1]=x+y;
if(ch=='-')
Op1[++top1]=x-y;
if(ch=='*')
Op1[++top1]=x*y;
if(ch=='/')
Op1[++top1]=x/y;
}
}
cout<<Op1[0];
}
int main()
{
int Operator[5],top1=-1,top2=-1;
char Operand[5];
char str[20];
cout<<"Enter the Infix Expression ";
cin>>str;
calExpr(str,Operator,Operand,top1,top2);
return 0;
}
void my_add(char *n1,char * n2,char *n3)
{
int top=-1,carry,sum;
int i=0,j=0;
carry=0;
while(n1[i] && n2[j])
{
sum=n1[i] + n2[j] - 96 + carry;
printf("%d .. ",sum);
carry=sum/10;
sum%=10;
n3[++top]=(char)(sum+48);
i++;j++;
}
while(n1[i])
{
sum=n1[i] - 48 + carry;
carry=sum/10;
sum%=10;
n3[++top]=(char)(sum+48);
i++;
}
while(n2[j])
{
sum=n2[j] - 48 + carry;
carry=sum/10;
sum%=10;
n3[++top]=(char)(sum+48);
j++;
}
if(carry)
n3[++top]=(char)(carry+48);
n3[++top]='\0';
printf("%s",n3);
printf("Add\n");
}
void zigZagTraversal(struct node *root)
{
struct node *Stack1[20],*Stack2[20],*temp;
int top1=-1,top2=-1,LeftToRight=1;
Stack1[++top1]=root;
while(top1>=0 || top2>=0)
{
if(LeftToRight)
{
while(top1>=0)
{
temp=Stack1[top1--];
printf("%d ",temp->data);
if(temp->left)
Stack2[++top2]=temp->left;
if(temp->right)
Stack2[++top2]=temp->right;
}
printf("|");
}
else
{
while(top2>=0)
{
temp=Stack2[top2--];
printf("%d ",temp->data);
if(temp->right)
Stack1[++top1]=temp->right;
if(temp->left)
Stack1[++top1]=temp->left;
}
printf("|");
}
LeftToRight=1-LeftToRight;
}
}
I can think of one approach. First run a loop to ensure that date in an interval ranges from lower to higher[this is a test case].
Now, sort the data in increasing order higher range. nlogn
run a loop & check whether lower of an interval is smaller than the previous higher of interval. If yes, this is the overlapping interval.
@banerjee36, did you try below approach
Here is the logn approach
int power(int n,int k)
{
int p;
if(k==0)
return 1;
else
{
p=power(n,k/2);
p*=p;
if(k&1)
p*=n;
return p;
}
}
int main()
{
int n=3,k=27;
power(n,n)==k?printf("Yes"):printf("No");
return 0;
}
***ideone.*com/oEpgE***
- Aashish June 23, 2012Here N=9
int isSafe(int (*maze)[N],int x,int y)
{
if(x>=0 && x<N && y>=0 && y<N && !maze[x][y])
return 1;
return 0;
}
void Maze(int (*maze)[N],int x,int y,int (*sol)[N])
{
static int i,j;
if(x==N-1 && y==N-1)
{
printf("\n\nSolution\n\n");
sol[x][y]=1;
for(i=0;i<N;i++)
{
for(j=0;j<N;j++)
printf("%d ",sol[i][j]);
printf("\n");
}
}
else
{
if(isSafe(maze,x,y))
{
sol[x][y]=1;
Maze(maze,x+1,y,sol);
Maze(maze,x,y+1,sol);
sol[x][y]=0;
}
}
}
isIsotropic(root1,root2)
{
if(!root1 && !root2)
return true;
if(!root1 || !root2)
return false;
return root1->data==root2->data && ( (isIsotropic(root1->left,root2->left) && isIsotropic(root1->right,root2->right)) || (isIsotropic(root1->left,root2->right) && isIsotropic(root1->right,root2->left)) )
}
1. Use augmented BST where each node will contain two extra fields, one keeping track of the index of the element, another keeping track of the largest index of element less than this node's element.
Making clarifications, while inserting a value in BST, if it is less than root node, update the second field only if it is larger than the field stored there. If the field value is not set, then store this index.
2. Insert the elements into BST, if we use self balancing BST, the running time complexity is O(nlogn).
3. For each element in the array, search it in BST & print its corresponding field .
Let me know if i am missing anything.
k=0;p=0;
for(i=p;i<row;i++)
{
for(j=k;j<col;j++) //k represents column
printf("%d ",arr[i][j]);
p++;
for(m=p;m<row;m++)
printf("%d ",arr[m][col-1]);
col--;
for(l=col-1;l>=k;l--)
printf("%d ",arr[row-1][l]);
row--;
for(n=row-1;n>=p;n--)
printf("%d ",arr[n][k]);
k++;
}
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.
while(head1)
{
cur2=head2;
while(cur2)
{
if(cur2==head1)
return cur2;
cur2=cur2->next;
}
head1=head1->next;
}
Time Complexity: O(N*M)
Space 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)
What if the file contain duplicate integers?
Will the list of k largest elements contain duplicate elements?
If yes, then i don't think that bit vector in that case is going to work.
Because, a bit corresponds to only a single integer. I doesn't keep track of duplicate elements.
The file size is 4GB. i.e. 2^32 bytes. The number of integers would be [on 32 bit machine] 2^32/4=2^30.
The main memory size is 1GB i.e. 2^30 bytes.
So, The size is exactly the same.
We can follow one out ofthe two below approaches:
Approach 1:
Read the file in chunks say 4 chunks. Maintain a min heap of size k & update it as said by the @wgpshashank. After the file scanning is over, we are left with k largest elements.
Now, it depends whether we are using signed int or unsigned int, In simple words, it is a good point to discuss with the interviewer because overflow may occur. We will have to handle it accordingly.
Approach 2:
Instead of reading file in chunks, we can create a bit vector & mask it accordingly where each bit will represent one integer. So, the space complexity reduces by a factor of 8.
Follow the above approach of min heap afterwards.
This is basically a backtracking algorith.
void print(char *s1,char *s2,char *s3,int N1,int N2,int depth)
{
int i;
if(N1==0 && N2==0)
{
for(i=0;i<depth;i++)
printf("%c",s3[i]);
printf("\n");
}
if(N1!=0)
{
s3[depth]=*s1;
print(s1+1,s2,s3,N1-1,N2,depth+1);
}
if(N2!=0)
{
s3[depth]=*s2;
print(s1,s2+1,s3,N1,N2-1,depth+1);
}
}
int main()
{
char s1[]="abc",s2[]="de",s3[10];
print(s1,s2,s3,strlen(s1),strlen(s2),0);
return 0;
}
The explanation goes as follows:
1. First include the first character of string 1 & iterate for the rest of take of the characters.
2. Apply the same for the second string.
3. If both the strings are finished, output string 3.
The approach will vary based on whether the function would be called once or multiple times.
If it is called multiple times, then below approach may be good as amortized time complexity is reduced.
Here s one approach. Make a look up table[using bit vector] of the numbers present in the set.
Apply divide & conquer technique. generate a random number & look in the bit vector whether its already present. If not,return.
else, call recursively for 0 to k-1 & k+1 to N.
Let me know if there is any better approach.
Cracked it!!
Sometimes, we use to think too much. However, we already know the solution.
Modified partition algorithm of quick sort solves the problem in O(MxN) time& without using any extra space.
here is the working code:
#define M 3 //number of rows
#define N 3 //number of columns
struct Index
{
int row;
int col;
}ind;
void swap(int *a,int *b)
{
int temp=*a;
*a=*b;
*b=temp;
}
void partition(int (*A)[N],int lr,int lc,int hr,int hc)
{
int pivot=A[lr][lc],j,k,l,m;
j=hr;k=hc;
l=(lc==N-1)?(lr+1):lr;
m=(lc==N-1)?0:lc+1;
while(1)
{
while(pivot>=A[l][m])
{
m++;
if(m==hc && l==hr)
break;
if(m==N)
{
l++;
m=0;
}
}
while(pivot<A[j][k])
{
k--;
if(k==lc && j==lr)
break;
if(k<0)
{
j--;
k=N-1;
}
}
if(l<j || (l==j && m<k))
swap(&A[l][m],&A[j][k]);
else
{
swap(&A[lr][lc],&A[j][k]);
ind.row=j;
ind.col=k;
return;
}
}
}
void findkthSmallest(int (*A)[N],int lr,int lc,int hr,int hc,int k)
{
int i;
if((hc<N && hr<M) && (lr<hr || (lr==hr && lc<hc)))
{
partition(A,lr,lc,hr,hc);
i=ind.row*N + ind.col;
if(i+1==k)
{
printf("%d ",A[ind.row][ind.col]);
return;
}
else if (i+1<k)
{
(ind.col==N-1)?(ind.col=0,ind.row++):(++ind.col);
findkthSmallest(A,ind.row,ind.col,hr,hc,k);
}
else
{
(ind.col==0)?(ind.col=N-1,ind.row--):(--ind.col);
findkthSmallest(A,lr,lc,ind.row,ind.col,k);
}
}
else if(lr==hr && lc==hc)
{
i=lr*N + lc;
if(i+1==k)
printf("%d ",A[lr][lc]);
}
}
Call : findkthSmallest(A,0,0,M-1,N-1,k); where A is the 2D Matrix.
Let me know your thoughts on this approach.
Well there are multiple approaches.
Approach 1:
Take a max heap & insert first k unique elements[can be easily checked]. Heapify the heap.
Now, when a new element is smaller than the head of the heap,replace head with this new element heapify it. At the last, the head of the heap indicates kth smallest element if size of the heap is k else kth smallest element doesn't exist.
Time complexity: O(NlogK)
Space complexity: O(K)
Approach 2[A better approach]:
The elements may be duplicated right. So, check for unique elements by comparing with its previous elements & stop if unique variables found so far counts to k.
Time complexity: O(N)
Space complexity: O(1)
Approach 3[A better approach(may be)]:
A modified version of quick sort partition algorithm can also be used. But possibly it will lead to a worst case as the array is already sorted.
here two questions arise:
1. Does it work if the array contain duplicates?
2. Would it be better than my second approach?
Approach 4:
Here's an O(kLogN) solution:
Using a variation of Binary Search to find the last occurrence of a given value,
Get 1st value - O(1).
Search for last occurrence of this value O(logN), then look at next element to get 2nd value - O(1).
Repeat until kth value is found.
Use max_heap of size k.
Scan upto k elements of the matrix & insert in the max heap.
Now, for each new element of matrix, check whether if it is smaller than the head of the heap.
If it is smaller, replace the head element with this new element. Update the heap.
At last, The head denotes the kth smallest element.
Time complexity: O(M*N*log(k))
Space complexity: K
Let me know if i am missing anything.
This is basically a boundary edge traversal.
void printBoundaryEdgesLeft(struct node *root)
{
if(root->left)
{
printf("%d ",root->data);
printBoundaryEdgesLeft(root->left);
}
else if(root->right)
{
printf("%d ",root->data);
printBoundaryEdgesLeft(root->right);
}
}
void printBoundaryEdgesLeaves(struct node *root)
{
if(root)
{
printBoundaryEdgesLeaves(root->left);
if( !(root->left) && !(root->right) )
printf("%d ",root->data);
printBoundaryEdgesLeaves(root->right);
}
}
void printBoundaryEdgesRight(struct node *root)
{
if(root->right)
{
printBoundaryEdgesRight(root->right);
printf("%d ",root->data);
}
else if(root->left)
{
printBoundaryEdgesRight(root->left);
printf("%d ",root->data);
}
}
void printBoundaryEdges(struct node *root)
{
if(root)
{
printf("%d ",root->data);
printBoundaryEdgesLeft(root->left);
printBoundaryEdgesLeaves(root->left);
printBoundaryEdgesLeaves(root->right);
printBoundaryEdgesRight(root->right);
}
}
I have updated my post. Please read it again.
- Aashish June 25, 2012