## 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 India`void 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

A simple DP approach:

The function can be written as:

F(N, A, S) = F(N - 1, A, S - 1) + F(N - 1, A, S - 2) +........+ F(N - 1, A, S - A)

Where, The F(N, A, S) represents the number of ways of getting S with N dice each with A faces, numbered from 1 to A.

Explaining the above equation in words,

Find the number of ways of getting Sum (S - 1) from (N - 1) dice +

Find the number of ways of getting Sum (S - 2) from (N - 1) dice +

.................

..................

Find the number of ways of getting Sum (S - A) from (N - 1) dice

Carefully handle the base cases like:

1. N = 1, S > A

2. S < 1

@buckCherry,,

1) By head, i mean start/first element of the list only.

2) Sum of counts yield 4 nodes( 3 + 1 ).Step#4 outputs value of count as 1.

Explaining once again: Fix hare at node C and move tortoise to node A. Move both hare and tortoise one step. Now, hare is at node D and tortoise is at node B. Now, next of B and next of D are same node C. So, the algo stops here.

Let me know you are facing any problem.

Thank you.

@buckCherry, Apologies. The concept of Double Linked List is not correct, same for cycle concepts.

Coming back to your initial doubt, how my algo works in your example?

In step#2, hare and tortoise meet at node C. Now move tortoise to node A. So, step#3 outputs 3 nodes( A, B and C).

In step#4, fixing hare at node C and moving tortoise at node A, move hare and tortoise one step until next of both are not equal. So, move hare to node D, and tortoise to node B. Now, next of both are equal, so stop here. The total number of nodes is 4 now.

NOTE: The above algo is inspired from Floyd's Cycle detection algo.

Please let me know if you have still any doubts.

So, you think the post is not relevant.

May i ask you where did you find the post is wrong.

Do not let other people think in your way. If they want, they will read.

If you have a better solution, why don't you post it and let other readers judge it.

And its not my blog. I read it there and found it a nice solution.

So, posted the link here.

CareerCup has not well defined indentation. If i would have posted the entire content, it would be messy to read. It is better to go through the link.

If you would have been interested in the solution, you would have been read it carefully. But, i guess you are only interested in downvoting and writing sarcastic comments.

@eugene.yarovoi, Before writing my thoughts, i experimented how firefox works in this respect. I found that they even keep browser history of 6 months old.

Here is my thought:

I would use a double linked list of dates. Each day, browser is accessed, i would be adding a new node to it. Now, each node of the double linked list will be another linked list for storing the URL's. I don't think timestamp is necessary here. We can add new visited pages to head of the list. In this way, the recent visited pages would be near the front of the list.

I liked your idea of treeSet. It will help if a user visits previously visited page. We need to adjust the nodes of the list.

Now, if the user wants to see the history by data, list will serve the purpose. If the user wants to search a particular URL, we can provide prefix searching like TRIE.

Let me know your thoughts.

@eugene.yarovoi, here is my approach:

```
void push( void** stack, int* top, void* data, size_t size )
{
unsigned i;
++*top;
stack[*top] = malloc( size );
for( i = 0; i < size; ++i )
( (char*)stack[*top] )[i] = ( (char*)data )[i];
}
int main()
{
void* stack[10];
int top = -1, data = 10;
char ch = 'a';
push( stack, &top, (void*)&data, sizeof( int ) );
push( stack, &top, (void*)&ch, sizeof( char ) );
printf( "%d ", *(int*)stack[0] );
printf( "%c ", *(char*)stack[1] );
return 0;
}
```

I want you to check & comment if you find any issues here.

- Aashish September 08, 2012@Andy2000, after some mathematical calculations, i concluded that the distance will be minimum if we fix the meeting point as one of the person's co-ordinates. Can the meeting point be one of the person's position? If yes, the solution goes simple. O( N^2).

Let me know if i am missing anything.

```
void generateIPUtil( char* str, char* output, int depth, int countDot, int val )
{
if( !*str )
{
output[depth] = '\0';
if( countDot == 3 && output[depth-1] != '.' )
printf( "%s\n", output );
}
else
{
output[depth] = *str;
val = val * 10 + *str - '0';
if( val <= 255 )
{
if( countDot < 3)
{
output[depth + 1] = '.';
generateIPUtil( str+1, output, depth+2, countDot+1, 0 );
}
generateIPUtil( str+1, output, depth+1, countDot, val );
}
}
}
void generateIP( char* str )
{
char output[30];
generateIPUtil( str, output, 0, 0, 0 );
}
```

Working code here: ideone.com/GMs87

- Aashish September 07, 2012This can be done in O(1) space.

Time complexity: O(MxN)

Find the max item in the row. Check whether it is the smallest in the column.

```
void foo(int (*arr)[COL])
{
int i,j,max, min;
for( i = 0; i < ROW; i++ )
{
max=0;
for( j = 1; j < COL; j++ ) // find max in the row
if(arr[i][j] > arr[i][max])
max=j;
min = 0;
for( j = 1; j < ROW; ++j ) // find min in the column
if(arr[j][max] < arr[min][max])
min=j;
if( min == i ) // if both items are same
printf("%d", arr[i][max]);
}
}
```

Here is the working code: ideone.com/XfGJV

- Aashish August 20, 20121. Take a BST with extra field count of occurrence.

2. Maintain a min heap of size 2 dealing with the frequency. Whenever any item occurrence is more than the frequency of the head, replace it & update heap.

