1,911 karma · joined March 8, 2009
IIRC, the correct solution to this is in sqrt(N) time; for a 100-floor building, you drop at floors 10, 20, 30, 40, 50, 60, 70, 80, 90, and 100, in that order. In general, this is sqrt(N) floors, spaced sqrt(N) floors apart. The bulb will break at floor sqrt(N) * X [10X in this example]. Now, drop the bulb from the approximately sqrt(N) [10] floors between floor sqrt(N) * (X-1) [10 * (X-1)] and sqrt(N)* X - 1 [10 * X - 1], inclusive. When it breaks, you have the exact tolerance rounded down to the nearest floor, and you've done it with at worst 2 * sqrt(N) drops.
By the way, this is a great example of a dumb interview question; it's not particularly obvious that there is a solution in sqrt(N) worst case time, but once you're told that there is one (and, perhaps, that binary search + linear search is linear search in the worst case), it's not too difficult to get it in sqrt(N).
Also, note that average case running time analysis is meaningless if you don't have a distribution for the input; simply assuming that the tolerance is distributed uniformly at random from 1 to 100 just because you have a 100-floor building makes little sense.
I'm in Ann Arbor, where the only efficient way to get to DTW is by car, which means bribing a friend (still not free in terms of friend's time), taxi ($50), traditional airport shuttle (~$30-$40), or shorter taxi plus regularly-scheduled airport bus (~$25). All cited costs are one-way, and a one-way trip is at least half an hour.
No, he didn't. A "small botnet" or Tor is not particularly useful to force you to violate the Adsense ToS by telling your visitors to click on your ads.
https://www.blackhat.com/presentations/bh-usa-09/ORTEGA/BHUS... https://www.blackhat.com/presentations/bh-usa-09/ORTEGA/BHUS...
Please don't submit comments complaining that a submission is inappropriate for the site. If you think something is spam or offtopic, flag it by going to its page and clicking on the "flag" link. (Not all users will see this; there is a karma threshold.) If you flag something, please don't also comment that you did.