Groupon Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: Phone Interview
Use max-heap of size K, where the K is the count of min values for which the indices have to be stored/found. A slight modification to the max-heap will need to be required to store not only the values but their indices too. Something similar to the structure below:
struct val_stat {
int idx;
int value;
val_stat () : idx(-1) {} // entry not initialized
};
I would use something similar to the pseudocode below:
template <class T>
class maxheap
{
struct val_stat {
int idx;
int value;
val_stat () : idx(-1) {} // entry not initialized
};
//CTOR
maxheap(int size) : maxsize(size), cursize(0) {}
/** Push to the heap if we have enough space.
If the heap is full, then pop the topmost
value first.
*/
void push(T, int idx)
{
if (cursize == maxsize)
pop();
// code to add the incoming value to the heap
....
}
T pop()
{
T retv = heaptop();
// code to remove the topmost value
// and heapify the rest of the entries
....
return retv;
}
private:
T heaptop()
{
// code to return the topmost element of the heap
...
}
private:
int maxsize;
int cursize;
}
Javascript solution
//Prepare an array
var min = 0,
max = 1000,
i,
arr = [];
for (i = min; i < max; i++)
{
arr.push(i);
}
arr.sort(function(a, b) {
return Math.random() > 0.5;
});
//Solution itself
var currentMin = Number.MAX_VALUE,
arrayOfMinIndexs = [];
arr.forEach(function(item, index){
if (item < currentMin) {
currentMin = item;
arrayOfMinIndexs = [index];
} else if(item === currentMin) {
arrayOfMinIndexs.push(index);
}
});
console.log('Min value: ' + currentMin);
console.log(arrayOfMinIndexs);
This is for how many min values?
- aks June 29, 2013