Amazon Interview Question Software Engineer / Developers


Country: India
Interview Type: Written Test


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

Looks like below is not correct
B[i] = min(A[i], A[i+1], ......., A[i-K+1]), where K will be given.

here A[i-K+1] should be A[i+k-1]

if i=0, and k=4 then i-K+1 will be negative, which is not correct

- Anonymous on May 13, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
4
of 4 vote

the algo could go on like this....
1.scan the array in reverse order and create a min heap of k elements.
2.the element B[i] would be the element at the root of min heap.
3. now delete the element at A[K+i -1] and insert the element A[i-1]
4.reheapify the heap.
TC-O(nlogk)

- codinglearner on May 17, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

deletion of element A[K+i-1] is O(k) operation. So, time complexity of solution is O(nk).

- jin on August 07, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

this algorithm is so cool.........I did it for another problem today..

- aaron liang on September 16, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

you can add an index point to a[k+i-1], then the deletion is O(1)

- yjy on November 05, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

How this algo will work for following input :

arr[] = {9,8,7};
N=3;
k=2;

So, as per step (i),starting from last K elements we will maintain MIN heap.
So, at first, heap will be {7,8} with 7 sitting at top. << b[1] = 7
But as per step (iii), 8 will be replaced by 9
So next time b[0] will be 7 as 7<9, and resulted output will be {7,7} instead of {8,7}

- varunnayal on November 21, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Is it not a sliding window problem ?

- Anonymous on May 27, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

That's definitely a sliding window problem and it's solved in O(n) time and with O(k) additional space.

- Aleksey.M on January 28, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

yes it should be i+k -1.

- krishna on May 13, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

segment tree concept will be used

- sanju on May 14, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

In segment tree the extra space order will not be maintained within O(k)

- Psycho on July 11, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

segment tree concept will be used

- sanju on May 14, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

segment tree concept will be used

- sanju on May 14, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

It won't work - b[1] may be between a[0] and a[k-1], but not b[0].

- jzhu on May 16, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

It won't work - b[1] may be between a[0] and a[k-1], but not b[0].

- jzhu on May 16, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

It won't work - b[1] may be between a[0] and a[k-1], but not b[0].

- jzhu on May 16, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think question is that k is some given number and length of B is N-k+1,
So can be done in O(n) Time Complexity
Traverse the array from i=N-k+1 to i=0{
keep one min variable if(a[i]<min) min=a[i]
b[i]=min;
}

- Sushil Kumar on May 16, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

the algo could go on like this....
1.scan the array in reverse order and create a min heap of k elements.
2.the element B[i] would be the element at the root of min heap.
3. now delete the element at A[K+i -1] and insert the element A[i-1]
4.reheapify the heap.
TC-O(nlogk)

- codinglearner on May 17, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

how will you find out a[k+i-1] in the min heap.you have to linearly search for the element for that.so it will be O(Nk).

- leet on June 12, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

we can use selection to find the min. number and complexy will be o(n) and space used will be o(1).....

- Anonymous on June 23, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Solution: O(n) time and excluding the result space + O(1) space if there are no duplicates (if there are duplicates we can move them to the end of the array and use extra HashMap to count the duplicates)
Here is the java code for nonDuplicate version (can be easyly modified for duplicates) :

public int[] getFirstElements(int[] arr, int k) {
  int[] result = new int[k];
  
  int currK = 0;
  for (int i = 0; i < arr.length && currK < k; i++)
   if (arr[i] != 0)
    result[currk++] = arr[i]; 
 
  return result 
 }
 
 //O(n) time
 private void sortArr(int[] arr) {
  for (int i = 0; i < arr.length; i++)
   while (arr[i] != i || arr[i] != 0)
    swap(arr, arr[i], i);
 }

- GKalchev on June 23, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

It seems you missed the full code

- GSi on October 04, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

We can use binary search for it.
Step-1: Add 1st k elements to bst tree.
Step-2: Print the min element from bst tree
Step-3: Print min element and Remove the ith element
Step-4: Add the i+k+1 th element..i++
Step-5: Repeat Step-2,3,4 until no more elements

- Vignesh V on July 11, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Using queue.

int arr[1000001];

void printKMax(int n, int k) {
    deque<int>  Qi(k);
 
    int i;
    for (i = 0; i < k; ++i) {
        while ( (!Qi.empty()) && arr[i] >= arr[Qi.back()])
            Qi.pop_back();  // Remove from rear
 
        Qi.push_back(i);
    }
 
    for ( ; i < n; ++i) {
        printf ("%d ", arr[Qi.front()]);
 
        while ( (!Qi.empty()) && Qi.front() <= i - k)
            Qi.pop_front();  // Remove from front of queue
 
        while ( (!Qi.empty()) && arr[i] >= arr[Qi.back()])
            Qi.pop_back();
 
        Qi.push_back(i);
    }
 
    printf ("%d", arr[Qi.front()]);
}

- Psycho on July 20, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-2
of 2 vote

can be done in O(N)
1.b[0] = the minimum of (0,1,K-1)
2. b[1] = min(b[0], a[k]
3. b[2] = min(b[1], a[k+1]

- Siva on May 13, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Bullsh**

- John on May 16, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Bullsh**

- John on May 16, 2012 | Flag


Add a Comment
Name:

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

Books

is a comprehensive book walking you through 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