Shutterfly 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 problem lends itself to a bucket sort + quicksort hybrid type solution.

Algo:
- keep 2 in memory structures.
a) int Largest[10];
b) Sort 100 nos from the file using a well known sorting algorithm (eg merge sort )
c) Select the 10 largest elements between the sorted 100 elements and Largest[10];
d) Repeat till end of file.

- sxs May 03, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

Max Heap Sort.
Maintain Heap Array of size 10 and read from file in chuncks and insert into the array.
End of reading the file you will have top ten largest numbers in the file

- Anonymous May 04, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

Why do we need a max heap. Build a min heap here of 10 number here. REad file in chunks and then replace the min element

- DashDash May 04, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

@DashDash: With min heap, root is checked whether it is smaller than number from file and if smaller, root is replaced with new number and restore the heap by percolating down.

With max heap, last child can be checked whether it is smaller than new number if so replace last child and you can do percolate up.

- Anonymous May 04, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

1) Heap sort first 1000 numbers,
2) Took max 10 elements max[10] and mix them with next 990 elements.
3)Again heapsort these 1000 numbers, take 10 max element
4) Repeat until end of file

Time complexity is O(n) = n i.e linear complexity

- pirate May 04, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

How can TC be O(n)....its actually O(n logn) as in each iteration heap sort takes O(nlogn) time complexity.

- loknathsudhakar May 08, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

To find k largest numbers we definitely don't need to sort.
The problem is cut out for Min heap.

- EK MACHCHAR May 04, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

1) Read first 10 distinct elements from file into the max array, A - constant time
2) Sort the above array - constant time
3) Maintain a hash map, m of the ints in the max array (to weed out duplicates) - constant space
4) For each incoming int,x read from file:

//A[0] is the min of maximums so far
    // you have to insert it at right position in the array if it is not a duplicate and is greater than A[0]

    if((x > A[0]) && (m.count(x) < 0)) {
     
    int i=1;
    while(x> A[i] && i<10){
      A[i-1] = A[i];
      i++;
    }
    A[i] = x;   
    }

- rcakella October 15, 2014 | 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