## Interview Question

• 1
of 1 vote

Country: United States

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

A stable version of counting sort should cater to the two different interpretations of the problem we have seen so far:

1) Sort all into one big list
2) Sort each independently.

We solve 1), but include enough information in the output to solve 2)!

Maintain an array counts of size n for the counts. Increment counts[k] when you encounter k and then generate the sorted list at the end, by walking the input again(in order we got it), so that we can tag the output number with the list it came from. This way, the numbers are sorted, but we also know which list we got them from, which can be used to solve 2).

If the sum of the lengths of the lists is L, then this algorithm is O(L+n) time and O(L+n) space.

We don't exactly need n = L.

Sample python code. count_sort takes a list of lists, and returns a sorted list of tuples (number, list_number), sorting by number. sort_all just extracts the number and creates a big list. sort_single create a list of lists, and puts in number in the appropriate list using list_number.

``````def count_sort(lsts, n):
count_list = map(lambda x: 0, xrange(0,n+1))
list_id = 0
total_num = 0
for lst in lsts:
for k in lst:
count_list[k] += 1
total_num += 1

offset = 0
for i in xrange(1, n+1):
count = count_list[i]
count_list[i] = offset
offset += count

result = [0] * total_num
num_seen = map(lambda x: 0, xrange(0,n+1))
list_num = -1
for lst in lsts:
list_num += 1
for k in lst:
result[count_list[k] + num_seen[k]] = k,list_num
num_seen[k] += 1

return result

def sort_all(lsts,n,r):
return map (lambda x: x[0], count_sort(lsts,n))

def sort_single(lsts,n,r):
results_lst = []
for j in xrange(0,r):
results_lst.append([])

for k,list_num in count_sort(lsts,n):
results_lst[list_num].append(k)
return results_lst

def main():
lsts = [[2,3],[3,2,1],[2,2,2,1,1,1]]
print "Input", lsts
print "All", sort_all([[2,3],[3,2,1],[2,2,2,1,1,1]],3, 3)
print "Single", sort_single([[2,3],[3,2,1],[2,2,2,1,1,1]],3, 3)

if __name__ == "__main__":
main()``````

Output

``````Input [[2, 3], [3, 2, 1], [2, 2, 2, 1, 1, 1]]
All [1, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3]
Single [[2, 3], [1, 2, 3], [1, 1, 1, 2, 2, 2]]``````

--------------------------------------------------------------

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

``````Like @Loler said: record the frequency of each number present in those lists in a hash table. then iterate ( in order ) over the possible keys and populate a sorted list with number whose keys are present in the hashtable. here is my implementation:

public ArrayList<Integer> sort(List<ArrayList<Integer>> list, int n)
{
if(( list == null) || ( n < 1)){
return null;
}
/* hash table to count the frequency of each number that occurs in those lists */
HashMap<Integer, Integer> table = new HashMap<Integer,Integer>();

for(ArrayList<Integer> a_list : list ){
/* for each list */
for(Integer m : a_list ){
/* count the frequency of that number and update the hash table accordingly */
if( table.containsKey(m)){

Integer val = table.remove(m);
table.put(m, val + 1);
}
else{
table.put(m, 1);
}
}
}
/* single past, populate a sorted list based on
the occurrence of each number from 1 - n */
ArrayList<Integer> sorted_list = new ArrayList<Integer>();
for( int i = 1; i <= n ; i++ ){

if(table.containsKey(i)){

int val = table.remove(i);
while ( val-- > 0 ){
}
}
}
return sorted_list;
}``````

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

@kx. You don't really need a hashtable, an array will do, but yes, something like that. +1 to you comment.

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

actually, but I think the interviewer expected to sort all the lists separately, not merging them into one sorted list

hence the answer is that add a prefix to every number for example for first list add prefix 1 to every number in first list in second list add prefix 2 to every number of that list ,finally take all these numbers and use radix sort

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

L (length of input)=n is needed because counting sort is of order of size of input.

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

@rdx: Eugene has convinced me that your interpretation is not as artificial as it seemed to me! Good solution, seems like it will work. +1 to your comment.

@Anonymous: What I meant to say was you don't really need L to be exactly n. It can be n+100, or 1000n. Counting sort requires bounded integers, why must that bound be same as the number of such integers? You can sort a million bits, for instance. We don't restrict to just two :-)

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

@Loler: regarding your comment to rdx, I actually don't think it's artificial at all to ask to sort the lists separately. That's how I interpreted the question too, and it's a little more difficult that way. The question is how you will ensure strictly O(n) complexity even when the n elements are distributed across r different lists (let's assume r <= n). A direct attempt to use counting sort directly on each list will use up O(n) time *per list*, resulting in a total complexity of O(r*n), which may not be O(n). You will need a modified and trickier form of counting sort to get the O(n + r) time bound, which can be taken to be O(n) under the r<= n assumption.

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

@Eugene: Ah! Good point. Thanks.

I will edit my answer to mention the interpretation it follows.

As to the other interpretation, I suppose rdx's solution works.

Treat each number as a 2-digit number in base n and use radix sort, one of the digits telling you which list the number belongs to, and the other the actual number. We can use a stable version of counting sort for the single digit sorting (which is what I suppose you were referring to?).

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

@eugene.yarovoi I have edited the answer to include a stable version of count sort, which does solve both interpretations. I am curious to know your solution. Care to elaborate? Thanks.

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

@Loler: I was just going to have a list of occurrence locations for each of the n slots instead of just having an occurrence count. When input list number x encounters a value y, just do arr[y].add(x). All the lists can be processed together in this way, and then the values can be restored in sorted order.

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

@eugene: Yeah, I realized that you were probably thinking of something like that, after posting this. Of course, the one I posted trades time for space (space is O(n) if all we need is a stable sort), but makes an extra pass. If we store the list instead of a count, that is O(L+n) space.

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

Please correct me if i am wrong, but I think the interviewer expected to sort all the lists separately, not merging them into one sorted list.

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

Use counting sort for each list.

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

this could take nlgn

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

but merge sort takes O(nlogn).

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

merge the r lists, takes O(n)

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

@Anonymous: The question does not say the lists are already sorted.

Even if they were sorted, I am curious: what O(n) time algo do you have which can merge r lists (where r can be as large as n itself) which does not take into account the 1 to n bounds?

Sorry, have to give this answer a -1.

@Anonymous: I wish I could give your comment a -1, but that changes the order, so I will leave it at that.

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

We know we can't merge an arbitrary array in less than O(n log n) using comparison-based techniques because it could be that r=n, in which case asking to merge is just the same as asking for a general sort.

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.

### 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.