Adobe Interview Question for MTSs


Country: India
Interview Type: In-Person




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

keep a variable c and every time u push it..then increment its priority such that..the element with high priority will be removed first ..so the element which is pushed in the end will have highest value of c so it will be the first element to be popped off.....
implement priority queue using linked list..and priority will be the time of insertion which we will track with c variable..

- c7c7 October 05, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

@above: could u please explain your algorithm with an example. I am not able to get it..thanks

- Shwetank October 06, 2012 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 vote

class Stack
{
    private int c = 0;
    private PriorityQueue pq;
    public void Push(int x)
    {
        c++;
        pq.Insert(x,c);
    }
    public int Pop()
    {
        c--;
        return pq.Remove();
    }
}

- DarkKnight October 07, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

is this push and pop O(1) implementation ?

- sukusuku October 15, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

This push pop operation takes O(lg n) time....where n is the number of already existing nodes..

- Sourin June 23, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@sukusuku @Sourine
correct me if i am wrong . We will have pointer to the last node of the list (node having max priority) , so we can add and remove (last node) in O(1) time.

- Saurabh Jain October 10, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

no O(1) solution exits.....

- Anonymous November 05, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

You can do it with the help of a queue implementation but how would you do it using a heap based implementation ? I tried but somehow or the other either we need to know the internal implementations of heap ( simple push and pop won't do) or one of the operations will be O( log n )

- sankalp October 11, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

can we implement a priority queue by stack ?
can we implement a stack by priority queue?

- Anonymous March 25, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

We can do push in O(1) if the priority queue being used is based on Fibonacci heap as its insertion operation takes O(1). But in this case pop will take O(lg n) using ExtractMax of Fibonnaci heap.

- Kartik Perisetla August 24, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

here one variable is storing two values that is one for c and other for the value of the element ... how is this possible?

- Anonymous May 30, 2014 | 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