Amazon Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: In-Person
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++)
{
k.add(a[i]);
System.out.println(k.findKMax());
}
}
public void add(int a)
{
if(pq.size()>=this.capacity && pq.peek() < a)
{
pq.poll();
pq.add(a);
}
else if(pq.size() < this.capacity)
pq.add(a);
}
public List<Integer> findKMax()
{
List<Integer> list = new ArrayList<>(pq);
return list;
}
}
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
class Tracker {
public:
Tracker(int k)
{
k_ = k;
}
void AddNumber(int n)
{
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) {
tr.AddNumber(n);
auto max_numbers = tr.GetMaxNumbers();
for (int m : max_numbers) {
cout << m << ", ";
}
cout << "\n";
}
}
Edit:
Although as pointed out k is not the index but the number of elements, we can apply the same concept:
- tnutty2k8 August 26, 2017