## Amazon Interview Question for Software Engineer / Developers

Country: United States
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
1
of 3 vote

``geeksforgeeks.org/kth-largest-element-in-a-stream/``

Edit:

Although as pointed out k is not the index but the number of elements, we can apply the same concept:

``````Solution #1  O(k)
- Keep sorted array of size K descending
- on every new element
- check if larger than last
- if so pop last( smallest ) and insert new item

Solution #2 O(logk)
- Use Binary Search Tree
- on insert check if item is larger than smallest
- if so remove smallest and insert new item

Solution #3 O(logk) but faster min lookup
- Use MinHeap
- on insert check if item is larger than smallest
- if so remove smallest and insert new item``````

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

K is not an index here, it's the number of elements 3,5,10 etc.

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

``````import java.util.PriorityQueue;
import java.util.ArrayList;
import java.util.List;
public class KMaximumNumbers
{
PriorityQueue<Integer> pq;
int capacity;
KMaximumNumbers(int k)
{
pq = new PriorityQueue(k);
this.capacity = k;
}

public static void main(String[] args)
{
KMaximumNumbers k = new KMaximumNumbers(3);
int[] a = {0, 10, 7, 1, 3, 4, 9, 5};
for(int i = 0;i<a.length;i++)
{
System.out.println(k.findKMax());
}
}

{
if(pq.size()>=this.capacity && pq.peek() < a)
{
pq.poll();
}
else if(pq.size() < this.capacity)

}

public List<Integer> findKMax()
{
List<Integer> list = new ArrayList<>(pq);
return list;
}
}``````

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

``````#include <iostream>
#include <vector>
#include <queue>

using namespace std;

class Tracker {
public:
Tracker(int k)
{
k_ = k;
}
{
if (pq_.size() >= k_ &&
n > pq_.top())
{
pq_.pop();
}
if (pq_.size() < k_) {
pq_.push(n);
}
}
vector<int> GetMaxNumbers()
{
vector<int> out;
while (!pq_.empty()) {
out.push_back(pq_.top());
pq_.pop();
}
for (int n : out) {
pq_.push(n);
}
reverse(out.begin(), out.end());
return out;
}

private:
int k_;
priority_queue<int, vector<int>, greater<int>> pq_;
};

int main(int argc, char const **argv)
{
vector<int> in = {4, 5, 2, 1, 7, 3, 6, 20, 0, -5, 1, 100};

Tracker tr(3);
for (int n : in) {
auto max_numbers = tr.GetMaxNumbers();
for (int m : max_numbers) {
cout << m << ", ";
}
cout << "\n";
}
}``````

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.

### 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.