CODEWITHSUNDEEP
algorithm
user1611545
user1611545

Reputation:

Sorting 1 million queries

I have 1 million queries on disk to sort, my local memory/cache can store
up to 1 thousand queries, how can I perform sort?

This is a google interview question. Can someone help me find the answer?

Upvotes: 1

Views: 528

Answers (4)

f_puras
f_puras

Reputation: 2505

I am lazy: Read all queries (1,000 each), dump them in a database, then SELECT ORDER BY anything. If it is Google asking, they'll have databases anyway...

Upvotes: 1

MSalters
MSalters

Reputation: 179907

Get more memory. A query is not that big. It's a question that tests whether you can think outside the box.

Upvotes: 1

twoflower
twoflower

Reputation: 6830

External merge sort can be employed to achieve that.

Upvotes: 1

Luchian Grigore
Luchian Grigore

Reputation: 258618

You load 1000 queries in memory and sort them using quicksort, writing them to a file. In the end you'll have 1000 such files.

You then go on to merging the files using, you guessed it, mergesort.

That's how I'd do it. By no means the most optimal solution.

Upvotes: 4

Related Questions