3. At the last, the top of the heap gives the required item.

```
int isValid(char* str,int k)
{
int i;
if(k<=0) return 0;
for(i=0;i<k;++i)
{
if(str[i]=='0' && (i==0 || str[i-1]=='0'))
return 0;
}
return 1;
}
void print(char* str,int k)
{
int i;
for(i=0;i<k;++i)
printf("%c",str[i]);
printf("\n");
}
int count;
void countValidString(char* str,int depth,int k)
{
if(depth<0)
{
if(isValid(str,k))
{
++count;
print(str,k);
}
}
else
{
str[depth]='0';
countValidString(str,depth-1,k);
str[depth]='1';
countValidString(str,depth-1,k);
}
}
```

Complete working code: ideone.com/cDPgI

- Aashish August 10, 2012Perform binary search.

```
int findFirstOccurrence(int* arr,int l,int h,int tofind)
{
int mid;
if(l>h) return INT_MIN;
if(l==h)
return arr[l]==tofind?l:-1;
mid=(l+h)>>1;
if(arr[mid]==tofind && (mid==l || arr[mid]>arr[mid-1]))
return mid;
if(tofind<=arr[mid])
return findFirstOccurrence(arr,l,mid-1,tofind);
return findFirstOccurrence(arr,mid+1,h,tofind);
}
```

Complete code here: ideone.com/8q91s

- Aashish August 05, 2012Use references in the same way you use pointers.

```
class A
{
public:
virtual void show()
{
cout<<"A class show()"<<endl;
}
};
class B: public A
{
public:
void show()
{
cout<<"B class show()"<<endl;
}
};
int main()
{
B b;
A a;
A &ref=b;
ref.show();
return 0;
}
```

Complete code here: ideone.com/Zuebz

- Aashish August 05, 2012The problem boils down to:

Given an array, find two indices min & max such that A[max]-A[min] is maximum and max>min.

```
int findMAxProfit(int* A,int n) // n is the number of days
{
min=max=0;
maxProfit=INT_MIN;
for(i=1;i<n;++i)
{
if(A[i]<A[min]) min=i;
if(A[i]-A[min] > maxProfit) // if you want, update buy & sell day here
maxProfit=A[i]-A[min];
}
return maxProfit;
}
```

Complete code here: ideone.com/Xt1ZA

- Aashish August 05, 2012```
#define N 1
char* g()
{
char* p="Hello";
printf("g() called\n");
return p;
}
char* (*foo())()
{
char* (*p)()=g;
printf("foo() called\n");
return p;
}
int main()
{
char* (*(*ptr[N])())();
char* (*p)();
ptr[0]=foo;
p=(*(ptr[0]))();
(*p)();
return 0;
}
```

Complete code here: ideone.com/3kdhv

- Aashish August 04, 2012Time complexity: O(N)

```
int findTrappedWater(int* H,int size)
{
int i,j,water=0,temp;
for(i=0;i<size;)
{
j=i+1;
temp=0;
while(j<size && H[i]>H[j])
{
temp+=H[j];
j++;
}
if(j!=size) // decreasing length histogram
water+=(j-i-1)*H[i]-temp;
i=j;
}
return water;
}
```

Complete code here: ideone.com/xCsHn

- Aashish August 04, 2012An easy approach:

1. Name the levels as 1,2,3.... A cup numbered i will pour extra water into cups with number i+level and i+level+1.

I am using an integer array cup[] to store the amount of water in each cup. The same logic applies to the float also.

Here is the pseudo code:

```
void fillWater(int C,int L,int n,int* cup)
{
int i,level=1,j,diff;
cup[1]=L;
for(i=1;i<=n;)
{
for(j=i;j<i+level;++j)
{
L=cup[j];
diff=(L-C)<=0?-1:L-C;
if(diff>0)
{
cup[j]-=diff;
cup[j+level]+=diff/2;
cup[j+level+1]=diff/2;
}
}
level++;
i=j;
}
for(i=1;i<=n;++i)
printf("cup number %d has %d water\n",i,cup[i]);
}
```

C: Capacity of each cup

L: Water poured in the first cup.

n: Number of cups

Complete working code here: ideone.com/7u7yU

```
void foo(int* res,int depth,int N,int tillnow)
{
int i;
if(tillnow==N)
print(res,depth);
else if(tillnow>N)
return;
else
{
for(i=N&1?N:(N-1);i>=1;i-=2)
{
if(!depth || i<=res[depth-1])
{
res[depth]=i;
foo(res,depth+1,N,tillnow+i);
}
}
}
}
```

Complete code here: ideone.com/tyxoZ

- Aashish July 29, 2012```
void interleaving(char* s1,char* s2,char* res,int depth)
{
if(!*s1 && !*s2)
{
res[depth]='\0';
printf("%s\n",res);
}
if(*s1)
{
res[depth]=*s1;
interleaving(s1+1,s2,res,depth+1);
}
if(*s2)
{
res[depth]=*s2;
interleaving(s1,s2+1,res,depth+1);
}
}
```

Complete code: ideone.com/35VNh

- Aashish July 29, 2012**CareerCup**is the world's biggest and best source for software engineering interview preparation. See all our resources.

Open Chat in New Window

As per my understanding, the solution has nothing to do with "forest of binary trees". We can just crawl the parents of both nodes n1 and n2 upwards and see if their parents are same.

Sample code module below:

Please let me know if I missed anything:

- Aashish December 26, 2015