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 datastructure 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 readonly. 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 minheap.
 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. 27, 59, 1020), 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 & viceversa?
If its not, then what factors affect it? OS version ? Compiler? Anything else?? Report Duplicate  Flag  PURGE
Microsoft Software Engineer / Developer Operating System
Also take care if b is negative.
if(b<0) call res=divide(a,b) & if a is negative call res=divide(a,b). The answer is res.
If both are negative call divide(a,b)
int divide(a,b) {
if (b == 0) print "Invalid";
else if (a < b) return 0;
else return(1 + (divide(ab, b));
}

Aashish
June 30, 2012 Assuming both arrays are sorted.
a[] is of size M & b[] is of size N.
c is the third array which contains the sorted data avoiding duplicates.
i=0;j=0; top=1;
while(i<M && j<N)
{
if(a[i]<b[j])
c[++top]=a[i++];
else if(a[i]>b[j])
c[++top]=b[j++];
else
{
c[++top]=a[i++];
j++;
}
}
while(i<M)
c[++top]=a[i++];
while(j<N)
c[++top]=b[j++];

Aashish
June 29, 2012 I think radix sort would be the best. As its complexity is O(N*d) where d is negligible as compared to N.
Here is the implementation.
#include <stdio.h>
#include <limits.h>
#include <math.h>
int findMaxDigit(int *arr,int size)
{
int i,max=INT_MIN,n=0;
for(i=0;i<size;i++)
if(arr[i]>max)
max=arr[i];
while(max)
{
n++;
max/=10;
}
return n;
}
int isEmpty(int *r,int j)
{
return r[j]==1;
}
void Enqueue(int (*Q)[10],int *f,int *r,int digit,int n)
{
if(f[digit]==1)
f[digit]++;
Q[++r[digit]][digit]=n;
}
int Dequeue(int (*Q)[10],int *f,int *r,int digit)
{
int n=Q[f[digit]][digit];
if(f[digit]==r[digit])
f[digit]=r[digit]=1;
else
f[digit]++;
return n;
}
void radixSort(int *arr,int size)
{
int i,j,k,Q[size][10],f[10],r[10],d,digit,top=1;
d=findMaxDigit(arr,size);
for(i=0;i<size;i++)
f[i]=r[i]=1;
for(i=0;i<d;i++)
{
for(j=0;j<size;j++)
{
digit=(arr[j]/pow(10,i));
digit%=10;
Enqueue(Q,f,r,digit,arr[j]);
}
top=1;
for(j=0;j<10;j++)
{
while(!isEmpty(r,j))
arr[++top]=Dequeue(Q,f,r,j);
}
}
for(i=0;i<size;i++)
printf("%d ",arr[i]);
}
int main()
{
int arr[]={4,2,6,1,5,5,1,2,45,444,44,45,4,1};
radixSort(arr,sizeof(arr)/sizeof(arr[0]));
return 0;
}

Aashish
June 29, 2012 As the questions speaks about finding the count of a particular word.
So, a buffer can be maintained for each word & matched with the word to be searched.
An alternate way is to use TRIE & at the leaf nodes, count the number of occurrences. If words are to be outputted in sequence with the sentence, search for each word in the TRIE else do an inorder traversal.
The main idea is to take care of the rows & columns which have been finished, thereby reducing the size of the matrix to be printed.
p denotes the lower boundary row & k denotes the lower boundary column.
#include <stdio.h>
void printSpiral(int (*arr)[4],int row,int col)
{
int i,j,k=0,p=0;
while(p<row)
{
for(j=k;j<col;j++)
printf("%d ",arr[p][j]);
p++;
for(j=p;j<row;j++)
printf("%d ",arr[j][col1]);
col;
for(j=col1;j>=k;j)
printf("%d ",arr[row1][j]);
row;
for(j=row1;j>=p;j)
printf("%d ",arr[j][k]);
k++;
}
}
int main()
{
int arr[][4]={{1,2,3,4},{12,13,14,5},{11,16,15,6},{10,9,8,7}};
printSpiral(arr,4,4);
return 0;
}

Aashish
June 29, 2012 We need two different cases to handle:
1. Both the characters are same.
2. Both characters are different.
Moreover, we also need to take care whether the ordering of the characters matter.
case 1. Both chars are same
for(i=0,pos=1,mindist=INT_MAX;i<N;i++)
{
if(arr[i]==c)
{
if(pos!=1)
{
if(mindist>abs(posi))
mindist=abs(posi);
}
pos=i;
}
}
case 2: Both chars are different
int i,minc1=1,minc2=1,minpos=INT_MAX;
for(i=0;arr[i];i++)
{
if(arr[i]==c1)
{
if(minc2!=1)
{
if(minpos>abs(minc2i))
minpos=abs(minc2i);
}
minc1=i;
}
else if(arr[i]==c2)
{
if(minc1!=1)
{
if(minpos>abs(minc1i))
minpos=abs(minc1i);
}
minc2=i;
}
}

Aashish
June 29, 2012 #include <stdio.h>
int findLocation(int i)
{
return (i%4)*3 + (i/4);
}
void swap(int *a,int *b)
{
int t=*a;
*a=*b;
*b=t;
}
void arrange(int *arr,int h)
{
int i,j=1,loc=1;
for(i=1;i<h1;i++)
{
loc=findLocation(loc);
if(loc!=j)
swap(&arr[loc],&arr[j]);
else
{
loc++;
j=loc;
}
}
}
int main()
{
int arr[]={1,2,3,4,5,6,7,8,9,10,11,12},i;
arrange(arr,12);
for(i=0;i<12;i++)
printf("%d ",arr[i]);
return 0;
}

Aashish
June 28, 2012 Time complexity will be O(K*N logk) because, each time, a new element is inserted in the minheap, the heap needs to be heapified so that at each time during extraction, we get the minimum element only.As heapify takes logk time & it is done K.N times, so O(k*N logk)
 Aashish June 28, 2012#include <stdio.h>
void par(int open,int close,int n,int idx)
{
static char a[100];
int i;
if(close==n)
{
for(i=0;i<2*n;i++)
printf("%c",a[i]);
printf("\n");
}
if(open<n)
{
a[idx]='(';
par(open+1,close,n,idx+1);
}
if(close<open)
{
a[idx]=')';
par(open,close+1,n,idx+1);
}
}
int main()
{
par(0,0,3,0);
return 0;
}

Aashish
June 28, 2012 p=root;prev=NULL;
if(p>alph=='A'  p>alph=='O')
cur=root;
else
cur=NULL;
while(p)
{
if(p>alph=='A'  p>alph=='O')
{
if(prev!=NULL)
{
prev>next=p>next;
if(cur==NULL)
{
p>next=root;
root=p;
}
else
{
p>next=cur>next;
cur>next=p;
}
cur=p;
}
}
prev=p;
p=p>next;
}

Aashish
June 27, 2012 So, according to this approach, there will be n array of 10[for digits0 to 9]probably an array of linked list. Whenever a phone number needs to be inserted, we will take out each digit & associate its pointer[through which we can display the phone number] to the linked list. Good thinking, But what to do when the phone number contains duplicates.
Also, don't you think that we will be storing the same phone numbers multiple times?
The output of first program is undefined. There is no sequence defined in the statement:
x = y++ + x++;
y = ++y + ++x;
In the older version compilers, the output is 13.......21, but the newer version compilers(c99 onwards) define the behavior as undefined.You will get the error.
See here: ideone.com/mEqiP
If the value of the same variable is changed more than once, then it is called as UB(undefined behavior).
For more details, search sequence point on wiki.
Here is the iterative approach.
Space : O(1)
Time: O(N)
connectNodesatSameLevel(root)
{
if(!root)
return;
root>nextRight=NULL;
while(root)
{
p=root;
while(p)
{
if(p>left)
{
if(p>right)
p>left>nextRight=p>right;
else
p>left>nextRight=findNextRight(p);
}
if(p>right)
p>right>nextRight=findNextRight(p);
p=p>nextRight;
}
if(root>left)
root=root>left;
else if(root>right)
root=root>right;
else
root=findNextRight(root);
}
}
findNextRight(root)
{
root=root>nextRight;
while(root)
{
if(root>left)
return root>left;
if(root>right)
return root>right;
root=root>nextRight;
}
return NULL;
}

Aashish
June 27, 2012 Here is the recursive approach which takes O(1) space & O(N) time complexity.
connectNodesatSameLevel(root)// call it after making root>nextRight=NULL
{
if(root)
{
if(root>nextRight)
connectNodesatSameLevel(root>nextRight);
if(root>left)
{
if(root>right)
{
root>left>nextRight=root>right;
root>right>nextRight=findNextRight(root);
}
else
root>left>nextRight=findNextRight(root);
connectNodesatSameLevel(root>left);
}
else if(root>right)
{
root>right>nextRight=findNextRight(root);
connectNodesatSameLevel(root>right);
}
else
connectNodesatSameLevel(findNextRight(root));
}
}
findNextRight(root)
{
root=root>nextRight;
while(root)
{
if(root>left)
return root>left;
if(root>right)
return root>right;
root=root>nextRight;
}
return NULL;
}

Aashish
June 27, 2012 We can further reduce the space to 24 bytes. Lets see how.
There can be only 8 information: pawn,king,queen,bishop,knight,rook,no piece[empty] & color of piece.
So, we need 3 bits to represent to represent these information.
We can design a 8x8 chessboard with each slot occupying exactly 3 bits using bitfield[can represent range from 0 to 7].So, the space reduces to 64x3bits=24bytes.
Why not use only minheap where pages with least recently used can be extracting the head of the minheap. Heap will be formed based on the time of use. Say we use a variable clock which represents the time of use. A new page will be inserted in logn time.
I don't see any use of hashmap there.
1. Build a minleft[] which contains the element less than arr[i] from 0 to i1 ,else 1.
2. Build a maxright[] which contains the element greater than arr[i] from i+1 to N1 ,else 1.
3. run a loop from 0 to N1,stat cheching the elements of minleft[] & maxright[].
if(minleft[i]<maxright[j]) j++ update maxdiff(ji)
else i++
x x a x a x b x b x c x a b x
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
lets say we need to search for segment containing a,b,&c.
1.start pointer is at 0, last pointer is at 0.
2.start pointer is at 2, last pointer is at 2.
3.start pointer remains at 2, last pointer is at 4.
4.Both words[start & last pointer ] are same, update start pointer to 4[since word at index 3 has no purpose].
5.start pointer is at 4, last pointer is at 12.
6.Both words are same, update start pointer to 8, last pointer remains at 12.
7.start pointer is at 8, last pointer is at 13.
8. Found both words equal,update start pointer to 10,last pointer being at 13[this is the smallest segment.]
9. start pointer is at 10,last pointer is at 14.
10. The file is finished. So, the smallest segment is from 10 to 13.
I don't know what issues are you finding in this approach.
To me, its working perfectly.
If the get() & reverse is O(1), then the sorting reduces to O(N).
No, pan cake is different from insertion sorting.
In insertion sorting, an element is inserted at proper place while it is comparing with every other element. Here elements are inserted at their proper place usin reverse() method.
This is a version of PanCake sorting where we are allowed to reverse the array from i to j.
1. Find the minimum element say its index is j.
2. reverse(i,j) where i represents how many elements have sorted till now starting from 0 to N1. So, the minimum element will come to its position.
3. Increment i. Again find the minimum element from i to N1.
4. Repeat above steps until i is not equal to N1.
Here is the complete code.
#include <stdio.h>
void swap(int *a,int *b)
{
int t=*a;
*a=*b;
*b=t;
}
void reverse(int *arr,int l,int h)
{
while(l<h)
{
swap(&arr[l],&arr[h]);
l++;h;
}
}
int findMin(int *arr,int l,int h)
{
int min=0,i;
for(i=l+1;i<h;i++)
if(arr[i]<arr[min])
min=i;
return min;
}
void sort(int *arr,int N)
{
int i,j;
for(i=0;i<N;i++)
{
j=findMin(arr,i,N);
reverse(arr,i,j);
}
for(i=0;i<N;i++)
printf("%d ",arr[i]);
}
int main()
{
int arr[]={2,1,5,4,6},size;
size=sizeof(arr)/sizeof(arr[0]);
sort(arr,size);
return 0;
}

Aashish
June 25, 2012 A graph is called as disconnected if there exists at least one pair of vertices (u,v) such that there is not any path between them.
To make the above definition correct, Separate one vertex & join the remaining n1 vertices.
So, it can be done in n1C2=(n1)*(n2)/2
@eugene, LOC doesn't matter at all.
You can also write a complex for loop in a single line which does the same work if it was written in a simpler version of 5 lines.
Better code means processor will take less clock cycles to execute the instructions.
Have you ever thought why bitwise operations are assumed to be better?
Suppose we need to check whether a number is even or odd,Which of the two version would you prefer?
if(n%2==1)//for odd
or
if(n&1)//for odd
The same explanation also lies here.
I have thought one approach.More like as suggested by @eugene.
Let me know whether it is efficient.
Use TRIE data structure where phone numbers will be inserted in sorted order. In the leaf nodes, we will have pointers to the original phone number[the phone numbers will be in the form of strings right!].
In order to handle collisions[two different phone numbers after sorting may represent the same leaf node],
we can have linked list at the leaf nodes. Whenever a new phone number is being inserted & the leaf node is already having pointer to some other phone number, we will chain this phone number[create a new node in the linked list & insert its pointer there].
Now, During search operation, lets say 321, first sort the string to be searched[say 123 in this case].
After reaching 123, an inorder traversal would be sufficient.Whenever a leaf node is encountered, all the strings[phone numbers] can be accessed through single linked list.
Comments are welcome.
I think the choice depends upon whether the threads shared data & code or not. If the threads are independent, then multiple processes with single thread would be better.
However,if the threads are interrelated, i would prefer process with multiple threads.
Also, as pointed by rukawa, if the threads are independent & one process with multiple threads are used, then one thread can make the entire process go down.
EDIT:
The previous algo failed for some input cases. Thanks to @ buckCherry for pointing it out. Below is the fresh algo.
Find the start of the cycle through Floyd cycle detection algorithm. The total number of nodes is the count of nodes that form cycle and count of nodes that are not part of cycle. If the list doesn't contain cycle, count of nodes that are part of cycle is zero.
1. Maintain two pointers called hare & tortoise.
2. move hare two steps & tortoise one step until either both become equal or hare reaches NULL.
3. Move tortoise to the start of the list. Move tortoise and hare step by step until their next node don't point to the same node( in case there is no cycle , hare will point to NULL. Ignore step#4 in this case). This next node is the starting node of the cycle. Meanwhile count the number of nodes that are not part of the cycle.
e.g. A>B>C>D>E>D
The number of nodes that don't form cycle is 3.
4. Count the number of nodes in the cycle. Start tortoise from the starting node of the cycle and keep on moving until it doesn't reach its initial position.
In the example explained in step#3, the number of nodes in the cycle is 2.
5. The answer is count in step#3 + count in step#4.
Base 26 representation
 Aashish June 30, 2012