Want To Work At Google?

ramboando writes "In an article on the ZDNet site 'chief culture officer' and HR boss Stacy Savides Sullivan describes the kind of traits that she's looking for in potential Google employees. If you're thinking about applying, she also goes over what kind of questions one might be asked in an interview, Google's 'happiness survey' and the best perks that makes employees tick and stay with the company (Google ski-trips or paid paternity leave, anyone?). 'I think one of the hardest things to do is ensure that we are hiring people who possess the kind of traits that we're looking for in a Google-y employee. Google-y is defined as somebody who is fairly flexible, adaptable and not focusing on titles and hierarchy, and just gets stuff done. So, we put a lot of focus in our hiring processes when we are interviewing to try to determine first and foremost does the person have the skill set and experience potential to do the job from a background standpoint in addition to academics and credentials.'"

Comments

"Fit Factor"

[Architect_sasyr]

So they basically want a Google-y employee or, put another way, someone with the right fit factor. Does this mean that a highly qualified person, skilled and high standing in the community, but prefers to be quiet, in the dark and working alone won't make it?

I ask because my own company puts so much store in the "fit factor" that they end up hiring people with less skills than the other candidates.

Do I want to work at google? Well now, that's between me and HR ;)

Re:"Fit Factor"

[rsmah]

Business is a team sport. The "fit" of an individual is as important as raw skill/talent.

Cheers,
Rob

Re:"Fit Factor"

[BiggerIsBetter]

I ask because my own company puts so much store in the "fit factor" that they end up hiring people with less skills than the other candidates.

I've worked with guys who are reputed to be very very good at their specialty, but at the same time they tear apart the projects they work within. I'd much prefer to have people who are good but not great, than people who are great but don't fit. Obviously Google is looking for those rare individuals with the 3 magic qualities.... social skills, technical skills, and academic skills.

Do I want to work at google?
Given what you write about your company's hiring practices, I suspect you'll be out of luck... ;-)

Re:"Fit Factor"

[Anonymous Coward]

She also doesn't mention that to Google, hiring is mathematically equivalent to Information Retrieval, except that they only care about "precision" not "recall".

What that means to lay-people is that so long as they can maintain 10,000 applications coming through per-month, false negatives (passing on a suitable applicant) do not matter because there'll be another candidate along in a minute. False positives (hiring an unsuitable applicant) are all they need to focus on. The "fit factor" is effectively the search string of traits; however, with such a large candidate pool, they can focus their "hiring algorithm" entirely on rejecting candidates where it is even slightly difficult to ascertain whether they fit or not.

So, their advertising blitz "aren't we a great place to work for" is a part of what lets them keep their hiring process easy. If they get bad PR and applications fall, then they'll need to worry about recall as well as precision.

Re:"Fit Factor"

[Yvanhoe]

If your goth friend is skilled and manage to write complete documentations and occasionaly answer questions, he could very well make it. I doubt however that even a computer genius can do the same amount of work than a good working team of five average engineers.

Re:"Fit Factor"

[Anonymous Coward]

>they end up hiring people with less skills

That's "fewer skills". Or, you could say "they end up hiring people that are less skilled".

Re:"Fit Factor"

[Anml4ixoye]

I interviewed with them about a year and a half ago. The first interview was awesome - lasted about 3 hours on the phone, and we talked about a multi-threading race condition. The second interview was really short, and it seemed to go well. I got a call from the hiring manager that they weren't continuing on because they didn't like the way I "thought".

Oh well, we really weren't sure about moving to Mountain View anyway. But I sure wish I knew what the heck that meant.

Re:"Fit Factor"

[kingtonm]

Right, but more important?

What would you say the balance should be, 60/40, 70/30? Can you quantify it? If you can't, how do you decide?

Re:"Fit Factor"

[speculatrix]

Business is a team

remember: there's no "I" in team. but there's no "we" either!!!

Re:"Fit Factor"

[Ihlosi]

remember: there's no "I" in team. but there's no "we" either!!!

There's a "me", though.

Re:"Fit Factor"

[Anonymous Coward]

I would agree with this - having interviewed with Google myself. I only got as far as the second 'telephone screening'.

I consider myself fairly skilled, but I also know my weaknesses. I passed on a technical question in an area that I'm not strongest (without having heard the question - they wanted a response in a specific language that I wasn't strong in), and said that normally I'd ask a peer for help in that area. From what my interviewer told me, that pass was enough to weigh the scales against me.

With hindsight, I would have tried to answer the question regardless.

Given my background and experience, I was a little surprised that such a small item ended the process there - considering that THEY contacted me, and not the other way around.

The application process described above makes me feel a little better about it though - and it also makes sense.

Re:"Fit Factor"

[Rudeboy52]

Skills can be taught, the right attitude, motivation, and "fit" cannot. So yeah, companies heavily invest in employees that fit the culture and then teach them the skills they need to succeed. I worked at Rackspace Managed Hosting for a while and this is a big factor in getting hired.

Re:"Fit Factor"

[Sinister Stairs]

I got a call from the hiring manager that they weren't continuing on because they didn't like the way I "thought"...
But I sure wish I knew what the heck that meant.

Instead of wishing, you should email/call back and ask. I've been rejected for a job for similar reasons, but I emailed and asked for details why and what I could do to improve. The manager was impressed and hired me for a different but parallel position because I showed I cared, and that I could take constructive criticsm and wanted to improve myself.

If nothing else, it would give you peace of mind instead of wondering "what if" -- maybe the answer would confirm you wouldn't have wanted to work there anyways.

Re:"Fit Factor"

[bynary]

Yes. If you show up to a technical job interview with a dirty t-shirt on and are rude to the receptionist because you can't "deal with people" then you may not even get the interview after all. Except in very few circumstances (academic research comes to mind), doing your job well consists mainly of solving problems for other people. If you can't get along with those people you may very well be unable or unwilling to help them solve their problems.

Someone who can learn quickly is more desirable than someone who knows Java like the back of their hand.

What would you say the balance should be, 60/40, 70/30? Can you quantify it?

I don't believe you can quantify it. The instances in which I have seen attempts at quantifying "fit factor" (think college roommate selection, most online dating services, and etc.) fail most of the time because personalities and relationships are, for the most part, dynamic. If you were to quantify it, you would probably have to do it on an individual basis. One person's technical ability may compensate for a shortcoming in personality whereas the opposite may be true for another individual. It also varies by the type of job (i.e. short-term contract versus full-time employee).

Still, I believe that "fit factor" is more important than technical competence.

Re:"Fit Factor"

[Anonymous Coward]

remember: there's no "I" in team. but there's no "we" either!!!

There's tea though. Preferably with crumpets.

Re:"Fit Factor"

[Vexorian]

Right, but more important?

Depends on the employer I guess.

But of course, if you are extremely bad in that you will have issues everywhere, I would say the importance rate of this deal goes from 40% to 90% depending of the business.

Re:"Fit Factor"

[Forge]

It's more important.

My reasoning may be a little simplistic but it gos like this: If your skills are 50% below the standard for your job it means you will be worth 1/2 as much to the company. A problem which can be handled in different ways without a large financial impact. I.e. Smaller salary to match your skill level, which increases as you are trained and grow with practice.

If however you are a misfit you could drag down the performance of other people. The wrong kind of misfit can cause your best people to quit or just not like the job any more.

What's the wrong kind of misfit? Imagine if you will an office like Slashdot (I hear google looks like a bank by comparison). How would Malder, Hemos and Cowboy Neal cope with the kind of person who won't even answer you unless addressed by his formal title I.e. "Dr. Doe", not "John" or "Doe". Worse yet "Mrs. Row" who will start an argument if called "Miss Row".

PS: An eager and ambitius recruit with below standard skills may be a great investment. Like buying a shoddy looking house which just needs a coat of paint at 1/2 the going rate.

Re:"Fit Factor"

[joto]

Nope, but there is tea!

Re:"Fit Factor"

[joto]

Actually a computer genius can do far more than a team of five average engineers. The term has gone out of favour, but there actually exists superprogrammers.

Re:"Fit Factor"

[Caffeinate]

"So remember, there's no 'I' in team, but there is an 'I' in 'pie'. In 'meat pie'. And 'meat' is an anagram of 'team' . . . I don't know what he's talking about."

Re:"Fit Factor"

[billcopc]

How would Malder, Hemos and Cowboy Neal cope with the kind of person who won't even answer you unless addressed by his formal title I.e. "Dr. Doe", not "John" or "Doe". Worse yet "Mrs. Row" who will start an argument if called "Miss Row".

Simple. They'd fire the pompous ass, then hire Taco to TP their house :)

Re:"Fit Factor"

[ShieldW0lf]

Google are a one trick pony. They did their innovation when they were in their garage, and they've been Microsofting ever since. Why would you want to work there?

Re:"Fit Factor"

[duffbeer703]

Consider what Google-y actually means. You may want highly qualified, skilled people, but based on Google's tight control about what gets communicated about the company, they want people who will conform and keep their mouths shut.

Never trust a company that spends lots of money on PR and advertising to tell you about what a great place it is to work at.

Re:"Fit Factor"

[Vellmont]

Yes. If you show up to a technical job interview with a dirty t-shirt on and are rude to the receptionist because you can't "deal with people" then you may not even get the interview after all.

Well, I think that actually goes towards being able to do the job rather than just being a cultural quality. I fear your extreme example has gone outside the bounds of what was being discussed.

I think perhaps what the OP was referring to was less universal "fit factors". It seems that Google wants people to "think like Google", which isn't always necessarily a good thing. A group bias of everyone thinking the same thing can be a dangerous thing indeed. Just look at the current Bush administration for the perfect example of how this can be a terrible, terrible thing.

Re:"Fit Factor"

[BoosterToad]

And "meat" !!!

Re:"Fit Factor"

[Blakey Rat]

There's no 'i' in "team," but there is an "i" in "Team Cheerios." Always remember that.

Re:"Fit Factor"

[Blakey Rat]

This article is total BS in any case. They asked me during my phone interview what file extension a Outlook email archive file had. WTF!? What does that question have to do with anything at all?

Re:"Fit Factor"

[Anonymous Coward]

This is the classic argument of the fragile "Agile" methodlogies. A bunch of incompetant people that get along fine dosent make a good team.

Re:"Fit Factor"

[Heembo]

Smart comments. Let me put this another way. Really good engineers/designers/analysts seem to "know" just what their clients need. EXCEPTIONAL engineers/designers/analysts work hard to DISCOVER what their clients need via TONS OF INTERVIEWS. That Requires A Lot of People Skillz.

Re:"Fit Factor"

[Anonymous Coward]

Well, it is clear they are looking for *technical* talent, or at least a certain kind of it.

Funny thing is, the one guy I know who went to work at Google could code like a god, but was promoted past his competence level and did considerable damage to his previous company through gross lack of people skills and business sense. That didn't keep him from getting hired there.

Re:"Fit Factor"

[nicerobot]

I think that Google-iness is somewhat PR BS. I love Google but I interviewed with them and it was heavily skills-oriented right out of the gate (nothing wrong with that for me since I have the skills). Though they talked about the culture at Google, which sounds wonderful, they showed little concern for whether I was Google-y. Personally, the fact that they didn't follow through with an offer shows me their hiring process is as difficult and flawed as any other moderate to large company compounded by their incredible demand.

Re:"Fit Factor"

[igny]

You are wrong, there is no you in team either!

Re:"Fit Factor"

[rmckeethen]

Someone who can learn quickly is more desirable than someone who knows Java like the back of their hand.

Interestingly, having spent the past few weeks interviewing, I tend to think desirability of 'quick learners' vs. 'skilled experts' depends upon the size of the company. Small companies prefer quick learners because there are always many more tasks to do than skilled employees available to handle the tasks. In this situation, quick learners have the advantage because they can more easily grow in a company where the jobs aren't always well-defined. If it turns out that the Java guy you just hired can also manage the corporate web site, this is a real plus in a small firm. Having people who can do lots of things, and do them reasonably well, is absolutely necessary when your company is limited by the number of resources available.

At large companies though, the situation is reversed; hiring managers in large corporations are often distanced from the actual work getting done, so their 'win' is to hire the person with the best current skills. This way, hiring managers get the most 'bang' for their corporate hiring buck because the expert employee is immediately productive in the job. In addition, larger companies spend much more time managing a workforce that expands and contracts depending on the economy. Human resources are just that -- something you aquire when you need to increase production, and get rid of when you don't. Overall, it's far easier to manage a large corporate workforce when employees have very narrowly defined skill-sets that you can swap in and out depending on the needs of the company.

In a nutshell, small companies want people who can get things done, where large companies want someone who can do one job and only one job, but still do that job better than anyone else.

Re:"Fit Factor"

[Anonymous Coward]

Some of this translates to elitism. Like a Mensa outfit, where they isolate themselves from other people who, for a variety of reasons, may have a lot to offer, but may not match a certain model of what they believe to be ideal.

That's unfortunate, but as you say, it's all about the numbers and public "image."

Sooner or later, the Google bubble is going to deflate (if not burst). They've done a good job managing it thus far, but it can't be sustained indefinitely. We all know that, from experience... and so should they.

I'd love to work for Goggle, you bet. But I don't have a PHD, Bachelors or all those wonderful "title-orientated" things. Isn't that a shame? I could care less, I'm good at what I do and that's what matters at the end of the day. Titles mean absolutely nothing.

I remember not so long ago where a sysadmin would be *begged* to work for a company. "Here, we'll even give you a car and a bonus to join the company!"

Those were odd days indeed.

Re:"Fit Factor"

[CopaceticOpus]

And "eat me!"

Re:"Fit Factor"

[Gatekeyper]

Sounds like a post from somebody bitter they didn't cut the mustard for Google.

Re:"Fit Factor"

[k.ovaska]

This article is total BS in any case. They asked me during my phone interview what file extension a Outlook email archive file had. WTF!? What does that question have to do with anything at all?

Maybe they wanted to see how you react to that kind of question? They might be completely satisfied if you said "I haven't handled Outlook archive files and thus don't know such details. In general, there are far too many details in the world to remember them all, I simply look them up when I need to. By the way, Google is a very good way to look up details."

Re:"Fit Factor"

[the_lesser_gatsby]

Is it a .pst? Just popped into my head! Hey, I've got a 2 minute bicycle ride to my office. I'm fine where I am...

Re:"Fit Factor"

[Andrewkov]

That Requires A Lot of People Skillz.

And also good spelling.

Re:"Fit Factor"

[Tim Browse]

I prefer despair.com's factory poster:

"We can't spell FAILURE without U R A."

Re:"Fit Factor"

[Tim Browse]

They asked me during my phone interview what file extension a Outlook email archive file had. WTF!

No, while you might be forgiven for thinking that they are .wtf files, they are actually .pst files.

Re:"Fit Factor"

[Heembo]

Coderz dont spell (or type) well, get ovr tit!

Re:"Fit Factor"

[Anonymous Coward]

and LOTS OF CAPITAL LETTERS!

Re:"Fit Factor"

[Anonymous Coward]

But I don't see a "U".

Re:"Fit Factor"

[Proteus]

there's no "I" in team. but there's no "we" either!!!

There is, however, a "u" in "suck". {ducks}

Re:"Fit Factor"

[Anonymous Coward]

Thank God we have a bunch of employees that are exactly the same. That way we can control them easier.

What a bunch of pompous twits.

Here have some koolaid, oh and leave your individuality / critical thinking about this company at the door - we are pod people here.

I wouldn't work there if they wanted me too ( and they don't ;-) )

Re:"Fit Factor"

[tigga]

I believe that "fit factor" is more important than technical competence.
Do you realy hire very nice but incompetent people?

Re:"Fit Factor"

[mshih]

My experience with Google hiring process was a joke and just turned me off of working for them. I was contacted by a recruiter a while back for a contract position. The first phone interview was missed because the recruiter didn't tell me that the hiring manager was calling and I missed the call. Then I found out the next day that the position was being "outsourced." A few days later, I was called back by the recruiter that the hiring manager changed her mind and wanted to talk to me again. So a new phone interview was arranged. The morning of the arranged phone interview, got a call that the hiring manager changed her mind again and will be "outsourcing" the position again. So the interview was cancelled. So I basically decided the people at Google were too annoying to deal with and don't really care about working for them anymore.

Re:"Fit Factor"

[Anml4ixoye]

I did. This certainly wasn't my first job, so I knew what to do. But they refused to give me any more information then that, basically just letting it go.

No matter, I took a job with a competitor. They may not have all of the fancy benefits, but they have great insurance, interesting people, and it's fun to tout Linux on the internal mailing lists. ;)

Re:"Fit Factor"

[Metasquares]

Don't assume that because someone knows the languages or broad technologies that a company uses, that person will immediately be able to jump into the job. Among other things, proprietary systems and a lack of experience with a company's environment, goals, and clients can easily foil people who still do have the requisite skills in the basic technologies to pass an interview. In these scenarios, quick learners have an advantage.

Re:"Fit Factor"

[wolja]

Yes. If you show up to a technical job interview with a dirty t-shirt on and are rude to the receptionist because you can't "deal with people" then you may not even get the interview after all. Except in very few circumstances (academic research comes to mind), doing your job well consists mainly of solving problems for other people. If you can't get along with those people you may very well be unable or unwilling to help them solve their problems.

Someone who can learn quickly is more desirable than someone who knows Java like the back of their hand.

What would you say the balance should be, 60/40, 70/30? Can you quantify it?

I don't believe you can quantify it. The instances in which I have seen attempts at quantifying "fit factor" (think college roommate selection, most online dating services, and etc.) fail most of the time because personalities and relationships are, for the most part, dynamic. If you were to quantify it, you would probably have to do it on an individual basis. One person's technical ability may compensate for a shortcoming in personality whereas the opposite may be true for another individual. It also varies by the type of job (i.e. short-term contract versus full-time employee).

Still, I believe that "fit factor" is more important than technical competence. Depends on the current role and the need to prepare for workplace changes as the business changes.

I took on a team lead role where the previous guy, a good friend of mine, was more focussed on the fit and blind to ability, flexibility and willingness to work for and as a team. The hirees were all chucklers and convivial in public and shiv wielders in private.

When the new mongrel took over who needed flexibility and needed em to retrain and widen their skills they fought and showed fit is not the most important. I'd prefer a team of useful misfits than a team of useless fits.

What they mean to say is...

[therufus]

What they mean to say is they don't want new employees using Google's internal internet bandwidth searching for another job.

I for one, would love to work at Google. Don't they let you bring your pets to work?

Re:What they mean to say is...

[Anonymous Coward]

Only dogs. The feeling is that it would be unfair to bring a cat to work due to the high population of dogs on campus.

Re:What they mean to say is...

[tomstdenis]

While it certainly seems like a "Free spirit" sort of place to work it's still a large megacorp (tm) which brings a lot of the downsides with it I imagine. Though the free meals/snacks does sound like a genius idea.

Though after having worked for one megacorp (tm), I can honestly say I'd rather be working where I am for a smaller company. Sure I don't get free meals, but at the end of the day I'm not a drunk anymore :-) [ok I wasn't really a drunk back then either, but I did drink way too often for my comfort...]

Tom

Re:What they mean to say is...

[therufus]

A wise decision. I haven't heard of many other companies being so employee friendly. Are there any other big companies out there that have this similar attitude?

I think it would be refreshing for employers to go out of their way to make their employees feel more at home. It would be much better for productivity.

Re:What they mean to say is...

[Anonymous Coward]

Really? The idea of wanting to go work for someone else seems strange to me. I work in my current job to pay the bills, at the end of the day. "Culture" is just a side benefit of that. Would I work at a place I didn't like? Not if I had a choice. Would I leave my job to go work for someone because their office seemed "fun"? No.

I'm going to start my own company, personally.

Re:What they mean to say is...

[WebCrapper]

MindSpring use to let employees bring pets. I would bring my dog in occasionally. Every once in awhile, someone would bring in their Ferret. I also had a friend that brought in a small fish tank and another one that brought in Hermit Crabs and would let them roam around her desk. Earthlink took over and all that stopped almost immediately.

Re:What they mean to say is...

[arivanov]

One of the reasons why I prefer to telecommute. If you are really stuck on something, there is nothing better than sitting for 5-10 minutes in front of the fish tank or taking the dog for a walk. Clears brain blocks outright. And as you clearly pointed out in the office this is at the mercy of the current PHB. That is, if you have the place to accommodate them in the first place. Most of the UK does not have it. Open plan country...

Re:What they mean to say is...

[NighthawkFoo]

One of my coworkers down the hall has a small aquarium in his office. He has a bunch of Neon Tetrasin it. It makes for interesting conversation.

Re:What they mean to say is...

[tomstdenis]

When I worked at AMD I always kinda smirked at the contrasts between the IBM campus [where I was a liason] and the AMD home office [in sunnyvale where I went for meetings]. IBM had all sorts of "earth tones", waterfalls, lounge areas, and darker lighting [with personal lights in the cubicles]. AMD on the other hand was a fluorescent wasteland of equal sized cubicles and green paint on the walls. Don't get me wrong, the OUTSIDE of the buildings looked nice, but the inside was very sterile and boring.

AMD would have been a bit nicer to work for if they had catered to the out of towners. Nothing like flying 3000 miles to then have to pay for the hotel and food out of pocket [expenses for out of country employees took 6 weeks to get at the least]. :-(

Where I work now it's fairly sterile too. We have a few posters up on the wall, but mostly it's a sea of beige and fluorescents. Fortunately, there is a pub just behind the office so I can sneak into there for a quick bite to eat when I get a case of the Mondays. That and we're tastefully colourful during lunch hour discussions [e.g. not PC-centric] so we can act like adults.

Tom

Re:What they mean to say is...

[Anonymous Coward]

What they mean to say is they don't want new employees using Google's internal internet bandwidth searching for another job.

Ha, that is precisely what I did at my last job for 6 months straight... surfed monster to get this job. I even talked to recruiters on the phones at work. The company I worked at was so big and too naive to notice the skills that I have, let alone realize that I was surfing monster numerous times every day. Their loss. :)

Re:What they mean to say is...

[WebCrapper]

Um, the fish tank dude had his fish murdered... Someone took the time to take the lid off the aquarium, pull 1 fish out, put it on a sticky note and beat the poor thing to death. They also wrote the obligatory "...swims with the fishes" on the note. He apparently wasn't liked too much.

Re:What they mean to say is...

[Anonymous Coward]

I get to work from home occasionally and I'm actually much more productive and I think its because of my "kids". Like you said, I can take my kids (dogs) for a walk, let them play outside for a few minutes and come back in to start fresh.

In fact, I'd love to be able to do that right now since I'm fighting (yep, cursing, beating things) at work with .Net

If I could meet the bastards that created this "language"...

Re:What they mean to say is...

[Anonymous Coward]

Why is it strange? A lot of people don't want to deal with all the bullshit and hassle that comes with running your own business. if you really enjoy doing X, and some company will pay you really good money to do a job that's say 80% doing X with some Y and Z that you maybe don't care for but don't absolutely hate, that's great. There are benefits to working for yourself, but there are a lot of benefits for working for someone else, too. It's all about your personality, skill set and goals.

Re:What they mean to say is...

[e2d2]

This is something I realized after 10+ years - smaller is better. I started out at a small shop and got my break doing everything and anything I could to help. I had to get along with 5 other people that were pretty much just like me.

Then I "moved up" for more pay to a mid size company, not bad. Pretty good actually.

Then eventually went to the largest privately owned company in the world. Benefits were great, but I was faceless. I was expected to do more work for less, but my heart wasn't in it. For some reason I couldn't help feeling used. Why? Because I felt detached from the company. Their goals were not my goals and they could have given a shit about my goals.

Maybe it was a personal issue, but at 30+ years old you simply come to a point in your life you make a decision. You either buy in and ass kissing becomes your specialty or you have a "life crisis" and try to find some sanity somewhere else. I chose the later and now work for a small company again. I don't think I'll ever go back to a large company, it just feels inhuman and unnatural.

But to each his own, some people don't have the same issues with authority that I have. More power to them.

Re:What they mean to say is...

[tomstdenis]

I think we learned the same lesson. Except I'm 25 and I was only at the megacorp (tm) for about 8 months. I are an quick learners yes I's am.

It's very true how you stop really caring about what the company is doing, especially if you have a sciences background. Don't get me wrong, I get the purpose of fluff and marketing, but when you spend more hours a day prepping something that has no lasting value [e.g. fluff] instead of real work, you just kinda go through the motions to get paid.

Tom

Re:What they mean to say is...

[afxgrin]

I want a workplace that employees are allowed to make a giant spray painted graffiti tag on the walls. Something that spells out the company's name in some illegible font, and looks as if it was created by MC Escher after a weekend long acid trip.

Re:What they mean to say is...

[tomstdenis]

Work from home :-)

Beige offices are annoying and are what lead people to extremes in their off hours. If you have just a normal comfortable place to work, you can be serious and goofy all throughout the day, then when you leave it's like you left a friends place or something.

The real companies know that in essence, you work to live, not the other way around. You can both be a serious professional, and a lighthearted goof during the span of a work day and get things done.

Besides, we know all the tight-ass execs who want the neutral beige offices are doing blow off a hookers ass during lunch anyways... :-)

Tom

Re:What they mean to say is...

[Dorceon]

Don't they let you bring your pets to work?

Well, they let people bring their dogs to work. If the dog is a natural predator of your pet, you might consider leaving it at home.

Re:What they mean to say is...

[AuMatar]

The idea of wanting to own your own buisness seems strange to me. High risk of losing everything you have, long hours, stress, needing to deal with lawyers, contracts, customers, accountants and others, spending most of your time on thing not relating to technology. No thanks. I prefer working for a company, I go to work at 9, leave at 5, take home a check and once I'm home I can leave the office behind because I just don't give a fuck. I'd rather flip burgers at McDonalds for minimum wage than make 6 figures owning my own business. I've done the McDonalds thing, it wasn't all that bad.

Re:What they mean to say is...

[afxgrin]

Beige offices are annoying and are what lead people to extremes in their off hours. If you have just a normal comfortable place to work, you can be serious and goofy all throughout the day, then when you leave it's like you left a friends place or something.

Coincidently ... my home office walls are painted a dark beige, but at least it has some tasteful artwork - like a big poster of Che Guevara, a Grand Theft Auto poster and some Escher-like posters, complete with a PC branded with various punk and anti-**AA stickers.

Besides, we know all the tight-ass execs who want the neutral beige offices are doing blow off a hookers ass during lunch anyways... :-)

It's good to know that some /.ers know the truth about corporate executives. :-) I've watched an auto exec roll a joint mixed with weed and hash in front of me, and an oil exec smoke hash oil. I think if they knew how much I posted on the Internet, they'd really not have done that. So far I haven't incriminated any of them... So I imagine the 'blow off the hookers ass' is probably left for the office. I'm sure a bump of coke and some head midday makes for a productive afternoon, or at least help relieve stress after you just laid off a few thousand employees.

Otherwise, I'm seriously considering a life of work from home. I'm sick of being stalked by my employers, or having to deal with their inflated egos. Everyone of them seem to find it necessary to belittle their employees as a means of flexing the only power they have in life. Oddly enough, the most modest bosses I've had all owned/managed a blue-collar shop and basically allowed us the greatest freedom over any office environment. Plus talking back towards someone more senior usually led to other co-workers joining in the heckling and the more senior employee lightening up a bit. If I did this in any office environment, I'd pretty much be fired within the following days. It seems so backwards, but it is a reasonably accurate reflection of my work experience -- It's all very confusing.

Re:What they mean to say is...

[Anonymous Coward]

How wonderfully mediocre. I bet you're a real blast at parties.

Re:What they mean to say is...

[sakasune]

The idea of wanting to flip burgers seems strange to me. High risk of getting grease burns, long hours, stress, needing to deal with idiots, managers, customers, and others, spending most of your time on thing not relating to technology. No thanks. ... I'd rather make 6 figures owning my own business than flip burgers at McDonalds for minimum wage. I've done the McDonalds thing, it WAS all that bad.

Is this a job ad?

[Timesprout]

Seems like quite a few people have been leaving Google lately

Re:i'm first?

[therufus]

No. Now move along. Nobody cares who's first. Try to make an intelligent/informative/funny/insightful comment. People will care about that.

When will the bubble burst?

[Anonymous Coward]

I hope all those perks leads to ultra increased productivity.

Bus seriously when will bubble 2.0 burst?

