Interview Question for Developer Program Engineers


Team: India
Country: India
Interview Type: In-Person




Comment hidden because of low score. Click to expand.
0
of 0 vote

see: stackoverflow.com/questions/4770627/how-to-implement-3-stacks-with-one-array/4770793#4770793

- cobra July 08, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

ok thanks.naga are you from pagalguy ?

- sujita July 08, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

no

- cobra July 08, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

divide array in 3 equal parts ....0-->n/3,n/3+1-->2n/3, 2n/3--> n

- atul gupta July 08, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Looks like you beat me to it. My answer explains this solution in considerably more detail.

- eugene.yarovoi July 09, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Stack 1 grows from left to right. Stack 2 from right to left. Stack 3 in the center such that it grows in one direction initially and if finds no space, reverses and grows in the other direction.
Example.

s1 = {1,2,3}
s2 = {4,4}
s3 = {7,8,9}

Array of size 10 looks like this

[1,2,3, x, x,7,8,9,4,4]

stack 1 and stack 2 give warning when there is no space to fill a new element.
stack 3 tries to use free spaces on either side. Above if we push(stack3, 10)
It will reverse itself and insert 10 to the left.

[1,2,3, x,10,9,8,7,4,4]

^

- Noobie July 09, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

So what will you do when I want to push something to stack 2 after you've completed that reverse operation? Reverse again? Seems like you might be doing a worst-case O(n) reverse for every push.

- eugene.yarovoi July 09, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Yes.Agree with you. In terms of time it will do horribly when stacks start getting full.

- Noobie July 10, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I would say that generally I would expect a stack data structure to have O(1) pop/push.

- eugene.yarovoi July 10, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

First stack grows from left to right. Second from right to left and third in middle.
When an element is inserted into third stack insertion is done like pendulum movement i.e once from left and once from right.In this way we have less wastage of space on an average.
We keep left, middle,right pointers and if left == middle we can't insert in stack1 and right = middle we can't insert from right.

- Raviteja July 13, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Start 1st stack from left, 3rd stack from right and 2nd stack from the middle. While doing operations on the stacks, we will try to maintain the invariant: the second stack occupies a contiguous chunk b/w the left chunk and the right chunk, and the 2 empty spaces b/w these 3 chunks are of equal size (or differ by atmost 1).

For example, here's a valid configuration of the array (*s denote empty locations):
{1,2,2,3,4,*,*,*,2,3,4,*,*,*,*,1,4}. And here's an invalid configuration: {1,2,3,4,5,*,2,1,3,*,*,*,1}.

If the invariant is maintained, whenever any 2 stacks meet, we have exactly 1 empty slot in the array, and then we can issue a warning "Stack getting full!".

Now how to maintain this invariant? For every element of the 2nd stack, we just need to maintain a variable which says whether the last element was added to the left or to the right. Also, while doing any push() or pop() operations on the 1st or 3rd stack, we need to push2(pop2()) i.e. pop an element of the 2nd stack and push it on the 2nd stack again (to 'refresh' the invariant).

I'm not completely sure if this works ;) but its O(N) extra space and O(1) for all push/pop operations.

- anujkaliaiitd July 08, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

hi anuj, are u from delhi??
we used to be pg mates...!

- prateek July 08, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

yes, but this is not the place:
http : / / www . facebook . com / beanuj

- anujkaliaiitd July 08, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

The problem is that you're not maintaining any ordering information in the second stack. If I want to pop off the last 100 elements I inserted into stack 2, how will stack 2 know which ones they were? They were definitely some of the ones on the left and some of the ones on the right, but in what order and how many from each side? You've lost that information.

- eugene.yarovoi July 09, 2012 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Here's a possible way to do it: consider the first third of the array to be devoted to elements of stack 1, the second third to stack 2, the last third to stack 3. If you run out of space devoted to any stack, double the size of the whole array.

To push on to the stack, we'll use a simple calculation like (totalArraySize * stackNumber / 3) + existingSizeOfGivenStack. To pop, we'll remove the element at (totalArraySize * stackNumber / 3) + existingSizeOfGivenStack - 1.

What's the complexity of resizing, you might ask? After resizing an array of n elements at a cost of O(n), each stack has n/3 capacity, and since that's doubled from before, previously the largest stack had n/6 elements. So there's at least n/6 free space in each stack, and it will be at least that many operations before we resize again.. So the O(n) cost of resizing is amortized over n/6 elements, for an O(1) cost per element. So pushing and popping is O(1).

The array of size n contains at least n/6 elements, so space usage is O(n) with the number of elements.

- eugene.yarovoi July 09, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Why the downvote? I would say my solution is probably the standard solution to this classic problem.

- eugene.yarovoi July 09, 2012 | Flag
Comment hidden because of low score. Click to expand.
-2
of 2 vote

we can do above question by merge sort iam write

- nelakurthivamshi July 08, 2012 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More