6 ms·
Want a job working on mongoDB? Your first online interview is in this post
- zxcvb 15y agoThis site is flagged as "Sites likely to contain little of no useful content" by my Universities web filtering software.
- flogic 15y agoI see your University is on a race to the bottom. The lack of academic integrity implied buy filtering for "useful content" is astounding.
- mschireson 15y agocurious what algorithm you use to determine that. i personally think my blog has useful content. maybe because i talked about a job it looks like just a job board? -- Max
- flogic 15y agoHeaven forbid college students get jobs.
- zxcvb 15y agoI'm not really sure to be honest. Job boards and such things are not blocked. I've never this category before. It's not blocked; it's just flagged. edit: just noticed it has a secondary category as: "potentially damaging content"
- mschireson 15y agoIs it hacker news that's potentially damaging or my blog? If its my blog I'm kinda flattered :) (Would rather be "potentially damaging" than useless) -- Max
- zxcvb 15y agoAlso, they use websense which holds a master list of categorised sites so it is very very likely that a lot of other people from other companies and universities also see your site as flagged. You should email websense and ask to get your URl removed.
- dotBen 15y agoWow, I never knew web filtering software had moved beyond the obvious (pornographic, malware, etc) to "no useful content". That be considered true for most of the Internet, and yet there's nothing wrong with that. The internet isn't just for work!
- mikepurvis 15y agoNot sure if this is what's being discussed in the comments already, but it seems like you should be able to XOR all the numbers in the array, and then compare that to the XOR of all the consecutive numbers (which will xor to 0 if n mod 4 == 3).
- esrauch 15y agoThis only works if you are simply missing one value, in this case the problem is presented that one number is missing and one is duplicated. (xor-all data) xor (xor-all Range-1-N) = missing# xor duplicate# Simply knowing that last xor won't let you determine the actual values of missing# and duplicate# (just as the same thing with sum will end up giving you the difference between them and not their actual values).
- mikepurvis 15y agoInteresting you should say that. What about having both the sum and the xor? Then it's two equations, two unknowns. That should be enough to solve for it...
- esrauch 15y agoI actually posted a reply to this above, knowing both the sum and the xor is not sufficient to determine the two variables. Consider a situation where you know that (a xor b) = 1 and (a - b) = 1. Both a missing 2/extra 3 and missing 4/extra5 and any 2^N/2^N+1 are solutions to that equation. Just because you have two equations and two unknowns doesn't necessarily mean you end up with a single value for each except in certain circumstances (eg they are linear equations of full rank).
- yuvadam 15y agoHere's a sketchy description for a possible solution. The easy part is that we know that if x and y are the missing and duplicate indices form vector V then we have: |x-y| = |sum(V) - (N*(N-1))/2| So far - constant space and linear time. From here it's either cleverly (linearly!) scanning the vector or similarly concluding something else about the vector and crossing that info with what we have ;)
- slay2k 15y agoDid you mean (N*(N+1))/2 ?
- yuvadam 15y agoNope :)
- makmanalp 15y agoThis is close to the solution I had in mind, however summing lots of 64 bit integers probably yields a huge number that overflows, so some Bigints (which are comparatively slow) or clever hackery might be required to mitigate that.
- deleted 15y ago[deleted]
- BarkMore 15y agoThis was a common Microsoft interview question in the 1990s. The answer is probably easy to find on the inter-tubes.
- carbocation 15y agoI wonder if a Bloom filter would allow you to (probably) identify the missing value and the duplicated value. Create a Bloom filter on your array, one element at a time. For each element, test whether it is present in the set, and then add it to the set. By testing whether the element is already in the set, you identify the duplicated value. After creating your complete Bloom filter, then test integers 1 to N to see which is not in the set; this is your missing value. I believe this should be constant space and linear time. Above I said "probably" because there are false positives (though not false negatives).
- warrenwilkinson 15y agoPretty easy. Compare the sum with the expected sum. Compare the sum of squares with the expected sum of squares. Two equations, just solve them. I wrote the final equations in the blog comments.
- tel 15y agoExcept that the sum and sum of squares could both be too large for machine precision. I'd suggest: Scan over the array accumulating two quantities. P <- P*arr[i]/i; % prod(arr)/N! Q <- Q + i - arr[i]; % (N/2)(N+1) - sum(arr); If A is the missing value and B is the extra value, after doing the whole array P = B/A and Q = A-B. Therefore, A = Q/(1-P) and B = AP. You could conceivably compute P in log terms as well to make it a bit more stable if needed.
- amock 15y agoIt seems like you'd be IO bound when scanning the array so using larger than machine precision integers shouldn't slow things down. Particularly since you know the number of bits you'll need beforehand.
- rglullis 15y agoSince you didn't put SPOILER ALERT, I guess it's okay to say that I was going for a similar approach, except that I was going to use sum of elements and the XOR of all elements. I guess the only advantage is that computing the XOR should be faster/smaller space than summing squares.
- esrauch 15y agoYour solution won't work because you can't solve for a and b if you are given (a xor b) and (a - b), consider an extra 3 and missing 2 will give 1 for both values, as will extra 5 and missing 4.
- rglullis 15y agoShit, you are right. I was trying to avoid being a victim of nerd sniping on this one, failed at that.
- zwischenzug 15y agobitmap, one extra int and some bitfucking at the end to get the zero bit.
- zwischenzug 15y agoHm, 2^64 bits is rather more space than I thought...
- deleted 15y ago[deleted]
- bermanoid 15y ago(EDIT: this doesn't work, as lisper pointed out below) I haven't worked out the details or explicitly proven that this will work, but I think the following algorithm should do it: 1) Count up the number of even numbers in the list and compare it to the number we'd expect if the list was "right". This will either be correct (in which case both missing and dupe are even, or both are odd), high (the missing one was odd and the duped one was even), or low (the missing one was even and the duped one was odd). If high or low, we've just pinned down the last binary digit of each of the numbers. If even, the digit remains in an unknown state. 2) Slice off the last digit. 3) Repeat 1) and 2) for all 64 bits. 4) Now we have our missing number in the form 001001x1...xx01x (64 bits worth), where the x's represent digits where the missing number's digit matches the duped one. 5) We know the difference between the missing and duped numbers because of the triangular sum formula N(N+1)/2. Use that to solve for the xs in the missing number. That equation will not be possible to solve in general, but the statement of the problem here assures us that it will have a solution; further, I'm pretty sure that as long as the duped and missing numbers are not equal, that solution will be unique (EDIT: it's not, and this method doesn't work at all :P ). Maybe I'm missing something, though? Haven't thought this through too deeply...
- deleted 15y ago[deleted]
- biobot 15y agoThis is the solution I posted there: Called the missing number m, duplicate d. The main idea is to find m+d and m-d. Then it’s trivial to find m and d. 1) Find n XOR d: X_array = 1; I_array = 1; for (i=2..N) X_array = X_array XOR A[i]; I_array = I_array XOR i; endfor Then m XOR d = I_array XOR X_array 2) Find m – d It will be a little bit more complicated. The idea is to get the sum of (1..N) subtract the sum of our array. But we have to be careful not to over or underflow the result. Diff = 0; i = j = 0; // i index I, j index A while (i < N) && (j < N) if (Diff + i < N-1) Diff = Diff + i; i++; //consume one in I else Diff = Diff – A[j]; j++; // consume one in J endif end // Need some corner case check here to but I will omit 3) So we have (m XOR d) and m – d. Also, note that m XOR d is basically m + d without the carry bit so it will be trivial to get m and d. running time : 3 N <- can be squeeze to 2N if merge the two logic space : O(1)
- pedrocr 15y ago>note that m XOR d is basically m + d without the carry bit This isn't true. XOR is addition without any carry bits so there are several solutions that have the same XOR and difference
- biobot 15y agoThere are at most 2 solutions: if m XOR d = a then either m+d = a or m+d = a+N. With the combination of m-d = b, you will find m and d. If both of them satisfied ( remember m and d are bounded by 1 and N) then we actually have two solutions.
- deleted 15y ago[deleted]
- pedrocr 15y agoHere's a counterexample. Sequence is [1, 2, 3, 4, 6, 6, 7, 8, 9, 10] so m = 5 and d = 6 diff = 5-6 = -1 xor = 5^6 = 3 1-2 = -1 1^2 = 3 5-6 = -1 5^6 = 3 9-10 = -1 9^10 = 3 So three different combinations, within N, that obey the two constraints
- pedrocr 15y agoThis seems to work (in Ruby): def find_missing_duplicate(seq) sum = seq.reduce(0, :+) corrsum = (seq.size*(seq.size+1))/2 sumpow = seq.map{|i| i*i}.reduce(0, :+) corrsumpow = (1..seq.size).map{|i| i*i}.reduce(0, :+) diff = sum - corrsum diffpow = sumpow - corrsumpow seq.each do |i| miss = i-diff if (i*i - miss*miss == diffpow) return miss, i end end end And here's some code to test it: MIN_N = 2 MAX_N = 1000 (MIN_N..MAX_N).each do |n| duplicate = missing = rand(n)+1 duplicate = rand(n)+1 while duplicate == missing seq = (1..n).map{|i| i} seq[missing-1]=duplicate miss, dup = find_missing_duplicate(seq) if !(miss == missing and dup == duplicate) $stderr.puts "ERROR: expecting #{missing}:#{duplicate} got #{miss}:#{dup}" end end
- bumbledraven 15y agoSince the list consists entirely of 64-bit integers, there's a trivial linear-time solution: for x in [0..2^64) count = 0 for i in [0..N) count += (array[i] == x) } number[count] = x // 0 <= count <= 2 } print "missing: ", number[0]," duplicate: ", number[2]
- laxk 15y agoPython solution. http://pastebin.com/KyFTXpEr http://pastebin.com/KyFTXpEr O(N) / No additional arrays
- biobot 15y agoOne of my friend came up with this solution: m is missing,d is duplicate. I is 1..N, A is input. Step 1: Compute m XOR d by XOR all values of A and I together. let say x = m XOR d. Then x must has at least one 1 bit (or else m == d). Call the bit p. So now we can separate A into two list A0 are those with bit p == 0 and A1 are those with bit p == 1. So we have separated m and d into two different list. Step 2: Iterate through I, maintain two number x0 and x1 as the results of XOR operations of those elements with p bit == 0 and == 1 respectively. Do the same for A to get a0 and a1. Then we know that m is either a0 XOR x0 or a1 XOR x1. One more linear test in A to confirm the missing element m. In the end, the running time can be squeezed into 2 N. space = O(1).
- BarkMore 15y agoHere's a solution in Go. package main import ( "fmt" ) func main() { // a is the sample array a := []int{0,2, 3, 3} // Reorder values such that a[i] == i when i is not the missing value. for i := 0; i < len(a); i++ { j := a[i] k := a[j] a[j] = j a[i] = k } // Look for a[i] != i for i := 0; i < len(a); i++ { if a[i] != i { fmt.Println("missing:", i, "duplicate:", a[i]) break } } } This is a simple expression of a solution. The code can be improved.
- BarkMore 15y agoOops, the problem statement says that the array cannot be modified.