31–40 of 66 posts
Solution to problem 1: summing the numbers and then subtracting the sum from 1 + 2 + 3 + ... + n gives the deleted number x. Solution to problem 2: let x be the deleted number and let y be the duplicated number. Summing the numbers and subtracting the sum from 1 + 2 + 3 + ... + n gives x - y. Xor-ing the numbers and xor-ing the result with (1 xor 2 xor 3 xor ... xor n) gives x xor y. Now x xor y (expressed as a binar…
[deleted]
Solution to problem 1: summing the numbers and then subtracting the sum from 1 + 2 + 3 + ... + n gives the deleted number x. Solution to problem 2: let x be the deleted number and let y be the duplicated number. Summing the numbers and subtracting the sum from 1 + 2 + 3 + ... + n gives x - y. Xor-ing the numbers and xor-ing the result with (1 xor 2 xor 3 xor ... xor n) gives x xor y. Now x xor y (expressed as a binar…
2. Not constant space. Not linear time.
3. Looks correct.
Edit: For the down voter: I searched around and found a discussion of the puzzle [1]. Please go ahead and read it.
[1] http://books.google.de/books?id=415loiMd_c0C&lpg=PP1&...
People tend to hire, not so much the best people they can find, but the people who are most like themselves. And if you hire people like yourself, and your job ad says "We hire the smartest people," then you must be the smartest people! I've found it to be a huge negative signal. These sorts of interviews seem to mostly be about developers patting themselves on the back about how they stumped the applicants in interv…
Maybe if you are Google
A quick Google will find you the answer to the first question. The second just requires an additional equation, where people are suggesting powers in finite groups. This seems rather complex. Can we not reach the same constraints by only summing the even numbers, for instance?
Solution to problem 1: summing the numbers and then subtracting the sum from 1 + 2 + 3 + ... + n gives the deleted number x. Solution to problem 2: let x be the deleted number and let y be the duplicated number. Summing the numbers and subtracting the sum from 1 + 2 + 3 + ... + n gives x - y. Xor-ing the numbers and xor-ing the result with (1 xor 2 xor 3 xor ... xor n) gives x xor y. Now x xor y (expressed as a binar…
1. Not constant space. Not linear time. 2. Not constant space. Not linear time. 3. Looks correct.
If you really are hiring the smartest people, what you are paying them should leave average people with their chins on the ground(1). If this is not the case, then I wish they'd quit bragging, because the smartest people aren't working there.
(1) This and/or have about the coolest place to work on the most interesting problems in the world.
Solution to problem 1: summing the numbers and then subtracting the sum from 1 + 2 + 3 + ... + n gives the deleted number x. Solution to problem 2: let x be the deleted number and let y be the duplicated number. Summing the numbers and subtracting the sum from 1 + 2 + 3 + ... + n gives x - y. Xor-ing the numbers and xor-ing the result with (1 xor 2 xor 3 xor ... xor n) gives x xor y. Now x xor y (expressed as a binar…
Say you have N gas stations. For any n between 1 and N, say:
* f_n is the amount of fuel in the nth station, and
* d_n is the distance from the nth station to the (n+1)th.
So how do we show that we can visit all the gas stations while keeping the sum of (f_n - d_n) non-negative? Well, since we have just enough gas to get around the track, we know that the sum of (f_n - d_n) along the entire path is zero. In other words, if we write out the partial sums:
S_1 = f_1 - d_1
S_2 = f_1 - d_1 + f_2 - d_2
...
S_N = f_1 - d_1 + ... + f_N - d_N
Now look through this list and find the smallest partial sum. Call it S_m. If we change our path to visit gas station 'm' last (and start at station 'm+1'), we get these updated partial sums as we move along our new path (call them U_n):
U_1 = f_{m+1} - d_{m+1}
U_2 = f_{m+1} - d_{m+1} + f_{m+2} - d_{m+2}
...
U_{N-m} = f_{m+1} - d_{m+1} + ... + f_N - d_N
U_{N-m+1} = f_{m+1} - d_{m+1} + ... + f_N - d_N + f_1 - d_1
...
U_{N-1} = f_{m+1} - d_{m+1} + ... + f_N - d_N + f_1 - d_1 + ... + f_{m-1} - d_{m-1}
U_N = f_{m+1} - d_{m+1} + ... + f_N - d_N + f_1 - d_1 + ... + f_m - d_m
U_1 = S_{m+1} - S_m
U_2 = S_{m+2} - S_m
...
U_{N-m} = S_N - S_m
U_{N-m+1} = S_N - S_m + S_1
...
U_{N-1} = S_N - S_m + S_{m-1}
U_N = S_N - S_m + S_m
Therefore our last stop should be the gas station with the biggest fuel deficit compared to its distance from the next station (and we should begin our trip at that next station to guarantee we never run out of gas).
I very much doubt that the OP can solve either problem 1 or problem 2 with constant space. Hint: even storing an additional integer N requires \Omega(log(N)) space. Edit: For the down voter: I searched around and found a discussion of the puzzle [1]. Please go ahead and read it. [1] http://books.google.de/books?id=415loiMd_c0C&lpg=PP1&...
Maybe they meant "constant additional space". Or constant space for the data you are using in addition to the space required for the inputs.
That however tends to go against the main principles of complexity theory and O-notation. The main principle of O notation is that you mostly care on how things grow as n becomes large. Thus, constant terms should be deleted if you have a linear term. In other words, if you have something that adds constant space to linear space, you get linear space. Thus, if you already have something that requires linear space, and have to add something else to it, it is not that important (for complexity theory purposes) if the second thing is in constant space, or log space or even linear space, as long as it is smaller or equal to linear space.