Would you fail if...

[niceone]

Would you fail if... you threw up at the first mention of the word "Google-y"? Ah, that's me out...

Re:Would you fail if...

[coaxial]

Would you fail if... you threw up at the first mention of the word "Google-y"?

You're allowed to throw up if "Google-y" was used in the sentence, " Stacy Savides Sullivan! I'm Google-y eyed for you!"

Re:Would you fail if...

[Library Spoff]

I also hate cricket...

Re:Would you fail if...

[Anonymous Coward]

Not if the noise you make when throwing up sounds like "Google-y"

Re:Would you fail if...

[Anonymous Coward]

Dunno... but I might have failed a Microsoft interview because I struggled to keep a straight face when the manager talked about writing software focused on stability and backwards compatibility.

Re:Would you fail if...

[MikeBabcock]

That'd be me. I'm a cynic and sarcastic to boot. Not with customers or anything, but within my workplace yes. And if anyone has a problem with it ... lol :-)

My boss where I am now is of the same bent I am that way, which is great. We joke and laugh and feed off each others' remarks half the time. Sometimes someone tells the other to 'F' off ... and we've been working together 8 years now. I'm pretty sure that wouldn't go over as very "Google-y".

Re:Would you fail if...

[lintux]

It made me feel itchy. But they didn't fire me yet. Fortunately you never hear the word again after the first week, so don't worry. ;-)

Best benefit

[marc_garcia]

For me best benefit working at Google's headquarter are individual swimming pools... any other company has it?

Re:Best benefit

[Timesprout]

Of course. I arrive into work every day by driving my rolls-royce into my personal pool. I won't even consider working for any company that does not support my rock and roll lifestyle commute.

If it were any other company...

[strobexii]

I'd translate it thus

Google-y is defined as somebody who is fairly flexible, You'll be working long hours. Weekends, possibly holidays...

adaptable Management will shuffle you around as it sees fit

and not focusing on titles and hierarchy, Promotion?! Haha! Here's a compromise: you're getting a new boss.

and just gets stuff done. Get to work and stop asking questions!

But it's Google, so we know better. Or do we? Seriously, which side are we taking today?

Re:If it were any other company...

[Anonymous Coward]

I'd translate it thus

At another company, sure it might be like that. Though at the G, it's more like:

Flexible = You don't turn down opportunities to do a variety of interesting things.
Adaptable = Able to fit in well with a variety of people (the world doesn't revolve around you)
!Hierarchy focussed = Don't care for power games, politics and related bullshit. Happy to field requests from outside your dept.
Get stuff done = Like above, no power games but actually like to do your work instead of a multitude of 'meta-work'.

J.

Re:If it were any other company...

[cyberkahn]

The funny thing about comedy is that it is often true.

Re:If it were any other company...

[appelsiini]

Probably this is the way it is. Ten managers per one employee who really does something. Processes for the sake of processes. Just like working for some say like Hewlett-Packard. Lick bottom and you'll do nice, speak out the truth in wrong place (like to customer, for God's sake) and you're so fired. Bad management practices tend to spread around. If I'd work for Google, I'd sell my stocks and run. Barely before armies of wannabe-millionaires and other incompetent morons who smell money will start pouring in from doors and windows. Hey, who are those hippies standing besides my Ferrari?

Re:If it were any other company...

[Anonymous Coward]

Parent's interpretation is closer to reality than most people might want to see. Even google cannot completely eliminate bureaucracy and politics in the workplace. After all, where there is money, there will be politicians. The best it can do is minimize the chance of conflicts and the impact to productivity thereof.

Of course, parent's is a rather cynical viewpoint, but that doesn't make it any less true. But some of these issues are present in many other organizations, not just Google. That's probably why a programmer who moves around a lot (once every 3-5 years) ends up getting paid better.

Perfect work environment ...

[Anonymous Coward]

Application question 1: What is your proficiency at leveraging non-google resources?

School education

[Anonymous Coward]

School education has nothing to do with how skilled you are and how well you can get the job done.

Re:School education

[Anonymous Coward]

No but every Google employee I know is pretty damn smart. I don't know that they are all college educated but most are.

This is going to change rapidly though, every double click employee I know is a dumbass. It's business, eventually google will run out of folks to hire or water down.

Re:School education

[deblau]

School education has nothing to do with how skilled you are and how well you can get the job done.

School education affects how skilled you are and how well you can get the job done to varying degrees, but is not outcome-determinative. Duh. I wish people would stop taking black-and-white extremist positions just to make a point. It makes you sound like an idiot.

Re:School education

[drgonzo59]

Oh how wrong. I have heard that phrase a countless number of time from every one who didn't to do well in school and just gave up and dropped out. You see, your GPA also shows how well you can get stuff done even if you are not terribly interested in it. It is not likely that everyone will enjoy Literature,Math, Biology, Psychology all at the same time, BUT if they can still get an 'A' in it that says a lot about that person's work ethic. Because in a work place not every single day and every single project is going to be 'fun' there is a plenty of times where you'd rather be doing something else so the employer will think 'will he drop out and leave when he gets bored here as well?'

 

Re:School education

[Asklepius M.D.]

While I agree that this is used all too often as an excuse, I still have to agree with the spirit of the parent's sentiment. To rely on GPA to measure work ethic is as prone to error as using GPA to measure knowledge. There are many students with mediocre GPAs (i.e. not dropouts, but not star pupils either) who have sufficient work ethic to meet the inane requirements set by bureaucratic administrators or professors who believe rote parroting == learning, but who have the personal initiative to go out an actually LEARN in spite of these requirements. I would prefer to hire one of these students as they will put up with the BS of an administration without wasting countless hours kissing @$$ or filing triplicate TPS reports to "make the grade" without actually accomplishing anything meaningful. Straight A's doesn't necessarily equate to a good work ethic - it might just be a high tolerance level for "busy work". My hiring preference goes to B and C students who's transcript shows an abnormally high number of classes/credit hours in difficult or interesting courses and who also is proficient in his hobbies/extracurricular activites (especially those that are unsanctioned - anybody can "join" something - I want to see that the applicant can "start" something and follow through with it). I've worked with people who's specialty was jumping through administrative hoops, and strangely enough, I got stuck doing all the actual work while they were busy buzzwording. I don't care what somebody else says you're capable of - I care what you ARE capable of, and would rather put in the effort to judge for myself rather than rely on the opinion of professors who've seen only a narrow aspect of the applicant's abilities.

Re:School education

[drgonzo59]

I don't care what somebody else says you're capable of - I care what you ARE capable of, and would rather put in the effort to judge for myself rather than rely on the opinion of professors who've seen only a narrow aspect of the applicant's abilities.

I am capable of building a time machine, hire me, pay be $200,000/year and in 5 years we might have a time machine and we can sell rides to people.

So would you hire me? How would you know what a new college grad is capable of? Sure they'll say they a capable of many things. Nobody will tell you "yeah, I'm kind of lazy, and I get bored and give up easily..." or "I could have gotten an 'A' if I'd worked harder but I just wanted to party and slide by with a 'C' ".

In order to know what an applicant is capable of you need to also look at what others say about them. GPA is the result of a large, 4-5 year project that this person accomplished. It included doing boring grunt work, as well as learning exciting new stuff and the GPA is the most objective index you have of the result of that project. I would definetly look at that index. Otherwise you are left guessing and gambling.

...who also is proficient in his hobbies/extracurricular activites And how can you tell how proficient they are in fishing? Would you ask them about the biggest fish they caught. Again, hobbies might be interesting but I don't think I would want a person with 10 different hobbies and a GPA of "2.0".

bureaucratic administrators or professors who believe rote parroting == learning

Here I would do what you said and look at the classes and the school. Someone who can get a 4.0 in a local community college is different than someone with a 4.0 from Yale. There is a different learning environment at different schools. It is not clear cut and I would never rely on GPA alone but combined with the school and the major it can be a good, fairly objective indicator of that hiree's potential.

Re:School education

[metamatic]

School education has nothing to do with how skilled you are and how well you can get the job done.

So, where do you get your dental work done? Some guy in a garage? Or do you go to a dentist who went to school and studied the subject?

I'm prepared to bet you also get your medical treatment from a qualified doctor, rather than someone who didn't go to medical school but has read a bunch of books and seen every episode of "ER".

Re:School education

[ciggieposeur]

GPA is the result of a large, 4-5 year project that this person accomplished. It included doing boring grunt work, as well as learning exciting new stuff and the GPA is the most objective index you have of the result of that project.

No, GPA is not the result of a "project". Not even in graduate school, where the bulk of the work is in fact a project (thesis or dissertation). GPA is the result of a "grind", a long series of classes, some interesting, many not, that we all have to get through in order to obtain the piece of paper that ensures our resumes are not immediately trashed. It is a rite of passage, either a grueling crapfest or a 4+ year party depending on your parents' willingness to spend.

Now, if school really WAS a project, one in which the results could be immediately shown after graduation, and if GPA was really a measure of one's results, then GPA would be a great indicator of potential success. As it is now, no way.

One of my friends is a manager with a Fortune-10 company. He was on a recruiting trip with his manager and two other team leads. At lunch, the discussion revolved around GPA criteria: the 2nd-line manager loved to hire 3.8+ GPAs. My friend and the team leads pointed out that by that criteria, none of them would have been hired by their boss, and all of them are the highest performers in the unit. I suspect it is this way in many other places.

Re:i'm first?

[arachnoprobe]

Try to make an intelligent/informative/funny/insightful comment. People will care about that.

You know, you are sooooo 1.0 ! This is /. 2.0, it's not about the content anymore... ;)

HR could use some help...

[ndykman]

I gone through the initial process with Google twice, with the same outcome. It seems to me they need to improve their HR process, as I've gone through a phone interview, but then told I wasn't a good fit.

If you look at my background and resume, I think you would concur that the positions I was interviewed for weren't a good fit, but because it was Google, I gave it a shot. But, fool me once, fool me twice and all that. If they call again, I'll let them know how I feel about the whole process.

Re:HR could use some help...

[Timesprout]

I gone through the initial process with Google twice, with the same outcome. It seems to me they need to improve their HR process

OK so Google is broken because they didn't hire you for a position you admit you were not suitable for. Is the earth still flat in your reality?

Re:HR could use some help...

[dummkopf]

same here. comment to to the other responder: if HR calls you and wants you to work for them, it implies they have researched your background and have something in mind. clearly this is not the case. the approach is more a "here is a smart guy, let's get him. wait, no, we do not know what to do with him, oh well. bye".

Re:HR could use some help...

[Anonymous Coward]

I gone through the initial process with Google twice, with the same outcome. It seems to me they need to improve their HR process, as I've gone through a phone interview, but then told I wasn't a good fit.
  That's their stock answer, I'm afraid. The HR contact you speak to initially (your "handler") will promise detailed feedback on the phone and stress how important he thinks it is that they are transparent with their process. Then after an unnecessarily long process involving telephone interviewers with people who are shockingly bad at conducting a technical telephone interview, you'll get a bland response that they "couldn't find a position that was a good fit for you".

If you actually ask for the detailed feedback you'll get a second generic comment that might be a laughably poor fit for you as a candidate. There is a disconnect between the HR handler and the people who conduct the interviews -- your technical interviewers don't actually care [and aren't well enough trained] to give detailed feedback, but the HR handler is told how important it is for PR that everyone gets some meaningful and not-too-negative feedback. (Surveys have shown rejected candidates often refuse to use the company's product, and if you're Google with so many rejected candidates they rely on using the product, that's a problem!) Hence the somewhat duplicitous message -- it's not that the HR guy is lying about the importance of feedback; it's just that practically he doesn't have the feedback to give.

Re:HR could use some help...

[Jerf]

His point was that they should have been able to tell he wasn't suited for it.

I've read about this a lot, even been on the receiving end of it once; Google seems to be very spastic about what job offers they give you. It's like they have a template for an "acceptable resume" which is very broad and includes everything from sysadmin to deep-magic AI search engine worker, but once you pass that filter, what job offer they'll talk to you about is randomly selected from the pool of current jobs. So you might qualify for the deep-magic search engine job that is the core of your work, then be referred to interviews for a sysadmin position.

I didn't go much past the "random email solicitation", but even then, despite having my resume on hand the email was talking about a job position that was inappropriate for me. Working for Google is not so awesome that I'm willing to give up my development career to become a system admin for them. Moreover, the fact is that I'm not really qualified to be a large scale system administrator, which really isn't at all like being a developer (entirely different skill set and history). I could work on any web application you can think of, and that's the only way I can imagine I got past their resume screen (even the initial one)... but then they talk about sysadmin jobs. Very random. Honestly unimpressive, I've never heard of such haphazardness from any other company. This is a Google process flaw that needs to be fixed at the HR level.

Re:HR could use some help...

[lintux]

> if HR calls you and wants you to work for them, it implies they have researched your background and have something in mind.

I've seen recruiters send that kind of mails to mailing list. Don't be so sure... Ah, found one on a Python mailing list.

Re:HR could use some help...

[Aliriza]

Google when considered time is a young firm , with owners that has academic career. We'll on sunnny days it is easy to sail , we'll see when the storm comes.

Re:HR could use some help...

[don.pratt]

I gone through the initial process with Google twice, with the same outcome. Theys said I don't got good grammer. I axed "Whats my momma's momma got to do with anything?"

Too much spin

[ushering05401]

Not that Google is breaking down my door, but I wouldn't work there just based on this article.

One of the top gripes I have with corporate culture is all the bullshit language that is employed. What is this 'Happiness Survey?' This smells of new-age rebranding. Aren't they talking about 'workplace satisfaction?' Don't most companies conduct workplace satisfaction surveys? The companies I have worked for do.

What is this Culture Czar position? You take workplace issues to HR, who coordinates with all other departments to implement the corporate workplace vision. Some companies are better at it than others, but rebranding the position doesn't make Google any better at it.

Google produces innovation based on incentive... which is basic capitalism. It's great that they want the incentives to be more than just cash, but this just feels like a while lot of cheerleading. These tactics don't strike me as being professional. It feels like more spin in an age of way-too-much-spin.

Regards.

Re:Too much spin

[cyberianpan]

What is this Culture Czar position? It feels like more spin in an age of way-too-much-spin Positive marketing works, people like Coke because of the brand which causes similar brain changes to drugs. A cheap way to make someone happy is nice corporate art, similarly internal company branding works. Google employees get a buzz from working in the company with the most valuable brand in the world. Having kooky titles like Culture Czar & Google-y reinforces the buzz about the place.

Google produces innovation based on incentive... It's great that they want the incentives to be more than just cash People actually only need so much money, the article clearly talks about the reward of a stimulating environment that is more campus like than other employers:

'Happiness Survey?' This smells of new-age rebranding. Aren't they talking about
'workplace satisfaction? Maybe, maybe not. Workplace satisfaction points towards the colour of the walls, the taste of the food... the focus "sounds" narrow. Work is where we spend about say 50% of our quality time so it is a major part of our lives. Google with its ski trips, for example, is acknowledging the blur between work & personal life. Thus with a hapiness survey they take a wider interest/responsibility than with a workplace satisfaction survey.

Personally whilst I find this blurring interesting it's also a little disturbing- many of the people I know who work at Google have an incredible personal loyalty to the firm, they socialise together, ski trips, voluntary charity events... somewhat cultlike.

Re:Too much spin

[TodMinuit]

Having kooky titles like Culture Czar & Google-y reinforces the buzz about the place.

I feel like they're infantizing their employees, reducing them to cutesie-wootsie titles.

Perhaps I'm just different.

Re:Too much spin

[elrous0]

Just take your Soma and realize that this is a doubleplus good place to work, citizen!

Re:Too much spin

[l0cust]

No you are special, because you are my cuddly-wuddly lumpy-gumpy pumpkin pie.

Excise the Stanford out of Google first

[sethstorm]

Google-y is defined as somebody who is fairly flexible, adaptable and not focusing on titles and hierarchy, and just gets stuff done
Odd for an organization that prides itself on the contrary through their bit on favoring exclusivist universities and the concepts that go with them. They would do well to take a few pages from the concept of Jante Law to have an honest effort at meeting those concepts. That includes doing away with everything that connects them to Stanford in terms of exclusivity as well, as that hasn't helped in that effort as well.

Re:Excise the Stanford out of Google first

[ealar dlanvuli]

It is just possible that exclusive universities produce good people, and part of google's success is the fact that they do expects a decent degree or spectacular experience in it's stead.

The "computer industry" has been so anti-degree of late it's not surprising this offends people. But, honestly, every other industry places value on a good degree, so why should we be special in this regard?

Is it just possible that the top 10% of students, after spending 4-5 years studying a field, might actually be more qualified than a high school graduate? I know this is pretty much blasphemy, but honestly, perhaps people should consider this more.

