Groupon Interview Question for Software Engineer / Developers


Country: United States
Interview Type: Phone Interview




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

This is for how many min values?

- aks June 29, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

There might be duplicated min values, so not given, have to record all of them which match the requirement when traversing the array.

- orangetime23 June 30, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- ashot madatyan June 30, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Bottom up merge sorting is the best procedure to find the first K min values in an efficient manner

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

we can use k-th select approach from a median sort

- braj March 03, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Can we just do one pass scan through the array?
-maintain the min and an array of indices int[] INDS
-when a new min found, record this min and the index

at the end, we have both min and indices

- Jerry June 24, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);

- nikita.groshin July 24, 2015 | Flag Reply


Add a Comment
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.

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