StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
primarykey
Id
14621044
data
AcceptedAnswerId
0
AnswerCount
0
ClosedDate
CommentCount
8
CommunityOwnedDate
CreationDate
2013-01-31T08:03:00.877
FavoriteCount
0
LastActivityDate
2013-01-31T12:18:09.490
LastEditDate
2013-01-31T12:18:09.490
LastEditorUserId
14860
OwnerUserId
14860
ParentId
14620724
PostTypeId
2
Score
6
ViewCount
0
LastEditorDisplayName
text
Body
No, I don't believe so. You either need extra space to be able to "sort" the data in O(n) by assigning to buckets, or you need to sort in-place which will not be O(n). <hr> Of course, there are always tricks if you can make certain assumptions. For example, if <code>N < 64K</code> and your integers are 32 bits wide, you can multiplex the space required for the count array on top of the current array. In other words, use the lower 16 bits for storing the values in the array and then use the upper 16 bits for your array where you simply store the count of values matching the index. Let's use a simplified example where <code>N == 8</code>. Hence the array is 8 elements in length and the integers at each element are less than 8, though they're eight bits wide. That means (initially) the top four bits of each element are zero. <pre><code> 0 1 2 3 4 5 6 7 <- index (0)7 (0)6 (0)2 (0)5 (0)3 (0)3 (0)7 (0)7 </code></pre> The pseudo-code for an O(n) adjustment which stores the count into the upper four bits is: <pre><code>for idx = 0 to N: array[array[idx] % 16] += 16 // add 1 to top four bits </code></pre> By way of example, consider the first index which stores 7. That assignment statement will therefore add 16 to index 7, upping the count of sevens. The modulo operator is to ensure that values which have already been increased only use the lower four bits to specify the array index. So the array eventually becomes: <pre><code> 0 1 2 3 4 5 6 7 <- index (0)7 (0)6 (1)2 (2)5 (0)3 (1)3 (1)7 (3)7 </code></pre> Then you have your new array in constant space and you can just use <code>int (array[X] / 16)</code> to get the count of how many <code>X</code> values there were. But, that's pretty devious and requires certain assumptions as mentioned before. It may well be that level of deviousness the interviewer was looking for, or they may just want to see how a prospective employee handle the Kobayashi Maru of coding :-) <hr> Once you have the counts, it's a simple matter to find pairs that sum to a given <code>X</code>, still in O(N). The basic approach would be to get the cartestian product. For example, again consider that <code>N</code> is 8 and you want pairs that sum to 8. Ignore the lower half of the multiplexed array above (since you're only interested in the counts, you have: <pre><code> 0 1 2 3 4 5 6 7 <- index (0) (0) (1) (2) (0) (1) (1) (3) </code></pre> What you basically do is step through the array one by one getting the product of the counts of numbers that sum to 8. <ul> <li>For 0, you would need to add 8 (which doesn't exist).</li> <li>For 1, you need to add 7. The product of the counts is 0 x 3, so that gives nothing.</li> <li>For 2, you need to add 6. The product of the counts is 1 x 1, so that gives one occurrence of <code>(2,6)</code>.</li> <li>For 3, you need to add 5. The product of the counts is 2 x 1, so that gives two occurrences of <code>(3,5)</code>.</li> <li>For 4, it's a special case since you can't use the product. In this case it doesn't matter since there are no 4s but, if there was one, that couldn't become a pair. Where the numbers you're pairing are the same, the formula is (assuming there are <code>m</code> of them) <code>1 + 2 + 3 + ... + m-1</code>. With a bit of mathematical widardry, that turns out to be <code>m(m-1)/2</code>.</li> </ul> Beyond that, you're pairing with values to the left, which you've already done so you stop. So what you have ended up with from <pre><code>a b c d e f g h <- identifiers 7 6 2 5 3 3 7 7 </code></pre> is: <pre><code>(2,6) (3,5) (3,5) (c,b) (e,d) (f,d) <- identifiers </code></pre> No other values add up to 8. <hr> The following program illustrates this in operation: <pre><code>#include <stdio.h> int arr[] = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9, 4, 4, 4, 4}; #define SZ (sizeof(arr) / sizeof(*arr)) static void dumpArr (char *desc) { int i; printf ("%s:\n Indexes:", desc); for (i = 0; i < SZ; i++) printf (" %2d", i); printf ("\n Counts :"); for (i = 0; i < SZ; i++) printf (" %2d", arr[i] / 100); printf ("\n Values :"); for (i = 0; i < SZ; i++) printf (" %2d", arr[i] % 100); puts ("\n=====\n"); } </code></pre> That bit above is just for debugging. The actual code to do the bucket sort is below: <pre><code>int main (void) { int i, j, find, prod; dumpArr ("Initial"); // Sort array in O(1) - bucket sort. for (i = 0; i < SZ; i++) { arr[arr[i] % 100] += 100; } </code></pre> And we finish with the code to do the pairings: <pre><code> dumpArr ("After bucket sort"); // Now do pairings. find = 8; for (i = 0, j = find - i; i <= j; i++, j--) { if (i == j) { prod = (arr[i]/100) * (arr[i]/100-1) / 2; if (prod > 0) { printf ("(%d,%d) %d time(s)\n", i, j, prod); } } else { if ((j >= 0) && (j < SZ)) { prod = (arr[i]/100) * (arr[j]/100); if (prod > 0) { printf ("(%d,%d) %d time(s)\n", i, j, prod); } } } } return 0; } </code></pre> The output is: <pre><code>Initial: Indexes: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Counts : 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Values : 3 1 4 1 5 9 2 6 5 3 5 8 9 4 4 4 4 ===== After bucket sort: Indexes: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Counts : 0 2 1 2 5 3 1 0 1 2 0 0 0 0 0 0 0 Values : 3 1 4 1 5 9 2 6 5 3 5 8 9 4 4 4 4 ===== (2,6) 1 time(s) (3,5) 6 time(s) (4,4) 10 time(s) </code></pre> and, if you examine the input digits, you'll find the pairs are correct.
Tags
Title
singulars
PostAcceptedAnswerId
1. This table or related slice is empty.
PostParentId
1. POFind pairs that sum to X in an array of integers of size N having element in the range 0 to N-1
 singulars
 PostTypePostTypeId
 PTQuestion
PostTypePostTypeId
1. PTAnswer
UserLastEditorUserId
1. USpaxdiablo
UserOwnerUserId
1. USpaxdiablo
plurals
PostLinksPostIdRelatedPostId
1. This table or related slice is empty.
PostLinksRelatedPostIdPostId
1. This table or related slice is empty.
PostsAcceptedAnswerId
1. POFind pairs that sum to X in an array of integers of size N having element in the range 0 to N-1
 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
 VTUpMod
CommentsPostId

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.