StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
primarykey
Id
4024641
data
AcceptedAnswerId
0
AnswerCount
0
ClosedDate
CommentCount
1
CommunityOwnedDate
CreationDate
2010-10-26T14:21:57.703
FavoriteCount
0
LastActivityDate
2010-10-26T19:59:29.997
LastEditDate
2010-10-26T19:59:29.997
LastEditorUserId
285726
OwnerUserId
285726
ParentId
4012523
PostTypeId
2
Score
7
ViewCount
0
LastEditorDisplayName
text
Body
As other people have noted, you can use an O(n) <a href="http://en.wikipedia.org/wiki/Counting_sort" rel="noreferrer">counting sort</a>. However there are some additional problems you need to consider. We'll assume you're storing 32-bit integers, so 100GB ~ 27e9 ints. If all the integers are the same, then it will occur ~27e9 times, which is larger than a 32 bit int. Therefore your counters will have to be 64-bit integers. With 2GB of RAM, you can only store ~125e6 counters in RAM at any one time. If we can't make any assumptions about the distribution of integers, we would either have to: <ul> <li>individually increment the counters on the HD, or </li> <li>ignore all integers we encounter that are not in the counter array we currently have stored in RAM.</li> </ul> I think the latter option is better. Since we need ~4e9 64-bit counters and can only store 2GB, we would need to run through the entire array ~16 times. The first option is clearly no good if we consider encountering a sequence of integers such as 0,1<<31,0. These counters would not be stored in RAM at the same time, and thus at least 2 HD writes are required. Because of this, I think for the specific size of your problem (100GB), an <a href="http://en.wikipedia.org/wiki/External_sorting" rel="noreferrer">N-way merge</a> sort would be better, as this would only require reading the entire array log_2(100) ~ 8 times. However, if the interviewer immediately changed the question to "10TB array, still 2GB of RAM", then the counting sort would easily win.
Tags
Title
singulars
PostAcceptedAnswerId
1. This table or related slice is empty.
PostParentId
1. POSorting huge Number of Integers from hard disk
 singulars
 PostTypePostTypeId
 PTQuestion
PostTypePostTypeId
1. PTAnswer
UserLastEditorUserId
1. USDijkstra
UserOwnerUserId
1. USDijkstra
plurals
PostLinksPostIdRelatedPostId
1. This table or related slice is empty.
PostLinksRelatedPostIdPostId
1. This table or related slice is empty.
PostsAcceptedAnswerId
1. POSorting huge Number of Integers from hard disk
 singulars
 PostTypePostTypeId
 PTQuestion
PostsParentIdCreationDate
1. This table or related slice is empty.
VotesPostIdCreationDate
1. VO
 singulars
 PostPostId
 PO
 UserUserId
 This table or related slice is empty.
 VoteTypeVoteTypeId
 VTUpMod
2. VO
 singulars
 PostPostId
 PO
 UserUserId
 This table or related slice is empty.
 VoteTypeVoteTypeId
 VTUpMod
3. VO
 singulars
 PostPostId
 PO
 UserUserId
 This table or related slice is empty.
 VoteTypeVoteTypeId
 VTAcceptedByOriginator
CommentsPostId
1. This table or related slice is empty.

Querying!

Guidance

A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.