(Note, before anyone replies with a sob story, if you hire people that get C's, expect C work in the world)

3sat

Re:Excise the Stanford out of Google first

[Anonymous Coward]

I don't think they produce good people as much as they select good people. Why go to the trouble of perfecting your own interview process when top-tier universities already have it down to a science?

Not having a good degree doesn't necessarily mean you're not qualified. But having a good degree virtually guarantees that you are.

Re:Excise the Stanford out of Google first

[danbert8]

Is it just possible that the top 10% of students, after spending 4-5 years studying a field, might actually be more qualified than a high school graduate? It IS possible, but realistically, grades are pretty much meaningless. I basically do nothing in college (no studying, no homework unless it's graded, etc) and still get A's. It's because I am very good at test taking. So someone who works their ass off to get a B is considered less qualified?
 
You also need to note that grades can vary greatly by the teacher. Some teachers curve, which encourages laziness, while other teachers have biases that reflect in grades. You can't tell me you've never had a teacher that you've argued grades with. Einstein and Edison didn't exactly excel in school either, and it's because school is designed to cater to the mediocre, and the smartest students often don't care.

Re:Excise the Stanford out of Google first

[TodMinuit]

Is it just possible that the top 10% of students, after spending 4-5 years studying a field, might actually be more qualified than a high school graduate?

A fresh out of high school graduate, yes. But a high school grad who has been in the indsutry working for 4-5 years? No. Most of the time, he'll wipe the floor with the college graduate.

I always find it a little sad when people think you need schooling or a degree to truly know something. It's like they're putting artificial limitations on themselves.

Re:Excise the Stanford out of Google first

[eric76]

A fresh out of high school graduate, yes. But a high school grad who has been in the indsutry working for 4-5 years? No. Most of the time, he'll wipe the floor with the college graduate.

That may be true for relatively mundane tasks, but not for something that requires more background knowledge of the subject matter.

For example, very few, if any, computer professionals without degrees are going to have any serious understanding of things like algorithmic complexity. The few who will understand it without college will have studied it on their own. Yet, above a certain minimal level, any serious developer had better have a better than minimal understanding of them.

Without that wider background, all you end up with is someone who is knowledgeable about their own area but will likely never go much beyond it.

As it is, too few computer professionals with degrees have an adequate understanding of the nature of what they are doing. What you end up with is a bunch of developers who insist on reinventing the wheel instead of using what is already well understood. And when they reinvent the wheel, they generally do so very, very badly.

Re:Excise the Stanford out of Google first

[Bedouin X]

Note, before anyone replies with a sob story, if you hire people that get C's, expect C work in the world

In the world of proper HR, grades don't mean a whole lot by themselves as a relative measure for applicants. This is because their veracity differs between school systems, schools, school units (e.g. college of engineering, college of business), degree programs, degree concentrations, and individual professors. It is almost impossible to compare students from two different schools solely on their grades.

My undergrad GPA was something like a 2.8. I understood the material covered at least as well as the 4.0 students, but many times I had better places to be than in class, better things to do than "homework," was placed with subpar, motivation-killing students in group assignments (the bane of higher ed these days), yet somehow people were surprised that I scored in the 97th percentile (SEM would have dropepd me to 94th) nationwide on my exit assessment exam. So little of a grade is based on whether you know the material and so much of it is based on the professor's ego. Now that's my business school experience (management, I dropped out of systems because I could teach myself that stuff in 1/4 the time) so maybe engineering programs are different.

I would hope so, but as I've worked in Higher Ed for the last nine years, I really doubt it.

Re:Excise the Stanford out of Google first

[maxume]

Your statement is meaningless without at least stating the admissions policy of the college that you are attending. For example, in Michigan, Michigan State has 'selective admission', which mostly means you remember to wipe your chip when you drool, whereas the University of Michigan has 'highly selective admission' which means you wipe your chin when you drool, but you don't drool as often. Northern Michigan University has 'open admission' which means you remember to wear clothes most of the time. Getting A's with the clothes most of the timers is an easier task than getting A's with the don't drool most the timers(and the course work is actually designed to separate the good from the bad in each category).

Re:Excise the Stanford out of Google first

[poot_rootbeer]

That includes doing away with everything that connects them to Stanford in terms of exclusivity as well, as that hasn't helped in that effort as well.

Sounds like someone's a bitter USC grad...

Re:Excise the Stanford out of Google first

[ealar dlanvuli]

Engineering tend to be better in that regard than what I expect business is like (judging by my experience having to kiss ass like an idiot in most liberal arts classes).

However, there are still failures at teaching in every field, and there are tons of engineering classes worth nothing.

On the other hand, using your own statements, if you spent 4 years of college not going, what is the likelyhood that you will actually care when you get a job? I have no reason to expect you would work hard if I hired you, considering you demonstrated that you didn't work hard at school.

Sean

Re:Excise the Stanford out of Google first

[ealar dlanvuli]

It's both production and selection. I have always been in the top candidates as a worker. After studying the field, I am now able to intelligently compete with people that make the field (rather than stumble across something interesting and luckily make a niche for myself).

3sat

Re:Excise the Stanford out of Google first

[ealar dlanvuli]

Well I think there is a divorce in what we're saying. There are a lot of jobs that don't requre a very expansive knowlege base. In fact, for a lot of things, I'd say job training is the best, and this is the big problem with America's university system (it tries to be everything to everyone, while about 60% of the students just want a piece of paper and won't get real value from learning)

Job's I'd trust a HS grad with: Web programming, MySQL database design (if it doesn't need to be too fast), Windows programming, testing, being a DBA after some training courses, etc. etc.

Job's I'd want a college diploma (ugrad for some, at least masters for most of these) while hiring: Desiging a new communication protocol, vetting the security of an encrption algorithm, developing new programming languages, desigining "complex" windows programs -- e.g. Visual Studio / Word, taking some open source software and throwing together a massive distributed system from scratch (e.g. google or amazon), desigining new algorithms to search the web (these tend to require very advanced maths).

So while yes, there are tons of jobs out there that "work experience" does fine for, when I want a graph theorist, I do not look to people with high school degrees. When I want a VBA coder, HS is perfect.

3sat

Re:Excise the Stanford out of Google first

[flooey]

A fresh out of high school graduate, yes. But a high school grad who has been in the indsutry working for 4-5 years? No. Most of the time, he'll wipe the floor with the college graduate.

I always find it a little sad when people think you need schooling or a degree to truly know something. It's like they're putting artificial limitations on themselves.

I think that it's a bit different at Google than at some other places, at least for certain positions. A high school graduate that's been in the industry working for 4-5 years can certainly do a lot of jobs. But there's a huge benefit to studying theoretical computer science when you get into highly specialized fields like search, as well as trying to do things on Google's level (where things like scalability and algorithmic complexity are extremely important).

Basically, the industry worker may well know C++, Python, or the Windows API inside and out, but he probably wouldn't be able to explain why support vector machines usually perform better than Bayes classifiers or when mergesort should be used instead of quicksort.

Re:Excise the Stanford out of Google first

[TodMinuit]

You certainly wouldn't be allowed to do my hiring. All I'd want are capable employees.

To do any of these, all that is required is knowledge. Knowledge which is covered much more verbosely in books and papers than in lectures. An H.S. grad with a serious interest in computers should be able to do all of these just as well as a college grad, if not better as he's learned the specific knowledge required out of self-interest, developing a deeper understanding than a college grad who was merely chasing a good grade.

Passion and experience are worth far more than degrees.

Re:Excise the Stanford out of Google first

[Bedouin X]

I didn't go to class because it was pointless most of the time. You can tell after two classes is the professor is actually adding anything to the material or just reciting powerpoint slides, in the case of the latter (read: the majority) I had better things to do (e.g. reading software development books, writing programs, going to professional user groups, etc) than listening to somebody read notes for an hour. I paid go to school to learn things. I didn't pay to inflate the teacher's ego with my attendance. If I can demonstrate mastery of the subject matter, it shouldn't matter if I was in class or not. I worked my ass off when the class required it.

As for not hiring me, that would be your loss. I have 10 years of outstanding employee reviews - never merely average or good - and successful projects under my belt. Primarily because I am good at applying the 80/20 rule - recognizing the things that matter the most and getting them done. It was clear to me which 80% of the time spent in a classroom was pure garbage and I decided to make better use of the time. Comparing college to a job is specious on a number of levels, which - like I said - is why most trained HR recruiters (HR was one of my management concentrations) take GPA with a grain of salt.

Re:Excise the Stanford out of Google first

[TodMinuit]

College isn't the only place to you can learn theoretical computer science.

Re:Excise the Stanford out of Google first

[flooey]

College isn't the only place to you can learn theoretical computer science.

It's definitely not, but I'd expect that most people who haven't gone to college haven't gone ahead and learned it on their own. Recruiting and interviewing people costs money and time, so it's a question of how much return they expect to get on any particular investment.

Re:Excise the Stanford out of Google first

[Anonymous Coward]

Well, I only have an undergraduate degree from a university in a third-world country and I've already had 3 phone interviews with them. They have invited me to one of their locations in Europe and now I'm just getting my visa ready so I can go there on site. The fact that they are inviting me there means I'm a good prospect for a hire, which would go against your accusation of them only favoring exclusive universities...

Re:Excise the Stanford out of Google first

[Abcd1234]

It was clear to me which 80% of the time spent in a classroom was pure garbage and I decided to make better use of the time.

And that's why you didn't do your homework?

Re:Excise the Stanford out of Google first

[Bedouin X]

No, the homework assignments that I skipped were generally reinforcement exercises and they primarily happened in core classes (Freshman and Sophmore year). Some people require less reinforcement than others, it seems silly to me to base a portion of a grade on such things.

The assignments that truly required thought and analysis - which were more the norm when I hit my major - I did happily.

Re:Excise the Stanford out of Google first

[l0cust]

You are an IIT'ian, aintcha?

Re:Excise the Stanford out of Google first

[ealar dlanvuli]

While we are probably going to have to agree to disagree, there is a distinction between mastering one field (definitely possible to do with books and so forth) and getting a good grounding in the theoretical basics of computer science.

Perhaps another way to say it. The same extremely gifted people we are talking about have two options when they are college age, they can go to college and expand their skill, or they can go to work and expand their skill. At work you will learn a few skills very well, but at college, these same people will master an entire academic discipline. So if your goal is to be a MySQL administrator, then work experience is a good idea. If your goal is to design and implement MySQL, you'll probably want the solid grounding that school offers you. While you might luck out and get a mentor on the job that teaches you everything that a degree would, it is not likely, and despite the size of the average programmers ego, there is only so good you can get without interaction with people better than you.

Also, you seem to think that a university education entails taking classes. If this is so, then you would be underwhelmed by the students that come out. The real value of university is having a place to hang out with professors, grad students, and ugrads that are brilliant. All of you working on expanding your understanding of the field. When you find someone from this group of people, you won't be dissapointed by what they learned at school. Unfortunately, these people comprise about 2-3% of graduates.

3sat

Re:Excise the Stanford out of Google first

[Anonymous Coward]

No. I work very well with other people. I also believe I'm a very good worker (and my employers and co-workers seem to agree). I'm just trolling because the anti-academic mentality on /. is hillarious.

3sat

Re:Excise the Stanford out of Google first

[TodMinuit]

If your goal is to design and implement MySQL, you'll probably want the solid grounding that school offers you.

*sigh* Try getting out of school and learning a completely new subject on your own. You'll end up surprising yourself.

The fact is there is nothing unique that a university offers. The professors tend to be disinterested in teaching and the students (undergrads, at least) more interest in partying than learning. A college is not a place to get a truly deep understanding of material. It's where shallow learning takes place.

Re:Excise the Stanford out of Google first

[Anonymous Coward]

Also, you seem to think that a university education entails taking classes. If this is so, then you would be underwhelmed by the students that come out. The real value of university is having a place to hang out with professors, grad students, and ugrads that are brilliant.

So paying to interact with smart people who don't/haven't actually worked in the real world is somehow better than being paid to interact with smart people who do? That wasn't my experience at all.

Re:Excise the Stanford out of Google first

[Anonymous Coward]

Remember that Google employs a large number of computer science PhDs. If I remember correctly, 3 or 4 years ago they weren't really interested in hiring new bachelors graduates at all. Forget 4 years, the people with PhD's have something like 7 or 9 years of study, half of it devoted to becoming expert enough in the state of the art in some area of interest to contribute valuable new ideas to the world.

Re:Excise the Stanford out of Google first

[nil0lab]

...
> The "computer industry" has been so anti-degree of late it's not surprising this offends people. But, honestly, every other industry places value on a good degree, so why should we be special in this regard? ...

Um, because there is such a history of people with "great degrees" doing poorly.

Programming is really a personality thing... and real academic types often can't get "real" enough to solve the "real world" problems.

Re:Excise the Stanford out of Google first

[Anonymous Coward]

Once again, you seem to labor under the impression that brilliant people, at the university, are learning less than the same brilliant people on a job.

Of course I've taught myself several fields. It's something I do a few times a year, whenever a new topic interests me or is necessary to complete a task.

How the hell do you think brilliant people are brilliant? They sit around waiting for their teacher to spoon feed them yet another tasty bit of information, and do nothing on their own? That doesn't make a lot of sense, really. That would just make you good at academia, a fairly worthless crown.

3sat

Re:Excise the Stanford out of Google first

[Anonymous Coward]

I know! And it's totally not possible that they learned anything during all that study! On the job training is the wins!

I love /..

Google recruiter email

[Ricin]

"I found your contact information on the Internet. I am interested to know
your openness to new job opportunities and find out more about your past
work experience." ... etc

A few months ago I got a few like these (not copies of the same text). A bit spammish but with restrain. I remember being surprised and wondering how many people were getting these. I wouldn't want to relocate to another country so I never replied. I'm also not a big Google fan personally (call me paranoid). Especially the cultivated "kool-aid factor" (aka PR) ticks me off.

Anyone else been contacted this way?

Re:Google recruiter email

[mlk]

I have as well (a year ago). I was very tempted to reply, asking how they actually got my details.

Have they recently opened, or about to open a new office? I got mine shortly before they opened the London office, apparently they were having problems filling posts due to the very long and round-about process they had in place (involving multiple trips to the US).

Re:Google recruiter email

[Anonymous Coward]

Yeah, I went through the whole thing, and in the end they were not interested unless I would relocate to Mountain View. Then a couple of months later a new e-mail from another recruiter, saying how they found my details somewhere, and asking if they can interview me... I got the impression that their recruiters don't care shit about the people they bring in, they just need to fill some quota, and if instant gratification is not in sight, they dump you fast as they can.

I am with Monkey Boy on this one.

Re:Google recruiter email

[Ricin]

That's possible, London and various US locations mentioned, but also IIRC in Switzerland. That might have been a new office.

Re:Google recruiter email

[lwriemen]

The fact that they require relocation to their office somewhere implies a lack of trust in their employees to get jobs done without explicit management or peer oversight.

Re:Google recruiter email

[CrazyTalk]

Yep, I got one too - around the time they were opening the Pittsburgh (where I live) office. I'm sure they just do a keyword search on monster and other job boards (Doesn't even require a "Sophisticated" search engine like google) and contact every resume they find in the proper geographic area.

Re:Google recruiter email

[0xdeadbeef]

Some chick named Bianca? Same text, "openness" and "opportunities" phrases transposed. Ignored it. Fucking spammers.

Re:Google recruiter email

[Kris Warkentin]

I've been contacted by at least 3 different recruiters. One tried to add me to her contact list at http://www.linkedin.com/ but I declined since I don't want to work in the U.S.

Re:Google recruiter email

[Ricin]

I'm not on one of those. SF.net maybe.

Re:Google recruiter email

[bernywork]

I was in discussions with a recruiter, but wasn't willing to relocate to Ireland.

Re:Google recruiter email

[dr_dank]

If you have a resume up on Monster/Hotjobs/Careerbuilder, then its a safe bet that your resume was seen and replied to by these scammers. Hardly a day goes by that I don't get an email offering "payment transfer agent" jobs where you take bogus checks or checks from fraudulent auctions, skim a percent off the top, and wire the remainder to your "bosses". Weeks later after bouncing around from bank to bank, the original check is dishonored and now you're on the hook for the money you wired out like an idiot. That, or the police come knocking on your door asking why you're laundering money from bogus ebay transactions.

Another was a flimsy phishing scam aimed at stockbrokers, luring you into filling out their "application" with your info.

Caveat emptor, indeed. With the desperate people who look to these sites for work, it's no surprise that these scammers clean up.

Re:Google recruiter email

[anticypher]

Google's first contact was from one of their recruiters calling my Irish mobile number, which forwards to whichever mobile I'm on at the time. So later they thought I still lived in Ireland, even though I left at an early age, and only have the mobile for when I work projects there. I sent a specially polished CV to them with a white-listed email address for exclusive Google use. I still get the occasional spammy-feeling email from randomly named recruiters on that address.

If I were to believe the word-of-mouth excuse I recently heard from a friend now inside Google, they really thought I lived near their HQ, and my question of "what Google facilities are near my home?" caught them by surprise. I believe I just wasn't technical enough for them, or I post too much on /.

the AC

Over one thousand posts in a decade. I have a social life, I swear

Re:Google recruiter email

[houghi]

There will be a new center in Belgium. Perhaps that might be more interesting. The choice in beer is better anyway.

It will be the center for the rest of Europe.

Re:Google recruiter email

[bernywork]

What happened to corporate headquaters in Ireland?

Why the move?

Re:Google recruiter email

[Topherbyte]

I received one too and I know an `important` person there, so I'm unsure as to that correlation. However after a careful 2-second consideration and a very strong bout of nausea at the idea of being surrounded with so much self-importance, I decided that Google couldn't pay me enough to abandon my own business.

Working for oneself is what job satisfaction is all about, IMHO.

Re:Google recruiter email

[Anonymous Coward]

I have gotten a couple. The first time I got targetted with relatively specific position descriptions, that suggested they used some combination of my web pages or mailing list participation to figure out what kinds of things I do. When I replied no thanks to that message, I actually got a reply back.
More recently I got a more generic message and when I replied back to that one, I didn't get a followup message.
So I suspect that their recruiting strategy has been changing over the last year or so.

Re:Google recruiter email

[bill_mcgonigle]

Some chick named Bianca? Same text, "openness" and "opportunities" phrases transposed. Ignored it. Fucking spammers.

Is any contact you're not expecting spam, or is the problem that they didn't craft a unique message for each contact?

Your /. id is low enough that you've been around tech for a decade at least, so maybe you made a list of potential good candidates? Or should they stick to folks who fill out job applications? I'm honestly curious why it would be a cause for anger.

Re:Google recruiter email

[0xdeadbeef]

I haven't had my resume on the market in over four years, and I still get sub-literate headhunter spam. The worst is from people actually using texting slang. Recruiters by their very nature offend me, so there is something particularly annoying about getting an unsolicited form letter from what it is supposedly the most "desirable" place to work.

Then again, maybe I'm just projecting hostility because I'm afraid of their interview process.

Chief Culture Officer

[Albanach]

Google-y is defined as somebody who is fairly flexible, adaptable and not focusing on titles and hierarchy

This is from their Chief Culture Officer. Do as I say, not as I do?

Re:Chief Culture Officer

[Timesprout]

This is from their Chief Culture Officer. Do as I say, not as I do?

That was a typo.It should have read 'Chief Culture Club Officer'. It's a little known fact that Sergey and Larry are HUGE Boy George fans.

Re:Chief Culture Officer

[ez76]

That's not a title. She's a Native American, you insensitive clod.

Re:Chief Culture Officer

[Spacezilla]

That is just about the funniest thing I've ever read!

Re:Chief Culture Officer

[suv4x4]

Google-y is defined as somebody who is fairly flexible, adaptable and not focusing on titles and hierarchy

This is from their Chief Culture Officer. Do as I say, not as I do?

This is only natural. See: they are a big corporation now, and it operates like a big corporation. But they recognize their old image lets them do a lot of things without a public outcry.

They are so casual and open, it's simply so ok to hold your personal data (since they're good guys and won't abuse it), and it's even ok if they mess up and lose some of your emails and settings (they're just guys like you and me, not robots, give 'em a break!).

But it's really just a shell. Do you know those exotic bees which lay their eggs inside caterpillars. To anyone outside, this is still a caterpillar for a long, long time (Google-y! Yei!), but on the inside the bee is eating it up ("Chief Culture Officer" and other corporate signs).

One day the caterpillar cracks open and you see nothing is left except the bee and an empty shell.

Re:Chief Culture Officer

[Anonymous Coward]

You win at the internet today

No interviews required

[El_Muerte_TDS]

All google needs is your unique google id and your name and they can find the rest themselves. Saves both parties a lot of time.

Re:No interviews required

[anticypher]

My first interview with Google last year, the interviewer made it perfectly clear that he already knew my /. login, had read personal and highly technical emails in my gmail accounts, had discovered some old technical papers not widely published from more than 20 years ago (hence my login name here), and other widely dispersed private information about me. Just putting my RL name into google, and other attempts to discover how all this information was gleaned showed that his sources were more than just some mad googling skillz.

I was quite paranoid for a while after that interview.

But as I've pointed out elsewhere, they didn't know I didn't live in Ireland, and thought I still lived just up the road from their new European HQ.

the AC

Re:No interviews required

[CopaceticOpus]

The interviewer had read personal emails out of your gmail account? I haven't reviewed gmail's privacy policy, but in any case that sounds evil. If I were an applicant, I would feel much less inclined to take a job with a company that showed me such little respect.

Re:No interviews required

[afxgrin]

Thank you for confirming everything I've begun to believe over the past month about Google. Are you still using that Gmail account you've got listed here?

Re:No interviews required

[anticypher]

I can't be 100% certain that they just read my gmail accounts, but I was in raving paranoid mode soon after the first interview.

First question was from my dim, distant past, close to the dawn of telecommunications. Nothing at all I would list on a CV that only highlights the best of my recent career. Cool, thought I, I know this because I did my thesis research in it. Now, I never finished my thesis, and never published my results because private industry came courting and I haven't mentioned this on a CV in at least 15 years. Some of my closest and geekiest friends understand it, though, so who knows.

Next two questions were about some technology I emailed some /.ers about through my published gmail account. Cool again, for I had recently posted on those topics on /., then received follow up emails from like minded people which led to long email conversations that ranged into other themes. Both questions were almost exactly lifted from those email threads, but not from the /. postings. I had the first indications that my Clark Kent identity and my AntiCypher identity had been compromised. I know of only two close friends who know both, and neither are the types to let on, or really care.

The next question was straight from a forum where I've never used my real name, or any alias except for a gmail account that was linked through an invite at some point. Since I long ago made a conscious decision to never be professionally associated with that forum, and took extreme precautions to avoid posting from traceable IP addresses and the like. I kind of stammered through a half-assed response about knowing very little on the subject. At that point I suddenly realised that something wasn't right.

The rest of the interview alternated between topics on my CV and archaic systems I haven't admitted to knowing in a long time. Clearly the first interviewers from Google had access to information about my early career and life back to childhood. It was exactly like sitting a government security clearance interview, they already had the information, the interview was just to confirm you and your past were in agreement. I knew all the answers, because the first interviews were obviously running from a script that I could have written.

Later interviewers just wanted to know really detailed technical things that ranged all over and some of it I had to admit I didn't know. One interview lasted about 5 minutes, the guy knew I wrote some programs about 20 years ago, so he started asking questions as if I were still actively coding. When I told him I no longer write code, he wondered why I had applied for a job as a programmer, but then figured out I was being recruited for other things and politely ended the interview.

the AC

They don't reply to applications

[Anonymous Coward]

I have been job hunting in the US and the thing that has stuck me most is the cavalier rudness of recruiters, including those at Google.

When I applied for a job in the UK my application went in at 11pm one evening and I received a phone call the next day at 9am. With US companies they never seem to bother to reply unless they want something.

Perhaps they don't realise the bad feeling this creates, but when I have gone out of the way to prepare an application, tailor my resume and cover letter and get references in order to offer my skills and exprience the *least* I expect is a polite thank you for my time. Otherwise perhaps when they look through their files to fill a vacancy in six months time I will be the one who does not bother to reply to them.

If you are from HR then your mindset should not be that you are giving out jobs like favours to be bestowed, your mindset should be that you are looking for talented people who you can persuade to bring onboard. Otherwise all you will end up with is persistant fools who can't get an offer elsewhere and instead keep on bothering you.

Re:They don't reply to applications

[Anonymous Coward]

Given the huge number of applications Google receive on a daily basis, it's no wonder they don't reply in a timely manner; if at all. Google seem to go for more active recruitment; I.e. they head-hunt for the important positions, instead of waiting for the Right Candidate to drop on their doormat.

Re:They don't reply to applications

[Anonymous Coward]

If you're as sensitive to rejection as your post suggests, you're almost certainly not going to prosper (let alone be happy) in the no-bullshit, no-praise zone that is Google.

Politeness in technical companies is a choice, not a requirement.

If you think this is harsh or needless, consider what this says about what is important to you vs. what is important to them. Consider that Google may have been doing you a favor.

To be sure, there are plenty of workplaces were people play nicey-nice games, avoid confrontation, and focus on employee "messaging" rather than substantive content of communication.

Such companies are really pleasant places at which to work, for most of the year. Then in the winter you get your annual review and you spend a quarter wondering why you got blindsided because "things seemed to be going so well."

Re:They don't reply to applications

[Anonymous Coward]

Politeness in technical companies is a choice, not a requirement.
<br><br>
Politeness is a requirement in every aspect of human endevour and those who don't understand that usually sabotage their ability to get things done. Mismanaging your stakeholders is not an effective strategy for sucess.

Re:They don't reply to applications

[Anonymous Coward]

All hail the continued pussification of people in our culture.

Seriously, not to be a dick here, but grow up. It's just business. You applied, they didn't need you, so they didn't respond. I'd agree with the GP if THEY got a hold of HIM and then rejected him, but HE initiated conversation, not the other way around.

Oh and parent? WAAAAAAAAAAAAAH someone was *MEEEEEAAANNN* to me! /gocry
GROW UP. Some people are mean and some people are polite. Hell, I'm BOTH depending on a lot of factors... It's not a requirement to be polite. The mean ones are usually the "sharks" who end up getting way farther than the idiots and overly-politically-correct retards who cry every time someone makes an off-color joke.

You people make me sick.
Grow some balls for christ sake. The world is a harsh place, deal with it.

Re:i'm first?

[Tickletaint]

Jeez, show some appreciation! After all, without a first poster, there wouldn't be a second.

I had an interview with Google a few weeks ago

[skurk]

A bit OT, but could be helpful to others applying for a job at Google:

I had an interview with Google a few weeks ago. I didn't really know what I was getting into, as I applied just for fun.

After the initial emails and phone calls, I was contacted by a local Google employee (developer) for a detailed phone interview. He wanted to ask me "some technical questions" I was told.

Great, shouldn't be a problem? I got ready for C/C++/UNIX specific questions.

He called and we did some minor chit-chat before beginning the interview. But, to my surprise, here's what he asked:

The first question:
"Imagine you have two marbles and a 100-story building. You are told that the marbles will break if they are dropped from a certain floor. Figure out a way, as effectivly as possible, how high you can drop the marbles before they break. Remember, it could be the 1st floor, it could be the 99th."

Second question:
"Let's say you have a computer with 2M RAM. This computer has a hard drive (with lots of free space) and a 100M file which you should sort. Let me know how you, as effectivly as possible, sort the file."

Third question:
"We take the computer from the previous question and replace the hard drive with a network adapter. You have no local storage but the RAM. You will receive one million eight-digit phone numbers through a TCP stream which you shall sort in RAM. You are now allowed to send any data before all the numbers have been sorted. How would you solve this?"

Needless to say, the interview didn't go very well and ended with him saying "Well.. I've heard enough. Buh-bye."

Re:I had an interview with Google a few weeks ago

[tomstdenis]

first question: Find the density of the marble, then calculuate the ... oh what do I know.

Second question: Radix sort on disk.

Third question: Binary weighted tree in memory.

BTW I hate job interviews like this. I did one for RIM (in like 2002 ish) and at one point after answering like 5 different "puzzles" I turned around and asked the interview "here are two 1024-bit numbers, multiply them quickly." To which he replied "I'm asking the questions." I just got up and left. I don't want to work somewhere where I have to sit pretty and beg all the time just to get paid. I'm sure had I taken the job with RIM I'd be one of those "middle name" people (mass murderer) types eventually. Sure I have to please my boss by finishing my work, but I certainly don't kiss ass.

Next time you have an interview like that, just stump the interviewer, see how they like pressure. :-)

In all honesty, if you don't have prior job experience and/or a portfolio of projects, they can't really tell what you're capable of anyways. High pressure interview questions do not reflect the job scenario in the slightest.

Tom

Re:I had an interview with Google a few weeks ago

[glwtta]

Needless to say, the interview didn't go very well and ended with him saying "Well.. I've heard enough. Buh-bye."

I actually don't see why it's "needless to say" how it went from there - did you just find the questions too wanky? (but then, I hear lots of large companies rely on even wankier questions).

The first one is annoyingly vague (what the hell does "effective" even mean in this context?), but the second two are straight out of the second chapter of any algorithms book (ie "Sorting"); from the "virtually never used" section.

Is this really all they asked you, or is that just how far the interview went?

Re:I had an interview with Google a few weeks ago

[ahxcjb]

"Imagine you have two marbles and a 100-story building. You are told that the marbles will break if they are dropped from a certain floor. Figure out a way, as effectivly as possible, how high you can drop the marbles before they break. Remember, it could be the 1st floor, it could be the 99th."

Go up in 3's. So, if you get to floor 12 and no marble has broken - go to 15, if it then breaks, go to 14. If that breaks, then you know floor 13 is the answer. And so on..

--

http://www.cjbuckley.net/

Re:I had an interview with Google a few weeks ago

[BiggerIsBetter]

first question: Find the density of the marble, then calculuate the ... oh what do I know.

Here's one possibility:

With the first marble, drop it from floor one, then ascend, doubling the floor each time. When it breaks (unless it's the first floor or the top floor), start with the second marble, working up sequentially from the last known good floor. Is that an elevator sort, or something?

Re:I had an interview with Google a few weeks ago

[djce]

I could be wrong, but 1 million 8-digit (assuming decimal digits) numbers takes at least 3.3 megabytes of storage, before you even start trying to sort anything. So kinda hard to see how you can do that in 2 meg of memory ...

Re:I had an interview with Google a few weeks ago

[cheekymunky]

But how would you be certain whether the 13th floor was the last floor the marbles could be dropped from without breaking, or the first floor at which the marbles broke?

Re:I had an interview with Google a few weeks ago

[ps236]

Woah! You had to answer those questions on the phone whilst he was talking to you?

Unless this is the sort of thing you've been doing before, it's unlikely you'd be able to do that - I'd have expected you'd need some time to work out the answers. I know I would, and I've been programming for 25+ years.

The first question is quite easy to answer -ish. I guess they meant 'as efficiently as possible' - not as 'effectively as possible' (in which case, as long as you got the right answer you'd meet the requirements). To get the basic concept isn't hard, but to get it "as efficiently as possible" you'd need some thought, which would be hard on the phone. (You go up in steps (eg 10 floors at a time) until the first marble breaks, then go back a step and go up one floor at a time until the second marble breaks - the "hard" bit is knowing what size steps to use for the first part to be most efficient)

BTW - the second question there was a bit meaningless - how can you 'sort a 100MB file'? Do they want the file in byte order (all the 0 bytes first, then all the 1 bytes) If so, then you could do that with 256 bytes of data RAM... Maybe they want it in BIT order - that would only need 8 bytes :) If this isn't what they want, then it would help to know WHAT you are sorting - eg a radix sort could be good here, but it might depend on the type of data

Were you allowed to ask how much memory was taken up by the OS, network stack and what programming language you were using to guess how much memory was taken up by the program?

For the 3rd question I'd have difficulty. AFAICS you'd have to use some form of compression to be able to do it (you have to hold 8M characters in 2M RAM - you could convert the phone numbers to 'real' numbers, but that'd still be 4MB in 2MB RAM). I reckon I'd be able to do it, but I'd guess it would take at least several hours to work out the nitty gritty - which sounds dumb for a phone interview.. (There's a cool way I can think of that would sort up to 10 million 7 digit numbers in 2MB RAM - but it would need 12MB to sort any number of 8 digit numbers - and this would rely on the numbers being unique, which isn't specified)

Could I offer to donate £50 from my first pay cheque to buy Google some more RAM? ;)

Re:I had an interview with Google a few weeks ago

[ps236]

(Sorry, didn't mean 256 bytes, I meant 2048 bytes)

Re:I had an interview with Google a few weeks ago

[Speare]

First question: boolean search. You'll need up to seven marbles.

Re:I had an interview with Google a few weeks ago

[Anonymous Coward]

The answer I see for the first question is a good ol' binary search. Throw from the 50th, if it doesn't break, throw from the 75th and so on. The other two you hit the nail in the head.

A friend of mine is going thru this process right now, and from what he told me, the phone interviews weren't so riddle-ish, but nonetheless, they required deep knowledge of various Comp. Sci. disciplines (which he, fortunately, has). One question went like "describe what happens when type 'ftp google.com' in a linux shell such as bash". They want every actual step, like bash forking for the tcp program, the tcp invoking kernel network services, querying dns, routing and etc.

Another interesting question they asked was: "given a computer with limitless RAM, describe the most efficient way to count how many bits of a 10000 bytes string are 1".

<tinfoil>Posting anonymously, just in case google is watching my friend's friends for subversive behaviour</tinfoil>

Re:I had an interview with Google a few weeks ago

[PeeAitchPee]

Second question: "Let's say you have a computer with 2M RAM. This computer has a hard drive (with lots of free space) and a 100M file which you should sort. Let me know how you, as effectivly as possible, sort the file."

Easy. Plug a 1 GB SDRAM in that puppy. Isn't that a core part of Google's approach to scaling their search anyway (i.e., acres of commodity grey market boxes)?

Re:I had an interview with Google a few weeks ago

[Anonymous Coward]

I'll second this.

Within the first 2 minutes of my phone interview, I was asked to solve a simple story problem that hinged on recognizing the use of a logarithm on a very large number. I told the interviewer the (correct) answer as an equation, and was immediately challenged with the most absurd question I've ever experienced in an interview: "so...how would you calculate that?"

I've never been asked to be a human calculator in an interview before, so it took a few seconds to realize that I was actually being quizzed on my ability to do math in my head. I don't know why, but apparently, Google thinks that the ability to quickly mentally calculate the log of a large number correlates with developer skill.

Needless to say, I didn't impress my interviewer. I got all of the questions right, but I think it took me about ten minutes longer than the Google-mandated time, and I made a few stupid (nervous) mistakes along the way. The call ended abruptly; I haven't heard back.

From what I can tell, Google is making the same arrogant mistakes that Microsoft made when they were king of the technical hill: thinking that brain teasers and puzzle smarts are the only kind that matter to a product developer. There's a certain amount of arrogance inherent to the process, given the silliness of the questions -- if Google is hiring thousands of people a year, you know damn well that not all of them are smart. So what are they selecting?

Re:I had an interview with Google a few weeks ago

[Ihlosi]

Go up in 3's.

You could go up in 10s, which gives you a lower maximum number of drops (19, I think) than going up in 3s (30-something).

Re:I had an interview with Google a few weeks ago

[tomalpha]

I've been asked all of these questions at (fairly) recent interviews. They're definite favourites at City (of London) type institutions.

The first question can actually end up using a little calculus - you need to advance by square-root of the number of floors IIRC.

Two I can't remember my answer for, but think there were a couple of variations.

Three requires you to realise that the numbers are unique, within a finite range, and you have sufficient *bits* for a radix sort.

Re:I had an interview with Google a few weeks ago

[glwtta]

Third question: Binary weighted tree in memory.

If only it was 40,000,000 numbers and 6MB RAM - then it'd be count sort; but it's never count sort...

I wonder what they were getting at with the requirement that you can't send any data until you are done sorting - seems kind of implicit in the whole "sort the numbers" requirement.

Re:I had an interview with Google a few weeks ago

[Ihlosi]

The answer I see for the first question is a good ol' binary search. Throw from the 50th, if it doesn't break, throw from the 75th and so on. The other two you hit the nail in the head.

Ow. That gives you an awfully big number of tries (50 tries) in the worst case (49th floor). Going up in smaller increments (10 floors, for example) would give you a much lower maximum number of tries (19 tries).

Re:I had an interview with Google a few weeks ago

[ps236]

Eh? It would give you 7 tries wouldn't it?

50, 25, 37, 43, 46, 48, 49 (or similar)

Not that it matters - because you've only got 2 marbles. So, you can't test for a bigger number than the one you're looking for more than twice. If it was 49 you'd be OK, your marbles would break at 50 and 49. But, if 51 was the answer you'd be scuppered - your marbles would break at 50 and 75, and then what do you do?

The answer is to go up in steps, then when the first marble breaks go back a step and go up in ones.

The 'debate' is what size steps to use?

Re:I had an interview with Google a few weeks ago

[Anonymous Coward]

I think going up by 10s is the right answer. I've gotta go to work, so I can't demonstrate it at this time, tho. The maximum number of drops is 18, though -- the marbles are guaranteed to break on the 100th floor from the wording of the question, so don't drop them from there. ^_^

Re:I had an interview with Google a few weeks ago

[Ihlosi]

The 'debate' is what size steps to use?

I think some other poster answered that below - use the square root of the number of floors. I happened to pick 10 by dumb luck. :P

Re:I had an interview with Google a few weeks ago

[Anonymous Coward]

Why would you assume you couldn't use a calculator, or better yet, just type it into Google and let Google calculate it for you?

Trapped inside the box, are we? I wouldn't hire a linear thinker like you either.

Re:I had an interview with Google a few weeks ago

[glwtta]

BTW - the second question there was a bit meaningless - how can you 'sort a 100MB file'?

I think that was the whole point of these questions - get the general gist without getting bogged down in the details. In this case the reasonable assumption is that the files contains some kind of comparable records (what's most likely to happen in the real world), and the size is much larger than your RAM, so you know you have to go to disk, so you know it's some variant of radix sort.

There's a cool way I can think of that would sort up to 10 million 7 digit numbers in 2MB RAM - but it would need 12MB to sort any number of 8 digit numbers - and this would rely on the numbers being unique, which isn't specified

He said you only need to sort a million 8 digit numbers, so you are good. I would've said a trie, but really, a number of different trees would do the job; the possibility that they are non-unique didn't occur to me, but you could always tack on a leaf that stores the number of occurrences.

Re:I had an interview with Google a few weeks ago

[ps236]

> Three requires you to realise that the numbers are unique, within a finite range, and you have sufficient *bits* for a radix sort.

Do you? At the risk of looking dumb, how's that work then?

If they were 7 digit numbers it's trivial, but I can't see it with 8 digit numbers. I need 100,000,000 bits for that, and I've only got 16,000,000 bits. Unless there's a trick I can't think of at the moment.

(PS - it doesn't say the numbers were unique. It's quite plausible for a set of phone numbers to contain duplicates, but that may just have been bad memory by the poster, or bad wording by the interviewer)

Re:I had an interview with Google a few weeks ago

[Ihlosi]

Why would you assume you couldn't use a calculator,

Maybe you want to run the algorithm on an 8-bit microcontroller that's slow as heck when you're using floating point (and the floating point library will eat 85% of the code memory space) ?

True, not likely when you're working at google, but it might well pop up if you're working with small processors.

Re:I had an interview with Google a few weeks ago

[Councilor Hart]

The lowest maximum is 20.
The large step size being x and the smallest 1, you get a function like this:
y = x + (floors/x)
Where floors is the number of floor (duh).
If you plot this (try gnuplot) you get a minimum at 20 for 100 floors.
Fill in and solve gives you this
x^2 - 20*x +100 =0
The answer to this particular problem is 10.

Re:I had an interview with Google a few weeks ago

[khakipuce]

Stop being so literal and read the article. The point of the questions is not necessarily to get the correct answer, they are interested in your though processes.

Over the years I have had more than my fair share of jobs and many of them I got even though I failed to answer the technical questions. What I did was explain my thinking, even on multiple choice tests, I write my thinking along side. You are never ever going to have to solve the marble problem, but they want to know if you have heard of things like a binary search and more importantly how do you respond in situations that are "out of the box".

It aims to demonstrate problem solving, communication, breadth of knowledge. They do not want you to sit in silence for 5 minutes and then given them the right answer, they want you to explain ALL the ideas you have about how to solve the problem, and then the criteria you may use for selecting a solution from the available ideas. Arguing the toss about the number of marbles, the mass of the marbles, etc. is not going to get you anywhere.

Re:I had an interview with Google a few weeks ago

[CrazyTalk]

Great first question - and a chance for candidates to show off their knowledge of search algorithms. Do you just try dropping from the first floor and continue linearaly until you find the floor that the marble breaks? Do you do every other floor? Implement some kind of binary search or more sophisticated technique? And the fact that you only have two marbles means that you are only allowed one "Failure" of the marble drop to make a determination. I bet there are plenty of hard-core programmers that might not get this because they can't make the leap from the dropping marbles problem (WTF?) to computer search algorithms - and that is likley the kind of out-of-box (I can't believe I used that phrase in a sentance) thinking google is looking for.

Re:I had an interview with Google a few weeks ago

[BlueTrin]

I hope you are not a programmer.

Re:I had an interview with Google a few weeks ago

[Splab]

No, doing it with divide and conquer as the gp suggest you need 7 tries. But the original problem states two marbels, so I would probably try divide n conquer with first marble till it breaks, then do a linear search for where the second one breaks (somewhat like B+ trees).

Re:I had an interview with Google a few weeks ago

[Anonymous Coward]

You have two. They've already told you that. You've just managed to fail the interview at the very first question.

Re:I had an interview with Google a few weeks ago

[Anonymous Coward]

hmm I was the GGP and didn't notice the "only two marbles" detail. In this case, the 10 floors at a time thingie is the solution.
Yeah, guess I wouldn't be hired by them. bummers.

Re:I had an interview with Google a few weeks ago

[tomalpha]

You are quite right, it would have to be a 7 digit number. Teach me not to read the question properly. This perhaps is why I do not work for Google.

Re:I had an interview with Google a few weeks ago

[ps236]

No, my idea only works with (any number of unique) 7 digit numbers - ie there are less than 16 million possible numbers - basically you build a bitmap of all the used numbers, and they're automatically sorted with zero effort. It won't work with any number of arbitrary 8 digit numbers, as that needs 100,000,000 bits to be available - approx 12MB.

I can't see how a tree could be used to solve the problem. A tree node typically consists of 2 pointers, and a lump of data. If you have 1 million nodes then you have only 2 bytes per node. Given there's 1 million nodes, your pointers need to be 20 bits, so each node needs 5 bytes just for the pointers, plus some data saying WHAT phone number this node is. I can't see that working.

OK, I might be missing something, but I don't know what.

AFAICS A better way would be just to use a simple insert sort (not quick, but it uses far less memory), and it may be doable by using some rudimentary form of compression, but it would need a bit of design work.

Re:I had an interview with Google a few weeks ago

[skurk]

The answer I see for the first question is a good ol' binary search. Throw from the 50th, if it doesn't break, throw from the 75th and so on. The other two you hit the nail in the head.

So let's say you drop the first marble from the 50th floor and it breaks. Then you drop the second marble from the 25th floor and it breaks too.

Then what?

Re:I had an interview with Google a few weeks ago

[Anonymous Coward]

"Maybe you want to run the algorithm on an 8-bit microcontroller that's slow as heck when you're using floating point (and the floating point library will eat 85% of the code memory space) ?"

You're making the assumption that the problem was related to programming. It wasn't; the guy just wanted me to estimate the log of a large number in my head; he made that point perfectly clear.

Re:I had an interview with Google a few weeks ago

[Anonymous Coward]

The first question is quite easy to answer -ish. I guess they meant 'as efficiently as possible' - not as 'effectively as possible' (in which case, as long as you got the right answer you'd meet the requirements). To get the basic concept isn't hard, but to get it "as efficiently as possible" you'd need some thought, which would be hard on the phone. (You go up in steps (eg 10 floors at a time) until the first marble breaks, then go back a step and go up one floor at a time until the second marble breaks - the "hard" bit is knowing what size steps to use for the first part to be most efficient)

The way you put it (having more than 2 marbles), it sounds more like a sorting problem, in which case i guess quick sort would give the least tries O(logn). Throw it off the 50th floor, if it breaks, try the 25th, if not the 38th etc... But the way I understood it was that you have only 2 marbles..

Re:I had an interview with Google a few weeks ago

[Electrum]

Three requires you to realise that the numbers are unique, within a finite range, and you have sufficient *bits* for a radix sort.

If the numbers are unique, you don't need to sort at all. Use a bit vector to store them and print in order.

Re:I had an interview with Google a few weeks ago

[skurk]

Woah! You had to answer those questions on the phone whilst he was talking to you?

Yup, on the phone. I have 22+ years of programming on my back, and I applied for a position named "system developer". If I knew they were looking for some search engine optimizing guru, I wouldn't even bother contacting them in the first place.

BTW - the second question there was a bit meaningless - how can you 'sort a 100MB file'? Do they want the file in byte order (..)

Ah, yes. Sorry, I thought that was obvious.

IIRC, the correct answers (according to Google) were:

1st question: Start on the 14th floor. If it breaks, start with the second marble on the 1st floor and increase until it breaks. If it doesn't, go to the 14+13th floor, then 14+13+12th, etc. That gives you a maximum of 14 attempts.

2nd question: Split the file into 2M segments on disk, sort them (for example with quicksort) then use mergesort to get everything back together.

3rd question: Sort everything in RAM using bit vectors.

If you disagree with the answers, contact Google. :-)

Re:I had an interview with Google a few weeks ago

[haihainicknameused]

then you magically turn the interviewer guy into a marble and throw him from the 50th floor

Re:I had an interview with Google a few weeks ago

[Anonymous Coward]

BTW I hate job interviews like this. I did one for RIM ... Sure I have to please my boss by finishing my work, but I certainly don't kiss ass.

So why did you apply for a RIM-job in the first place?

Re:I had an interview with Google a few weeks ago

[kanweg]

You guys are all smarter than I am. As to step size I may contribute. Given that the marble falls by 0.5 m v^2, the step size should be perhaps smaller at the beginning than at the end.

Bert

Re:I had an interview with Google a few weeks ago

[Anonymous Coward]

About the third question...
hint: The phone numbers technically sort themselves.
The phone number value as an integer must be used as an index in a bitfield.
text xxxxxxxx -> integer N -> set bit to 1 at index N
You can them spit the received and ordered phone numbers by scanning the 1's in the bit field.
Simple & useless.

Re:I had an interview with Google a few weeks ago

[appelsiini]

Wrong. It does. I've reviewed several guys for a high demand positions, who thought they were good but didn't have slightest idea. I think those questions can be pretty much answered by anybody who has B.Sc or M.Sc in computer science. In my area it's common practice you won't get even in to the interview without M.Sc degree. Usually it so waste of time hiring "just some nerd", who can do good thing in one place, but can't even document what he's doing nor code by design. Army service is a definite plus, cause it displays one can stand some pressure in his/hers life. Plus being an officer in army also is good background for being a team leader or manager position. I think Google or any sane company don't need wannabes, loners, sociopaths, trainees or talk-a-lot's, who make much noise but no real know-how. Heavy filtering is good, and if you really know the things, you won't take a pressure about it. People who get things done, talk less and do more.

Re:I had an interview with Google a few weeks ago

[locofungus]

Woah! You had to answer those questions on the phone whilst he was talking to you?

Unless this is the sort of thing you've been doing before, it's unlikely you'd be able to do that - I'd have expected you'd need some time to work out the answers. I know I would, and I've been programming for 25+ years.


Similar to the sorts of questions I've been asked at job interviews for other companies. They're also the sorts of questions we pose to one another at the end of our team meetings.


The first question is quite easy to answer -ish. I guess they meant 'as efficiently as possible' - not as 'effectively as possible' (in which case, as long as you got the right answer you'd meet the requirements). To get the basic concept isn't hard, but to get it "as efficiently as possible" you'd need some thought, which would be hard on the phone. (You go up in steps (eg 10 floors at a time) until the first marble breaks, then go back a step and go up one floor at a time until the second marble breaks - the "hard" bit is knowing what size steps to use for the first part to be most efficient)


The first question is very vague and poorly structured but gives an excellent opportunity to mumble^Wtalk while your thinking.

"Well the obvious solution is to start on floor one dropping the marble and then climb the stairs to the next floor. The problem with this solution is that once you get high enough you will probably need to climb all the way down after each drop to see if the marble has broken - although we'd probably have lost it unless we have someone at the bottom so we can assume we don't need to climb down again.

If we only have stairs then this is quite likely to be the best solution. Any other solution is going to involve going back down again which is likely to make it slower. Going up two floors at a time might be faster because once the first marble breaks you'll only have to go down one floor to test that one and never have to reclimb. However, our time is still going to be dominated by the climbing.

If we have a lift then we need to reconsider. It will depend on how long it takes to call the lift. Riding the lift to the 50th floor and dropping the first marble and then working up one floor at a time either from here or the bottom will require climbing up to fifty flights with up to two waits for the lift.

Of course, we could prop the lift door open, then we'll never need to wait for it (although there's still the danger that it will decide it's going down when we want to go up).
So we could go up 10 floors (square root of number of floors). That would give us 19 drops (10 to floor 100 then 9 from 91 to 99) worst case. However we could also solve the problem for a building with 109 floors in the same number of drops. Going up 10 floors at a time to floor 50 and then 9 floors at a time to floor 95 gives us a worst case of 5 (drops to floor 50) +5 (drops to floor 95) +8 (drops from 87-94) =18

And I've just realised a problem with my very earliest assumption - you're going to have to go back down to collect the marble after two drops anyway. This means an optimum solution will probably have bigger steps at the bottom and smaller steps at the top. I'd need more information on things like lift speeds and need to run simulations to give a better answer than that."

(That was written exactly as I was thinking - an interviewer might pick up on the having to retrieve the marble after each drop (or two) or might allow me to continue my thoughts. If they did interrupt me early on I'd probably not get to the final paragraph above.)


For the 3rd question I'd have difficulty. AFAICS you'd have to use some form of compression to be able to do it (you have to hold 8M characters in 2M RAM - you could convert the phone numbers to 'real' numbers, but that'd still be 4MB in 2MB RAM). I reckon I'd be able to do it, but I'd guess it would take at least several hours to work out the nitty gritty - which sounds dumb for a phone interview.. (There's a

Re:I had an interview with Google a few weeks ago

[tomalpha]

I won't argue with your knowledge of sorting nomenclature. But I think that's what I said ;)

Re:I had an interview with Google a few weeks ago

[eric76]

With the proper assumption, you need only one marble.

Assume that the marbles rebound back to the same height from where they were dropped.

Start at the first floor.

Drop the marble. If it breaks, you are done. Otherwise, catch it on the rebound, go up one floor, and repeat.

They probably won't let you get by with such a simple assumption, though.

Re:I had an interview with Google a few weeks ago

[MikeBabcock]

Actually, for the marble, I'd drop it from a fairly 'sure to be safe' height like one story or even half a story. If it breaks, drop the other marble from some fraction of the height of the first marble. If it didn't break, I'd double it and try again (since if the marble doesn't break, you can use it again). If it breaks, drop the second marble from some (smallish) percentage of the distance between the last successful drop and the unsuccessful drop.

Its used in TCP/IP (exponential back-off) and it works quite well, although not perfectly.

Re:I had an interview with Google a few weeks ago

[chhamilton]

First question:
You've got 2 marbles, so the best you can do involves 2 * (sqrt(100)-1) possible tests. If you had n marbles, you could do O(n100^(1/n)). So, using the first marble, drop if from the 10th, 20th, 30th, etc floors until it breaks. Say it breaks at the 30th. With the second, start testing the 21st, 22nd, etc. At most you will require 18 tests and only the two marbles. (I'm assuming the marbles maintain their integrity after repeated drops.)

Second question:
Use an external memory sorting algorithm, of which the best reqires O(N/Blog[M/B](N/B)) IOs (M is the size of the internal memory, B is the size of a 'block' or single sector on the disk, N is the problem size). The last decade has seen the development of an entirely separate model of computation which counts disk accesses rather than clock cycles. All old problems are new again as algorithms are found that solve them optimally in this new paradigm. Certain problems (like sorting) have been solved so that they are simultaneously optimal from an IO and a clock cycle point of view. IO efficient sorting generally uses a merge sort. So, for this problem you would sort 2M of data at a time, and then merge as many of these chunks together as you could simultaneously (using the largest heap that would fit in the 2M, in this case you could easily merge all 50 sorted subchunks), then repeat. There's actually another model of computation called the 'cache oblivious model' which aims to build algorithms that are IO efficient across every level in the cache hierarchy of a modern computer (disk, disk cache, L2 cache, L1 cache). Again, there exists a sorting algorithm that is cache oblivious called a funnel sort. It also uses merge sorts, but the size of the merger at each level varies. Interesting stuff... (disclaimer, I am doing my PhD research on IO efficient and cache oblivious graph and computational geometry algorithms).

Third question:
(I'm assuming that should read "You are NOT allowed to send any data before all the numbers have been sorted")
There are 10^8 possible unique phone numbers. You could imagine using a large bit table to keep track of which values have been seen but this would require ~12MB of memory when we only have two. You could imagine 'run length' encoding such a table, where strings like '0000...1' are encoded as the number of preceding zeroes. Worst case scenario we could have up to 10^8-10^6 leading zeroes, requiring 27 bits to represent. So, we could encode the table using 3.2MB of memory. This is still too big. Go another level deep and use a variable length code to encode the run lengths. The worst case is still a 27 bit run length, so we'll require 5 bits to represent the number of bits required to represent the run length, followed by that number of bits actually encoding the length. Worst case scenario pushes all of the run lengths to the same size, in which case they are 10^8/10^6 = 100 bits long. This requires log[2](100) = 7 + 5 = 12 bits per encoded phone number, or 1.43MB of RAM. So, this'll fit, but its still pretty tight. This was just to see how hard it is to fit the data into the available space; while it does highlight a possible algorithmic approach its likely not going to be too efficient. Likely, using a radix tree over the phone numbers represented as 32 bit sequences (4 bits per digit) would be the best approach, although you'd have to be extremely frugal with your data structure to ensure it fits.

Re:I had an interview with Google a few weeks ago

[Paolone]

1: try a dychotomic search (binary search? sorry English is not my first language); if the marble crashes, work up from the bottom 1 floor at time. 2: bucket sort, then merge. 3: encode the 8 decimal digits in 27 bits. 27 * 10^6 /8/1024/1024= ~ 3.22 megabytes. Darn. Ok, without compressing the numbers and with no data on them I'm a bit stuck. We should get the entropy down to 16 bits/number. or do something else.

Re:I had an interview with Google a few weeks ago

[tomstdenis]

I strongly think that just having a degree or not should not be a show stopper. A lot of smart people I know don't have PhDs (and our regular submitters and published in first tier journals). That's why I made the portfolio comment. If you can see that someone is capable of not only developing a quality piece of OSS, but documenting, supporting, and maintaining it, that speaks volumes more than someone who merely went through the motions to get a degree.

Army service is hard to judge because we're afraid to talk down, for fear of being unpatriotic. Sure they're brave, but are they actually smart enough to work a comp.sci job? And not everyone who is discharged from service is for positive reasons. Not trying to talk smack [here I go ... see!] about service folk, as I have some in my family too. But I wouldn't hire someone just because they had service experience. It's what they actually did in the service that I'd want to know about.

Tom

Re:I had an interview with Google a few weeks ago

[Idbar]

What do you mean by 10? Start dropping a marble at the 10th floor? If it breaks what? You only have two marbles.

I would start dropping from the 2nd floor, if it breaks I use the reminder (one) on the first floor. Otherwise go to 4th, and so on.

Re:I had an interview with Google a few weeks ago

[LordNimon]

You can get away with two if you use a boolean and a linear search. That is, use the first marble in a boolean search, and then when it breaks, use the second marble in a linear search from the last known floor where it doesn't break. Although I think the other poster's idea of doubling the floor every time might be better for the first floor, but I'm not sure.

Re:I had an interview with Google a few weeks ago

[LordNimon]

Out of curiosity, do you have a degree in computer science? Because these questions sound like real-world examples of basic computer science concepts.

Re:I had an interview with Google a few weeks ago

[jmac1492]

You don't need to assume that it bounces. Go outside and pick it up, and then go up one floor.

Re:I had an interview with Google a few weeks ago

[Ihlosi]

What do you mean by 10? Start dropping a marble at the 10th floor? If it breaks what? You only have two marbles.

If it breaks, you search 1-9 with the other marble, starting at 1 of course. If it breaks at 40, you search 31-40, and so on. (There's an even better solution somewhere in the thread. Going up by 10 yields 10.5 tries average, 19 tries maximum, while the best solution yields 9.91 tries average, 14 maximum). I would start dropping from the 2nd floor, if it breaks I use the reminder (one) on the first floor. Otherwise go to 4th, and so on.

That would give you around 25 tries on average and 51 maximum.

Re:I had an interview with Google a few weeks ago

[Saberwind]

(You go up in steps (eg 10 floors at a time) until the first marble breaks, then go back a step and go up one floor at a time until the second marble breaks - the "hard" bit is knowing what size steps to use for the first part to be most efficient)

Well, I think the first question you must ask the interviewer is: How do you define efficiency?

If they want the fastest solution, use a binary search. Start at the 50th floor, then go to either the 25th or 75th, etc.

If speed is not an issue (e.g. they want to minimize the number of broken marbles, but are willing to sacrifice five for testing), then another approach can be taken.

Obviously, for the third question, if no phone number appears more than once, then you can use a simple array of bits, and turn the bits on when the corresponding phone numbers are encountered. Then just loop through the array and send the index of each set bit.

Re:I had an interview with Google a few weeks ago

[markov_chain]

How do you figure that ability to do mental math is not correlated with software development aptitude? From experience I'd say it's the opposite.

Re:I had an interview with Google a few weeks ago

[Viv]

1st question: Start on the 14th floor. If it breaks, start with the second marble on the 1st floor and increase until it breaks. If it doesn't, go to the 14+13th floor, then 14+13+12th, etc. That gives you a maximum of 14 attempts. Of course, Google would be wrong about that. You don't have to test above the floor at which terminal velocity can be reached.

Do some back of the envelope calculations, take into account that the terminal velocity of a marble-sized hailstone is 45 ft/s, and you'll estimate that terminal velocity occurs within 15 floors.

Drop it at 7, and do a linear search on either side of that depending on whether it breaks or not. That yields less than 14.

Re:I had an interview with Google a few weeks ago

[lessthanjakejohn]

Find the terminal velocity of off the marble and then you could cut 75+ floors

Re:I had an interview with Google a few weeks ago

[Viv]

Also, here's the other fun thing:

You can't really know with just two marbles unless you get lucky and nail it on the first try. Each time you drop the marble, it's going to be stressed by the impact, and as you approach the height at which it would break from one drop, you've accumulated damage from previous drops.

In such a case, the marble will likely break before the perfect height due to the accumulated damage.

Re:I had an interview with Google a few weeks ago

[eric76]

I had the same idea about using a bit map of the search space, but it was obvious that there wasn't enough memory for that approach.

I suspect that what would it would take to fit the one million telephone numbers into 2 MB of memory would be to store the first number and then the offset to the next number, ..., and insert each item into memory as it comes in. It would be slow but could be speeded up by breaking it into groups.

Thus, if the first three numbers were 00000005, 00000088, 00001088, you would store them as 00000005, 83, 1000. Thus, 4 bytes, 1 byte, and 2 bytes. I would imagine that using 2 byte offsets would be best. If there was a gap between two consecutive numbers greater than 2 bytes, put in a gap value of 0 to indicate the end of one sequence and the beginning of another sequence.

That is, if the first six numbers were 00000005, 00000088, 00001088, 10001088, 10001100, 10001123, the stored sequence would be 00000005, 83, 1000, 0, 10001088, 12, 23 and would require 18 bytes instead of 24 bytes to store the 6 numbers individually.

If one could do the entire one million numbers without any big gaps of 65,536 or greater, the total space would be 2,000,002 bytes. Each gap of 65,536 or more would add 4 more bytes to the length -- two for the 0 to indicate a new sequence and 4 to store the entire number.

So let's assume that 2M bytes = 2^11 = 2,097,152 bytes. That would give us some breathing space, but not enough for a worst case since we could only handle 24,287 gaps of 65,536 or more between consecutive numbers.

Re:I had an interview with Google a few weeks ago

[tomstdenis]

hahahaha you said rimjob.... shut up. I didn't apply for it. An employee found me and was tasked to interview me during their trip to Ottawa. I didn't even score a free lunch out of the deal.

It might have been a decent place to work if it wasn't for the "OMG I'M IMPRESSED WITH MYSELF" attitude I got off the guy. I mean, he wrote the first blackberry calculator, the guy is a genius [and yes, he bragged about it during the interview].

Tom

Re:I had an interview with Google a few weeks ago

[rodp]

Few years ago, this type of interviewing would seem pointless to me, as well. However, since then, I have become a team leader at my company and had several opportunities to interview candidates for positions in our development team. Managing developers has taught me that technical knowledge and years of experience in programming language X on platform Y, although important, is secondary to one simple property of a human individual: intelligence. I know it sounds unfair but I can say in all honesty: I don't worry too much if an experienced developer never coded in Ruby. He'll learn it in 3 days! What I worry about is whether his poor logic will cause our applications to run slowly or our projects to run late. That's what questions like these help me figure out at an interview.

BTW, the first question is interesting. I'd start by dropping one marble from the first floor, moving up 3 floors at a time, dropping the same marble and keeping one in reserve. Therefore, if a drop from the floor n was successful and a drop from the floor n+3 wasn't, I'd try the floor n+2 with the second marble. If it doesn't break, n+2 is the answer. If it does, it's n+1.

Re:I had an interview with Google a few weeks ago

[Dr. Photo]

For the 3rd question I'd have difficulty. AFAICS you'd have to use some form of compression to be able to do it (you have to hold 8M characters in 2M RAM - you could convert the phone numbers to 'real' numbers, but that'd still be 4MB in 2MB RAM)

Well, 10**7 -> 10,000,000, and 2 ** 24 -> 16,777,216, so you could hold even the largest 7-digit number in an unsigned 3-byte (24-bit) integer (fitting a million of them into ~2.9 MB), but not the 8-digit numbers mentioned in the parent post.

I'm assuming that we still (a) only have 2MB of RAM to work with, (b) the OS and programs themselves don't live in this region of working RAM, and (c) we don't want to have to figure out how to sort compressed numbers (unless that compression scheme happens to work by virtue of sorted ordering)...

Now, if all these numbers were equally distributed among any given starting digit, then we could have equally-sized regions of memory corresponding to that first digit (and leave it off of the actual integer in memory)... if we were to order them from 9 down to 0, then we'd only have to sort each of these subregions internally, as the regions themselves are already sorted.

Since we have no guarantee about the distribution of the numbers, however, we might start with 10 small regions of memory, each dedicated to a given starting digit, and expand them as necessary (moving any data out of the way as needed).

That'll shave off a digit and bring us down to the aforementioned ~2.9MB, but that's still more than we've got to work with. And, as we don't want to have to keep track of 23-bit integers (or however many digits we're shaving off), let's go to 16 bits. 2 ** 16 -> 65,536, 10 ** 4 -> 10,000. So we've got at least 4 digits to work with (9999), or if we're clever, any 5-digit suffix that's less than 65,536. We'll assume the worst case for now, and say that grants us 2-bytes per 4-digit suffix, but requires us to keep track of the other 4 digits in the form of 65,536 distinct memory regions (which, if the numbers are evenly spaced, would only allow 32 bytes, or 16 4-digit suffixes per region, but if they're evenly spaced, then that's okay).

That allows us to track the million phone numbers in exactly 2 million bytes, or ~1.9 MB, plus 2**16 24-bit integers to point to the addresses of each region (region size can be calculated on the fly by subtracting the address of the next region from the address of the current one), or 196,608 bytes... whoops, we can't have that, as 2 million bytes of data leaves us only 97,152 bytes to work with!

So let's see... if we have (2**16) regions (and we can't usefully force things to be byte-aligned... (2-byte-aligned is possible, but un-useful, as I'm trying my damndest not to have to deal with fractional-byte-length integers!)... well, there are (2**16) regions of memory, with a minimum size of 2 bytes each (henceforth we shall call 2 bytes a WORD). And each region contains a MAXIMUM of (2**16) unique WORDS (assume that we can merge duplicate entries in this sort). So any region would have a maximum address offset of (2**16) WORDS from the previous region.

So we can store the addresses as 16-bit offsets from the previous region (maybe adding 1 to each number, as we want a range of 1-65,536, not 0-65,535, although if we're only using up to 4 digits of each number, it doesn't matter), for 2 * 65,536 bytes -> 131,072 bytes, which is still 33,920 bytes more than we've got!

But wait! If each region had even 257 unique numbers, there would only be ~3,892 regions: So we can store 3,892 * 4 bytes of special pointers (2 bytes to identify the region number, 2 bytes to identify the offset from its predecessor region), and 65,536 bytes of (offset-1) pointers for small regions. Looking up a region's true address involves (1) crawling the special pointers and seeing if the region is mentioned there; if so, grab the offset; if not, (2) look for its (offset - 1) in the small-regions offset array. Rep

Re:I had an interview with Google a few weeks ago

[ps236]

I'd just come up with the delta idea which I was going to write as another response.

Anyway, I don't think you'd need to worry about only being able to handle 24287 gaps of 65536 or more. If you have 1526 gaps of 65536 you've run out of 8 digit numbers. So, your idea is OK, AFAICS.

You could be more efficient by having variable length encoding for the deltas (similar to UTF8 encoding, but more efficient) - I reckon you could store the data in (worst case) about 1.7MB if you did that (773437 deltas of 129 needing 2 bytes, the rest deltas of 1)

Re:I had an interview with Google a few weeks ago

[poot_rootbeer]

I'd have expected you'd need some time to work out the answers.

That's the point exactly. The interviewer doesn't want to hear an immediate response of "oh, I'd use a radix sort". They want to hear you talk out your problem-solving process in real time, to see how close to their optimal solution you get in ten minutes' time and what ideas you might have for improving your first-pass solution if you had had more time.

No doubt it's a grueling process, and many of the people they interview don't possess the demeanor or the algorithmic brilliance to do well in such a scenario. But if they're finding engineers they want to hire using the system, I guess it must be working for them.

Re:I had an interview with Google a few weeks ago

[AndersOSU]

Strangest question I've ever got: "How would you determine How much wood would a woodchuck chuck if a woodchuck could chuck wood?"

I'm a mechanical engineer, so I gave some answer about measuring hardness and whatnot. The interview told me the last guy wanted to put strain gauges on the woodchucks teeth, I got the impression he wasn't getting called back due to ethical concerns...

Re:I had an interview with Google a few weeks ago

[Anonymous Coward]

Better, but still not optimal. I'm assuming you want to minimize the worst case (though I think mine also has better average case).
10 floors at a time has a worst case of 19 drops when the answer is floor 99.
Instead, the first marble should use a larger step size at the bottom and a smaller step size at the top, such that (number of drops so far) + (step size) is constant. The sequence is then something like 14,27,39,50,60,69,77,84,90,95 which gives a worst case of 14 drops.

Re:I had an interview with Google a few weeks ago

[seth_hartbecke]

They told you the correct answers! How very nice of them.

After 3 such phone calls, and a plane trip to one of their offices so they could grill me with such questions for 6+ hours all the more I got was 'we've decided to halt the interview process.' When I attempted to ask them why (really honstely so I could improve whatever skilset they felt I didn't have) I got no response.

Found it to be a bit on the rude side.

Re:I had an interview with Google a few weeks ago

[pmc]

If y = x + (n/x) then dy/dx = 1 -n/x^2

As we know it is a extrema then dy/dx= 0 therefore n/x^2 = 1, => n = x^2, => x = n^(1/2).

Which someone else said was the answer somewhere else.

Now, the problem with m marbles and f floors....

Re:I had an interview with Google a few weeks ago

[Anonymous Coward]

you take the derivative of the following 100/n + (n-1) where n is the interval between floors. This will give you the graph where you can determine the lowest point (which is the most efficient interval to test at).

For example, if n = 3, you drop the first marble every 3 stories, then when it breaks you go back down to the floor right above the last successful test and go up 1 floor at a time until the second marble breaks. Efficiency in this case is limiting the trips up and down the stairs.

IIRC the answer is 10 or 11, after that it starts to go back up.

Re:I had an interview with Google a few weeks ago

[19061969]

I know this is a tremendously bland answer, but I would buy a bag of my own marbles (they don't cost much) and take some exercise dropping one out of each window as I ascend.

it's actually quite effective: I get lots of exercise, the challenge of climbing to the top of a tall building without a lift, a lovely view when I get to the top, and a reliable answer without having to think or worry too much. Plus, I give the questioner their original two marbles back intact. Magic, see?

Unimpressive for a computer scientist, but then I'm a psychologist who enjoys exercise and challenges.

Actually I wouldn't drop any out. Imagine the damages in court if a marble hit someone?

Re:I had an interview with Google a few weeks ago

[Lemmeoutada Collecti]

Why not use a Huffman coding for the numbers, since the limit of the digits being 0-9 only has 100 possible forms, out of 256 per byte. That would allow a rudection of the data storage for whole numbers to at worst 7/8 (since 100d=64h=7 bits) The lookup table would require 100bytes, so for that to be useful you would have to store >50 of the complete numbers. Of course, given 8 million, the probability is high that more than 50 complete numbers would need storing. The lookup could be precalculated and is a one time cost, and an O(1) lookup function since the two digit decimal number is a lookup offset into the table.

Re:I had an interview with Google a few weeks ago

[Creepy Crawler]

I was thinking something a bit different about the marble problem (I love logic puzzles).

1. Drop marble A on 1'st floor. Also drop marble B at 10'th floor.
2. If marble A breaks, answer is floor 1. If ONLY marble 10 breaks, the floor is from 2 to 10. Test with remaining good marble.
3. If neither breaks, switch marble tests to 11 and 20.
4. Retest # 2 but in appropiate tested floors.

If floor 99 was the target, my test would only take 18 rounds (or 28 total marble drops). Your method of go up by 3, would take 35 tests.

I've yet to get even a bachelors degree (and Im studying for chemistry at that).

Re:I had an interview with Google a few weeks ago

[Nevyn]

first question: Find the density of the marble, then calculuate the ... oh what do I know.

:). My first guess was: try every tenth floor with the first marble, then every floor with the second. Which I'm pretty sure isn't the answer they would want.

Second question: Radix sort on disk.

I had assumed what they wanted with this was N different sorts of RAM size, followed by a merge sort of N buckets. But maybe I'm being too practical, and you're right (I admit I had to look on Wikipedia to remember what Radix sort was, and I have no idea if it's better than my simple merge sort solution :).

Third question: Binary weighted tree in memory.

This one confused me, 2MB RAM, no other storage and 1 million 8 digit phone numbers ... my answer == by more RAM. I guess you are supposed to "know" there is a way to reduce 8 digits into 2 bytes? (assuming that the OS and all your code fit into ROM, and take zero RAM ... or something magic like that) ... or assume there is magic swap? ... or just something else I have no idea of.

Summary: I shouldn't apply to work for Google :).

Re:I had an interview with Google a few weeks ago

[eric76]

Except that a Huffman coding would end up making the sort more difficult. It's much easier by keeping things on nice neat byte boundaries.

I assume that each telephone number would be inserted as it arrived just to simplify the sort a bit.

So you'd receive a telephone number, calculate where it goes into the table, decide whether you have a big gap requiring 6 bytes to insert (2 bytes for the zero offset (used as a flag) plus the entire number) or just a small offset that fits in 2 bytes, shift the rest of the table by that many bytes, insert the number, and adjust the next number. One might even shift back 2 bytes if the new number fell in what had been a gap of 65,536 or greater and resulted in two smaller offsets.

Of course, if this routine was to be used many, many times, one would want to be more efficient. For example, one could use the extra space that won't be needed to store the encoded list of numbers to do some things in small steps and move back into the proper position in the array. For example, one might add the numbers as they come in into a smaller list and then merge the list into the bigger list.

Re:I had an interview with Google a few weeks ago

[IndependentVik]

You've come the closest so far. Yes, you go up in steps, but the trick is that you decrease the size of the step each time you go up so that the worst case for each step remains constant. The worst case would be 14 drops. I'm disclaiming here that I didn't think this answer up myself; I'd heard the question and numerous answers myself sometime back because I was researching precisely these kind of (stupid) brain teasers in my quest to get a job.

Drop the first orb from floors 14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99, 100... (ie, move up 14 then 13 floors, then 12, etc) until it breaks (or doesn't at 100). Call the first floor at which it breaks n and the previous tested floor n'. Then try the intervening floors (n'+1 .. n'-1) with the other orb.

Worst case is if correct floor is 13,14,26,27, etc which require m drops with the first orb and 14-m drops with the second.

If you map it all out, you'll see that it holds together. I have yet to see a better answer, but would love for someone on /. to find one :)

Re:I had an interview with Google a few weeks ago

[flooey]

That's the point exactly. The interviewer doesn't want to hear an immediate response of "oh, I'd use a radix sort". They want to hear you talk out your problem-solving process in real time, to see how close to their optimal solution you get in ten minutes' time and what ideas you might have for improving your first-pass solution if you had had more time.

Yeah, that's exactly what they're looking for, I think. When I was phone interviewed by Google, the interviewer asked me the majority finding problem, which I hadn't encountered before. I iterated through a few solutions but never came up with a solution that was better than O(n log n). I still got called back for an on site interview.

Re:I had an interview with Google a few weeks ago

[rodp]

Good challenge. BTW, you don't need 18 rounds, you need 17 because there's no need to check the floor 99 after you've checked 98. However, I believe you missed one important issue. In order for the solution to be efficient, it's not important how many rounds you do but how many floors you have to walk up and down. For example, if the right floor is 99, with your solution you'd have to do 17 rounds but walk up and down 1215 floors. With my solution, if I used both marbles (drop first, go up 3 floors, drop second, go down to pick them up), I'd do 18 rounds but walk up and down 983 floors. The difference gets more obvious in the lower floors. For example, if the floor 9 was the right one, you'd do 8 rounds and walk 45 floors, while I'd do just 3 rounds and walk 23 floors, etc.

Re:I had an interview with Google a few weeks ago

[Lonath]

With the first marble, drop it from floor one, then ascend, doubling the floor each time. When it breaks (unless it's the first floor or the top floor), start with the second marble, working up sequentially from the last known good floor. Is that an elevator sort, or something?

I like this question. A lot of these "thinky" interview questions are bad, but this one has a subtle point that I like since it's about doing a complexity analysis on your algorithm.

The idea is you want to use the first marble to skip floors till you get above the breaking point, then go up floors 1 by 1 with the second marble from the last safe floor until you find where it breaks. Let B denote the breaking floor.

It's a "computer problem". What do you do with computer problems when you have to skip numbers? You take powers of 2. So you do this taking powers of 2 and then you find the breaking point with the first marble. Then you start going up 1 by 1 with the second marble, right?

BUT. How many floors are between 2^(N-1) and 2^M? 2^(N-1). This means the 1 by 1 test from the second marble is O(B), which is no better than the naive algorithm of just going up 1 floor at a time with the first marble. The subtle point is that you have to do a complexity analysis on your solution to realize that there's a tradeoff between the number of drops with the first marble and the number of drops with the second marble. This means that we need to shrink the gap size from the first marble so that the number of 1 by 1 drops with the second marble.

The next obvious choice is to take N^2 instead of 2^N. And what we find here is that the first marble will break just at or above B, which means you've used O(sqrt(B)) drops to get to that point. (So if B=50, you drop at 49 and it's ok, so you drop at 64 and it breaks, but you've only done 8 drops...1,4,9,16,25,36,49,64.)

Then, what is the difference between (N-1)^2 and N^2? It's 2N-1. That means if the marble broke on floor N^2, you need to do at most O(N) 1 by 1 drops to get to the breaking floor. But remember that N is O(sqrt(B)) so your whole algorithm is O(sqrt(B))+O(sqrt(B)) drops which is O(sqrt(B)). And I guess you could play with constants to get a better result, but changing the squares formula won't matter because there's a tradeoff between the complexity of the two halves of the problem, so if you decrease one, you will have to increase the other.

Re:I had an interview with Google a few weeks ago

[Lonath]

Ah I see someone below has the correct answer for this one. You start with larger gapsizes and decrease them. That works better when you do know the upper limit on the height of the building.

Re:I had an interview with Google a few weeks ago

[Daverd]

This approach is nearly identical to the Slow Start algorithm used in TCP congestion control.

Re:I had an interview with Google a few weeks ago

[ps236]

However, your algorithm is wrong...

For instance, you drop a marble from floor 10, it's OK

So, you drop a marble from floor 13, it breaks

Now, according to your algorithm, you drop a marble from floor 12. Let's say this breaks.

So, is floor 10 the last safe floor, or is floor 11 - you can't tell! The marble might have broken if you dropped it from floor 11 or it might not...

After the drop from floor 13 has failed, you MUST go down to try 11, then 12 in that order. Nothing else will work.

Re:I had an interview with Google a few weeks ago

[rk]

"Woah! You had to answer those questions on the phone whilst he was talking to you?"

That is interesting, isn't it?

What I find even more interesting is I have gone through the Google phone screen process twice (I've never applied, they love cold-calling me), and that exact same question has been asked of me as the second question, in the second phone screen, both times. So, I call BS on the "no set questions" comment from the article.

The second time that question was asked of me, I ended the phone screen then and there. Here I am thinking this a company that prides itself on creativity and imagination and I'm feeling more and more like someone's trying to recruit me to sell Amway by following a carefully crafted script.

They still write me every three or four months and ask me if I'd be interested in working for them. I just politely decline them now. I love their services, but I'm not comfortable with the idea of hitching my wagon to that particular star anymore.

Re:I had an interview with Google a few weeks ago

[Pastis]

Question about this majority finding problem:

If I got it right, with: A A A C C B B

the answer will be B, while I thought it should find A.

Re:I had an interview with Google a few weeks ago

[Anonymous Coward]

I find it really amazing that so many people are posting wrong answers for the first question. I thought it was very simple.

Take the square root of the number of floors, call it n, and throw the first marble from the floors that are multiples of n (in ascending order). When it breaks, use the second marble to work upwards one floor at a time starting from the highest floor from which you know it doesn't break.

I've taken some phone interviews with them and they just invited me to one of their european offices for more interviews. I think I'll soon be working with them. Wish me luck.

Re:I had an interview with Google a few weeks ago

[flooey]

Question about this majority finding problem:

If I got it right, with: A A A C C B B

the answer will be B, while I thought it should find A.

Well, the algorithm operates in two passes. The first pass finds a candidate for the majority element. The second pass confirms whether or not that element is actually the majority element.

For A A A C C B B, there isn't a majority element. So you're right that the candidate finding pass will return B, but then the second pass will discover that B holds only 2 out of 7 slots, and thus will return that the sequence has no majority element.

Re:I had an interview with Google a few weeks ago

[Anonymous Coward]

Ever heard of the GI Bill? At least during times when the US isn't in the middle of someone else's civil war a lot of smart people (myself included) spend a couple years in the service to make money for college. While I probably wouldn't work for a company that asks retarded questions about dropping marbles or how many breadboxes you can fit on a plane, I do consider myself "smart enough to work a comp.sci job". I've written (from scratch) a persistent object based database (with 10s of millions of objects in it currently) a Web Server, a GIS mapping system, Geocoding software etc., all of which get beat on in commercial use every day. I also don't think I would have any trouble being accepted to a PhD program at a mid-level university, but haven't gotten around to it (and several of the projects I've worked on would have made decent PhD research projects anyway). The bottom line is that there are some knuckleheads in the military, but there are quite a few smart people as well.

ajs

Re:I had an interview with Google a few weeks ago

[Anonymous Coward]

I strongly think that just having a degree or not should not be a show stopper. A lot of smart people I know don't have PhDs (and our regular submitters and published in first tier journals). That's why I made the portfolio comment. If you can see that someone is capable of not only developing a quality piece of OSS, but documenting, supporting, and maintaining it, that speaks volumes more than someone who merely went through the motions to get a degree.

Don't get me wrong: I agree with you in principle. A degree isn't necessarily the "be all and end all". But I'm about to get my Software Eng degree, and I can tell you, I have worked damned hard for it. So much that I have almost zero free time for any of the projects I'd like to do.

What I'd like to do is exactly what you describe: develop a (hopefully) quality piece of OSS, document it, support it maintain it. I'd like nothing more than this, but instead, I've been told that I need to spend 20 hours a week developing a piece of Microsoft-based software for some jerk, plus all the lectures and other subjects I have to attend, just so I can get a piece of paper which says I'm qualified.

Do I like this system? No, I hate it. But this is what I'm going through, and it's been four years of total slaughter. I think "doing an open source project" is the easy way out. Getting a SE degree certainly isn't "going through the motions".

(Yes, yes I am bitter).

Re:I had an interview with Google a few weeks ago

[paulgrant]

Jeez its simple:

#1 - binary search
#2 - merge sort/quick sort
#3 - a binary/heap sort (for insertation) with a travesal to spit back the results as needed
(assuming the data is meant to be processed as it is sent and queryable in sorted order at any point).

they just turned classic search algorithms (and hence search problems) into word problems.

Re:I had an interview with Google a few weeks ago

[Anonymous Coward]

I would guess that 3 is just impossible :)

Assume that none of the first 999999 numbers is equal to 0000000. Obviously
sorting algorithm has to read all 1M numbers before it outputs anything -
otherwise how could it know if first number to output is 00000000 or not?

So we need to store 999999 8-digit numbers in just 2M of memory. For every
possible first_999999_nonzero_numbers there must be unique encoding (state of
memory). With 2M of RAM there are only 8^2097152 encodings.

From mathematics, there are (10^8+10^6-3)! / (10^6-1)! possible 999999-multisubsets of {00000001, ... ,99999999}
(10^8+10^6-3)! / (10^6-1)! >= (10^8)^(10^6-1) / (10^6)^(10^6-1) = 100^(10^6-1) =
= 25^3999996

Unfortunately 25^3999996 > 8^2097152, so there is no way to assign every
unique memory image to every possible input.

Any flaws?

Re:I had an interview with Google a few weeks ago

[igny]

Doubling up is soooo binary. Try decimal elevator sort (TM).

Re:I had an interview with Google a few weeks ago

[Xentor]

In regards to #2... Wait a second, they just want it sorted by BYTES? Wow...

1) Make 256-element array
2) Iterate through file, incrementing array elements to count occurrences of each byte value
3) Iterate through array, outputting desired number of each value.

Total storage required: 256 x 4 bytes, supporting file sizes up to 4GB, working in O(n) time.

Of course they probably meant the file contained a list of strings or numbers, but then it's their fault for being too vague...

(I applied on their website, and didn't get past the first screenings... Guess my 2.9 GPA wasn't good enough, huh? Stupid history courses...)

Re:I had an interview with Google a few weeks ago

[4D6963]

Indeed. You take a fixed gap size for the first marble, and go 1 by 1 for the second. To find what is the optimal gapsize, you calculate how many drops in average (considering that the distribution of the break point is normal) you'll need for your first marble to break, which is 2*100/gapsize, and how many drops it'll take in average for your second marble to break, gapsize/2, and you add both results to obtain the mean number of drops needed in total in function of the gap size.

I found that a gapsize of 10 is the most optimal, since it takes in average 10 drops (5 of the first marble and 5 of the second)

Re:I had an interview with Google a few weeks ago

[4D6963]

If that breaks, then you know floor 13 is the answer

No, it's not because it doesn't break at floor 12 and breaks at floor 14 that you can determine whether or not it would break at floor 13. For your idea to work you would have to go up by 2's, and that would be higly inefficient since, considering that the break point is distributed normally, in average it'd take you 25 drops of the first marble plus 1 for the second marble.

It's much less efficient than going up by 10's with the first marble and once it breaks go up by 1 since the latest non breaking floor with the second marble, since it would take in average 10 drops.

Re:I had an interview with Google a few weeks ago

[Anonymous Coward]

Oops I found out that actually 100^(10^6-1) != 25^3999996.

It should be:
100^(10^6-1) = 10^1999998 = 8^(1999998/log(8)) >= 8^2214616
which is still greater than 8^2097152

Re:I had an interview with Google a few weeks ago

[vertigo!37]

I've heard many, many similar accounts. I had two phone screens (the first was "inconclusive" my inside referrer says: 1st screener didn't ask right questions, or I was on the borderline, or sometimes they do 2nd to confirm). Mine were entirely on par with things on my resume and areas I claimed to be experienced in, or relevant to computer science.

ex: make writes to a fixed log atomic. however, I this guy was more of a 'regular' guy as I asked each screener at the end "what's a typical day for you" and I got the "google doesn't encourage long hours, but rewards productivity; and many do long hours to do that, but not me." he was a family man.

I got the idea the 2nd screener took a more balanced view of life either.

Believe me I'm not some google fan-boy, but I went into the process if anything biased against their process, and am turning around. It's only downfall: they want it standardized for every engineer so it takes so long. they know it. basically they are trying to scale start-up style hiring and it's hard.

maybe, though, i'm the exception and the poster is the rule? or vice versa? I don't have enough data points to say -vertigo^3

Re:I had an interview with Google a few weeks ago

[CopaceticOpus]

1. I'm too valuable to spend time dropping marbles from buildings. Give an intern one of the marbles, and tell him to start on floor number one and work his way up. Keep the second marble as a toy on my desk.

2. Email the file to my Gmail (TM) account. Open the file as a spreadsheet in Google Docs & Speadsheets (TM). Choose "Sort" from the application menu.

3. Chew out the idiot who removed the hard drive, get it back, and reinstall it in the machine. Save TCP stream to a text file. Repeat answer #2.

Re:I had an interview with Google a few weeks ago

[Furry Ice]

I'm not exactly sure what you mean by "binary weighted tree" but I don't think it's going to work because you don't have enough RAM to store 1 million phone numbers directly. The numbers are 8 digits, which means you'll need 27 bits to store them directly. That's 3.375 MB for all of them--it's not going to fit. There's certainly no room for pointers or anything else normally associated with a tree.

The way I would solve this would be to encode each number as a single bit. We have 100,000,000 possible phone numbers. We can use a bit representation of this set and it will require 12.5 MB, but because we are storing only 1% of the numbers, we can compress it and easily fit it into 2MB. It would just be important to have several independent chunks that you can uncompress and recompress easily to add new numbers as they come in. Maybe use arithmetic coding (or even just run-length coding because there are going to be lots of zeros). After you've read in the whole set, it's already sorted. Just print it back out in the usual encoding.

Re:I had an interview with Google a few weeks ago

[Creepy Crawler]

---Good challenge. BTW, you don't need 18 rounds, you need 17 because there's no need to check the floor 99 after you've checked 98.

Admitted. I was considering a 100 floor test to make sure the marbles BREAK at floor 100 (you know, "marble" ball bearings). Just to make sure, I'll retest here..

1. 1-10 (check floor 1 for defective floor 1 BREAK marbles)
2. 11-20
3. 21-30
4. 31-40
5. 41-50
6. 51-60
7. 61-70
8. 71-80
9. 81-90
10. 91-100 100-BREAK
11-18. 92 93 94 95 96 97 98 99-BREAK

I thought it at first, but we cannot assume breaks because we ARE dealing with engineers. They do funky stuff. We need to check them veeery carefully.

---However, I believe you missed one important issue. In order for the solution to be efficient, it's not important how many rounds you do but how many floors you have to walk up and down.

Its illegal for buildings these days not to have elevators because of that nice law ADA. Therefore, I dismissed that consideration.

But not to dismiss your (very true) concern, what would be the best proportion for Drop/stair_step ? That would change the whole algorithm completely.

Re:I had an interview with Google a few weeks ago

[Anonymous Coward]

The question is to find the most efficient way of testing, not the actual floor that it breaks at.

Re:I had an interview with Google a few weeks ago

[l0cust]

I am losing faith in human species now. I can understand not getting up to change the channels but now you want the marbles to bounce back to exactly the same height from which they were dropped? ... JUST GO DOWN AND PICK UP THE DAMN MARBLE! And do 50 push ups while you are at it.

Re:I had an interview with Google a few weeks ago

[Anonymous Coward]

I got the marbles terminal velocity to about 45-50 m/s. A hailstone would have lower density than a marble and have a higher drag coefficient.

Re:I had an interview with Google a few weeks ago

[Anonymous Coward]

1. define "effectively" first.
2. Look it up online (people that do sorts all day long for money are better at it than me).
3. Look it up online (people that do sorts all day long for money are better at it than me).

Re:I had an interview with Google a few weeks ago

[Viv]

So, do the calculation for your estimate of terminal velocity. They're not looking for an exact answer ;)

Either way, you still end up having to deal with one hell of a lot less floors (in your velocity's case, roughly 31 floors or less, as opposed to 100).

If you can eliminate 70%-85% of the search space without ever dropping the marble, you might as well.

Re:I had an interview with Google a few weeks ago

[eric76]

But that's the point.

If the marble could rebound to 100% of the height dropped from, the search algorithm would be strictly linear in terms of the number of floors climbed since you wouldn't have to go back to the street each time to retrieve the marble.

Re:I had an interview with Google a few weeks ago

[Anonymous Coward]

The answer to the first question isn't the most efficient way, it is the way that has the smallest number of drops in the worst case. If you wanted to have the fewest drops on average, you would need to have some probability distribution over each of the floors with your expectations before doing the experiment.

Re:I had an interview with Google a few weeks ago

[rcharbon]

You can drop the marble 99 floors. Drop it from Floor #100 - it'll go at least 99 floors before breaking.

Re:I had an interview with Google a few weeks ago

[Anonymous Coward]

"How do you figure that ability to do mental math is not correlated with software development aptitude? From experience I'd say it's the opposite."

I said that it was peripherally related, not that it was uncorrelated.

The ability to think mathematically is important. The ability to do non-trivial math in your head (while nervous, during a telephone interview) is of more debatable importance.

Re:I had an interview with Google a few weeks ago

[bjorniac]

You're thinking of kinetic energy. What's relevant here is potential energy: mgh. But realistically, it's not even a physics problem - you have to find the floor at which the marble breaks. If you wanted an approximate answer, you're on the right track, but I'm guessing they want the exact floor at which the marble breaks. Now it could break at 60mph, or 60.000001mph, that doesn't matter, the units you're working with are floors of the building, ergo you have to find a way of testing each floor as efficiently as possible. The way to do this is to use marble 1 to eliminate as many floors as possible by skipping many of them and using marble 2 to fill in the floors in between starting at the lowest non-break floor +1. (I believe going 14-27-39-50 etc etc with marble 1 will do this best, as you need about 9 drops on average to find the right floor).

Re:I had an interview with Google a few weeks ago

[martinmarv]

For A A A C C B B, there isn't a majority element.

Ah - I can see why it's confusing. When I read it and spotted the same issue, I thought the problem was to find the modal element (the element that appears more than any other element). The problem is actually asking for an element which appears in more than 50% of the cases - i.e. the majority of the sequence must be made up of one element.

Re:I had an interview with Google a few weeks ago

[Anonymous Coward]

Even assuming a rebound, doing it on every floor still isn't very efficient.
See my previous post: http://slashdot.org/comments.pl?sid=232757&cid=189 27803

Re:I had an interview with Google a few weeks ago

[naoursla]

Google has a hiring committee. I'm not sure of the exact size but it is on the order of 6-18 people. If any one of the hiring committee rejects you then they do not offer you a job. They are more interested in stopping false negatives than they are in stopping false positives. I think false negatives are potentially as damaging as false positives. At least you can fire the false positive. The false negative may go to work for a competitor, with a bad memory of Google, and not go back onto the job market again for years.

Re:I had an interview with Google a few weeks ago

[naoursla]

Unlimited memory? Store the answer in memory at the address specified by the 10000 byte address. Maybe you add an offset so your program has space to run. Setting up the table might take a while, but it should be easy once you have solved the pesky unlimited memory problem.

Re:I had an interview with Google a few weeks ago

[naoursla]

Or maybe 8 digits into 4 bytes?

Technically, you only need 27 bits per phone number so you could squeeze 6 numbers into 10 bytes with only 2 bits of entropic waste, but that sounds like a pain to work with.

Re:I had an interview with Google a few weeks ago

[Anonymous Coward]

maybe i'm missing something here but if every floor is equally likely the fastest way would be a binary search because the floors are 'ordered'. worst case 7 steps.

Re:I had an interview with Google a few weeks ago

[Anonymous Coward]

First question: start with binary search and modify to satisfy the conditions of the problem. If you had any number of marbles to break you know (should know) you'd do best by dropping the first one from the 50th floor: if it breaks the floor you're looking for is lower, if it doesn't it's higher, pick the mid point of the corresponding section of the building and repeat. Unfortunately this takes 7 marbles in the worst case; you can either simulate the worst case step by step to arrive to that "7" or believe when I say it's equal to ceiling(log2(100)).
Since you only have two marbles, let's try to apply the same procedure and see how far we get: drop the first marble from the 50th floor, if it breaks search the lower half, if it doesn't search the upper part. You will immediately notice an asymmetry: if the first marble breaks you will have to do a linear search in the lower half (i.e., drop the second marble from the first floor, then from the second, etc. until it breaks, which you know will be at most when you reach the 50th floor again since that's when your first marble broke), but if it doesn't you have reduced your search space in half FOR FREE since you still have the same two marbles to experiment with, and in that case you can still give a second go to a binary search in the upper half of the building (i.e., your second drop would be from the 75th floor, not from the 51st, and in the worst case you would have to search linearly only from 51st to 75th, not from 51st to 100th).
This clever observation on your part allows you to conclude that even if the absolute best you can do is binary search, in the present conditions you can go further by being less ambitions and trying to get your first marble to last as long as possible. So instead of dropping it from the 50th floor in the first try, why not try a much lower number? Say drop it from the 5th floor: if it breaks then you have only to search linearly with the second marble from 1st to 5th, clearly a huge improvement. What if it doesn't break? In that case you reduced your search space by 5% for free, that is, without sacrificing any marbles (although of course you will have to count one drop).
OK, so now the question becomes: what is the best "n" you can choose so that you have to do the minimum number of drops? Let's try five: in the worst case scenario you will have to do 20 drops to break the first marble (say it doesn't break in floor 5, or floor 10, or floor 15, ... but it does break on floor 100) and then 5 drops to break the second marble (floors 96, 97, 98, 99 and 100th again, where it breaks again). That's a total of 25 drops, your best result so far.
Up until here you have applied only basic concepts of computer science (linear search, binary search); at this point is where your high-school education will pay itself off! If you went to a few algebra classes, after some thought you will discover that the expression to calculate the number of drops depending on the number of floors you decide to skip on each try (let's call it "n") is 100 / n + n. Then, if you went to a few diferential calculus classes, you will know that to optimize the corresponding equation you derive once, make the derivative equal to zero and resolve for your variable, which (left as an exercise to the reader ;-) will tell you that your best "n" is 10, with a minimum of 20 tries before finding the lowest floor from which all your marbles will break!
You will say that is a bit of a mouthful for a phone interview, and of course it takes quite a few lines to explain as I just did ... but devising the actual procedure actually took me just a couple of minutes. Add to that the fact that when you're doing a phone interview (just as when you do one in person) you should be describing your thought process to your interviewer (instead of just keeping silent for two minutes and then providing a "perfect" answer, that gives him space to think you might be cheating) and that phone interviewers don't expect 100% accurate

Re:I had an interview with Google a few weeks ago

[tomstdenis]

I guess it depends on where you go. As I've met quite a few comp.sci grads who didn't know their arse from a semi-colon to save their life. They'd end up doing some coding job and just end up regurgitating the last two years of classes wherever possible. [e.g. shit code that looks nice on paper but doesn't do shit all in reality].

Having completed an associates degree in comp.sci I guess my experience was different, I had plenty of time for OSS and took advantage of it. Sure I wasn't a straight A student [or GPA 4.0 whatever] but I did write some software that was just barely important enough to get me noticed and a decent job in Ottawa. Score one for the good guys, whaddya say?

Tom

Re:I had an interview with Google a few weeks ago

[bclark]

I thought I'd share my experiences interviewing with Google as well, since they're somewhat similar to yours. I had sent them my resume twice previously in hopes of getting a summer internship, no response. I ran into an acquaintance at a career fair, a fellow Cal grad, who gave me a referral to get me an interview for a full-time job.

They also asked me to bring in a code sample for a problem they sent me about a week before the interview was scheduled. I was to write a program that takes a directory path, and returns the names of any files whose contents are identical (even if the filenames are not) in that directory and its sub-directories. Ostensibly, this is useful if you have a huge media collection where you might want to remove a bunch of copies of large files for disk space. The trick, since this is Google, is to do this efficiently. I wrote a DFS that hashed the file paths into a table by their length, since getting the length is a cheap operation most operating systems support. Then I did a slow O(N^2) comparison of all files in the same-length bucket, using two methods. First, I randomly selected some sections of each file and compared them byte-by-byte. This could be tailored to work well with how much RAM your machine has / how your disk reads work. Since the algorithm was supposed to be deterministic, if the files passed the random selection, then I did a very slow byte-by-byte compare, to ensure they were identical. I think the random selection could also be done using some sort of checksum, which might be marginally faster. When I handed the interviewer the print-out, he glanced over it in 5 minutes or so, and asked me how I might have to change the algorithm if the files were instead on a server on a local network, instead of on the machines hard disk.

It was an on-campus interview, but they asked me the same three questions as they asked you. Apparently they share a list of them among the recruiters. The marble one I struggled with by trying to start out with calculating probabilities, but I got the right algorithm and narrowed the floor interval down to between 12 and 15 in my head, good enough. The second question was simple for me (just break the file up, use an in-place sort and then merge the runs of smaller files). The third question I was lost on, mostly because I was tired by that point, and annoyed that the interviewer didn't seem to be listening to me at all. Overall, I thought the interview went alright, but they contacted me about two weeks later to say that they had too many applicants and too few positions.

I was simulataneously contacted by a different HR person at Google, who was interviewing me for a Web Application developer position (the other interview was for a generic Software Developer position). I had basically no web development on my resume, so I'm not sure why I was picked up, but I said I was interested. They sent me a 10 page worksheet to complete for them in a week, including a Python question (I didn't know Python at the time), some user interface questions, a lot of questions about my prior work experience, some basic math problems (algebra, estimation, simple probability), and a bunch of MySQL questions I had no idea how to answer since I had no useful prior experience with databases. After turning in the worksheet, they left me hanging for about two months before I got another e-mail saying they weren't interested.

Re:I had an interview with Google a few weeks ago

[Lemmeoutada Collecti]

Good point... I guess that the hammer I'm using right now looked like it would fit that nail. But then again, I didn't spend anymore time on that one than I would on a phone interview, so I am hoist in my own petard.

That just serves to illustrate that a hasty solution is not often an efficient one.

Re:I had an interview with Google a few weeks ago

[eric76]

If you have 100% rebound and if the efficiency is based on the total vertical distance covered, then it is close to the most efficient because you would never have to backtrack.

You would end up climbing the precise distance to the floor at which the marble breaks, when dropped.

If efficiency is based on the number of drops involved or upon the number of trips up and down, then it wouldn't be the most efficient. Of course, without 100% rebound of the marble, I don't really see how one can argue that the number of trips up and down counts for more than the number of floors covered in those trips. For example, a trip to the 2nd floor is much less expensive than a trip to the 100th floor.

So the most efficient strategy strongly depends on the working definition of efficiency. But, I assume, that is considered to be part of the problem.

Re:I had an interview with Google a few weeks ago

[Nevyn]

Or maybe 8 digits into 4 bytes?

8 digits into 4 bytes is obvious, as I assume pretty much everyone would know that you can convert 8 hex digits into exactly 4 bytes. It's also "obvious" that it's a bit less than 32bits, but I didn't/don't see it being enough smaller.

Technically, you only need 27 bits per phone number so you could squeeze 6 numbers into 10 bytes with only 2 bits of entropic waste, but that sounds like a pain to work with.

Ok, I'll take your word for it that it's 8 numeric didgits == 27 bits. ((27 * 1_000_000) / 8) == 3_375_000 ... and you have 2 MB of RAM, at this point you have to know/assume than you can half that value somehow due to redundancy. And personally I'm not fond of suggesting solutions that contain phrases like "but if we get input we don't expect, everything blows up".

Re:I had an interview with Google a few weeks ago

[Temporal]

OK, you can have your 1GB of RAM, but now you are trying to sort the entire internet.

Welcome to Google. :)

Re:I had an interview with Google a few weeks ago

[Anonymous Coward]

First drop the first ball from the 14th floor. If it breaks you can determine the exact breaking point with the other ball in at most 13 more droppings, starting at the bottom and going up one floor at a time.

If the first ball survives the 14 floor drop then drop it again from the 27th (14+13) floor. If it breaks you can determine the exact breaking point with at most 12 more droppings.

If the first ball survives the 27 floor drop then drop it again from the 39th (14+13+12) floor. If it breaks you can determine the exact breaking point with at most 11 more droppings.

Keep repeating this process always going up one less floor than the last dropping until the first ball breaks. If it breaks on the xth dropping you will only need at most 14-x more droppings with the second ball to find the breaking point. By the 11th dropping of the first ball, if you get that far, you will have reached the 99th floor.

Re:I had an interview with Google a few weeks ago

[Anonymous Coward]

you are missing something.

binary search:

drop marble at 50th floor: it breaks, 1 left.
drop marble at 25th floor: it breaks, 0 left.

and all you know is that the answer is somewhere = 25

Re:I had an interview with Google a few weeks ago

[Anonymous Coward]

First question - wow

Second question - a merge sort comes to mind, though this doesn't feel optimal. O(n log n)

Third question - you use a bit vector; the phone numbers are going to be all eight digit, unique numbers, so their presence or absence is all that matters. In this way, you can suck in all the numbers, populating the bit vector as you go (one loop), and then iterate over the bits, transmitting indexes for ones and nothing for zeroes. O(n) (see Programming Pearls for this answer in more detail)

Re:I had an interview with Google a few weeks ago

[Anonymous Coward]

or jump off of the 100th floor with both marbles clutched in your hands and let the marbles break your fall.

Re:I had an interview with Google a few weeks ago

[Anonymous Coward]

Not so, efficiency in this case is how many trips it takes to find out where the marble breaks. The definition of trips is fairly meaningless. Yes you can say, having it bounce is twice as effective as if it didn't, but the question still remains, how can you find the MOST efficient way of determining where the marble will break.

In other words (IMHO) this isn't a complete answer.

P.S. This comes from the experience of having the same question asked to me (although with lightbulbs so the bounce thing seems unlikely) and the question was how to figure out the minimum number of trips made).

Re:I had an interview with Google a few weeks ago

[eric76]

But the original question did not specify "number of trips". It used the phrase "Figure out a way, as effectivly as possible" and left the question of how to determine relative effectiveness open. Any good candidate should spell out his interpretation of that and be ready to justify that interpretation.

Of course, that doesn't spell out whether or not they want an efficient solution, a solution that comes up with a valid answer, or maybe a solution that arrives at the most correct answer. If they want the most correct answer, than maybe we might want to drop both marbles from the first floor, then the second floor, then the third, ..., until they break. If one breaks but not the other, then we must consider the possibility that maybe the marble that broke was defective and doesn't represent the normal marble. Or maybe the one that broke was the normal marble and the one that didn't was unusually strong.

But that is not likely what they are looking for. It seems clear that their marbles are assumed to be of uniform quality and will always break when dropped from the critical floor.

If it were me climbing those steps, I'd define efficiency in terms of number of steps climbed. Even if you are taking an elevator up and down (unless you have an elevator that makes the trip between any two floors in an equal time, it will take longer to go to a higher floor than a lower floor and so the height of the floor would still matter.

By the way, I didn't say that having the marble bounce is twice as effective. I merely said that if the marble bounced back to the same height from which it was dropped (that is, 100% bounce), the solution would be much different than if it didn't bounce because you wouldn't have to go back down to get it.

I never claimed it was a complete answer and wouldn't accept it as a complete answer if I was the interviewer. But I would look more favorably on a candidate who brought it up as a possibility and then continued on to the far more probable case of a marble with a limited bounce.

I'd also look more favorable on a candidate who took into account that the marble would have a terminal velocity and adapt their algorithm. I wouldn't think that a marble dropped from the 100th floor would really have much more of an impact, if any, than one dropped from the 20th floor.

Do you really want a candidate who only considers the most obvious approach?

Re:I had an interview with Google a few weeks ago

[dave1g]

After the first ball breaks wouldn't you actually want to go up by 2 each time in the linear part of the algorithm since the break/non break at floor n and n+2 can tell you the answer at n + 1.

I know its just a constant factor but we are going for the absolute best answer.

I dont know if anyone has truly captured the complexity of going up and down the building to test, but I assume someone else can stay at the bottom to check if the ball broke.

Re:I had an interview with Google a few weeks ago

[naoursla]

Ah, I misunderstood your original intent. You were not saying there is a way to squeeze 8 digits into 2 bytes. You were saying you would have to squeeze 10 digits into two bytes and you are surprised one would be expected to know how to do that.

I agree about the unexpected input part.

(incidently, log2(100000000)=log2(100)+log2(1000)+log2(1000)~=7 +10+10 is where I got the 27 bits from).

I think you would have to implement some sort of paging system to do this. But once you start accessing the disk, efficiency goes out the window.

Suppose you made heaps around .5MB in RAM and represent each number in 4 bytes. Building a heap is average linear time. When the heap fills you write it to disk and start a new heap. Each heap will hold 131k numbers. With 1M numbers we will write 8 heaps to disk {A B C D E F G H}. Doing a merge sort on these heaps is a bit tricky.

We load two of the heaps on disk into memory and merge them into two new heaps. We only have to store one of the two new heaps in memory at a time. When the first heap fills up we just write it to disk and create a new heap. An obvious solution is to do O(N^2) merges:
((((((A+B)+C)+D)+E)+F)+G)+H) => [Min Ordered Set] + {7 partially ordered sets}
Repeat for the remaining seven incompletely ordered heaps and you are done.

I suspect we can do better than O(N^2) though. The problem is if we do something like this:
A+B => AB1, AB2
C+D => CD1, CD2
E+F => EF1, EF2
G+H => GH1, GH2

We know that all elements in AB1 are less than all elements in AB2, but we know nothing about the relationship between CD1 and AB2. We can't just merge AB1+CD1 and expect to get anything meaningful.

We do know that the root element on each heap is the smallest element in that heap. Since we only have 8 heaps we can store that in memory (the heaps probably have to shrink a little bit). We merge AB1 and CD1 into two heaps at once. Items that are less than AB2_min go into heap 1, items larger than AB2_min go into heap 2.

We have a new set of heaps now that are slightly better ordered. The item at the top of each heap is the smallest item in the heap. All of the items in XY1 are less than all of the items in XY2. We remember the minimum item in each of the XY2 heaps...

Crap, I just realized that is all too complicated. Just do a quick sort using pages. Create two pages each 512K in size. Choose a 9 digit number as the pivot. Assume over all time the numbers will be uniformly distributed so you choose 500000000. As each number comes in put it in heap one if it is less than the pivot and into heap 2 if it is greater than or equal to the pivot. As a page fills up then write it to disk and create a new page. In the end you will have 8-9 pages where one set of pages is less than the pivot and the other set is greater than or equal to the pivot. Start the process over, but instead of reading from the network, load a third page as your data source. Select the new pivot by sampling from the new set (which could be done during the initial processing) -- pick 10 or 20 numbers from the set and use the median as the new pivot. Worse case performance is O(N^2) but it will probably be closer to O(N*logN). Merge sort is usually guaranteed nlogn, and that is what I was trying initially, but I don't know if it will actually work with partially ordered sections like this.

Re:I had an interview with Google a few weeks ago

[Anonymous Coward]

Assuming you mean from the nth floor up, the marble will break. Take the first marble, drop it from the 1st, 2nd, 4th, 8th, 16th, and so on. When it breaks, go to the previous power of 2 plus one floor, and start dropping the other marble one floor higher each time.

Re:I had an interview with Google a few weeks ago

[d33p1x]

1st question: Start on the 14th floor. If it breaks, start with the second marble on the 1st floor and increase until it breaks. If it doesn't, go to the 14+13th floor, then 14+13+12th, etc. That gives you a maximum of 14 attempts.

Are you sure that's the best? This is a simple binary search. You have 100 floors and the "key" is finding which floor breaks the marble. You start at floor 50. Then you try floor 75 if the marble doesn't break, or 25 if it does. Then 87 or 12, and so on ... even if the building has 128 floors, you need only 7 attempts in the worst case.

Re:I had an interview with Google a few weeks ago

[xsuchy]

Third question: Binary weighted tree in memory.

In the question was 9 digit number => you need 4 bytes to store it. You get one milion this numbers. => You need 4 MB of memory, but you have only 2MB RAM. Even if you choose to store it in just 30 bites, you still need 3.75 MB of RAM.

So you must somehow store data on network. Either by not sending ACK for some packets or juggling with packets.

What?

[glwtta]

You mean there are still people who don't work at Google?

From the sheer number of articles about or relating to the Google hiring process and corporate culture I just assumed that they would have hired the entire qualified workforce by now.

(though they do have some really nice sounding quality of life type perks...)

Re:What?

[pudknocker]

From what I was told, each prospect goes through 5 interviews before being hired, I made it through 2 1/2 (1/2 being the technical screening questions by the recruiter) interviews before I was told "no thanks". I didn't even apply (never did find out how they got my name and contact info, not that it should be hard for "them"), just got a call out of the blue from a recruiter. What I wonder is, if they skim through so many people (as it appears from the other posts), once they've gone through everybody, do they lower their "standards", and start back through the people they've pissed off?

Know your audience

[evilviper]

"In an article on the ZDNet site 'chief culture officer' and HR boss Stacy Savides Sullivan describes the kind of traits that she's looking for in potential Google employees.

Do those traits include reading Slashdot at 03:24AM, Monday morning?

*crosses fingers*

Google is hiring flunkies?

[boyfaceddog]

"Google-y is defined as somebody who is fairly flexible, adaptable and not focusing on titles and hierarchy, and just gets stuff done."

In my experience, this translates into a dead-end grunt job.

Fairly flexable = Willing to do anything from sweep floors to fetch coffee.
Adaptable = Doesn't need to be shown how to sweep floors or fetch coffee.
Not focusing on titles or hierarchy = No promotions and everyone is your boss.
Just gets stuff done = This would be the stuff no one else wants to do.

Translation: Paid Intern

Re:Google is hiring flunkies?

[dubl-u]

"Google-y is defined as somebody who is fairly flexible, adaptable and not focusing on titles and hierarchy, and just gets stuff done." In my experience, this translates into a dead-end grunt job.

Possibly, but not necessarily. That's basically what you want out of any startup employee. Even if you're CEO, you'll be bringing in the mail, and you'd be more likely to go fetch coffee than the devs would, as they are the bottleneck.

So they could legitimately be trying to run things more as a bunch of internal startups than as the typical large, hierarchy-focused company. That's certainly possible, as they still have a lot of people there who fondly remember the early days when you could just get stuff done. Further evidence in favor of that is the relatively uncoordinated way they run their products; it suggests that they really do have a lot of small groups running around and doing things, and worrying about coordination later.

Paternity leave

[heffrey]

It just shows the difference in cultures between the USA and western Europe that paternity leave of a "couple of weeks off" can be viewed as a perk. Sadly as a Brit we are much closer to the USA than the rest of Europe (especially Scandinavia and Finland).

Re:Paternity leave

[Anonymous Coward]

It just shows the difference in cultures between the USA and western Europe that paternity leave of a "couple of weeks off" can be viewed as a perk. Sadly as a Brit we are much closer to the USA than the rest of Europe (especially Scandinavia and Finland).

Actually, most UK employees are entitled to two weeks paid paternity leave now. See http://www.direct.gov.uk/en/Employment/Employees/W orkAndFamilies/DG_10029398 for details. Pathetic compared to Scandinavia but better than nothing.

Re:Paternity leave

[Anonymous Coward]

In South America, some countries can trade part of the women's maternity leave for the father's one. They together should add up to 3 months (I think).

Re:Paternity leave

[heffrey]

Well, I've just done it and it's not exactly "paid". The amount is capped at £108/wk which is not a right lot. I earn very much more than that and of course can afford what amounts to 2 weeks unpaid leave. It's good for me since I get an extra 2 weeks leave at an important time. For a low paid worker it's useless since there is no way they could afford 2 weeks unpaid leave. Not to mention the fact that it would be frowned upon in the type of job that pays minimum wage.

Essentially then this is a benefit for the poor! Robin Hood would not have been amused!

But, even with this the UK is well behind all other western European countries I think. It's the Scandies and Findland which lead the way - as usual of course.

Re:Paternity leave

[heffrey]

Er, I meant that this is a benefit for the rich!

Employee who just gets the work done??

[madbawa]

Yeah right. They only want PhDs, people who have published papers or have patents against their names. Basically, very brilliant people. So there sure as hell ain't no hope for the rest of the 95% of us software engineers who actually fit their 'description' of a google employee. All this is just eyewash.

Re:Employee who just gets the work done??

[dummkopf]

dude, i have a phd. in fact, i am an assistant professor at a very good university. that is clearly not what they need either. you have to be very "special" to fit in. i know someone who works at google in zurich. when i see her, i understand...

Re:Employee who just gets the work done??

[tomstdenis]

Just because you have a patent in your name doesn't mean you're "brilliant." While I have no doubt Google is looking for smart and intelligent folk to work for them, being a PhD hardly seems like a sufficient requisite.

Though compared to most computer related jobs I'm sure google does a proper job of sieving out the non-hackers. just because you can script monkey C# doesn't mean you understand computer science, which is basically what google is after anyways.

Tom

Re:Employee who just gets the work done??

[Opportunist]

Just because you have a patent in your name doesn't mean you're "brilliant."

SCO allegedly holds some. QED.

Re:Employee who just gets the work done??

[gol]

really? I'm just about to apply to Google Zurich. Is there anything I should know?

Re:Employee who just gets the work done??

[b0s0z0ku]

They only want PhDs, people who have published papers or have patents against their names.

They're not only an R&D house -- they actually have daily operations and need people to run things as well. If they only hired geniuses, they'd end up with a lot of bored geniuses in no time.

-b.

Re:Employee who just gets the work done??

[dummkopf]

yes: heard rumors that they want to shut down zurich and move it to the uk.

Re:Employee who just gets the work done??

[madbawa]

Just because you have a patent in your name doesn't mean you're "brilliant." While I have no doubt Google is looking for smart and intelligent folk to work for them, being a PhD hardly seems like a sufficient requisite.

Though compared to most computer related jobs I'm sure google does a proper job of sieving out the non-hackers. just because you can script monkey C# doesn't mean you understand computer science, which is basically what google is after anyways.

Tom Then pray tell me how the hell do they screen resumes? How can they write you off without taking even an interview? Or should I just mention in my resume: "I know computer science, come try me" Or write all the "special qualities" they require in the "Skills" portion?
There has to be some criteria of rejection and thats what I am talking about. If you know computer science to the extent that Google wants you, you need to have some hairy stuff on your resume. Top notch qualifications are one way of showing this.

It's part of the test...

[BiggerIsBetter]

One of the little known Google hiring practices is that they want to know if you play Cricket.

A googly, or "wrong'un", is a delivery which looks like a normal leg-spinner but actually turns towards the batsmen, like an off-break, rather than away from the bat.

http://news.bbc.co.uk/sport2/low/cricket/skills/41 73812.stm

Want To Work At Google?

[Anonymous Coward]

Want To Work At Google?
 
Eh? No.

Re:Want To Work At Google?

[Notquitecajun]

Me neither.

Mostly because it would probably require me to live in a place where God didn't plant the grass. No thanks.

Also, I'm not a programmer.

Here's my inside scoop at a google interview

[dummkopf]

Passed the first stage with HR, then had the interview with one of the engineers. The guy asked the mandatory question "tell me what you do" but after two minutes cut me off as it was clear he was not interested in optimization problems in physics. It was clear from the start that we spoke "different languages" and that lunchtime was looming in Mountain View, i.e., he was in a rush. Then he asked me some test questions. For example: "Suppose I give you a phonebook and ask you for a name, how long would that take?" As you can see, the question and answer are wide open. I told him that if the book had N pages, it would take me worst case N lookups. He was not pleased and asked for a faster solution. Hence I said, OK, I throw it into a hash and then the lookup is O(1). Then he complained that there would be too much preprocessing (although I would expect google to hash things...). He wanted "something in between". Hence I said, OK, let's sort the book and then partition to the name wanted, i.e., O(log(N)). Then the guy asked what log that was. I said that it does NOT matter since, in the O-notation prefactors are irrelevant and as you might know, you can always transform a log from one base to another by just a multiplicative factor. That was not a pleasing answer and he kept asking me to what base. Eventually I told him base 2, if he really had to know, but it did not matter. I admit I did not well in the interview, but the guy at the other end did NO effort in leading a good interview. The next question was (since I do some distributed computing) if I have many clients and they want to upload data to a server, what is the best way to do that. Again waaaaay open. I said, well, the client sends a request and when the server is free it answers and gets the data. Not good. Might overwhelm the server. Of course he would not tell me what he wanted to hear so I poked around a bit to realize that he wanted that the server floods the network with a "I am free signal" and then clients can upload the data. So what about reaching the limit of the network? "Well, that is not an issue here". Aha, I thought, I see, an issue is only what the guy deems to be an issue. At that point it was noon in Mountain View and he suddenly wanted to hang up. No "do you have any other questions?" or anything that shows good manners from an interviewer. Hence I decided to stop him cold and said "I have some questions for you". You could feel how pissed he was about this -- after all lunch is looming around the corner -- and he gave me the probably shortest answers you could think. For questions which I had gathered from whitepapers published by google (and there are only FEW out there) he would always say "I cannot talk about that".

So... You really want to work there? Yes, you get lots of money, yes you get brainwashed it seems and rather arrogant after a while. Granted, this was one guy only, but letting him onto candidates which are not necessarily computer scientists. Hm... Needless to mention, Ihad a negative email the net day. Note that I did NOT apply for a job at google. One day I had an email from a HR person in mymailbox with the Subject "Hello from Google",and that's when this story started...

Re:Here's my inside scoop at a google interview

[Shados]

Actually, it seems obvious to me what the guy that interviewed you wanted to know: if you could convert what you learned in school in the real world. "Worse case scenario" (aka: O) isn't something you can blindly follow, as in many, many cases its irrelevent (thus why the 2 others). I can't talk for them, but in the place of a google engineer, I'd be MUCH more interested in "the most likely scenario" than in the worse case, since when you deal with a large amount of customers, the only thing that really matters is what happens day to day, and if the "worse case" happens, you add an extra server, be it at google, be it at your average corporation (not that simple, but you get the idea)

On top of that, google interviews are fairly known for seeing how you -react- to challenges, not your answers to them, thus the open ended questions. You could have answered all the questions wrong and they would take you anyway, if you showed your only weakness was experience, but they probably have seen too many people worrie about which sorting algorythm is the best when having to sort a 10 item dropdown menu...

Oh well, I'm sure your skillset will be more appreciated elsewhere, so no big loss to you :)

Re:Here's my inside scoop at a google interview

[lwriemen]

I interviewed with a small company once where the final stage of the interview was with the president of the company. We ended up getting into an argument, because he said something I knew to be wrong on a technical issue and I called him on it.
I didn't really care at that point anyway, because he seemed to be a pretty arrogant bastard.

Re:Here's my inside scoop at a google interview

[backwardMechanic]

What's the big problem with open questions? A good interviewer will give you some space to show your knowledge. One way of doing that is to ask open questions and see where the interviewee goes. Real life isn't like an exam question, with nice clean solutions from section xx.y of the syllabus.

Re:Here's my inside scoop at a google interview

[glwtta]

Wow, I know interview questions can be annoying, but you were being kind of a dick about it. I mean, it would've taken about 2 seconds to just tell the guy what he wanted to hear.

Re:Here's my inside scoop at a google interview

[Anonymous Coward]

Attitude problems need not apply.

Re:Here's my inside scoop at a google interview

[C_Kode]

I have my own stories about a Google interview with an engineer.

Google Engingeer: A person cannot login to his computer. Help desk doesn't know what is wrong and have called you. How do you fine out what is wrong?
Me: I check the LDAP logs for errors.
GE: None.
Me: I check the users local system logs.
GE: None.
Me: Check the users login script for errors.
GE: None.
Me: Check permissions on users home directory.
GE: Very good, users home had incorrect permissions.
Me: Wouldn't the logs have told me this without checking the permissions?
GE: Maybe, next question.
GE: What is the difference between NAS and SAN?
Me: File I/O vs Block I/O and cost mainly.
GE: Cost? How much does a SAN cost?
Me: Well, we just traded up one of our older SAN peices (Clairiion FC4700) to a new CX300 with (15) 73GB drives for $18k with 3/yrs support.
GE: Well, NetApps cost $25k. Thats more than your SAN cost.
Me: What did you pay per GB on your NetApp?

GE: This isn't important. Do you have any questions for me?

Needless to say, he gave me a bad review. It's ok though, I have a mortgage and their pay scale probably wouldn't cover anything but rent on a small apartment.

Re:Here's my inside scoop at a google interview

[wass]

So... You really want to work there? Yes, you get lots of money, yes you get brainwashed it seems and rather arrogant after a while.

Interesting, from your story it appears he wasn't the arrogant one.

When you were describing your physics optimization, you really shouldn't expect him to want to listen more than a few minutes anyway. You say you spoke 'different languages'. Communication is a key skill, and perhaps you weren't explaining your research project in a way comprehensible to an outsider of the field. Or perhaps he only has 15 minutes he can devote to the interview, lunchtime or not, and needs to get as much info about you as possible. You can't expect him to give you all the time you desire, merely in a first-stage phone interview.

He wants to see how you think, and you didn't seem to make that obvious, you were more interesting in answering questions with academic answers not immediately useful for the real world. His question for the phonebook asked "how long" it takes to look up the name, and just reciting O(1) isn't the full answer to this. You're right that logs of diffeerent bases are only related by a multiplicative factor, but if someone wants to know how many comparitive lookups you need what reason could you possibly want for expressing this in any base other than two? (I'm a physicist, not a comp-sci guy, so if there is an answer to that I'd be curious to know). To answer how long, you need to know how long each lookup takes and how many lookups you would need to perform (assuming he wanted an answer in time). You were like a politician, and answered a different question than the one he asked.

You also made it clearly obvious to the interviewer that you would be a very difficult guy to work with, Ie, if you're of average google hiring intelligence and experience, half of your coworkers at google would be less smart or skilled as you. And if someone needs help understanding big(O) notation for their project and asked you to help them, you might be a dick to them, as per your interview.

Additionally, if he's in a hurry, it's your obligation to sell yourself in the phone interview while making the most optimized use of time that you can, which you severely failed to do. In any job your superiors will almost always be very busy, and you must demonstrate how to efficiently use their time, as well as your own. You made yourself seem to high maintainence.

Finally, if the interviewer was in a hurry and didn't ask you if you had any questions, you should have left it there, or at least been mature about it instead of cutting him off as you said. This is only a first round phone interview, and perhaps not the proper venue to ask questions if the interviewer didn't ask you. If you're serious about working for Google, and they're serious enough about you to fly you back for a follow-up interview, that's where you should start asking questions. You should have done enough research about the company on your own, prior to the phone interview, to see if it's a good enough fit for you to seriously consider the interview process.

You complain about the interviewer making no attempts to lead a good interview, well sorry to bust your bubble but the effort to sell yourself falls entirely on YOU and only YOU. It's unfortunate if you did have an annoying interviewer, but in the actual workplace you'll have annoying coworkers too, and you need to know how to deal with them effectively to get the job done. Your focus at the phone interview should have been on selling yourself to get invited back to a second interview. At that interview you can then judge what the work atmosphere is like, and whether it's a friendly environment or not.

The interview doesn't only test your technical knowledge but your personality too. Your description makes it relatively obvious that you failed in all those aspects, and to me you really didn't come off as a mature responsible potential employee that I would ever want to hire. Sorry.

Re:Here's my inside scoop at a google interview

[Jerf]

On top of that, ... interviews are fairly known for seeing how you -react- to challenges, not your answers to them, thus the open ended questions.

That's the theory. When it's done correctly, it works.

But the interviewer has to understand that and be on board with it. If they forget why they are asking open-ended questions, it becomes pointless. If they want O(log2N), including the 2 (and despite the meaningless of the 2), then they need to realize that it's going to be an interactive question. If the interviewer gets frustrated that you don't jump directly to the answer, and (even worse) gets frustrated that you insist on asking questions rather than "just giving the correct answer", than the entire interview process really becomes a joke, a crapshoot as to whether you luck into the "correct" answer despite not having enough information to give it.

I've stripped out the word "Google" from your quote because this is a generic response. I see this happening in a lot of people's accounts of technical interviews with many big companies.

I wasn't at the GP's interview, but I get the sense this was in play there. The interviewer was probably asking the questions he'd been told to ask, and expecting the right answers he'd been told to expect, but hadn't picked up on the fact that there was going to have to be some interaction with the interviewee, and it's the interaction that he needed to be looking at, not the "correct answer". (Calling it the "correct answer" tends to load the mind up with certain expectations in many testers; the idea of getting a question correct without arriving at the sole and singular "correct answer" blows some people's minds.)

Re:Here's my inside scoop at a google interview

[Shados]

I'll be 100% honesty and say that I was never interviewed by Google myself, but my girlfriend did relatively recently and I got a fairly detailed description of how it went, and was able to match the OP's description on top of it, thus my above conclusion, so take what I say with a grain of salt, but...

from what Im seeing, the interviewer was doing exactly what they should have: put the person being interviewed in an unexpected challenge situation. Its more or less impossible to answer "correctly" a question from a google interview. They'll do and ask anything it takes to mess you up and throw you off balance, just to see how you react. The person who described their experience above seemed like they somewhat knew what they were saying (at least, the school-taught part of it), and the interviewer made things super precise until they didn't know what to answer anymore.

If the person had known these answers right off the bat too, they would have pushed further. All of it was probably just to seehow they'd react.

As a contractual developer, I've been to more interviews than I can count (douzans upon douzans upon douzans), and have myself passed people under interview. The challenges developers face are when they hit the unknown. No one gives a darn how you react to questions you know the answer of, or that are clear. In the real world, you'll have to deal with customers, clueless business analysts, buggy software, uncontrolable situations, and some that simply don't make sense. The way people handle these situations will dictate if they can shine or not, in that real world, especially a higher end environment like at Google. So again, from my point of view, the interviewer was quite clever. Maybe a bit too much :)

Of course, can't tell for sure without actually being there...

Re:Here's my inside scoop at a google interview

[Anonymous Coward]

The cafeteria runs out of food as I discovered when the inverviewees I was interviewing with were taken to the cafeteria near the end of the lunch operating hours. I suspect you have to get their early to get the best selection.

Re:Here's my inside scoop at a google interview

[Flarelocke]

He wants to see how you think, and you didn't seem to make that obvious, you were more interesting in answering questions with academic answers not immediately useful for the real world. His question for the phonebook asked "how long" it takes to look up the name, and just reciting O(1) isn't the full answer to this. You're right that logs of diffeerent bases are only related by a multiplicative factor, but if someone wants to know how many comparitive lookups you need what reason could you possibly want for expressing this in any base other than two? (I'm a physicist, not a comp-sci guy, so if there is an answer to that I'd be curious to know). To answer how long, you need to know how long each lookup takes and how many lookups you would need to perform (assuming he wanted an answer in time). You were like a politician, and answered a different question than the one he asked.

You also made it clearly obvious to the interviewer that you would be a very difficult guy to work with, Ie, if you're of average google hiring intelligence and experience, half of your coworkers at google would be less smart or skilled as you. And if someone needs help understanding big(O) notation for their project and asked you to help them, you might be a dick to them, as per your interview. They were probably looking for base 26, actually. It's the number of letters in our alphabet, so a trie (which is an m-tree where each path from the root to a leaf denotes a sequence) would have 26 children at each node. Although this may have been what they were looking for, Knuth proved that any m-tree can be expressed as a binary tree with only a constant factor difference, which puts it in the same bucket as differences between machine architectures.

Big O notation is one of the foundational concepts in computer science, right after the Church-Turing thesis and the proof of the undecidability of the halting problem. As a physicist, it would be similar to applying to a highly technical company (one that, say, makes scanning electron microscopes or maybe helium refrigeration equipment), and having to explain to one of your future coworkers that work should be measured in Joules or electron-volts instead of man-hours.

Ask him back ...

[Ihlosi]

"Imagine you have two marbles and a 100-story building. You are told that the marbles will break if they are dropped from a certain floor. Figure out a way, as effectivly as possible, how high you can drop the marbles before they break. Remember, it could be the 1st floor, it could be the 99th."

"Minimize maximum search time, minimize minimum search time, or minimize average search time ?" ;)

Probably ...

[Ihlosi]

But how would you be certain whether the 13th floor was the last floor the marbles could be dropped from without breaking, or the first floor at which the marbles broke?

By searching from the bottom after the first marble breaks. So, if the first one didn't break at 12 but broke at 15, try 13 and 14 in that order.

Not math in your head ...

[Ihlosi]

I've never been asked to be a human calculator in an interview before, so it took a few seconds to realize that I was actually being quizzed on my ability to do math in my head.

Nope. That wasn't a question of doing math in your head, it was a question on how to calculate a logarithm using only basic math. It's fairly simple actually in a 10-base system and trivial (requires only subtraction and bit-shifting) in 2-base, but you have no chance of figuring it out yourself if you've not heard of it before.

Re:Not math in your head ...

[Anonymous Coward]

"Nope. That wasn't a question of doing math in your head, it was a question on how to calculate a logarithm using only basic math. It's fairly simple actually in a 10-base system and trivial (requires only subtraction and bit-shifting) in 2-base, but you have no chance of figuring it out yourself if you've not heard of it before."

I know; as I said, I got the right answer. But "trivial" as the solution may be, it's still a question about doing math in your head. It's only peripherally related to the set of skills that makes someone a good developer.

Re:Not math in your head ...

[Ihlosi]

I know; as I said, I got the right answer.

Well, if the question only was "How would you calculate that?", I would have said that I'd use my pocket calculator. It's not that they said I wasn't allowed to use one. ;)

Paid paternity leave

[deletedaccount]

Everyone gets this in the UK. It's a basic right. *points and laughs at the Americans*

Re:Paid paternity leave

[TodMinuit]

People and corporations have freedom in America. *points and laughs at Britian*

Re:Paid paternity leave

[Anonymous Coward]

Oh, everyone gets paid paternity leave in at least Sweden and Finland too. Both men and women, 100% paid and for 10-12 months or so. And it's illegal to fire someone because of taking it (the law is enforced very ruthlessly against companies).

Fyi, we got more freedom as well, don't start trolling about irrelevant issues however.

Re:Paid paternity leave

[deletedaccount]

Freedom to never see your kids because you don't get any holidays!
Go you
*gloats about his 30 days of paid holiday per year + paternity benefits*

Re:Paid paternity leave

[TodMinuit]

Corporations have the freedom to provide whatever benefits they want, including none.
People have the freedom not to work some place that doesn't provide the benefits they want.

Freedom is good.

Re:Paid paternity leave

[Isvara]

It's a basic right to get a tiny fraction of your salary for two weeks. A little over 100 pounds a week, IIRC. And that's if you've been with your employer for 26 weeks at 15 weeks before the baby's due date. If you're lucky, your employer might give you full pay during all or part of your paternity leave as a perk.

Re:Paid paternity leave

[Anonymous Coward]

Hum.. let's see.. so the negotiation process is between you and Mega Corp X..

You: I want 30 days of paid leave per year
Manager: 10
You: Ok, 20
Manager: no 10
You: Forget it, I'm going to Mega Corp Y
Manager: Fine, your loss

You leave the room while Manager calls up his golf buddy at Mega Corp Y.

The market only works when power is not concentrated to the side of one party. That's why some economists consider unions be the lesser evil.

Re:Paid paternity leave

[Anonymous Coward]

I'm afraid Americans are merely spoonfed that they have freedom. You come living in liberal European states like some scandinavian states, the Netherlands etc. for a while and you'll start to realise that the free live outside the US.

B., posting AC, because access to the US may be denied to this otherwise decent person just because this post might get him into a US computer
Who's still wondering how much research American's do before they state that the US is the greatest democracy. After a comparison with North Korea and China only?

Re:Paid paternity leave

[TodMinuit]

First, nice broken English.

Second, make some solid points demonstrating that the U.S. lacks freedom. Otherwise, you're just trolling.

Re:Paid paternity leave

[hyperstation]

well, recreational drug users aren't subject to anywhere near the level of government harassment in the netherlands as here in the US, so that's one point. when i visited last year, i found the air of openness quite refreshing.

Re:Paid paternity leave

[utnapistim]

... wish I had modpoints ...

Re:Paid paternity leave

[Anonymous Coward]

Classified laws, National Security Letters, warrantless searches, FISA "secret courts", widespread, warrantless, domestic communications surveillance, do not fly lists ?

HR is the last place to get real information

[walterbyrd]

I would be more impressed if were somebody at a suppervisory level, speaking off the record. All you will get from zdnet HR piece is stupid hype.

Google-y definition

[Anonymous Coward]

"fairly flexible"

willing to work all the hours of the day.

"adaptable"

there's no job structure, you'll be pimped out to whatever teams we please.

"and not focusing on titles and hierarchy"

you've got no chance of promotion or a pay rise.

"and just gets stuff done"

no complaining about ridiculous deadlines or having to do all the work whilst the idiots we've teamed you with slack off.

"So, we put a lot of focus in our hiring processes when we are interviewing to try to determine first and foremost does the person have the skill set and experience potential to do the job from a background standpoint in addition to academics and credentials."

non-PHD's need not apply.

Re:Google-y definition

[Anonymous Coward]

furthermore:

We're trying to figure out how committed people are to the company, what's causing that commitment level to be high or low, what makes a difference to them and their management and direct managers. The results ended up being centred a lot on career development and growth. So career development is more of a focus than giving more stock options or increasing salaries.

Sounds like the gravy train may have hit the end of the tracks.

I'm not entirely sure what 'career growth' even means if people aren't moving through a corporate hierarchy.

Google

[Beatlebum]

They want young, smart people. Forget it if you are old (>30) and smart, you won't even make it to the interview.

Re:Google

[Anonymous Coward]

You bet. Once I got to Mountain View, I was told what a great place it was at Google, and that it is full of smart, talented and young people. Then she gasped and realized she should never had said that.

I always figured my 2 mistakes over 6 hours of interviews were why I didn't get hired. Since I meet all of their criteria for the job, and they flew me out after two phone interviews.

After some introspective days after being told via email that I was not a "strong match", I realized it was probably because my hair is disappearing.

Re:Google

[b0s0z0ku]

After some introspective days after being told via email that I was not a "strong match", I realized it was probably because my hair is disappearing.

Shave your head if you get another chance.

If anyone asks:
"I'm recovering from brain surgery. I just had a neural implant of my own design, which doubles the memory capacity of the brain and communicates via WiFi for backup purposes. Next question?"

-b.

Re:Google

[dubl-u]

They want young, smart people. Forget it if you are old (>30) and smart, you won't even make it to the interview.

They've recently hired a number of 35-ish people that I know, so I doubt that's the case.

However, they do probably favor what I think of the "absent-minded professor" type, where 90% of your time it taken up with hacking on one thing or another because you love it so much. That's probably age-biased, as a lot of great technical people eventually discover things like girlfriends, kids, and other hobbies.

Re:Google

[kindbud]

If you're old and smart, you have no interest in perks designed to make your stay at work more comfortable and enjoyable, and you don't like people who enjoy them and stay at work for 18 hours a day. Makes us look bad. That's why we old farts run around adjusting the a/c or heat to make the place insufferable so you people will go home at a quitting time.

Re:Google

[Dystopian Rebel]

I hear that Google's HR team is a bunch of Actuarial Math PhDs who have done a complex analysis and figured out that as people grow older, they have probably done a complex analysis and figured out that HR teams have probably done a complex analysis (especially if they are all Actuarial Math PhDs) and realize that as people grow older, they are not going to put up with long hours and two-faced corporate BS and would rather spend evenings at home.

Re:Google

[Kelz]

Well I'm young, and I would consider myself smart in that I haven't had a job (non-coding) that I couldn't pick up fairly easily. I don't however have a degree nor the money to get one. They want young, smart people with a peice of paper.

Google's requirement of academic background

[Anonymous Coward]

I have gone through interviewing at Google not a long ago, and when I reached the on-site interview stage, these guys were surprised that I didn't fill anything in the academic background section. Their forms are not even suitable for not having an academic background.

So, is it true that absolutely *no* collage dropout can be considered a genius these days?
The fact I've been a self taught workaholic software engineer since an early age doesn't count at all?
Is it my fault for starting a career and making money instead of wasting my time over a pointless CS degree?

Maybe it's just my pride being hurt, but I think that their hiring process should be considered much less optimal than what it may appear.

Re:Google's requirement of academic background

[Afecks]

If you don't want to play by their rules then you have to start your own business. This is how most of us dropouts are making it big. If you're going to be a serious programmer it's probably the best way to do it anyways. Find some niche that isn't being served well and take it over. You'll get a lot more return on the time you spend. I think they only problem with this approach is having to deal with the customers.

The reason why they want academics is because they are too lazy to screen everyone that comes through with some sort of actual test. They'd rather use a coarse grain filter and only let the good worker bees in. Then they can cherry pick the rest a lot more easily.

Re:Google's requirement of academic background

[Anonymous Coward]

I applied for, and was offered, a position at Google. I turned them down, but I went through the process. Many friends and colleagues of mine are at Google.

I will soon have a doctorate in computer science. So I have three "pointless CS degrees." In a row.

It is possible that you are a "collage" dropout who is, indeed, a self-taught genius. As other posters have said, though, Google seems to get literally thousands of applications per month. How do you distinguish yourself? How can you show anybody - Google or a random Internet user like me, that you are, in fact, a self-taught genius? What evidence do you offer?

Me, and my Google-employed friends, have published repeatedly in the top journals and at the top conferences in software engineering in the world. We spent five or six or seven more years beyond our Bachelors Degrees doing applied and novel research, and we learned to write it up. That's the academic version of sales.

It is not your "fault" for starting a career and making money. Although there'd be some small process exceptions made, I'm sure that Google would give you a pass on the academic background if you've, say, started a renowned company. Or were a developer of a widely-used programming language. Or were a major contributor to a project like Apache. Are you?

Re:Google's requirement of academic background

[maple_shaft]

You are a loser. You can't even spell "collage dropout" right. If there is one thing I can't stand it is when pretentious dropout snobs start complaining about nobody hiring them because they don't have a degree. The rest of us software engineers had to suffer through that bull before we could get a job and so should you.

What just because you think your smart you don't have to play by the rules?

Granted I learned almost NOTHING during my 4 years in school but I played by the rules and got that piece of paper, which is why I am in the game, and your still living with your mom because you believe her when she says you are the smartest boy in the world and that your @$$ is special and different from everyone elses.

Re:Google's requirement of academic background

[b0s0z0ku]

you are a "collage" dropout

No need to be snarky about spelling, BTW. Plenty of people who went to "elite" schools spell worse than the OP, plus typing (and spellcheck) mistakes can easily be made.

I'd say, mod parent down, but the rest of the post is actually of decent quality and makes some valid points.

-b.

Re:Google's requirement of academic background

[b0s0z0ku]

You are a loser. You can't even spell "collage dropout" right. If there is one thing I can't stand it is when pretentious dropout snobs start complaining about nobody hiring them because they don't have a degree. The rest of us software engineers had to suffer through that bull before we could get a job and so should you.

Pretentious snob? Pot. Kettle. Black. Apart from the spelling error, the rest of his post was well-written. It could have been a spellcheck thing, a simple typing mistake, or someone not natively speaking English. Interviews should test education and knowledge, not whether someone finished a certain college. There can be many reasons for not finishing university -- illness/injuries, family poverty, needing to take care of an ill family member, to just name a few.

If someone gained a lot of knowledge *without* a formal education setting, they deserve even more credit for their achievements, IMHO. And, BTW, I've known fools with lots of formal education and some really smart people who never finished high school.

-b.

Re:Google's requirement of academic background

[dubl-u]

So, is it true that absolutely *no* collage dropout can be considered a genius these days?
The fact I've been a self taught workaholic software engineer since an early age doesn't count at all?
Is it my fault for starting a career and making money instead of wasting my time over a pointless CS degree?

As somebody else pointed out, their hiring goal isn't to get every good person possible. It's to avoid getting any bad ones while still keeping up a good hiring rate. The correct strategy there is to downcheck people for pretty much any reason they can find.

The founders were both in a top-end CS PhD program when they started Google. Like everybody else, they have a bias toward hiring people like them. Part of that's irrational monkey bias, but part of it makes a lot of sense: it's easiest to evaluate somebody a lot like yourself.

Further, Google is probably one of the places in the world where a super-solid CS education matters most. For your average professional programmer, Moore's Law covers up a lot of flaws. But when your code is going to run on 100,000 boxes or more, a deep understanding can easily save many times your salary.

And beyond that, just the fact that they are filled with eggheads means an egghead background means you'll be able to communicate much more effectively with your colleagues.

So you shouldn't take it personally. Google is what it is. Like, say, Walmart, they've done a good job holding on to their roots and turning that into something very successful. That you don't fit in at Google (or at Walmart) is more about them than it is about you. So don't sweat it.

Re:Google's requirement of academic background

[Nick Number]

What just because you think your smart you don't have to play by the rules?

Granted I learned almost NOTHING during my 4 years in school but I played by the rules and got that piece of paper, which is why I am in the game, and your still living with your mom because you believe her when she says you are the smartest boy in the world and that your @$$ is special and different from everyone elses.

Ha-ha!

Re:Google's requirement of academic background

[tnk1]

Honestly, you'd be working for people who did the Stanford PhD thing and got rich doing it. Those people only want people who they know how to work with, ie. other PhD types with a similar background.

Google, contrary to the way that they make it seem, wants people trained in a very regimented way. Instead of insisting on strict hierarchy and things like that, they insist on people coming to them regimented from the beginning, that is to say, they all have generally had to adhere to the discipline of graduate level education.

In short, Google wants professional grad students. Grad students have knowledge that is up to date, they tend toward academic questions (which is why the interview sounds like the SAT or GMAT), they are used to working long hours for little (or no) pay, and they are idealistic enough to ignore certain pragmatic objections or limitations to what they are doing.

Actually, its a reasonably good recipe for success... until you run into a situation where you hit a disadvantage that all of the monoculture shares. When that happens, it can be catastrophic because there is no one there who knows how to deal with it.

They might have you believe that there is no downside, but the fact is that with a monoculture, you get more done with less culture clash, but you sometimes find that you simply end up running headlong into a specific disaster which people from a different culture may have prevented you from having to face.

That's why many companies have development and operations organizations that seem to clash constantly. The reason for that is that development likes getting the core job done so that they have a product to release, but the Ops people know that they have to run it for the next ten years after the developers move on to working on Web 9.0 and want to forget all about what they pushed out the door.

Google, with its emphasis on new products all the time makes me wonder what their Operations teams deal with. Are they forcing good habits on the grad students, like documentation and good alarming, or are they just enjoying their paternity leave, personal swimming pool and fembots while a huge legacy problem creeps up on them. Google is still a pretty new organization that is the place people want to work at, but what happens when they become AOL, or Microsoft, and their talent that wrote all of the orignal stuff runs off and leaves the next generation with indecipherable processes run on top of TCL?

Re:Google's requirement of academic background

[bclark]

Just to chime in with some more evidence to support you on this... in my job search for a full-time developer position after graduation, I interviewed with about a dozen companies and sent my resume off to at least thirty. Google was the only one that required that I send them a copy of my academic transcripts as well.

That's what tags are for

[Quince alPillan]

I'm missing the googleisgood and googleisevil tags already.

To answer your question

[portwojc]

How many bread boxes could you fit in an airplane?

As many as the airplane could hold.

Re:To answer your question

[VinB]

Depends. Do the bread boxes have to be in a useable state when removed from the plane?

Re:To answer your question

[afxgrin]

How many bread boxes could you fit in an airplane?

Heh, I kept thinking "Depends on how many you're allowed to break." :-)

paid paternity leave

[appelsiini]

Paid paternity/maternity leave is common practice for everybody in Scandinavian countries (finland, sweden, demark, norway, iceland). What's the fuzz?

seems I'm not alone

[jilles]

Google has basically been approaching lots of people more or less randomly. Including me. Twice so far. I wouldn't actually mind working for a company like Google but I'm not likely to respond positively to random recruiting attemtps.

So why does it not work with people like me? Well very simple. I don't do job interviews. I get invited to discuss specific, custom job descriptions matching my CV & ambition level. We discuss the proposal and then I either accept it or not. I suspect it is like that for most people with a decent level of competence in our business. If you want to hire me, you will need to convince me that you are any good and that it is a substantial improvement over my current job.

If you are going to contact me about a job offer, it had better be specific & well aligned with my interests otherwise I'm not likely to be very enthusiastic about the whole thing. Also I prefer to not deal with HR other than discussing technical details on contracts. If you want to hire me, make sure I talk to the right person right away and don't waste my time with people not capable of telling me anything useful.

Both times I was approached by Google, the person in question hadn't read my CV (on my website); was not aware of my research career (likewise) and did not have a specific job in mind. On the contrary, the first time I talked with a Google HR person, the person projected a months long process with lots of interviews after which I should count myself lucky to be allowed an unspecified job at an unspecified location for an unspecified amount of money. Needless to say I politely declined because if they didn't have anything specific to talk about, our conversation was quite pointless & definitely over.

Re:seems I'm not alone

[MikeBabcock]

I too have been randomly contacted by a Google recruiter. They were however aware of my Slashdot postings and my website. They also had two specific jobs in mind for which they provided links to descriptions. That said, I live very happily now in Ontario, Canada and don't want to move to their California offices where the jobs were. I wouldn't mind working at Google at all, but I do have a very comfortable job where I am now with a good boss and established customer base.

Re:seems I'm not alone

[Sax Maniac]

So right. I get mails all the time from various companies. I tell them point-blank that I'm happy at my job and I'm not interested in applying. You can recruit me, which means it's your job to convince me to work for you. Usually I just mail back my current salary times 1.5, and that's enough to shut them up.

It's sort of like those pre-approved credit card offers, which invariably say "you're conditionally pre-approved*"! Which means: absolutely fucking nothing.

*based on your current income and debt levels.

Google-y

[SilentSheep]

Did all this mention of Google-y make anyone else think about cricket? Or is that just me?

Re:Google-y

[rbp]

It makes me think of Ned Flanders... :P

Want To Work At Google?

[jmenon]

No thanks. I like having a life of my own.

Uh.

[Anonymous Coward]

No.

7 digit vs. 8 digit ?

[Ihlosi]

will receive one million eight-digit phone numbers through a TCP stream which you shall sort in RAM.

Hm, for 7-digit numbers this could be done with just 1.2 MB of RAM, but for 8 digits ? I'd say it's not possible in every case. If you have a lot of contiguous numbers you could get away with storing just start and end numbers, but for a totally random selection you'd need more RAM. Or am I missing something ?

Oblig. Dilbert

[megaditto]

PHB's answer:

We have enabled knowledge-based decision making based on real-time information by implementing an enterprize resource management system.

The King interviewing prospective Court Jesters

[justthinkit]

Sounds to me like Google is fishing the global talent pool for the one-in-a-millions who can help them with their algorithms. This makes sense from Google's point of view in that search/storage algorithms are all that separate them from MSN. Or Altavista.

Personally, I don't care for their spammish approach and would not try very hard in any such interviews. Putting a lot of energy into one of them would be like staring really really intently at the lotto numbers you just picked.

Why do tech companies suck so badly at interviewing?

The physics approach to the marble question...

[sczimme]

"Imagine you have two marbles and a 100-story building. You are told that the marbles will break if they are dropped from a certain floor. Figure out a way, as effectivly as possible, how high you can drop the marbles before they break. Remember, it could be the 1st floor, it could be the 99th."

That's easy! First, assume a spherical marble of uniform density...

Easy - 2 ways to answer all the questions...

[billybob_jcv]

Answer method #1: 1) Google for the answer. 2) Google for the answer, right mouse-click, view source, ctrl-C. 3) See #2. Oh, you can't find the answers by googling? You could if you hired me... Answer method #2: My rates are $300/hour, I'll send you a SOW.

Yeah well, I warned them about it

[SmallFurryCreature]

It just had to happen, you put the interview rooms on the first floor and no elevator and BAM, there go your hopes of any >30 making it to the interview. If only they had made it uphill both ways through a snow storm. That would have been a cakewalk.

Solution for problem 1

[Opportunist]

2 and 3 are fairly straightforward and sound like something I've read back when I was learning sort algos. The first is intriguing.

The basic problem is that with the second marble you'll have to go sequentially story by story since you cannot skip, or you won't know whether you hit the right floor or one of the floors you skipped would have been the right one. So the general algo would be to start at floor x and increase by x floors until it breaks, then go back to your last "known good" floor and go sequentially up from there.

How it is implemented from there depends on whether it's a one shot experiment or whether you have a lot of sets of 2 marbles to test. In the latter case, it also matters whether the average density of said marbles is equally spread over the spectrum (i.e. whether there are equally many sets that break at floor 1 and at floor 50), whether it follows a gauss bell (i.e. you have a lot of sets that break at or around 50 and a lot less that break at 1 or manage to work up to 99).

In general, though, with no special cases applying, the best increment would be 8, 9 or 10, each with a worst case of 19 tests.

Easy

[Grindalf]

Keep on on 6 month trial and pull the trap door if they don't knuckle under! Grinbert...

Depends on the school...

[mario_grgic]

It may be true for some schools, but for some others it sure does.

Oddly enough, the first interview question

[Anonymous Coward]

happens to be:

You look down and see a tortoise. It's crawling toward you. You reach down and you flip the tortoise over on its back.
The tortoise lays on its back, its belly baking in the hot sun, beating its legs trying to turn itself over but it can't. Not without your help. But you're not helping.

More universities need co-op programs

[euri.ca]

That's why I can never understand why more universities don't have co-op. At my university, anyone who was serious about being employed someday alternated school and work every four months. Work was anything from make-work projects like rebuilding our school's webpage twice a year to serious positions at MS, Google, and Amazon.

It means that our graduates are in demand despite it being a pretty lousy educational venue (it also meant that I can grok algorithms despite being a math major -- try finding high paying work in pure mathematics :)

Google's bennies are not that great

[assantisz]

If you really want to work for an employer that gives great benefits you should look into education or the public sector. I work for a private university in NYC and the benefits I get are unbeatable. Sure, I don't get paid a bonus (and we don't get free food with the exception of certain kinds of meetings) but free education for the entire family, a retirement plan that requires me to put in 5% of my gross while they match 10% of my gross, up to six weeks of paid maternity/paternity leave, ability to get whatever gadget I'd like to "get my job done", and job security make it well worth it. The salary is not that bad either (a little over average for a Sr UNIX system admin in the metro area). Anyway, the random e-mails that Google's recruiters send out are a little off-putting. Also, isn't it a little weird that when you are about to reach your fifth year of your employment with Google just when your stock options are abot to vest HR will be bothering you about how happy you are etc. etc. If you really have to try so much something is not quite right. Happiness test? Please!

Re:Google's bennies are not that great

[kook44]

I have to agree here. I work for a big 'ol boring publishing company as a software engineer. It's not the "sexiest" place to work. No, there's no free sushi in the caf. But, they pay me slightly above market, they have a liberal telecommute policy, generous time-off, have great health benefits. I sometimes think about sending my resume to Google, but then i think - do i really want to be part of that elitist techno-snob culture? (I have a degree from a state college woud they even consider me in the first place???) And what am I really getting for it - looooong hours and the ability to _tell_ people i work for google. That's really all it is. I mean, just how much more do non-managers make at google than other companies?
I think I'll take my nice work/life balance with a pretty darn good, although not earth-shattering, salary.

Re:Google's bennies are not that great

[Anonymous Coward]

I mean, just how much more do non-managers make at google than other companies?

On average, about 10% less than the industry average, according to exit surveys.

Re:Google's bennies are not that great

[t0rkm3]

In my experience, CA companies in general, and companies with large names in particular are not very generous with benefits. The name on your resume is part of the compensation.

Luckily, I now work for a Fortune 10 company whose benefits are outstanding. They are an oil company with a long heritage of treating their employees right. A friend of mine worked for them back in the day, and his AC died in midsummer in TX. This company sent out AC repair guys to their house and had the AC repaired, on the company's dime. That's what happens when you have a network of people who care about you and yours.

Some of that has been scaled back, but we do have free athletics (basketball court, 8 lane Olympic length pool, well provisioned weight room, hot sauna, whirlpool spa), savings match plan at 9.25%, bonus up to 15%, health-care, vision plan, flexible spending plan matching, and a slew of other benefits including use of the facilities (athletic and health-care) if you retire from the company for the rest of your life.

They also recognize the value of hiring experienced employees. I was hired on with 12yrs credit toward retirement and vacation accrual.

That's why I moved back to the land where people still actually care about you...

Re:Google's bennies are not that great

[naoursla]

Schlumberger is a fantastic company. Although the cancer rates in Houston are pretty bad.

Am I the only rejectee who is not bitter?

[minotaurcomputing]

I also interviewed with Google... did the 3 phone interviews, wacky questions, flying out to CA at odd hours, and ultimately got rejected. However, I think it was overall a great experience for me. I do not feel bitter about the process and in fact feel that it probably helped motivate me to become a better computer scientist. The impression that I got from its employees is that they are truly in love with computer science and I would do well for myself to take a similar approach to my craft.

In fact, I was asked soon after my Google experience to help interview a group of candidates at my current company, and I decided to take the Google approach. While there were very few people who were able to ace the battery of questions, there was an interesting effect. That is, you learn very quickly by asking those types of questions the kinds of people that YOU would want to work with. There are those people who simple brush those questions off by saying, "I don't know that... I've never needed to know that..." and there are those who try to work through the problems and seem enthusiastic about learning the solution. Which of those two would you rather interact with on a daily basis?

-m

I *aced* an interview with Google a few weeks ago

[euri.ca]

My interview went quite the other way, possibly due to my ace interviewing skills. (note, mostly sarcasm)

3rd question: store info in the address space

[thbb]

3rd question: the trick lies in using the address space to hold the information on the 1st digits of the phone numbers, which allows you to strip down the 8 digits phone numbers to a number of bits that is small enough to make them all fit (i.e., 16 bits of storage per phone number).

You have 100M possible phone numbers. To hold a phone number, you need a 27 bits integer. So, as you read the phone numbers you start by converting them to 27 bit integers.

Next, you need to get rid of 11 bits in each phone number to be able to hold them all, by storing each phone number in a block that corresponds to its 11 first bits: it is the address of the phone number that gives you the 11 first bits.

The first section of your memory (the first 40kb) are arranged in a table of 2048 (2^11) entries of 20 bit pointers each that point to the address in memory of the block of phone numbers that start with 0x0,0x07ff... up to 0x07ff^2 (=2^27-2^11).

As you receive each phone number and convert it in its 27 bits representation, you perform:

++blocktable[curnumber>>0xff]=curnumber

plus some bookkeeping on the blocktable to avoid overflows between neighbouring blocks.

Once you've absorbed the whole data set, you can output them by first sorting each block using a "inplace-guaranteed" sorting algorithm such as shell sort on each block:

for i in 0..2048 {
        shellsort(blocktable[i],blocktable[i+1]);
        for j in blocktable[i]..blocktable[i+1]
                out << convertToNumber((i<<16) + blocktable[j]);
}

This means you have a tad more than 8kb left in memory to store your program and the program's stack... seems enough to me, if you know assembly language...

PS: it occurs to me you don't have to use a split 11/16, a split 14/13 would let you save more memory...

Isn't it about time Google got their own icon?

[turing_m]

Yeah, I know, Slashdot uses Google's default logo. I'm no fan of MS, but surely Google must be getting omnipotent enough to deserve a special icon all of their own, to complement the Gates as Borg MS icon?

Only 2 marbles..

[Hyperhaplo]

The first question:
"Imagine you have two marbles and a 100-story building. You are told that the marbles will break if they are dropped from a certain floor. Figure out a way, as effectivly as possible, how high you can drop the marbles before they break. Remember, it could be the 1st floor, it could be the 99th."

First, state that 'this must be done so that an answer is found using only 2 marbles.
This means that when the second marble breaks you must have an answer.

Try this:
1. Go up 1 floor. Drop a marble. If it breaks, the answer is '0 floors' (special case! )
2. Until (the first marble breaks)
      Go up 3 floors, drop one marble (and retrieve it if it doesn't break)
      If it breaks, go down 2 floors and drop a marle
            If it doesn't break go up a floor and drop a marble

This will check for floors 1, 4, 7, 10 and so on.
When the marble breaks, you check current floor -2. If it is ok, you check the -1. From this you can tell which floor the marble will break on.

Takes 4 tries to get check level 10 though, and 22 tries to get to 100.

Any thoughts?

In other words...

[paralaxcreations]

Google-y is defined as somebody who is fairly flexible, adaptable and not focusing on titles and hierarchy, and just gets stuff done.

...we're looking for worker ants.

I have no experience with google, but it is my experience elsewhere that in HR, "fairly flexible" means "will work long hours without compensation," "adaptable" means "will not make a fuss when his/her review date comes and goes without action" and/or "will accept that any bureaucratic injustices with the company do not exist, and if he/she has a grievance, it is actually the one filing the grievance who is in the wrong". And "not focusing on titles and hierarchy"...well that just means "not focusing on titles and hierarchy while those above him/her do."

Again, I don't know much about Google in specific, but this is the way HR tends to word things in most other companies.

But no, I'm not bitter at all.

Dogs at Google

[pestie]

Isn't Google one of those "dog-friendly" workplaces, where people bring their goddamned pets to work with them? That alone would be enough to keep me from ever applying for a job there. I'm allergic to dogs, but I also just dislike them. The company I work for now is dog-friendly and around Christmas a couple of people got puppies. It was so obnoxious I wanted to stab myself in the eye with a fork. They made a racket, they stank like ass, and they pissed and shit on the floor, and my allergies kicked into overdrive. There were parts of the office I couldn't stand to be in for more than a minute or two. So, yeah, I'm leaving my current job (not because of this, but this didn't help) and I'll make very sure I don't ever work in a "dog-friendly" office again.

Re:Dogs at Google

[Anonymous Coward]

The dog policy is discretionary - if your office-mates are offended by/ allergic to/ simply dislike your dog, they will most likely let you know and ask you not to bring him/ her in. I have yet to hear of an instance where this was met with anything but an appropriate response.

Aren't you 1 too high?

[Anonymous Coward]

If the first marble breaks on the 100th floor after going up in ten steps, then you'll take the second marble up from steps 91, 92, 93, 94, 95, 96, 97, 98, and, finally, 99. That is only 9 more attempts. Thus, though your math is correct in determining that you need to go up in steps of ten, the actual most efficient number of marble drops is 19. In fact, you could achieve this by taking the first marble up in blocks of 9, 10, 11 or 12 steps. Then the second marble step by step to a worst case of, respectively, 10, 9, 8, or 7 steps.

Like IIT?

[Anonymous Coward]

I know someone who went to IIT.
He thinks he's the god of code. He no longer works here. Anyone who has been in his code has re-written it from scratch as the only way to get out the bugs.

3rd question - I think I've got the answer

[harry666t]

All phone numbers are unique, aren't they? So we won't need to actually do any sort of sorting then.

Create an array of bits, call it A*;

Label L;

Read next phone number, store it in P;

Mark A[P] as true;

If there are any numbers left, goto L, else, continue;

Iterate over A, sending back every I for which A[I] is true;

Now, can I work at Google?

Re:3rd question - I think I've got the answer

[laffer1]

1. If they asked for a phone number from a customer, 2 or more people could live at the same household and use the same number.
2. They may want all the numbers in the same area code together. If you were distributing a call list for sales people to call, you might want to break it up by region.
3. Just because something is unique does not mean you don't want them ordered.

Re:3rd question - I think I've got the answer

[ps236]

Now, can I work at Google? Nope, fraid not.

How big does your array 'A' need to be?

How much memory do you have?

...

Lots of other people have come up with this idea and discarded it because it doesn't work.

Either Google asked the question incorrectly, the person posting the message remembered it incorrectly (if you had 12MB, or if they were 7 digit numbers your answer would be right), or it's a LOT harder than any question I'd expect to be asked in a phone interview. The other two questions are reasonable, but this one has no decent answer. There are answers (using compression, storing deltas, using memory partitioning etc) but they'd be horribly inefficient to sort and quite complex. If you HAD to do it, you'd probably have to come up with several possible methods and try them out to see which works best, as they're all going to be slow, but it isn't obvious which method would be the least slow. (In reality, you'd go out and buy more memory and/or a hard disk...)

No ambition

[Anonymous Coward]

So if you wanna have a title or go up in the company you may shut up now! what a great place, stuff done, shut up and code! thats what i see in that post

Google=Bulls**t!

[Newer Guy]

I looked at Google and they won't even consider you without an advanced degree. How can thay claim to be SO entreprenaurial when they EXCLUDE half the entreprenaurs out of hand? There's MUCH more to life then "book learning", something that Google (obviously) hasn't figured out yet.

I was told by one of my mentors (a PHD that worked for Harvard/Smithsonian Astrophysics - He has an orbiting telescope named after him) that "sometimes schooling INTERFERES with your education". I guess that Google hasn't figured that one out either!

Pathetic.

under thrity years old

[peter303]

Tremendous ageism at Google.

Tangible vs Intangible

[Anonymous Coward]

Google is trying to quantify something that is somewhat intangible, which for a lack of a better term I will call "getthingsdonedness". In other words, they want people who are not number crunchers, but who are idea crunchers.

This is very, very hard to do, but having more money than God helps.

Solving Problems for Free aka Interviews.

[Anonymous Coward]

My dad told me this story long time ago. I didnt think much of it, until I grew up. He told me that Japanese companies would offer good salaries to engineers, and just like Google, THEY would contact American engineers and offer them good salary and positions in their famous company. My dads friend worked as an engineer back in the day for Xerox. So one day he had a call from an American speaking person who was in town, and would be interested if my dad's friend would be interested in the interview.

  Long story short, he arrived and met the interviewer. He was really nice, showed the job postion, and credentials. They had short talk, and somewhere during the talk the interviewer started to ask technical questions. Liking the challange of those engineering questions. They were in his field, he was according to my dad his friend was fond of engineering puzzles. But then he suddenly stood up, and left. He told my dad "Doug, (my dad) " he said "it wasnt interview, but industrial espionage at worst, or free work at best" What happend is that the interviewer was asking some fundumental questions for Xerox technology, and how to solve it. Instead of paying people money to do research for them, or pay for royalties, they would set up "interviews" and ask creative people "under the guise" of interview to solve them. That was 1970's or so.

  I wouldnt be surprised to see Google doing that the same way. Get people to give them creative ideas for free by pretending to give you a job offering.

  Thats my 2 cents, for what it is worth.

Amen bro

[melted]

This takes years for some to understand. Ask and ye shall receive. But you have to ask, no, scratch that, demand career advancement. That's how things work around here in the US. Just doing your job doesn't get you anywhere. You have to also act like a primadonna and tell everyone how cool you are, otherwise someone else will do it instead and get promoted.

Two Kinds of Judgement

[alienmole]

You might be interested to read Two Kinds of Judgement, which discusses this issue in some depth and explains why you shouldn't take such rejection too personally.

Re:Two Kinds of Judgement

[Anonymous Coward]

I was probably one of those few who had 3 phone interviews (+3 onsite) (for a position that was offered, but I couldn't join as it was less relevant to my qualification) and then 3 more phone interviews and then on site staring at me sometime sooner...Every time, every parameter was different, but the interviewers in all cases weren't arrogant, but were pleasing to talk in all of them..

The "Fit Factor" goes both ways.

[emil]

I was recently interviewed by google. I had three technical interviews over the telephone, and for each of these interviews, I spoke with at least two google "recruiters" at each stage, and I would describe this process as extremely disorganized.

At one point, one of these technical interviews was canceled on a half hour notice. When I spoke to the technical interviewer the next week, there was no apology even though I had taken time off work (and I work contract, so that was money out of my pocket). I was positively astounded that any company could behave this way.

My questions about the process became a lot more pointed after this "debacle." I learned that problems with the relocation program were common, and in the end, I didn't trust these people to sell my property and move me, and the job wasn't the best fit anyway.

Some people may have great luck with google, but I would recommend that anyone look carefully before they leap. Despite my initial enthusiasm, they did not earn any special consideration from me.

Re:The "Fit Factor" goes both ways.

[cthulhu11]

I had a phone screen with them. The above article's claimed criteria weren't pursued at all -- instead the guy on the other end obsessed about trivial details of technologies unrelated to the job I'd applied for.

Re:The "Fit Factor" goes both ways.

[loki1978]

I had one technical interview over phone (in English, but thats no problem) and then one interview day with
2 interviews, by two different people each, each one hour long (also both in english).
No sign of disorganization, but of high professionalism.
The interview site was a big buisness job recruiting agency.
During the whole process, from first call to welcome me to the interviews and setup a date for the phone interview, to the last call to say they are sorry but i will be set on a waiting list for the job, a personal contact person has always been avaiable for me.

Re:The "Fit Factor" goes both ways.

[emil]

Obviously, we went through very different google interview processes. I didn't experience any "oddball" questions, but I had the intense drilling over unix process creation/destruction, shell usage, sorting, etc. I don't know what you faced, but google needs lots of different people, and they obviously don't hire them in a uniform way.

Re:The "Fit Factor" goes both ways.

[DirtyAmish]

Sorry to hear of the crap time you had. I understand the taking off work thing as I used to be a contractor also and something similar happened to me once. Luckily, I am with a great company now, Navigant Consulting with some/many/all of the same perks as Google. Holler if you need a hook-up! They have many available positions all over the world.

Sell 1 share of google...

[billybob_jcv]

...buy a sack full of stainless steel ball bearings, and it won't f'n matter how high you drop them.

Being Googl-y is in and always has been

[wsanders]

The unsocialized rude punk who showed up in the dirty T-shirt only got hired between 1997 and 2000 during the boom years. Since the boom years represent of a large proportion of total /.ers experience, it may seem like those punks had cred.

But the reality is that Google's hiring practices and work environment aren't all that different from the Silicon Valley pre-boom good old days. I worked at Sun from 1991 to 1996 on and off, and Google doesn't sound a whole lot different from Sun in those good old days. They are even in the same buildings - you could easily go sailing or windsurfing on your lunch hour then, and you still can, now.

Re:Being Googl-y is in and always has been

[LordMyren]

if any dirty unsocialized hacker punks are looking for work in denver or boulder, we're hiring. ;)

seriously, your capability to deliver to the client are all that matter. you can be awful in every way but if you can magically make clients happy it just does not matter.

Passe

[Anonymous Coward]

It would have been cool to go work for Google circa 2001. Nowadays, Google is just a big, fat corporation that gobbles up other big, fat corporations in the quest for the almight buck. The traits that once made it cool diminish by the day. Ski trips and free sushi are wonderful until everybody starts whipping out their Blackberries and inwardly bemoaning being away from work. Google was an exceptional startup, but it's no exception to the rule that startups becoming increasingly structure, corporate, hierarchical and boring and they grow.

Phone Interview Last Week- They Suck

[ShrapnelFace]

I had a 4.0 at my University, a 2.5 at the J.C. I transferred from. The problem with me was that I was an idiot for 2 years and didnt go to class. Then I cleaned up my act, went to school and kicked ass. The damage was so bad, though, I could only raise myself up to 2.8.

I went to a small university out here that features professors from Berkeley and Stanford. We use the same exact curriculum that they do, the professors teach part time there and part time at our university because it gives them more hours and a range of flexibility.

Google took one look at my overall GPA and said "sorry- you dont meet our academic requirements." I tried tot ell them that my undergraduate GPA at the University was 4.0, but they wouldnt have it.

I am a top person in my field, working at companies like Oracle, and have never been less than #1 on my team since graduating college.

Companies with these unreal ideas in their head tend to do themselves in. I am the 4th person I know who have had this happen to them after being approached by Google.

They came to me- not the other way around. They have some really dumb hiring practices over there. The academics they hire arent necessarily the best employees out there.

Re:Phone Interview Last Week- They Suck

[ShrapnelFace]

Typo- Where I say 2.8, I meant 2.5. And that is in reference to my GPA from the Junior College. I did 3 years at the University with a 4.0

Whatever- I know a Naval Academy Graduate that got turned down with a 3.5, and he was never the idiot I was.

They start with GPA and work from there.

Questions to ask Google

[Animats]

What Google wants are people who won't ask questions like this:

• How can you justify a P/E of 47 when your basic business, search, is a mature industry?
• Is there still a separation between editorial and advertising at Google?
• Is revenue per employee going up or down?
• Is any product line other than search making money?
• Is the capital investment in new data centers really paying off?
• Do you think the DoubleClick merger violates the Clayton Act? Why or why not?
• The building we're in used to be occupied by SGI. What did they do wrong?

Re:Questions to ask Google

[evilviper]

How can you justify a P/E of 47 when your basic business, search, is a mature industry?

Search was a mature industry BEFORE Google was even invented. Guess what? "Mature" industries can be revolutionized at any time.

Perhaps more importantly, Google's basic business isn't search, it's advertising, which NEVER can, and never will mature. Advertising has to constantly change, or else it quickly becomes worthless. Google (adwords) was the most recent change to web advertising, and it's certainly causing a boom.

That said, I certainly believe Google is massively over-valued due to the current insanity of the stock market, but that's hardly unique to them. Like the years before good old depression, stocks are being sold like a massive pyramid scheme, and the whole thing is headed for one extremely massive correction, when any one tiny little hick-up suddenly causes a large number of people to wake-up to the reality of their nearly-worthless investments.

Is any product line other than search making money?

Adwords, of course.

I wouldn't be surprised if several others, like Google Earth are at least turning a small profit.

Re:Questions to ask Google

[Anonymous Coward]

Do you really think that PD controllers are non-obvious and patentable just because they are used to control humanoid figures?

Alright! But what helps?

[gorrepati]

Ok I see a lot of comments pointing out Google' flaws. A google recruiter approached me too - And my experiences were not that different. Heck the questions were pretty much same.

What I would like to hear is "What does it take to get in there?". And I am not looking for what's already laid out in the article. Some of these questions are not intended to be solved on the phone(atleast not in their entirety), unless you heard about the problem before. Did you all Googlers solved them on the phone right away? For heaven's sake give us some feedback on the interview. And not the crappy "Wow, we are so cool" messages and pompous advertisements. Until then, I am not applying there again, because I dont see how it could be different this time around.

Re:Alright! But what helps?

[Anonymous Coward]

Duh, you're supposed to google the answers.

I interviewed at Google last year

[xpsartanx]

I submitted my resume through a friend who was working for them at the time, he ended up quitting because he couldn't stand the people he was working around and his boss wouldn't do anything to help the situation. I didn't actually find out about this until after I had an in person interview.

I got an email from one of their recruiters about 5 months after I submitted my resume and she asked if I could do a phone interview for a data center technician position. Basically I would keep the hardware up and running, replace ram, hard drives, etc. I got a full position description, gave my salary requirements, and set up a time. I did the phone interview after my normal work hours, they were very flexible which was nice so I wouldn't have to do it on company time. At first it was general questions about how would you troubleshoot these situations like a machine keeps turning off on it's own, why? Or the machine won't power on, why? etc. Easy stuff. Then he started asking stuff I didn't know such as how to check the hard disk speed in Linux, how would I change user permissions if I wanted a group to access a file, but an individual in that specific group to not have access without creating a new group. I just said I didn't know, but I always look for help online if I come across something I didn't know. He said those answers were fine.

3 weeks later I got another email asking for an in person interview so I thought sweet, I might actually get to work for Google if they want to see me in person. So I set the day, had my sister help me pick out a new shirt and tie (I'm partially colorblind and was looking to make a good impression at least in my wardrobe). I drove an hour and a half to meet with them at a hotel conference room after asking for a 'vacation day' at work. I got there 15 min before my scheduled interview time and went into the hotel and said I was there for an interview with Google and they pointed me to the conference room. I waited for 45 minutes before anyone from Google showed up. Turns out they took a long lunch and forgot about me. Great. Oh well whatever, let's get the interview started.

Fun stuff now, I was told I was going to interview with one person, I ended up getting interviewed by 6! Two teams of three. Not what I expected, but I went with it. Half way through the first group one of the interviewers happened to mention 'Ok so why did you apply for Data Center Technician Temp'. I said 'whoa wait, temp?' and he said 'yes, we are temp to hire'. I told them that was first time anyone had mentioned the word temporary to me and they all got a puzzled look on their face. Even the job opening on their website didn't say temporary, it said permanent. That soured me. I went on with the rest of the interview. At the end I felt it was a huge waste of time and a few weeks later I got an email saying thanks for your interest in working at Google, but your background doesn't match the position. Which was their way of telling me I wasn't qualified for whatever reason.

All in all I felt the whole interview process was shady.

My Google On-Site Interviews

[Anonymous Coward]

I flew in for two on-site job interviews at Google in Europe. Like others have said before, the interviews mostly focus on problem-solving skills. The people doing the interviews were smart and fun to talk to, even when I did not find the answer to all questions. I found the questions fair and actually enjoyed this part.

But being on site, I also wanted to see a bit more, like the actual places where people work. It turned out that this wasn't possible for seccurity reasons (according to the HR person). Despite being flown in I saw little more than the conference room in both cases. There was almost no opportunity to experience the Google feeling. Also, nobody of any importance ever talked to me in person. All group managers and up were only available on the phone or video conference, where they were actually very helpful. The discussion of the work was vague (which did not bother me) but I would have liked to know how working at Google actually feels: how big are groups, how much discussion versus coding goes on, how many people share an office, and so on. I asked again on the phone about actual work space and it seems that they have mostly open floor plans and some cubicals but nothing specific emerged. Overall, I find this disturbing, because at some point I want to be convinced that Google is the right place for me and Google should present all the aspects that are hard to convey over the phone. And since Google interviews so many people I find it hard to believe that they don't have guidelines for the interview process that cover these aspects.

...and god help you...

[Anonymous Coward]

...if you get hired as a consultant by an incompetent know-nothing jagoff from one of said "exclusivist" universities who exudes so much Googliness you throw up a little every time you show up knowing the other contract coolies are being paid less than you and treated with the same patronizing b.s. they seem to think well be made all better with a free Powerbar and cappuccino as you bristle over the low-ball rate you threw out to get their name on your resume and now realize the only reason you got the job was so said moron could get /your skills/ on /his/ internal resume (as you eye the heavily bookmarked stack of relevant 'XYZ-tech For Dummies') and now you wouldn't consider the project for less than triple your usual full-freight rate if only to compensate for said idiot CONSTANTLY acting like he's doing YOU a favor.

Allegedly and hypothetically speaking completely in an abstract sense of possibility not to imply any of that would ever happen with a better bunch of people.

HS dropout interviewed 4 sw eng

[c0d3r]

I'm a high school drop out with no degree and I interviewed with Google for a sw eng position and may interview again.

My interview question

[c0d3r]

The interview question that I thought was the most fun was:

Given a function bool validWord(string word) write a procedure that takes phone numbers dials as input and returns all of the possible valid words that can be made up all of the possible text sequences for the selected numbers (sort of like text dialing). I got it right with a recursive search.

I disagree for one reason

[BitterAndDrunk]

Google contacted him - he wasn't seeking a job with Google until they approached him.

That should be a different interview dynamic, IMO.

community vs Yale

[ushering05401]

I grew up in Southern California where there were both many prestigious universities and many highly regarded community colleges.

The community colleges were staffed by people with degrees & years of workplace experience.

The prestigious universities were staffed by people with degrees & years of academic accomplishment.

My friends who went to the community colleges & worked intro level positions in their chosen field to pay for it are doing better in the workplace. Some of my friends who went to the big schools are still working in their chosen fields.

Degrees are an important metric. Who you are learning from, however, has everything to do with your effectiveness in the workplace.

Regards.

Requirements?

[bill_mcgonigle]

Maybe it's my line of work, but I would have answered each of those questions and other ones I've heard asked here basically the same way, "I don't know - what are your requirements in terms of best/worst/average-case strategies and how many resources do you have to throw at the problem?"

'cause most of the questions I've heard retold here don't have an ideal solution for all cases, though academics tend to think that way, and Google has been accused of preferring academic types.

I'd guess if I answered, "your question annoys me and sounds like a waste of my time" that wouldn't have scored too many points, eh?

Re: parent has the correct answer

[Anonymous Coward]

Drop the first orb from floors 14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99, 100 ...
I have yet to see a better answer, but would love for someone on /. to find one :)

Yes, what you presented is a version of the optimal sequence. Another optimal sequence is 14, 27, 39, 50, 60, 69, 77, 84, 90, 94, 97, 99, 100.

The fact that the sequence is optimal can be proven in O(marbles*floors^2) by creating a table of size (marbles * floors) and incrementally finding the best choice for each choice of marbles and floor. We already know the optimal answer for only 1 floor is 1, and the answer for 2 floors is 2 tries. However, the answer for 3 floors is 2 tries as well, because you can start on the 2nd floor, and then you only have to test the equivalent of a 1 story building for either outcome. For each new size of building, look for the smallest combination. Pseudocode:

fewest = height;
  for (i = 1; i < height; ++i)
  {
    br = 1 + f (height - i - 1, marbles - 1); /* e.g. 3 - 1 - 1 = 1 story if it breaks */
    ok = 1 + f (i, marbles - 1); /* e.g. 1 story left if it doesn't break */
    biggest = max (br, ok);
    if (biggest < fewest)
      {
        fewest = biggest;
        choice = height - i;
      }
  }

Below are some solutions for various combinations of floors and marbles. I've noticed that the optimal number of drops can be approximated by taking the ceiling of F(marbles,floors) = exp(log(factorial(marbles) * floors)/marbles). In other words, F(marbles, floors) is the marble-root of marble-factorial times floors.

100,2: worst case = 14 drops, start at floor 14, F(100,2) = 14.1
100,3: worst case = 9 drops, start at floor 37, F(100,3) = 8.43
100,4: worst case = 8 drops, start at floor 64, F(100,4) = 6.99 /* this one is slightly off */
100,5: worst case = 7 drops, start at floor 57, F(100,5) = 6.54
100,6: worst case = 7 drops, start at floor 63, F(100,6) = 6.45
 
1000,2: worst case = 45 drops, start at floor 45, F(1000,2) = 44.7
1000,3: worst case = 19 drops, start at floor 172, F(1000,3) = 18.2
1000,4: worst case = 13 drops, start at floor 386, F(1000,4) = 12.4
1000,5: worst case = 11 drops, start at floor 299, F(1000,4) = 10.4
 
10000,2: worst case = 141 drops, start at floor 141, F(10000,2) = 141.4
10000,3: worst case = 40 drops, start at floor 781, F(10000,3) = 39.1
10000,4: worst case = 23 drops, start at floor 1794, F(10000,4) = 22.1

A couple of notes: First, the variation in the starting floor is just indicative of multiple optimal paths. Second, the fact that 100,4 is slightly off of the value predicted by the formula suggests that my model is incomplete, but it seems to work well as a first approximation. Maybe someone else can provide some insight into the actual formula.

Re: who ware you replying to?

[Anonymous Coward]

After the first ball breaks wouldn't you actually want to go up by 2 each time in the linear part of the algorithm since the break/non break at floor n and n+2 can tell you the answer at n + 1.

No, you don't want to count by 2 after the first marble breaks.

Let's suppose the marble breaks on the first drop, and you've got 13 floors to cover and one ball left. Using your method, we drop from the second floor and the ball survives. Next, we drop drop the marble from the fourth floor and it shatters.

You know the marble survives from the 2nd floor, and you know it breaks from the 4th floor. But would the marble also break if dropped from the third floor? Answer: You don't have enough information to deduce that, and can't find out now because you're out of marbles.