Interview Question
Country: India
1. Sorting can be done by the OS itself and the result can be stored in an Array
2. As Fernando mentioned ... a Heap could be used. But the issue is ... that for 40,000,000. The value of nlogn would be very high.
3. We could use a hashmap with 'n' buckets, each bucket with increasing order of date.
Each bucket can then have a linked list, with items in sorted order.
Complexity should be n, considering a good hashing technique.
If the metadata of the files don't fit on memory I would use using external sorting. You can split the metadata of the 40 million files on chunks that fit on memory and that you can sort. Once all the files are sorted by date you can start transferring them.
- Fernando June 13, 2017If the metadata for all the files can be fit on memory I would use a min heap to get the files in order.
The cost temporal cost for both is approaches is nlogn but the heap approach takes less overhead