Amazon Interview Question SDE-2s
Country: India
Interview Type: Written Test
class MyMaxHeap
{
public:
MyMaxHeap(int n)
{
arr.resize(n);
currentSize = 0;
}
int getSize()
{
return currentSize;
}
int top()
{
return currentSize == 0 ? INT_MIN : arr[0];
}
void add(int val)
{
if (currentSize < arr.size())
{
arr[currentSize++] = val;
heapifyUp(arr, currentSize-1);
}
else if(arr[0] > val)
{
arr[0] = val;
heapifyDown(arr);
}
}
void print()
{
for (int i = 0; i < currentSize; i++)
cout << arr[i] << ",";
cout << endl;
}
private:
void heapifyUp(vector<int> &arr, int childIndex)
{
if (childIndex == 0)
return;
int parentIndex = childIndex / 2;
while (childIndex > 0 && arr[parentIndex] < arr[childIndex])
{
swap(arr[parentIndex], arr[childIndex]);
childIndex = parentIndex;
parentIndex /= 2;
}
}
void heapifyDown(vector<int> &arr)
{
int parentIndex = 0;
int childIndex = getMaxChildIndex(arr, parentIndex);
while (childIndex != -1 && arr[parentIndex] < arr[childIndex])
{
swap(arr[parentIndex], arr[childIndex]);
parentIndex = childIndex;
childIndex = getMaxChildIndex(arr, parentIndex);
}
}
int getMaxChildIndex(vector<int> &arr, int index)
{
int leftChild = 2 * index + 1;
int rightChild = 2 * index + 2;
int ans = -1;
if (rightChild < currentSize)
ans = arr[rightChild] > arr[leftChild] ? rightChild : leftChild;
else if (leftChild < currentSize)
ans = leftChild;
return ans;
}
int currentSize;
vector<int> arr;
};
int main()
{
//stream of numbers
vector<int> input = { 2,3,5,6,7,8,1,8,3,4,67,0 };
int maxSize = 3;
MyMaxHeap heap(maxSize);
for (int i = 0; i < input.size(); i++)
{
cout << "Adding " << input[i] << endl;
heap.add(input[i]);
heap.print();
}
getchar();
}
List<int> GetMinimums(List<int> stream , int totalMinElements){
int [] results = new int(n);
int minElementsSoFar = 0;
foreach(var num in stream){
var pivotIndex = FindPivot(result,0,minElementsSoFar-1,num);
for(int j=pivotIndex;j<minElementsSoFar && j<totalMinElements-1;j++)
results[j+1] = result[j];
results[pivotIndex] = num;
}
return results;
}
int FindPivot(int[] result,int low, int high,int key){
if(low > high) return low;
var mid = (low+high)/2;
if(result[mid] < key)
return FindPivot(result,mid+1,high,key);
else
return FindPivot(result,low,mid-1,key);
}
class Reservoir{
public:
Reservoir(int n){
size = n;
}
// put the number in stream in reservoir
void put(int n){
reservoir.push_back(n);
sort(reservoir.begin(), reservoir.end());
if(reservoir.size() >= size){
reservoir.resize(size);
}
}
// get the nth largest number
int get(){
return reservoir.back();
}
private:
int size;
vector<int> reservoir;
};
I would keep the top N (min in this case) in a sorted list. For each new number, I will check against the max of this list. If the new number is less than the max, than it deserves to be in the list and the max number if thrown out. e.g. if we order the list in decrementing order, list[0] will be the max of the min N.
list = [10000 for n in range(N)]
def process_number(n):
if n < list[0]:
list[0] = n
i = 1
while i < N and list[i-1] < list[i]:
(list[i], list[i-1]) = (list[i-1], list[i])
list[N] contains the N minimum values processed.
Instead of having recursive functions, we can just keep the code clean.
public static bool Find()
{
int[] minElements = FindMinElements(new[] {5, 3, 2, 34, 9, 1, 4}, 3);
Console.WriteLine(string.Join(",", minElements));
Console.ReadLine();
return true;
}
private static int[] FindMinElements(int[] ints, int numberOfMinElements)
{
var minArray = new int[numberOfMinElements];
for (int i = 0; i < numberOfMinElements; i++)
{
minArray[i] = int.MaxValue;
}
var maxIndex = numberOfMinElements - 1;
for (int currentIndex = 0; currentIndex < ints.Length; currentIndex++)
{
if (minArray[maxIndex] > ints[currentIndex])
{
var newElement = ints[currentIndex];
for (int i = 0; i < numberOfMinElements; i++)
{
if (minArray[i] > newElement)
{
var temp = minArray[i];
minArray[i] = newElement;
newElement = temp;
}
}
}
}
return minArray;
}
Instead of using recursive functions, we can just keep the code simple and clean.
public static bool Find()
{
int[] minElements = FindMinElements(new[] {5, 3, 2, 34, 9, 1, 4}, 3);
Console.WriteLine(string.Join(",", minElements));
Console.ReadLine();
return true;
}
private static int[] FindMinElements(int[] ints, int numberOfMinElements)
{
var minArray = new int[numberOfMinElements];
for (int i = 0; i < numberOfMinElements; i++)
{
minArray[i] = int.MaxValue;
}
var maxIndex = numberOfMinElements - 1;
for (int currentIndex = 0; currentIndex < ints.Length; currentIndex++)
{
if (minArray[maxIndex] > ints[currentIndex])
{
var newElement = ints[currentIndex];
for (int i = 0; i < numberOfMinElements; i++)
{
if (minArray[i] > newElement)
{
var temp = minArray[i];
minArray[i] = newElement;
newElement = temp;
}
}
}
}
return minArray;
}
Can we use insertion sort here ?During the first stream of numbers we can keep it sorted and insert new elements into the n element array as and when it comes.
import java.util.ArrayList;
/**
* Created by akhil on 12/13/2015.
*/
class Heap {
private int[] hArray;
private int maxSize;
private int currentSize;
public Heap(int maxSize) {
this.maxSize = maxSize;
this.currentSize = currentSize;
hArray = new int[maxSize];
}
public int insert(int data, int n) {
if (currentSize == maxSize)
return 0;
hArray[currentSize] = data;
// if(hArray.length<n)return 0;
trickleUp(currentSize++, n);
return hArray[0];
}
public void trickleUp(int index, int n) {
int parent = (index - 1) / 2;
int bottom = hArray[index];
while (index > 0 && hArray[parent] > bottom) {
hArray[index] = hArray[parent];
index = parent;
parent = (parent - 1) / 2;
}
hArray[index] = bottom;
int count = 0;
for (int i = 0; i < n; i++) {
System.out.println(" " + hArray[i]);
}
System.out.println("------------");
}
}
public class StreamMin {
public static void findMin(Heap hp, ArrayList<Integer> lst, int number, int n) {
lst.add(number);
hp.insert(number, n);
}
public static int findMinOfStream(ArrayList<Integer> stream) {
int minVal = 0;
return minVal;
}
public static void main(String args[]) {
final ArrayList<Integer> lst = new ArrayList<Integer>();
final Heap hp = new Heap(20);
Thread t = new Thread() {
public void run() {
for (int i = 0; i < 20; i++) {
findMin(hp, lst, i, 5);
try {
Thread.sleep(1000);
} catch (InterruptedException e) {
}
}
}
};
t.start();
}
}
- NoOne October 07, 2016// ZoomBA def infinite_stream(){ random(1000) } n = 5 h = heap(n) // infinite stream iterator h = lfold ( infinite_stream , h ) -> { println ($.o) ; break( $.o > 980 ) ; $.p += $.o } println(h)