Am gasit articolele de mai jos, destul de interesante si nu am vrut sa pierdem mesajul: chiar daca e pe undeva distorsionat, iar raspunsurile nu sunt cele mai elocvente. Se incearca raspunsul la intrebarile:
1. Esti micsorat pana ai inaltimea unei monede si aruncat intr-un blender. Masa ta e micsorata pentru ca densitatea sa fie aceeasi. Lamele incep sa se roteasca in 60 s. Ce faci?
2. Avem o problema de latenta in Africa de Sud. Diagnosticheaz-o.
3. Fa un plan de evacuare pentru San Francisco.
4. Folosind o clepsidra de 4 minute si o alta de 7 minute, masoara exact 9 minute.
5. Imagineaza-ti o tara in care toti parintii vor sa aiba baiat. Fiecare familie face copii pana cand apare un baiat. Apoi sotii se opresc. Care este proportia baietilor si fetelor in aceasta tara?
6. Foloseste un limbaj de programare ca sa descrii o gaina.
7. Care este cea mai frumoasa ecuatie pe care ai vazut-o pana acum?
8. Vrei sa te asiguri ca Bob are numarul tau de telefon. Nu poti sa-l intrebi pe el direct. In loc de asta, trebuie sa ii scrii un mesaj pe o bucata de hartie si sa i-l dai lui Eve, care va fi intermediar. Eve ii va da mesajul lui Bob, iar el ii va da o foaie de hartie lui Eve, pe care aceasta ti-o va da tie. Nu vrei ca Eve sa stie numarul tau de telefon. Ce il intrebi pe Bob?
9. Un om si-a impins masina intr-un hotel si si-a pierdut averea. Ce s-a intamplat?
10. Daca ai avea o stiva de monede care sa fie de inaltimea Empire State Building ai reusi sa le pui pe toate intr-o camera?
11. Cati bani ai cere ca sa stergi toate geamurile din Seattle?
12. De cata hartie igienica ar fi nevoie ca sa inconjuri intregul stat?
13. Cum gasesti cea mai apropiata pereche de stele de pe cer?
14. Poti inota mai repede in apa sau in sirop?
15. E dificil sa iti amintesti ceva ce ai citit, mai ales daca trec mai multi ani. Cum vezi problema asta?
16. Esti intr-o masina cu un balon de heliu legat de podea. Geamurile sunt inchise. Cand apesi acceleratia, ce se intampla cu balonul? Se misca in fata, in spate sau ramane pe loc?
17. Ai de ales intre doua variante. Prima: ti se da o minge de baschet si ai o sansa sa o scufunzi in apa [frumoasa traducere nu? dar de fapt interesează șansa de a da cos], pentru 1000 de lire sterline. Doi, trebuie sa reusesti asta de doua ori din trei incercari, tot pentru 1000 lire sterline. Ce alegi?
18. Ai n companii si vrei sa le unesti intr-o mare companie. Cate metode diferite sunt de a face asta?
19. Ai un ceas analogic cu 3 indicatoare. De cate ori pe zi cele 3 indicatoare se suprapun?
20. Lucrezi intr-o cladire de 100 etaje si primesti doua oua identice. Trebuie sa determini cel mai inalt etaj de la cafre un ou cade fara sa se sparga. Ai dreptul sa spargi ambele oua. De cate aruncari ai nevoie?
21. Adauga orice semn conventional acestei operatii artimetice pentru a avea egalitate 3 1 3 6 = 8.
sursa: yoda
Raspunsurile [asa cum le vad ei] si intrebarile originale se gasesc la:
1. You are shrunk to the height of a 2p coin and thrown into a blender. Your mass is reduced so that your density is the same as usual. The blades start moving in 60 seconds. What do you do?
Those who were paying attention in rocket-science class will recall the formula for the energy of a projectile: E = mgh. E is energy (of a bottle rocket, let's say), m is its mass, g is the acceleration of gravity, and h is the height the bottle rocket attains. The height increases in direct proportion with energy (as long as mass stays the same). Suppose you tape two bottle rockets together and light them simultaneously. Will the double rocket go any higher? No; it's got twice the fuel energy but also twice the mass to lift against gravity. That leaves the height, h, unchanged. The same principle applies to shrunken humans jumping. As long as muscle energy and mass shrink in proportion, jump height should stay the same.
"Latency problem in South Africa" is an inside joke at Google. The phrase is intentionally equivocal techspeak, like a line in science fiction. ("We're losing potency in our antimatter pods!") The candidate should be able to figure out what it might mean, though, and say something sensible. "Latency" means a delay. That could apply to almost anything, from getting a marriage licence to using public transit. It's a reasonable guess that a Google interviewer is thinking about the internet. The interviewer could mean either of the following:
• The internet is running slowly in South Africa.
• Google searches (only) are running slowly.
• Google searches (only) are running slowly.
The ping operation measures latency on the Internet. A ping is a dummy message sent from point A to point B and back. The time interval is a measure of how fast information is flowing. By pinging from many computers and stations in South Africa, you can tell whether the Internet infrastructure is slow there. If not, the problem may be with Google. Are there enough servers for the South African traffic? Try a set of search terms from many points in South Africa, to see whether all are slow or just some. This would allow you to map the (imaginary) problem, and that generally satisfies the interviewer.
The 2006 Emergency Evacuation Report Card of the American Highway Users Alliance gave Kansas City an A grade. New Orleans, reeling from Katrina, got a D. San Francisco's grade? F. New York, Chicago, and Los Angeles failed, too. The failing grades are due to these cities' size, hemmed-in geography, and dependence on public transportation. At such an environmentally conscious place as Google, some interviewees instinctively talk up San Francisco's public transit network. But most public transit runs within the urban area. (BART, the San Francisco underground, can get people to Oakland. Is that good enough? Or are we evacuating Oakland, too?) Amtrak doesn't even stop in San Francisco proper. For the foreseeable future, there's no such thing as a green evacuation. Emptying a city on short notice means internal combustion engines on public roads. Here are some bullet points to incorporate into your plan:
• Make use of the fact that everyone wants to get out of the city as fast as possible. Allow a marketplace of transportation options. The biggest hitch in the Katrina evacuation was that New Orleans authorities couldn't issue timely traffic advisories: they simply didn't know which roads were jammed. Katrina hit the year before Twitter and a couple of years before ubiquitous smart-phones. Your plan should encourage people to tweet or text about traffic conditions (but not while driving!) and should devise a way to swiftly incorporate this information into social networks, mapping applications, broadcast media, and so forth.
• Use school buses. The US's school buses have greater capacity than all the modes of adult "mass transit" combined. Organise free school bus shuttle service for those who don't have cars.
• Divert petrol to the region's petrol stations. There were fuel shortages in the Katrina evacuation.
• In an authentic emergency, most people can't leave fast enough, but you have to worry about three classes of stragglers: those who refuse to go; those who can't evacuate without help (they're disabled or in hospitals); and those so off the grid that they won't hear about the evacuation (probably, many of them homeless or elderly). As a legal and practical matter, there's not much that can be done when a resident chooses to stay behind. Efforts are better spent canvassing neighborhoods for people who want to evacuate but need help. Put into service all the existing dial-a-ride vans and ambulances, as they have special facilities for the frail and disabled.
• Make sure some of the buses and trains allow pets and suitcases. One reason people insist on staying behind is concern for their pets and valuables.
• Designate all lanes of traffic arteries outbound. This allows twice as much traffic and prevents the clueless from enter-ing the city. Known as contraflow, this idea will be familiar to Bay Area commuters. Since 1963, the Golden Gate Bridge has had reversible lanes. In the mornings, four of the six lanes are inbound to San Francisco. The rest of the time, there are three lanes each way, to the city and the Marin County suburbs.
With a four-minute hourglass, it's a cinch to measure four minutes, eight minutes, 12 minutes, and so forth. The seven-minute hourglass readily gives multiples of seven. You can measure still other times by "adding" the two hourglasses -- starting one the instant the other finishes. Let the four-minute glass run out, then start the seven-minute glass. This gives 11 minutes total. Similar strategies measure 15 minutes (4 + 4 + 7), 18 minutes (4 + 7 + 7), and so on.
This method won't measure 9 minutes. But there's another trick, "subtraction." Start both hourglasses simultaneously. The instant the four-minute glass runs out, turn the seven-minute glass on its side to stop the sand. There is then three minutes' worth of sand in one bulb. That sounds promising. Nine is 3 X 3. But notice that once you "use" the three minutes of sand, it's gone. You end up with all seven minutes of sand back in one bulb. You could repeat the whole process twice, but that doesn't permit measuring a continuous nine minutes.
The way to remedy this is a third trick that might be called "cloning." Start both glasses at zero minutes. When the nine-minute glass runs out, flip it over. When the seven-minute glass runs out, flip both glasses over. The four-minute glass, which had one minute left to run, now has three minutes after the flip. When those three minutes run out, flip over the seven-minute glass again. It will then have three minutes of sand. (You've "cloned" the three minutes that were in the small glass.) This gives a continuous nine minutes.
The above is a good answer, just not the best one. Its defect is that it requires 4 minutes of preparation time (to get 3 minutes of sand in one bulb of the 7-minute glass). The scheme therefore takes 13 minutes total, in order to measure 9 minutes. Would you buy an egg-timer that tool 4 minutes to warm up?
There is a solution that allows the timing to begin immediately. Begin with the safe assumption that we're going to start both hourglasses at 0 minutes. Then fast-forward to 7 minutes later. The 7-minute hourglass has just run out. The 4-minute glass has already run out once and (presumably) has been flipped over. It should have just 1 minute of sand remaining in its upper bulb.
All that's needed is to clone that 1 minute. At 7 minutes, flip over the 7-minute glass. Let it run 1 minute, as measured by the remaining sand in the 4-minute glass. That brings us up to the time 8 minutes. The 7-minute glass will have 1 minute of sand in its lower bulb. Flip the 7-minute glass over again and let the minute of sand run back. When the last grain falls, that will be 9 minutes.
5. Imagine a country where all the parents want to have a boy. Every family keeps having children until they have a boy; then they stop. What is the proportion of boys to girls in this country?
Ignore multiple births, infertile couples, and couples who die before having a boy. The first thing to realize is that every family in the country has, or will have, exactly one boy when they're done procreating. Why? Because every couple has children until they have a boy, and then they stop. Barring multiple births, "a boy" means one boy exactly. There are as many boys as completed families.
A family can have any number of girls, though. A good way to proceed is to take an imaginary census of girl children. Invite every mother in the country to one big room and ask on the public-address system: "Will everyone whose first child was a girl please raise her hand?"
Naturally, one-half of the women will raise a hand. With N mothers, N/2 would raise their hands, representing that many firstborn girls. Mark that on the imaginary tote board: N/2.
Then ask: "Will everyone whose second child was a girl please raise -- or keep raised -- her hand?"
Half the hands will go down, and no new hands will go up. (The mothers whose hands were down for the first question, because their first child was a boy, would not have had a second child.) This leaves N/4 hands in the air, meaning there are N/4 second-born girls. Put that on the tote board.
Half the hands will go down, and no new hands will go up. (The mothers whose hands were down for the first question, because their first child was a boy, would not have had a second child.) This leaves N/4 hands in the air, meaning there are N/4 second-born girls. Put that on the tote board.
"Will everyone whose third child was a girl raise or keep raised her hand?" You get the idea. Keep this up until finally there are no hands still up. The number of hands will halve with each question. This produces the familiar series
(1/2 + 1/4 + 1/8 + 1/16 + 1/32 + . . .) xN
The infinite series sums to 1 (x N). The number of girls equals the number of families (N) equals the number of boys (or very close to it). The requested proportion of boys to girls is therefore 1 to 1. It's an even split after all.
In 1968, the French writer and prankster Noël Arnaud published a slim volume of poems in the computer language ALGOL (now obsolete, it was a precursor of C). Arnaud restricted himself to ALGOL's short dictionary of twenty-four predefined words. The poems were not valid code. Describing a chicken in ALGOL, or C++, could be an exercise in the same quixotic spirit.
Interviewers usually intend for you to describe an individual chicken so that it might be distinguished from other members of its species. Pretend you're starting a social network site for poultry. "The chicken named Blinky is female, friendly, and dead."
They want something like that, in legal code or pseudocode.
One example that would satisfy most interviewers:
class Chicken
{
public:
bool isfemale, isfriendly, isfryer, isconceptualart, isdead;
};
int main()
{
Chicken Blinky;
Blinky.isfemale = true;
Blinky.isfriendly = true;
Blinky.isfryer = true;
Blinky.isconceptualart = true;
Blinky.isdead = true;
{
public:
bool isfemale, isfriendly, isfryer, isconceptualart, isdead;
};
int main()
{
Chicken Blinky;
Blinky.isfemale = true;
Blinky.isfriendly = true;
Blinky.isfryer = true;
Blinky.isconceptualart = true;
Blinky.isdead = true;
}
Asked of Google engineers, this question prompts you to analyse how an equation can be "beautiful" and then to give a suitable example. The one certain thing about beauty is that it's subjective. Even so, most conclude that a beautiful equation is concise and of universal significance. Note, however, that you're not just trying to think of a beautiful equation; you're trying to impress the interviewer with your originality. It helps to give an equation that the interviewer doesn't hear every day.
Most would agree this is a lame answer:
E = MC2
It's like a politician saying his favorite movie is Titanic.
You want Einstein? A better reply is:
G = 8πT
This packs the general theory of relativity into five characters. G is the Einstein tensor, representing the curvature of space-time. T is the stress-energy tensor, measuring the density of mass and energy. The equation says that mass-energy curves space and time (which curvature we experience as gravity).
Another five characters express much of quantum physics.
HΨ = EΨ
This is Schrödinger's equation, read as "the Hamiltonian of the wave function equals its energy." The canonical Google answer is Euler's equation. It connects five numbers central to mathematics: e, pi, the imaginary number i -- and of course 1 and 0, which are pretty important in the information business.
Eπi + 1 = 0
Euler's equation is regularly voted the "most beautiful equation" or something of the kind. It was tied for first (with all four Maxwell's equations!) in a 2004 Physics World poll for the "greatest equations ever." As one reader put it, "What could be more mystical than an imaginary number interacting with real numbers to produce nothing?"
"Like a Shakespearean sonnet that captures the very essence of love, or a painting that brings out the beauty of the human form that is far more than just skin deep, Euler's equation reaches down into the very depths of existence," the Stanford mathematician Keith Devlin wrote. The best-known commentary of all is probably that of Carl Friedrich Gauss, who said that unless this formula was immediately obvious to a student, that student would never be a first-rate mathematician.
You won't gain any points for originality by answering with Euler's equation, though. It's like saying your favorite film is Citizen Kane. The Gaussian integral has some of the same mystic appeal, connecting e, pi, and infinity. One point in its favor: Gauss didn't find it completely obvious.
The Gaussian integral also has something that Euler's equation lacks -- relevance to life as we live it. The e-x2 is the Gaussian function. A chart of it is the familiar bell-shaped curve of a normal probability distribution. This is the "curve" that teachers grade on -- the one that supposedly governs heights, IQ scores, and the random walk of stock prices (but doesn't quite). The Gaussian blur filter in Photoshop uses the same function to blur your ex out of the picture.
In the equation, the integral computes the area under the bell-shaped curve and finds it equal to the square root of pi, or about 1.77. The equation can be viewed as a symbol of the role of chance in the world. Many of the things we value most -- beauty, talent, money -- are the result of scores of random factors, ranging from genes to simple luck. When the factors determining a quantity are truly random and additive, the quantity will follow a normal distribution. Most people will be in the middle of the curve. A few outliers will have a lot more or a lot less than the mean. In 1886, Francis Galton said of this distribution:
"I know of scarcely anything so apt to impress the imagination as the wonderful form of cosmic order expressed by the "law of error." A savage, if he could understand it, would worship it as a god. . . . Let a large sample of chaotic elements be taken and marshalled in order of their magnitudes, and then, however wildly irregular they appeared, an unexpected and most beautiful form of regularity proves to have been present all along."
For the cult of the beautiful equation in all its delirious glory, look no further than the British physicist Paul A. M. Dirac. "It is more important to have beauty in one's equations than to have them fit experiment," he once wrote. Dirac was notoriously eccentric and socially awkward, partly the result of autism. As a theoretical physicist, he saw the world as a puzzle to which beautiful equations were the key. To a remarkable degree, contemporary science (and many job interviewers) accept Dirac's view of the world.
For an amusing rebuttal, see Richard Feynman in the second volume of The Feynman Lectures on Physics, in which he makes the amazing claim that all of physics can be reduced to a single equation. The equation is:
U = 0
That's it! That's everything about the universe! Feynman was half-serious. Take an equation like E = MC2. It is said to be deep. Its so-called beauty rests with the fact that it explains so much with just a few marks on paper, a few black pixels on white. This perception of simplicity rests on hard-won and messy concepts, Feynman argued. What is energy? What is mass? What is the speed of light? None of these concepts existed for al-Khwarizmi or Leonardo da Vinci. Energy and mass had only started to gel by Newton's time. "The speed of light" was hardly a scientific matter until the nineteenth century. Feynman's point is that E = MC2 is an abbreviation. Admire it, just don't get wrapped up in how "simple" it is. It's not all that simple.
Notice that you can transform Einstein's equation into:
Notice that you can transform Einstein's equation into:
E - MC2 = 0
All I've done is to subtract MC2 from both sides. They were equal before, and they must be equal now. Now square both sides of the equation. This gives:
(E - MC2) 2 = 0
The point of this will become clear in a moment. It's part of Feynman's recipe for the ultimate beautiful equation. Blend in a few more equations. For the heck of it, we'll use Schrödinger's equation and Euler's equation. Leave Euler's as is and tweak Schrödinger's:
eπi + 1 = 0
HΨ - EΨ = 0
Then square both sides of each and add to Einstein's rejiggered equation
(E - MC2)2 + (HΨ - EΨ)2 + (eπi + 1)2 = 0
All three terms on the left have to be 0 (say Einstein, Schrödinger, and Euler). The equation must be correct, assuming its three components are. Furthermore, the only way the equation can be correct is if all the terms are 0. (That's the point of the squaring. It guarantees that no term could be negative. The only way for three nonnegative terms to add up to 0 is for all to be 0.)
Don't stop there. Throw in the kitchen sink, said Feynman. All equations, great and trivial, can be put in this form and appended to the left side of this master equation. Feynman called the quantities on the left UN, where N ranges from 1 to as far as you care to go. Sum them up and you have simply U, standing for unworldliness. It is a measure of anything and everything that doesn't fit into the scheme of physics. The master equation says the unworldliness is 0. You can unpack all of physics from this.
U = 0 is simpler (more "beautiful") than any other equation. It says everything the other equations do, and it's as simple as an equation can possibly get. An equation means you've got an equals sign, with one thing on the left of it, and one thing on the right. Three characters is the bare minimum, and U E 0 delivers that beautiful (anorexic?) limit.
Feynman's real point was that "U = 0" is a silly kludge serving no purpose except to say everything about the universe as concisely as possible! Feynman was asking, are you sure that's what you mean by beautiful? It's worth thinking about. A good answer to this interview question might start with Feynman's U = 0. Then, if you think you've got a better notion of what "beauty" is, describe it and tell what equation best fits it.
8. You want to make sure that Bob has your phone number. You can't ask him directly. Instead you have to write a message to him on a card and hand it to Eve, who will act as a go-between. Eve will give the card to Bob and he will hand his message to Eve, who will hand it to you. You don't want Eve to learn your phone number. What do you ask Bob?
Even if you give the short, simple answer you may be asked to supply the RSA answer, too. It's not that complicated as long as Bob has a computer and can follow directions. You might ask the interviewer about Bob's maths and computer skills.
With RSA, each person generates two keys, a public one and a private one. A public key is like an e-mail address. It allows anyone to send you a message. A private key is like your e-mail password. You need it to get your e-mail messages, and you must keep it secret -- otherwise, anyone could read your mail. You won't be able to send Bob a secret message because he hasn't set up his keys. He may not know what RSA is until you tell him! But you don't need to send Bob a secret message. You want Bob to send you a secret message, namely your phone number. This means that you need keys for yourself, not for Bob. The outline of the solution is this:
With RSA, each person generates two keys, a public one and a private one. A public key is like an e-mail address. It allows anyone to send you a message. A private key is like your e-mail password. You need it to get your e-mail messages, and you must keep it secret -- otherwise, anyone could read your mail. You won't be able to send Bob a secret message because he hasn't set up his keys. He may not know what RSA is until you tell him! But you don't need to send Bob a secret message. You want Bob to send you a secret message, namely your phone number. This means that you need keys for yourself, not for Bob. The outline of the solution is this:
Hey, Bob! We're going to use RSA cryptography. You may not know what that is, but I'll explain exactly what you have to do. Here is my public key. . . . Take this and my phone number and produce an encrypted number by following these directions. . . Send that encrypted number back to me, via Eve.
The trick is to word the instructions so that almost anyone can do it. You also have to be concise. RSA cryptography was first described, it now appears, in 1973. Its original inventor was the British mathematician Clifford Cocks, who worked for Her Majesty's secret service. His scheme was considered impractical: it required a computer, of all things. That was not easy to come by when spies generally had to make do with cameras hidden in cuff links. Cocks's idea was classified until 1997. Meanwhile, in 1978 three MIT computer scientists independently came up with the same idea. The last initials of the MIT group -- Ronald Rivest, Adi Shamir, and Leonard Adelman -- supplied the acronym.
In the RSA system, a person who wants to receive messages must pick two random prime numbers, p and q. The numbers must be large and at least as big (in digits) as the numbers or messages being transmitted. For a phone number of ten decimal digits, p and q each should be at least ten digits.
One way to choose p and q is to Google a website that lists large prime numbers. The Primes Pages, run by Chris Caldwell of the University of Tennessee at Martin, works well. Pick two ten-digit primes at random. Here are two:
1,500,450,271 and 3,367,900,313
Call these p and q. You have to multiply them and get the exact answer. This is a little tricky. You can't use Excel or Google calculator or most other consumer software because they show a limited number of significant figures. One option is to multiply by hand. An easier one is to use Wolfram Alpha (www.wolframalpha.com):
Just type in:
1500450271 * 3367900313
and it will give the exact answer:
5053366937341834823
Call this product N. It's one component of your public key. The other component is a number called e, an arbitrarily chosen number, ideally of length equal to N, that does not divide evenly by (p - 1)(q - 1). I may have lost you with that last part, but don't worry. In many applications, coders simply pick 3 for e. This is good enough for most purposes, and it permits fast enciphering.
Having chosen N and e, you're good to go. You just need to send those two numbers to Bob, along with the Complete Idiot's Guide to RSA Cryptography. Bob has to compute:
xe mod N
Where x is the phone number. Since we've chosen 3 for e, the part on the left is x cubed. It will be a thirty-digit number. The "mod" indicates modulo division, meaning that you divide x3 by N and take only the remainder. This remainder must be in the range of 0 to N 1. Thus it's probably going to be a twenty-digit number. This twenty-digit number is the encrypted message that Bob sends back to you. Bob therefore needs to be able to cube a number and do long division. The crucial part of the instructions could say
Bob, I need you to follow these instructions carefully with-out questioning them. Pretend my phone number is a regular ten-digit number. First, I need you to cube the number (multiply it by itself and then multiply the product by the original number again). The answer, which will be a thirty-digit number, has to be exact. Do it by hand if you have to, and double-check it. Then I need you to do the longest long division you've ever done. Divide the result by this number:
5,053,366,937,341,834,823. The division also has to be exact. Send me the remainder of the division only. It's important that you don't send the whole part of the quotient -- just the remainder.
Assuming Bob has Internet access (a pretty safe assumption, right?), the message could say:
Bob, go to this website: www.wolframalpha.com. You'll see a long, rectangular box outlined in orange. Type my ten-digit phone number into the box, without using dashes, dots, or parentheses -- just the ten digits. Immediately after the phone number, type this:
ˆ3 mod 5053366937341834823
Then click the little equals sign in the right of the box. The answer, probably a twenty-digit number, will appear in a box labeled "Result." Send that answer, and only that answer, to me.
Naturally, Eve reads these instructions, and she also reads Bob's reply. She can't do anything with it. She's got a twenty-digit number that she knows is the remainder when the cube of the phone number is divided by 5,053,366,937,341,834,823. Nobody has yet figured out an efficient way to recover the phone number.
How are you any better off? You are because you have the secret decoder key. This, d, is the inverse of e mod (p - 1)(q - 1). There is an efficient algorithm for calculating that -- provided, of course, that you know the two primes, p and q, that were used to generate N. (You know them because you picked them, remember?) Call Y the encoded number/message Bob sends back. His original message is:
Yd mod N
To figure this, you just type it into Wolfram Alpha (replacing Y, d, and N with the actual numbers).
Eve knows N, since it was on the card you asked her to give to Bob. She knows y, since it was Bob's reply to you. But she doesn't know d, and she has no way of learning it. Eve has algorithm trouble. It is easy to multiply two numbers -- heck, they teach that to schoolkids. It is hard to factor a large number.
He was playing Monopoly.
10. If you had a stack of pennies as tall as the Empire State Building, could you fit them all in one room?
This may sucker you into thinking that it is one of those interview questions where you're intended to estimate an absurd quantity. Hold on -- the question doesn't ask how many pennies. It asks, will the stack fit in a room? The interviewer wants a yes-or-no answer (with explanation, of course).
That should be a clue, as should the fact that the question doesn't say how big the room is. Rooms come in all sizes. Intuition might suggest that the stack wouldn't fit in a phone booth but would fit easily in the Hall of Mirrors at Versailles.
The answer is roughly this: "The Empire State Building is about a hundred stories tall [it's 102 exactly]. That's at least a hundred times taller than an ordinary room, measured from the inside. I'd have to break the skyscraper-high column of pennies into about a hundred floor-to- ceiling-high columns. The question then becomes, can I fit about a hundred floor-to-ceiling penny columns in a room? Easily! That's only a ten-by-ten array of penny columns. As long as there's space to set a hundred pennies flat on the floor, there's room. The tiniest New York apartment, an old-style phone booth, has room."
Swagger counts. The goal is not just to get the right answer but to make it look easy. Great athletes do this naturally. Lately, job seekers are expected to do the same.
Swagger counts. The goal is not just to get the right answer but to make it look easy. Great athletes do this naturally. Lately, job seekers are expected to do the same.
11. How much would you charge to wash all the windows in Seattle?
The first step here is to estimate the population of Seattle. The U.S. Census recently put it at 594,000 (city limits) or 3.26 million (metro area). In a job interview, no one would fault you for saying Seattle has about a million people.
How many windows are there per Seattle resident? In Manhattan, young people count themselves lucky to have one window. Seattle is different; apartments are larger, and more people live in houses with panoramic windows overlooking evergreen forests. Many houses and townhouses are two story. A decent guess, favoring the convenient round number, is ten residential windows per Seattleite.
There are also windows at places of work, Starbucks, department stores, airports, concert halls, and so forth. This probably doesn't add all that much to the per capita total. The average cubicle has no windows. A big-box store has little surface area (and few windows) relative to its volume. The windows in public spaces like restaurants and airports are shared among the huge mass of people using them.
Don't forget windows in cars. (You might ask the interviewer whether to count them.) A car is going to have four windows at bare minimum, often twice that. But big 4x4s are driven by big families and don't add many windows per capita.
A reasonable guess is that windows outside the home account for another ten per person. This comes to twenty windows per Seattle resident. Assuming a population of a million, there are about twenty million windows to be cleaned.
A reasonable guess is that windows outside the home account for another ten per person. This comes to twenty windows per Seattle resident. Assuming a population of a million, there are about twenty million windows to be cleaned.
How much should you charge to wash a window? With the windows in your home, it takes a few spritzes of Windex, a few paper towels, and a few seconds. Some of the windows in Seattle are huge, like those in the restaurant atop the Space Needle, and they're high up, requiring special crews, special equipment, high workers' comp rates, and considerable guts.
Someone knowing what he's doing could probably clean one side of a typical window a minute, given that most are small. That means cleaning "a window" (both sides) in two minutes. That comes to thirty windows an hour.
Someone knowing what he's doing could probably clean one side of a typical window a minute, given that most are small. That means cleaning "a window" (both sides) in two minutes. That comes to thirty windows an hour.
Say the average window washer makes $10 an hour. Throw in another $5 an hour for supplies and insurance. That's $15 for an hour's work, which cleans thirty windows. Cost per window: 50 cents. Twenty million windows times 50 cents is $10 million. This question is used at Amazon and Google. Just so you don't miss the joke, such as it is, Windows is another company's registered trademark.
A square of toilet paper is about 4 X 4 inches. Nine squares, in a 3 X 3 grid, would then make a square foot. Let's call that "about 10" squares to a square foot. A roll of toilet paper has maybe 300 squares. Then a roll is about 30 square feet.
A mile is about 5,000 feet. A square mile is therefore 5,000 X 5,000 or 25 million square feet. The number of rolls of toilet paper needed to cover a square mile would be 25 million divided by 30. For Fermi question purposes, 25 is practically the same as 30. Call it a million rolls of toilet paper to the square mile.
A mile is about 5,000 feet. A square mile is therefore 5,000 X 5,000 or 25 million square feet. The number of rolls of toilet paper needed to cover a square mile would be 25 million divided by 30. For Fermi question purposes, 25 is practically the same as 30. Call it a million rolls of toilet paper to the square mile.
Greater London is more or less the area contained by the M25 motorway, which is almost circular. It takes about two hours to go round it at 50mph. This makes its circumference 100 miles. As a circle's diameter is its circumference divided by pi (roughly 3), the M25's diameter is 100 ÷ 3, which is about 30 miles. So, its radius is 15 miles. A circle's area is given by πr2, which means the area contained is approximately 3 X 15² = 675 square miles. To cover it, you'd need 675 X 1 million rolls. That's 675 million rolls.
This is the "closest pair" problem, well known to computer scientists. The human eye can often spot the closest pair of stars (or points in a plane) at a glance, just as the eye can tell whether a face is male or female or solve a Captcha. Microprocessors can't readily do any of these things. Algorithms for solving the closest-pair problem were intensively studied in the 1970s and are now a building block of the digital world. Even your smartphone has apps that use them, for purposes ranging from mapping to games to cameras. It's part of how our clever devices are starting to "see."
This means that the interviewer is really asking a technically trained candidate, "Were you paying attention in algorithm class?" More specifically: given the co-ordinates of a large number of random points in a plane, how can a computer, with no visual cortex, tell which pair is closest by pure computation?
One inefficient approach is to compute the distance between every pair of stars. That's a lot of calculations when N is a large number. But it's not actually necessary to check the distance between every pair of stars, only those that are "reasonably close." Unfortunately, computers are stupid. They can't tell which pairs are "reasonably close" unless they do the maths.
The optimal closest-pair algorithm goes like this. Mentally split the sky in two. There's a right half and a left half, each with N/2 stars. Keep partitioning the sky into quarters, eighths, sixteenths, thirty-seconds, and so forth. The cuts are all to be made vertically (or from celestial north to south).
The optimal closest-pair algorithm goes like this. Mentally split the sky in two. There's a right half and a left half, each with N/2 stars. Keep partitioning the sky into quarters, eighths, sixteenths, thirty-seconds, and so forth. The cuts are all to be made vertically (or from celestial north to south).
A suburbanite will see maybe a thousand stars in his hazy, light-polluted sky. It therefore takes about ten halvings to end up with strips of sky so thin that they contain about two naked-eye stars each (210 is 1,024).
The diagram on page 250 gives you the basic idea. Compute the distance between each strip's star pair. That's vastly less work than computing distances between all the stars.
A complete doofus might think that you're almost done. Find the strip with the closest pair of all, and that's it! Hardly -- look at the diagram. Because the strips are so long and narrow, the closest pair within a strip may not be so close at all. The closest pair in the whole sky is likely to be two stars straddling two strips. If you look below, I've circled a straddling pair in the diagram.
It's necessary to have an algorithm for knitting together two adjacent slices. You give the algorithm the closest pair in the left slice and the closest pair in the right slice, and then it deduces the closest pair in the combined left- plus-right slice. This algorithm would then be applied, over and over, to create slices twice as wide, four times as wide, eight times, and so forth. After ten stages of knitting together, we'd be back to a "slice" consisting of the whole sky.
We'd also know the closest pair in the whole sky. The knitting-together algorithm works like this. Given two adjacent slices, inspect a zone centered on the dividing line to see whether it's got a pair closer than any in either half. If it does, then that will be the closest pair in the combined slice.
Take the closest pair wholly within the right or left slice and call the distance between its stars d. Think of d as the distance to beat. We need to search within distance d of the dividing line for possible straddling pairs.
The zone is a 2d- wide strip. This can be efficiently done. You might be thinking, "Sure, whatever." Computer scientists have a way of worrying about worst-case scenarios (which the user experiences as bugs). The stars in the zone can be readily sorted by their vertical coordinates. For each such star, it's necessary to check distances to stars within d of it, up or down. A simple diagram (facing page) proves that there can be only six stars to check at most. That's nicely manageable.
Here we want to make sure that Betelgeuse, just to the left of the dividing line, doesn't form a close line-straddling pair with a star on the right. This defines a d X 2d box to check. Since we already know that no two stars on the right are within d of each other, there can be only six stars, at the very most, that fit within the box.
If you haven't studied computer science, your head is probably spinning. For coders, this question should be easier than the brainteasers -- it simply asks them to recite what they learned at university.
There is an offbeat answer that rates mention. Astronomy buffs may correctly point out that there are two kinds of close star pairs. They are binary stars (two stars orbiting around each other, the way the earth orbits the sun) and optical doubles (unrelated stars that just happen to look close in the sky, as seen from the earth). Given the profound emptiness of space, it's all but a certainty that the closest pair of stars in the earth's sky will be a binary.
Not only that, but there are eclipsing binaries, where the orbital plane is so close to our line of sight that the two stars actually pass behind and in front of each other. The most famous example is Algol, a visible star in the constellation Perseus. Algol looks like a single star to the eye and to the most powerful telescopes. Every three days, its brightness varies. Astronomers have determined that Algol is really two stars whose orbits look like this, to scale:
When one star partly blocks the other, Algol looks dimmer, even to the unaided eye. During an eclipse, there is no distance between the two stars' disks. They actually touch and overlap in the sky. That's as close as a pair of stars can get.
How do you find the closest pair? The astronomer's answer is that eclipsing binaries are identified by their regularly varying brightness and spectroscopic signatures.
How do you find the closest pair? The astronomer's answer is that eclipsing binaries are identified by their regularly varying brightness and spectroscopic signatures.
Isaac Newton and Christiaan Huygens debated this question in the 1600s, without resolving it. Three centuries later, two University of Minnesota chemists, Brian Gettelfinger and Edward Cussler, did a syrup-versus-water experiment. Maybe it's not so surprising that it took so long. Cussler said he had to obtain twenty-two approvals, including permission to pour massive quantities of syrup down a drain. He had to say no thanks to enough free corn-syrup to fill twenty lorries because it was judged hazardous to the Minneapolis sewer system. Instead he used guar gum, an edible thickener used in ice cream, shampoo, and salad dressing. About six hundred pounds of the stuff transformed a swimming pool into something that "looked like snot."
Gettelfinger, an Olympic- hopeful swimmer, had the unique experience of diving in. As to the outcome, I will leave you in suspense for a bit longer. The findings were published in a 2004 article in the American Institute of Chemical Engineers Journal. The next year, Gettelfinger and Cussler won the 2005 Ig Nobel Prize in Chemistry. The Ig Nobels are the silly counterpart to the better-known prizes awarded in Stockholm, and they automatically get news-of- the- weird coverage. The media attention was apparently responsible for the syrup riddle's revival as a uniquely sadistic interview question.
In the great syrup swim-off, the guargum glop's viscosity was about twice that of water. Its density was virtually the same as that of plain water. That was important because, as swimmers have long known, people swim faster in denser saltwater. Like a ship, a swimmer's body rides higher in saltwater, encountering less drag. Gettelfinger and other Minnesota students did laps through both water and "syrup." They tried the standard strokes: backstroke, breaststroke, butterfly, and freestyle. In no case did the speeds vary between fluids by more than a few percentage points. There was no overall pattern favoring the glop or the water.
This meant that Newton was wrong: he thought syrup's viscosity would slow swimmers. Huygens correctly predicted there would be no difference in speed. Gettelfinger and Cussler's paper supplies the reason. Think of the way smoke rises from a cigarette. For a few inches, the smoke rises in a sleek vertical column.
Above that, it breaks up into complicated swirls and eddies. The swirls are turbulence. Turbulence is bad for jet planes, speedboats, and anything that wants to cut quickly through a fluid. Because the human body is not optimized for swimming, we create a ridiculous amount of turbulence, which we then fight in our struggle to pull ourselves through the water. The turbulence produces much more drag than the viscosity does. Relatively speaking, the viscosity hardly matters. As the turbulence is similar in water and syrup, the swimming speed is about the same, too.
The flow of water is much less turbulent for a fish, and even less so for a bacterium -- which would swim slower in syrup.
Is this a fair interview question? Cussler told me that a background in computer science "is probably of no use" in answering the syrup question. But he added, "Anyone with sophomore physics should be able to answer it." As a physics graduate, I'm willing to bet that's optimistic. At any rate, most of those confronting this question on a job interview won't know much about the physics. Good responses invoke simple, intuitive analogies to explain why the answer needs to be determined by experiment. Here are four points:
Is this a fair interview question? Cussler told me that a background in computer science "is probably of no use" in answering the syrup question. But he added, "Anyone with sophomore physics should be able to answer it." As a physics graduate, I'm willing to bet that's optimistic. At any rate, most of those confronting this question on a job interview won't know much about the physics. Good responses invoke simple, intuitive analogies to explain why the answer needs to be determined by experiment. Here are four points:
1. You can't swim in the La Brea Tar Pits. Some fluids are too thick to swim in. Ask the mastodons in the tar pits. Imagine trying to swim in liquid cement or quicksand. Clearly, swimming is slower in very thick fluids than in water. Even though there's more to push against, you swim slower, or not at all.
2. "Syrup" covers a lot of territory. The question doesn't ask about pitch or quicksand but rather "syrup." There is maple syrup, cough syrup, chocolate syrup, high-fructose corn syrup, and the kind they sip in nightclubs, with consistencies ranging from watery thin to the crud left in the bottom of an old tin of golden syrup. The question is unanswerable unless you know the exact type of syrup -- or can prove that swimming is slower in every thicker-than-water fluid.
3. Cite Darwin. Suppose there's an optimum level of viscosity in which swimming speed is at a maximum. Is there any reason to believe that H20 just happens to be at that optimum level for swimming? You might say yes, were you an insightful fish. Evolution has streamlined fish to "fit" the way water flows over their sleek bodies. Humans are not very fishlike, and the way we swim is not much like the way a fish swims. Neither people nor our immediate ancestors have spent much gene-pool quality time in the pool -- or in rivers, lakes, and oceans. Swimming is something we do, like hang gliding, but we're not built for it. A creature built for doing the Australian crawl would look very different from a human. Edward Cussler noted, "The best swimmer should have the body of a snake and the arms of a gorilla." It might not be surprising to find that people could swim faster in something with a different viscosity than water. Nor would it be surprising to find that the speed was the same over a wide range of viscosities.
4. Swimming is chaos. The dynamics of liquids and gases is a textbook example of chaos. It is so dependent on the granular details as to defy prediction. That's why aircraft designers need wind tunnels to test their designs. The unstreamlined human body, with its relatively awkward movements in water, only complicates things further. This is a question that needs to be tested with an experiment, using the exact type of "syrup" in question.
Cussler's Ig Nobel Prize acceptance speech boiled all this down to six words: "The reasons for this are complicated."
15. It is difficult to remember what you read, especially after many years. How would you address this?
In a few years, practically all reading will be on digital screens of some kind. It's possible to envision a personal reading agent keeping track of everything you've read, on any device -- from e-mails and tweets to electronic books and magazines. This agent or its data would migrate from hardware device to device and follow you throughout life.
• The agent would index all that text so that you'd be able to do a keyword search.
• The agent would let you annotate things you read anywhere (as you can with e-book readers). The simplest annotation would be a highlight, essentially meaning "I may want to remember this later!" The highlighted passages should get extra weight in searches. You should be able to search the text of annotations, too.
• This agent could become a built-in function of Google search or its future counterparts. While Google "remembers" that newspaper article you read last October, and (via Google Books) everything in many books, the profusion of hits in a given search can be overwhelming. If Google (via this agent) kept track of what you read, on any and all devices, you could filter searches by "stuff I've read."
• You can search for something you remember you've forgotten, but not for something you've completely forgotten or aren't thinking about. Maybe you read the complete short stories of Nikolay Gogol at school and loved them but hardly remember a character, plot, or phrase now. The agent might address that by periodically reminding you of highlighted passages, those you've identified as worth the attention of your future self. Perhaps the agent would have a Twitter account and tweet random snippets of material you want to remember but don't otherwise have time to go back to.
• The agent would also "remember" podcasts, movies, and TV shows -- provided transcripts or subtitles exist or could be generated.
16. You're in a car with a helium balloon tied to the floor. The windows are closed. When you step on the gas pedal, what happens to the balloon? Does it move forward, backwards, or stay put? (generic the company question, including Google)
The near-universal intuition is that the balloon leans backward as you accelerate. Well, the intuition is wrong. Your job is to deduce how the balloon does move and to explain it to the interviewer.
One good response is to draw an analogy to a spirit level. For the not so handy, a spirit level is the little gizmo carpenters use to make sure a surface is horizontal. It contains a narrow glass tube of colored liquid with a bubble in it. Whenever the spirit level rests on a perfectly horizontal surface, the bubble hovers in the middle of the tube. When the surface isn't so level, the bubble migrates to the higher end of the tube. The takeaway here is that the bubble is simply a "hole" in the liquid. When the surface isn't level, gravity pulls the liquid toward the lower end. This pushes the bubble wherever the liquid isn't -- toward the opposite end.
Untie the helium balloon and let it hit the sunroof. It becomes a spirit level. The balloon is a "bubble" of lower-density helium in higher-density air, all sealed in a container (the car). Gravity pulls the heavy air downward, forcing the light balloon against the sunroof.
When the car accelerates, the air is pushed backward, just as your body is. This sends a lighter-than-air balloon forward. When the car brakes suddenly, the air piles up in front of the windshield. This sends the balloon backward. Centrifugal force pushes the air away from the turn and sends the balloon toward the center of the turn. Of course, the same applies when the balloon is tied to something; it's just less free to move. The short answer to this question is that the balloon nods in the direction of any acceleration.
Don't believe it? Put the book down right now. Go to the supermarket, buy a helium balloon, and tie the string to the gear stick or hand brake. Drive back home (no lead-footing necessary). You'll be astonished. The balloon does exactly the opposite of what you'd expect. When you step on the accelerator, it bobs forward, like it's trying to race the car to the next light. Brake hard enough to throw the kids' toys out of the backseat, and the balloon pulls backward. In a high-speed turn, as your body leans outward, the crazy balloon veers inward. It's so freaky that there are videos of this on YouTube.
Why are our intuitions right about spirit levels and wrong about helium balloons? In a spirit level, the heavy liquid is dyed a fluorescent sports-drink hue, while the bubble is a ghostly void. We associate color with density, and transparency with nothingness. That instinct is completely wrong with balloons. Air is invisible, and we ignore it 99+ per cent of the time. The balloon, on the other hand, is dressed up in pretty colors or Mylar and screams, "Look at me!" We forget that, masswise, it's a partial vacuum within the surrounding air. A helium balloon does the opposite of what a mass does because it's a deficit of mass. The real mass -- the air -- is invisible.
Interviewers who ask this question don't expect you to know much physics. But there is an alternate response that makes use of the theory of relativity. Seriously.
It relates to Albert Einstein's famous thought experiment about the lift. Imagine you're in a lift going to your tax accountant's office, and a mischievous extraterrestrial decides it would be fun to teleport you and the lift into intergalactic space. The lift is sealed, so there's enough air inside to keep you alive long enough to amuse the alien for a few minutes. There are no windows, so you can't look out and see where you are. The alien puts the lift in a tractor beam and tows it at a constant acceleration exactly matching that of Earth's gravity. Is there anything you could do in the sealed lift to determine whether you're experiencing real Earth gravity or "fake" gravity, mimicked by acceleration?
Einstein said no. Should you take your keys out of your pocket and drop them, they would accelerate toward the lift floor exactly as they would on Earth. Let go of a helium balloon's string, and it would float upward, just as on Earth. Things would appear perfectly normal. The Einstein equivalence principle says that there is no (simple) physics experiment that can distinguish between gravity and acceleration. This assumption is the foundation of Einstein's theory of gravity, known as general relativity. Physicists have been trying to punch holes in the equivalence principle for nearly a century now. They haven't been able to. It's safe to assume that Einstein's premise is right, at least for any experiments you can do in a car with a fifty-pee balloon.
All right, here's a physics experiment. Tie the string of a plumb bob (carpenter's weight) to your right index finger. Tie a helium balloon to the same finger. Note the angle between the two strings.
In a lift, a parked car, or a cruising jetliner, the outcome will be the same. The plumb bob points straight down. The balloon points straight up. The two strings, joined at your finger, form a straight line. This is the outcome whenever you are subjected to gravity. Now picture what happens when you start driving. As you accelerate, your body sinks back in the seat. Fallible intuition may tell you that the plumb bob and the balloon will each lean backward a bit from your finger. During acceleration, there will be an angle between the two strings (if this intuition is right). This would provide a way of distinguishing between gravity and acceleration. When the car is subject to gravity alone, the two strings form a straight line. But when it's subject to centrifugal force or other forms of acceleration, the strings form an angle with your finger as the vertex. That's all you need to prove that general relativity is wrong. Forget about getting a job at Google -- this would be worthy of a Nobel Prize.
But since the equivalence principle has been rigorously tested and shown to be true, this doesn't happen, and you can use it to answer this question. Physics must be the same in an accelerating car as in a car subject to gravity alone. In both cases, the balloon, your finger, and the plumb bob form a straight line. In answer to the question, then, the helium balloon does the exact opposite of what you'd expect of an object with mass. It goes forward rather than backward… left rather than right… and, of course, up rather than down.
17. You have a choice of two wagers: One, you're given a basketball and have one chance to sink it for £1,000. Two, you have to make two out of three shots, for the same £1,000. Which do you prefer?
Call the probability of making a basket p. With the first bet, you have a p chance of winning £1,000. Otherwise, you get nothing. On the average, you can expect to win £1,000 X p.
With the second wager, you shoot three times and have to make the basket twice to be in the money. The chance of making the basket on any given attempt is still p. Your chance of missing on any attempt is 1 - p.
There are 23, or 8, scenarios for the second wager. Let's list them. A check mark means you make the shot; a blank means you miss.
The first scenario is the one where you're really off your game. You miss all three shots. The chance of that is 1 - p, multiplied by itself three times. You don't get the money.
In four of the eight scenarios, you win the money. In three of them you miss once. These scenarios have the probability of p2(1 - p). In the case where you make all three shots, the probability is p3. Add all of them up. Three times p2(1 - p) comes to 3p2 - 3p3. Add p3 to that, to get 3p2 - 2p3. The expectation is £1,00 x (3p2 - 3p3).
So which wager is best?
First wager's expectation: £1,000 × p
Second wager's expectation: £1,000x (3p2 - 2p3)
You may be a complete klutz (p is roughly 0) or an NBA baller (p approaches 1). For reference, I've done what you can't do in the interview: plugged the formulas into a worksheet and made a chart. The chart shows how expected winnings vary with p.
The straight diagonal line represents the first bet, and the more S-shaped curve is the second. The first bet is better if your chance of making the shot is less than 50 percent. Otherwise, you're better off picking the second wager.
This makes sense. A poor player cannot expect to win either wager. He must pin his hopes on a freak lucky shot, which is obviously more likely to happen once than twice ("lightning never strikes twice"). The bad player is better off with wager 1.
The very good player ought to win either wager, though there is a small chance he'll miss the money shot. Two out of three is a better gauge of his talents, and that's what he wants. It's like the legal maxim: if you're guilty, you want a jury trial (because anything can happen); if you're innocent, you want a judge.
The very good player ought to win either wager, though there is a small chance he'll miss the money shot. Two out of three is a better gauge of his talents, and that's what he wants. It's like the legal maxim: if you're guilty, you want a jury trial (because anything can happen); if you're innocent, you want a judge.
Assuming you get this far, the interviewer's follow-up question is, "What value of p makes you switch bets?" To answer that, set the probability of winning the two bets equal. This represents the skill level where it's a toss-up which you pick.
p = 3p2 - 2p3
Divide by p:
1 = 3p - 2p2
and then get
2p2 - 3p + 1 = 0
From there you can use the quadratic formula, warming the heart of your old algebra teacher. The interviewer will be looking for brio as much as book learning. You know p, a probability, has to be between 0 and 1. It's better style to experimentally try a rea-sonable value. "Okay, I need a number between 0 and 1. Let's try 0.5." Works like a charm.
18. You have N companies and want to merge them into one big company. How many different ways are there to do it?
In the proper sense of "merger," two companies surrender their identities and fuse into a brand-new entity. The pharmaceutical giants Glaxo Wellcome and SmithKline Beecham merged in 2000 to form the pharma colossus GlaxoSmithKline. (You guessed it -- both parent companies were themselves merger spawn.)
CEO egos being what they are, true mergers are fairly uncommon. Mergers require a near-exact match of bargaining power. More typically, one company's management has the stronger hand, and it's not about to let the weaker company's leaders forget it. The deal is likely to be an acquisition, in which company A gulps up company B, and B ceases to exist as a separate entity (though it often survives as a brand). An example is Google's 2006 acquisition of YouTube.
Mergers are symmetrical. There is only one way for two companies to merge as equals. Acquisitions are asymmetrical. There are two ways for two companies to acquire or be acquired -- Google buying YouTube is not the same as YouTube buying Google. Most people outside investment banking gloss over the distinction between mergers and acquisitions. Any melding of corporations is loosely called a "merger." The point is, you need to ask the interviewer what is meant by "merge." Fortunately, most of the reasoning applies whatever the interviewer's answer.
Start with acquisitions because they're more common (and a little easier to work with). You can visualize the companies as draughts, and the acquisitions as the moves in the game. Start with N pieces. A move consists of putting one piece on top of another to signify that the top piece is "acquiring" the bottom piece. After an acquisition, you manipulate the pieces involved as if they were glued together (like a "kinged" piece in the regular game).
Every move diminishes the number of pieces (or stacks) by one. Eventually, you will be placing stacks of pieces on top of other stacks to create yet- taller stacks. It will take exactly N - 1 moves to achieve the game's goal, a single tall stack consisting of all N pieces combined into one. How many different scenarios can lead to that outcome?
The simplest case involves two companies. Company A can gulp up B, or B can gulp up A. That's two possible scenarios. With three companies, you have to decide which company first acquires what other company. There are six possibilities for that first acquisition, corresponding to the six possible ordered pairs of three items (AB, AC, BA, BC, CA, and CB). After the initial acquisition, you're left with two companies. The situation is then exactly as in the paragraph above. The number of possible acquisition histories for three companies is therefore 6 x 2 = 12.
With four companies, there are twelve possibilities for the first acquisition: AB, AC, AD, BA, BC, BD, CA, CB, CD, DA, DB, and DC. That decided, you have three companies and, as we already know, twelve histories. There must be 12 x 6 x 2, or 144, acquisition histories for four companies. Let's generalize. With N companies, the number of possible initial acquisitions is
N(N - 1) This just means that any of the N companies can be the first acquirer, and any of the remaining N - 1 companies can be the first acquiree. After the first acquisition, there will remain N - 1 distinct companies, and there will be (N - 1)(N - 2) possibilities for the second acquisition. Then there will be (N - 2) companies and (N - 2)(N - 3) possible acquisitions. We're going to be multiplying the ever- decreasing numbers of possible acquisitions until we're left with 2 x 1 possibilities for the final acquisition.
It's easy to see that, using factorial notation, the product will come to N! x (N - 1)! acquisition histories. What if you want true mergers instead of acquisitions? The above analysis overcounts the possibilities by a factor of two -- for each of the N - 1 mergers. That means the number of proper merger histories is N! x (N - 1)! divided by 2N - 1.Finally, if "merger" can mean merger or acquisition, you simply add the two answers.
19. You've got an analogue watch with a second hand. How many times a day do all three of the watch's hands overlap?
This is an update to a classic Microsoft interview question that asks how many times a day a clock's hour and minute hands overlap. Because that one's become pretty well known, interviewers have started using this variant.
The Microsoft answer: First, figure when the hour and minute hands overlap. Everyone knows the minute and hour hands overlap at 12:00 midnight and at approximately 1:05, 2:10, 3:15, and so forth. There's an overlap in every hour except 11:00 to 12:00. At 11:00, the faster minute hand is at 12 and the slower hour hand is on 11. They won't meet until 12:00 noon -- ergo, there is no overlap in the 11:00 hour.
There are thus eleven overlaps in each 12-hour period. They are evenly spaced in time (since both hands travel at constant speeds). That means that the interval between overlaps of hour and minute hands is 12/11 of an hour. This comes to 1 hour, 5 minutes, and 27 3/11 seconds. The eleven alignments of minute and hour hands in each 12-hour cycle take place at:
12:00:00
1:05:27 3/11
2:10:54 6/11
3 :16:21 9/11
4:21:49 1/11
5:27:14 4/11
6:32:43 7/11
7: 38:10 10/11
8:43:38 2/11
9:49:05 5/11
10:54:32 8/11
1:05:27 3/11
2:10:54 6/11
3 :16:21 9/11
4:21:49 1/11
5:27:14 4/11
6:32:43 7/11
7: 38:10 10/11
8:43:38 2/11
9:49:05 5/11
10:54:32 8/11
How can we determine if any of these times is a three-way overlap? Though the question is about an analog clock, think of a digital clock that gives time in hours, minutes, and seconds:
12:00:00
There is an overlap between minute and second hands only when the minutes figure (00 here) equals the seconds figure (00). There is a precise three-way overlap at 12:00:00. In general, the minute- and second-hand overlap will occur at a fractional second. For example, here,
12:37:37
the second hand would be at 37 past the minute, while the minute hand would be between 37 and 38 past the hour. The instant of overlap would come a split- second later. But the hour hand wouldn't be near the others, so this isn't a three-way overlap.
None of the hour- and minute-hand overlaps in the list above passes this test except for 12:00:00. That means all three hands align just twice every day, at midnight and noon.
The Google answer: The second hand is intended for timing short intervals, not for telling time with split-second accuracy. It's normally not in sync with the other two hands. "In sync" would mean that all three hands point to 12 at the stroke of midnight and noon. Most analog watches and clocks do not let you set the second hand from the stem. (I've never seen one that does.) A workaround would be to take the battery out (or let a windup watch run down), set the minute and hour hands in sync with where the second hand stopped, and wait until it becomes the time shown to replace the battery or wind up the watch. It would take a maniacal analogue watch fetishist to do that. But unless you do this, the second hand will not show the "real" time. It will be offset from the accurate seconds by a random interval of up to 60 seconds. Given a random offset, the odds are overwhelming that the three hands would never align precisely.
20. You work in a 100-storey building and are given two identical eggs. You have to determine the highest floor from which an egg can be dropped without breaking. You are allowed to break both eggs in the process. How many drops would it take you to do it?
Lest there be any confusion, the building and eggs are strictly imaginary. This is an algorithm question. It's a test of your ability to craft a smart, practical way of doing something. That's important in engineering, in management, and in everything else. Every cook knows that a raw egg dropped from counter height onto tile is history. But if Google's 100-story building is surrounded with something softer than concrete and harder than grass, the answer is not obvious.
To answer in the spirit intended, you have to assume that it is possible that the maximum egg-safe floor could be any floor at all, from 1 to 100. In fact, you should allow for the possibility that no floor is egg-safe (seconding the wisdom of cooks). You are permitted to ignore the strong element of chance in egg defenestration (demonstrated in the 1970 experiments). Pretend that the outcome of dropping an egg from a given floor will always be the same. Either it breaks or it doesn't. The interviewer is not expecting you to name the egg-safe floor. There are no eggs and there is no 100-story building: it's all a fictional situation, okay? You are asked only to devise an efficient method for determining the floor, while explaining your thought process.
The one question you are expected to answer with an actual number is, how many drops would you need? Scoring is like golf: the fewer, the better.
Bits and Eggs Dropping an egg is a simple experiment that yields one bit of information. To get the most bang for the bit, you'd start in the middle of the building. That would be floor 50 or 51, as there's no "middle" floor in a building with an even number of floors.
Try dropping an egg from the 50th floor. Let's say it breaks. This would mean that the desired egg-safe floor must be below the 50th floor. Split the difference again by dropping the next egg from the 25th floor. Oops! It broke again. Now you're out of eggs. You can now conclude that the highest egg-safe floor is below the 25th. You don't know which floor, and that means that the method has failed. It's possible to keep reusing an egg so long as it doesn't break.
Start on the bottom floor and drop the first egg. If it survives, go to the 2nd floor and try that. Then the 3rd, the 4th, the 5th, and so on until the egg breaks. That will tell the highest floor the egg can be dropped from without breaking. You will have determined it with just one egg. Call this the "slow algorithm." It's a miser of eggs and a spendthrift of egg drops. Every single floor might have to be tested, but it gets the job done.
The challenge is to create a solution that makes good use of both eggs. Suppose that Google's optimal algorithm for the egg-drop experiment was written in a book somewhere. You don't even have to suppose -- it is written in a book, namely this one. The algorithm reads something like this:
1. Go to floor N and drop the first egg.
How do I know the algorithm begins this way? Well, I'm not going out on much of a limb. An algorithm is a list of idiotproof instructions, starting with instruction 1. It tells you to drop an egg, naturally, because that's the modus operandi here. There's nothing else to do but drop eggs. The only interesting part (floor N) is currently concealed under an algebraic veil. The real algorithm gives a specific floor, like 43, in place of the N.
Further deduction: because the experiment in instruction 1 has two outcomes, it has to have follow-up instructions for both eventualities. Call them 2a (what to do if the egg breaks) and 2b (what to do if it survives). Once you break the first egg, you will have to play it safe with the second. You can't take the risk of skipping any floor, lest you break the second egg and not be able to deduce the correct floor.
Instruction 2a of Google's algorithm has to say this, in so many words:
2a. (To be used if the egg breaks in 1.) Go down to floor 1.
Adopt the "slow algorithm" with the remaining egg. Test it from every floor, working your way up the building until the egg breaks. The maximum egg-safe floor is the one below that. For instance, imagine the first drop is from the 50th floor, and the egg breaks. You can't risk trying the second egg from floor 25 because it might break, too. Instead, you have to try floors 1, 2, 3 . . . potentially all the way up to 49. And since we started with the 50th, that could mean making fifty drops in all. It doesn't take much coder's intuition to see that a search needing fifty tests to find one thing out of a hundred is not optimal. It's lousy. It's better to count on making the first drop from a lower floor. If we start from floor 10, and the egg breaks, we might need as many as ten drops. This is the key aha! moment of the puzzle. In general, when the egg breaks on a first drop from floor N, it will take as many as N drops total to identify the right floor. This strongly suggests that the first drop should be from a floor much lower than 50. This choice has the appealing feature that we use the first egg to deduce the tens digit of the egg-safe floor, and the second egg to find the ones digit. For example, test the egg from floors 10, 20, 30, 40, and 50. Say it breaks when dropped from floor 60. This tells us the maximum egg-safe floor is 50-something. Move down to floor 51 and work upward floor-by-floor with the other egg. If the second egg breaks at floor 58, that means the egg-safe floor is 57.How efficient is this procedure? The worst-case scenario would be to try 10, 20, 30, all the way up to 100, where the egg finally breaks. Then you'd backtrack to 91 and work up. You could end up needing nineteen drops in all to determine that 99 is the correct floor. This isn't a bad approach. But it's not the best.
Crash Test Remember, the question asks, "How many drops would it take you to do it?" That's a strong hint that you're being graded on how few drops you need. (More exactly, you're to minimize the number of drops required in a worst- case scenario. Sometimes you'll get lucky and arrive at the answer in just a few drops.)
Because the first egg's role is as crash-test dummy, you want to put it in high-risk situations; that's how you learn as much as possible as quickly as possible. The second egg is a backup. Once it's the sole remaining egg, you have to play safe with it. It's the crash-test-dummy egg that's crucial to achieving a good solution. It's the egg that can eliminate many floors in a single drop. The question is, how many? A bit of mental gymnastics is required to answer that. It throws many smart people.
I'll begin with an analogy. You're a professional golfer on the eighteenth hole, vying for a big prize. To win, you've got to make the hole within three strokes. That necessity dictates which clubs you choose and whether you risk a bunker rather than playing it safe. It will require you to aim for the hole on the third stroke (rather than being satisfied with making the green). The three-stroke limit constrains your strategy throughout. Google's perfect algorithm also has a limit: a maximum number of drops needed to determine the correct floor. Call this number D. The D-drop limit constrains your strategy. For the sake of concreteness, imagine the limit is ten drops. Then you might as well drop the first egg from the 10th floor. See why? You want to choose a floor as high as possible, to rule out as many floors as possible. The 10th floor is the highest option, for this reason: should the first egg break, you could end up needing all ten permitted drops to determine the correct floor. (The above paragraph is the hardest thing to understand, I promise.)
I'll begin with an analogy. You're a professional golfer on the eighteenth hole, vying for a big prize. To win, you've got to make the hole within three strokes. That necessity dictates which clubs you choose and whether you risk a bunker rather than playing it safe. It will require you to aim for the hole on the third stroke (rather than being satisfied with making the green). The three-stroke limit constrains your strategy throughout. Google's perfect algorithm also has a limit: a maximum number of drops needed to determine the correct floor. Call this number D. The D-drop limit constrains your strategy. For the sake of concreteness, imagine the limit is ten drops. Then you might as well drop the first egg from the 10th floor. See why? You want to choose a floor as high as possible, to rule out as many floors as possible. The 10th floor is the highest option, for this reason: should the first egg break, you could end up needing all ten permitted drops to determine the correct floor. (The above paragraph is the hardest thing to understand, I promise.)
Everything else follows from this insight. After the initial drop, you've got nine drops left. Assuming the egg survives, you will again want to move up as many floors as possible for the second drop. You might think you'd move up another 10 floors. Not quite. Since you've only got nine drops left, you can move up 9 floors at most. That's because the egg could break on the second drop, forc-ing you to use a floor-by-floor search thereafter. You might have to test every floor between 10 and the one you just tried, 19, using up all your allotted drops. Had you gone up even a floor higher, you could get caught short and not be able to single out the correct floor.Or say the egg survives the first two drops. That leaves eight drops. You would go up 8 floors for the next drop.The floors you test, assuming a series of unbroken eggs, form a simple series.
10
10 + 9 =19
10 + 9 + 8 = 27
10+ 9 +8 +7 = 34
etc.
10 + 9 =19
10 + 9 + 8 = 27
10+ 9 +8 +7 = 34
etc.
Wait a minute. The highest floor you can possibly reach is 10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1. That comes to 55. This scheme would work perfectly for a 55-story building. But the question says it's a 100- story building.
That's easily fixed. Remember, I just picked 10 out of the air. Replace 10 with D, the required number of drops in the best algorithm. The highest floor an optimal method can reach is
D + (D - 1) + (D - 2) + (D - 3)+ . . . + 3 + 2 + 1
This must equal or exceed 100.
From here on it's just algebra. The sum above is D plus every whole number smaller than it. This is a triangular number. Picture a rack of billiard balls. It's 5 + 4 + 3 + 2 + 1 balls. You may recall from school that the total can be computed by multiplying 5 by 5 + 1 and dividing by 2. So you've got 5 x 6/2 = 15, and that's the number of balls in a rack.
In this case, the sum of D and every smaller whole number is equal to D times (D + 1) divided by 2. So:
In this case, the sum of D and every smaller whole number is equal to D times (D + 1) divided by 2. So:
D x (D + 1)/2 ≥ 100
Multiply both sides by 2, and you get
D2 + D ≥ 200
Focus on D2 and ignore the much smaller D. This equation says that D2 is at least as big as 200 or so. The square root of 200 is just over 14. Try that for D.
142 + 14 = 196 + 14 = 210 ≥ 200
Bingo. It fits. Just to be sure, try 13.
132 + 13 = 169 +13 =182
Nope, that's not greater than or equal to 200. Fourteen it is. You drop the first egg from floor 14, and you're guaranteed to find the answer in fourteen drops or less. The recap: First, drop the egg from floor 14. If it breaks, go down to floor 1 and work your way upward floor-by-floor. This will get the answer in no more than fourteen drops total.
Should the first drop not break the egg, go up to floor 27 (14 - 1 floors above floor 14) and try again. Should it break this time, you'll have to go down to 15 and work up. This will also yield the answer in fourteen drops total or less.
Given a string of unbroken eggs, you'd test floors 39, 50, 60, 69, 77, 84, 90, 95, 99, and then 100 (actually, were the building higher, the next floor would be 102). This means it would take twelve drops, and no broken eggs, to deduce that the egg can survive every floor of the building. Should the egg break at any point in the process, you'd be shunted into the slow algorithm and might need all fourteen permitted drops.
Starting from the left, you see 3 and 1. The first maths sign you learned was probably a plus sign. 3 = 1 gives 4. Conveniently, 4 is half of 8, the number that's the goal. Moving righr, there's a 3 and a 6. Well, 3 is half of 6. Put a division sign between them and you've got 3/6 or 1 / 2. Dividing by 1/2 is the same as multiplying by 2. This gives the answer: (3 + 1) / (3 / 6) = 8.
That wasn't so hard, was it?
Postări
