A Wretched Google Interview Experience
symbo1ics.com
symbo1ics.com
When this person got there, two of the people they were supposed to meet with were traveling on business and hadn't notified the recruiter. A third was out sick. The supposed-to-be fourth, now first interview walked into the room and said, "Look, I don't have any idea how to interview product managers, so I'm going to ask you calculus questions", and proceeded to start to write equations on the board. The fifth interview was the first and only that happened AND dealt with product management.
When they got back to NY, this person was notified that they'd been rejected, then notified this was a mistake and they'd have to come back to MTV to redo all of the interviews, including the two that had happened.
Obviously, at this point they told Google to go scratch and went on to do really good work elsewhere.
I've interviewed at and worked for a number very very large companies before, and none of them have been as disrespectful at interviewing and hiring as Google sounds from these stories.
I was heartbroken, and I am sure other people have experienced the same thing.
Hiring by committee :)
Was never asked about GPA. I have no idea why the "no" in committee, but I get the impression that they approve more people than they hire. Moral of the story is probably that the initial approval is not a yes but it just means you passed the technical test.
I have mixed feelings. Would have been a cool place to work, but there are lots of alternatives.
I don't care about it anymore, but 5 years ago when this was my first job prospect out of school, I was really excited.
Yes, they can fill their spots, but the reality is that hiring bullshit means that over time their candidate pool progressively filters to "the people who will put up with bullshit", and while it takes years to filter through, in the end you up becoming Microsoft.
There was a time when Microsoft was the bee's knees and was the elusive dream employer. Then they started various HR initiatives and it became a place that only a certain type of person wanted to work, and the result is the malaise and technology lack of leadership that Microsoft now evidences.
HR as a profession is often a scourge, and the more influence HR has at a company, the more inertia pushes towards decline.
Get your HR droids on a leash, folks, before they kill your company.
They were doing just fine making things like Google Reader.
I suppose now Google is more balanced and their stock is much more valuable but their long term direction has changed significantly. They can now be disrupted.
Isn't that the case already???
Most people joining big web giants I know are generally the kind of people who don't do any great real work but practice hours daily and spend insane amount of time on interview sites, take huge efforts in achieving expertise in one thing and one thing alone 'clearing interviews'.
I'm not defending this practice at all, but I think I can understand it. It sounds like the typical problems involved in scheduling 10 people to all perform together at once. Nobody can prevent people from getting sick. Going out of town and missing an interview is pretty flaky, but it happens. You can look it as "Google is evil and wants to torture candidates" or "people are flaky".
It's certainly human nature to be bitter about someone fucking up an important day for you, but ultimately, bitterness gets you nothing. It's no problem if you want to complain to your friends or on HN, but why not come back for the second try? Your friend could have had another free trip to Mountain View to actually be interviewed properly, and maybe get the job he wanted. (They do pay pretty well at Google, after all; the interviews aren't for some volunteer position.)
(As for the calculus interview, that sounds like fair game. PMs are supposed to have some PM interviews and some SWE interviews, and math is a perfectly acceptable area to ask SWE candidates. It's not where I would spend my time, but that's part of the process that people hate; different interviewers have different preferred questions. I would probably have asked "how do you test that", which would probably raise a few eyebrows in a story like this too. But ultimately, having that understanding is something I value in future coworkers, so it's what I'd ask about in interviews.)
Finally, if you have any questions about the hiring process at all, feel free to send me an email, jrockway AT google.com. I'm not a recruiter, I'm a programmer who cares about making the process work, but I'll try to help you out!
Funny how the only people in this thread defending it are people currently employed by Google. The world viewed through Google Glasses sounds awfully distorted.
Sorry, "it happens", is such a callous sentiment regarding someone's future. "We booked and agreed on a time and couldn't be bothered doing it and couldn't be bothered telling you, either" is outrageous.
Maybe you have been at Google so long that you don't realise it, but this is not a normal or decent way to treat somebody. I can't think of anybody I know who would want to work there after going through that interview process even if they did get a job offer.
If you're having problems with the process, never hesitate to send me an email. jrockway AT google.com.
Interviewers not being on site I can see yes, that can happen and I agree we can attribute that to 'flakiness' if it's a one off. (Although I have to say I can't imagine it ever happening at anywhere I have ever worked, and I've worked in local government, a bumbling bureaucracy if ever there was one).
But failing to return calls just about every single time? Waiting months before getting back to tell somebody they progressed to the next stage or didn't make it? Having to call a friend at Google to find out if you passed the interview or not because they didn't bother to call back? Making snide remarks to the candidate? Just about every account in this thread reveals a similar story of waiting for months to get any reply, not getting replies, not being told how the interview went, not being told why they were turned down. That is systematic and reveals a hiring process that treats people like shit because you can get away with it.
Now, let's say there was some royal but completely understandable cockup where this guy completely spaced that this day was the interview or whatever. Fine. Where was the recruiter in this? Who was in charge of the process, and why didn't they realize that an interviewer was unavailable sometime in advance?
If I get an interview with a company and then just neglect to show up, odds are they will not give me a second chance unless I had a good reason, something more than just "I forgot". Why should things be any different if the roles are reversed?
All my other comment is saying is how to think about the problem from another perspective. You have a lot to offer Google, but Google is not exactly coming up empty on its end. Therefore, I think it makes sense to cut Google some slack. But if you don't, that's your prerogative. I personally don't aim for 100% perfection 100% of the time, but some people do, and that is respectable.
(Oh, and I don't think complaining about the interview on your blog is bad at all. What's "bitter" is refusing to come back for a second try, even though you still are kind of interested in working at Google.)
It's well known both inside Google and outside it that many parts of the hiring process are badly broken. Suggesting that people should just grin and bear such abuse just means the process will never get fixed. While if people just stopped the process if it got silly enough, somebody's bonus would be in sufficient jeopardy to cause some action.
(When I worked at Google I never referred any friends unless they asked me to -- the chance of them having a bad experience was just too high. And recruiters were always pretending to be shocked that anyone could think the process wasn't working properly.)
I upvoted you because it's not fair to down-vote people who are on topic, but you're not correct when you assume that of all things calculus (!?) should have anything to do with hiring a PM.
I honestly fail to see how solving some Cauchy sequence-related stuff 10+ years after you finished your studies has anything to do with managing a bunch of programmers. And I'm not saying this as an I-hate-maths guy, in fact the only A+ I got in college was in calculus, but were I to be given such a question during an interview I would have just left.
The OP says his friend was interviewing for "product manager", which is not that. Product management is basically coming up with ideas for new products and seeing them through to the end. That includes helping design the actual computer program, which is why they ask software engineering questions.
(There are a ton of jobs called "PM", but they're all very different. None of them manage engineers, though, that's just "Manager" or "TLM".)
Lets leave the managers alone for a while.
When exactly was the last time, you as a programmer used 'calculus' while writing programs.
Your statement shows everything wrong with hiring programmers these days. Which is to demand expertise in totally irrelevant areas, and when the persons fails to the test declare him incapable of doing his actual job.
And then when you hire people experts in irrelevant areas not being able to do the job, start complaining that good programmers are difficult to hire.
How will we find good programmers when we are not even looking out for them?
I'm not defending this practice at all, but I think I can understand it. It sounds like the typical problems involved in scheduling 10 people to all perform together at once. Nobody can prevent people from getting sick. Going out of town and missing an interview is pretty flaky, but it happens.
Except it doesn't at other companies. Or if it does, it's corrected before a candidate shows up at the door. In other words, you value a candidate's time. I interview people all the time, and if I have business travel come up, I look at my calendar and make damn sure I don't have any interviews when I'll be out of the office (and if I do, I reschedule. If an emergency happens, I get someone equally qualified to cover). Heck, I even send personal apology emails when I have to reschedule phone screens.
You know why? Because it's polite.
It's certainly human nature to be bitter about someone fucking up an important day for you, but ultimately, bitterness gets you nothing. It's no problem if you want to complain to your friends or on HN, but why not come back for the second try?
Again, I can't ascribe motive to someone else's actions, but it's because it's disrespectful. It's not like, btw, google was apologetic, or said, "You know what, let's do these next round of interviews over video chat", or "We're going to make this up to you in some way". If I recall these events correctly, it was, "Sorry, you didn't get the job because you didn't do well in your interviews". Then a few hours later, "Oh no, wait, you have to do them all again". That's just disrespectful.
Your friend could have had another free trip to Mountain View to actually be interviewed properly, and maybe get the job he wanted.
Who wants a free trip to mountain view? Bear in mind, this isn't a college grad who is just excited to get to go to california, this was someone who was already an experienced product management executive in a leadership position at a middling-size startup. Going out to mountain view messes with their schedule and their work, and again, it's disrespectful.
As for the calculus interview, that sounds like fair game. PMs are supposed to have some PM interviews and some SWE interviews, and math is a perfectly acceptable area to ask SWE candidates.
If the questions had been in the technical area in question, even from a software engineering perspective, I'd be in agreement. But arbitrary knowledge of calculus seems unkind and unnecessary. That's clearly a style preference, though, as you say.
The point I'm generally trying to make isn't about my friend's experience exactly, it's just to add on to what many many people here have said: that google as an organization may treat employees very very well, but treat candidates very poorly.
Coordinating interviews really isn't that hard. Tracking candidate progress isn't that hard. And when you as an employer screw up, picking up the phone and making an apology isn't that hard. Failing at all three shows a fundamental lack of respect for the people you're hiring. You can't just say, "The system is broken".
Google recruiters will tell you whatever you want to hear, including things that are not necessarily true. I was assured that a minor issue in my background would not be an issue multiple times (I have email proving this), then Google hired me and let me work for more than two months. I got comfortable, I moved to Mountain View, began real honest work and set about making an impact.
One Monday, I had just finished a feature for an internal monitoring tool and was discussing it with a teammate. HR scheduled a meeting 30 minutes in the future on my calendar, then informed me that my employment had been terminated because of the issue in my background. You remember, the one I disclosed and discussed repeatedly during the hiring process, before I even signed the offer. Two people in upper management at Google who had never met me fired me because of something seven years in my background, two months after hiring me with the assurance that it wouldn't be a problem.
I bet my teammate wonders where I went. I didn't get a chance to explain because they threatened me if I told anybody on my team what happened while I was collecting my things. The same woman had a hearty laugh earlier in the firing meeting after joking, "I bet you didn't expect your afternoon to go like this, huh?" Felt like I was back in grade school.
Two weeks after firing me, a Google recruiting coordinator attempted to connect with me on LinkedIn. Read into a company's competence what you will based on that.
I can never, ever recommend that anybody subject themselves to working at Google based on my experience. And that's even before discovering the absolutely clueless direction that company is taking. You think G+ is annoying now? Just wait.
The real victim in this is my family. I've never subjected them to no insurance coverage in my career. Thanks, Google.
I've seen it happen, no way. Right to work, too, sigh.
To be clear I moved from the Oakland area down here, so it's not like I came here from Cleveland. Also, I have no ill will for Google and just hope I can move on with my life, while warning people what they're getting into.
I've dreamed of working at Google since I was a teenager. Finally my career trajectory lined up and I got there. Then I have to come to terms with my dream company acting like an incompetent fast food chain in terms of HR. Tough enough without a lawsuit.
Moreover, that's not how it works in SV. Assuming you do good work, nobody will care if you sued Google and settled except perhaps Google. I know plenty of engineers who were fired from companies like Facebook and Twitter for perfectly legitimate reasons and are now working at similarly-awesome companies as engineers. And this is a situation where the termination was 100% warranted and broadly known in "the incestuous Valley."
I would have fired them had they done the same and I would have also hired them at another company, assuming they learned their lesson and otherwise seemed like people with integrity.
I don't see what harm there would be in getting a professional opinion, anyway.
I would. Unfortunately I'm up north in Sacramento. I don't know how long ago your ordeal was, what your situation is now, or your engineering background, but feel free to ping me.
I'm moving out to the Bay Area next year (for non-work-related reasons) and while I hear plenty of good things about working for Google, I would never do it. For me personally, choosing to work for them would be an implicit endorsement of their hiring/personnel/privacy/politcal practices, which I can't abide.
Bad enough that it should happen once (to the parent), but repeated incidents would point to some gross organizational dysfunction.
I served my probation sentence and am beyond tired of being punished for the same thing. If hiring people are reading this and understanding just that last sentence that I typed, then I'm happy.
Criminal? Civil?
I'd love to hear what else you can dish about that.
The direction is folly. I'll just say that.
I had a friend who interviewed at Google, who is an excellent software engineer I've worked with for years, but who got rejected with extreme prejudice because he was interviewed for the wrong position. He was going for software engineer, they interviewed him for networking/systems reliability, and asked him all of these sysadmin/network-admin style questions. Even after he told them they had set him up with the wrong set of interviewers, they still kept the schedule.
Given the sheer size of Google however, I'd expect lots of false positives and negatives in their filters.
Also recognize that regular Googlers are selected to do these interviews, and some of them have little training in giving interviews. If you're unlucky, you might get a bad interviewer. I consider myself a relatively poor interviewer and I usually decline to do them unless they intersect my subject area (compilers, GWT, etc)
When I got there, I was greeted by my first interviewer who started asking me questions about SONET. I stumbled for a moment then commented that I could try to guess a few answers, but I didn't have any experience with optics. The interviewer looked back and forth between me and his paperwork a few times, got flustered, then asked if I was interviewing to be a network architect.
No, I didn't expect to be.
Well, that's what they had me scheduled for. He asked me a few more questions about things I'd never heard of, then we sat back and chatted about valley life for the rest of the hour.
The trip to MTV was fun, but it would've been more interesting if I'd gotten to interview for a job I actually knew about.
Unfortunately, I've read similar anecdotes on HN. Pretty disrespectful of the candidates time.
On top of that, if you're going to throw out dickish comments like the article states (paraphrase: "ask your friend, he'll know the answer"), I wouldn't stick around. Is that the atmosphere at the company? Agree or disagree with the interview style, comments like that would piss me off to no end. Start a game of needling and insults? You know what, I've had enough.
That's the problem with large companies. There are companies where I would just walk out of an abusive interview, because the brokenness represents their whole company. Then you have massive, mega, ultra-sized companies like Google where even though this particular team is beating you with the interview bat, you may still want to work for other teams.
This is probably confirmation bias speaking, but by far I hear the most "primadonna interviewer" stories come out of Google. I'm not sure if that's just my impression or if there's really something going on there.
If you are scheduled, many people must refrain from screwing up.
It even took them months to figure out that they hired an ex convict, after he personally disclosed the fact multiple times.
I had great hopes for Google to innovate in sense of culture. I saw Larry Page and Sergey Brin as intellectuals. Turns out they just went and built a high school elite club, for geeks. Another bloated company ran by a corps of smug geeks that like to claim how they are holier than thou.
I am really sad about it.
A couple months later Rackspace cold called me to work there. It's a usual thing, I think, and I don't hold it against them.
If I show up to an interview slot (for which I'm spending my 15-30m), and the candidate speaks up about a mis-scheduling or whatever, and convinces me it's not worth our time to meet, I'll be happy to regain my time and complain to the HRbot/hiring manager about scheduling issues (aka please don't waste the my/company's time by messing up the scheduling).
End of story and if you catch them early enough in the interview you can be back at work happily coding the latest story in current sprint.
You should do what's best for you but understand why the folks on here are defending google; it's a big place and they are mostly powerless when it comes to direct influence or manipulation. Understand that and it will give you insight into how to hack their system for your benefit both before you are hired there AND after multiple interviews when you find that right team when but need to deal with ingrained systems; which rules must be followed and which rules everyone ignores, when to ask for forgiveness later and when and how to cover your ass from the start.
They freak out. I got blacklisted at a cellphone company for doing that a couple decades ago. I found that out via a friend on the inside. Basically I was looking for, and applied to get a lab bench job (basically a spectrum analyzer / communication analyzer jockey, beneath my ability, but it was an exciting growing company etc) and they wanted me to be a junior roving field tech, basically I'd help the real field techs carry heavy stuff into the building and then (literally) mow the lawn while the real tech worked. And I went to school for X years to run a lawnmower... uh huh...
If you think its mortifying for the candidate, imagine how the HR rep looks when you walk out, thus making a fool out of them. Note that I wasn't sarcastic or caustic or anything when I left, after all, I had lots of friends / acquaintances on the inside and telecom is a very small world. Lots of hand shaking and "you have a nice facility here but I'm not interested in the position" and so on. I got word from my inside contacts that the HR girl was fuming with rage and swore after I made a fool of her by walking out, that my resume would never pass her desk again in any capacity, etc.
Companies are always doing stupid stuff, just hopefully not too often, and they're at least partially interested in how you'll respond. So imagine you work there and someone in upper management makes the worlds dumbest presentation to the division, they're terrified you're going to laugh at them and walk out.
When I was younger and (even more) stupider, stuck at an interview I decided I didn't really want, I started flirting with the attractive HR staffer, which didn't work out, but it was fun at the time. Times were different back then, now a days politely asking a woman out at work would probably get you fired or arrested.
I was actually going to bring this up. I have a lot of friends who are interview pros. They say if an interviewer decides earlier on you're not going to get hired, they basically fold up their sheets and ask non-related general questions to pass the rest of the time.
As an interviewee, I have, more than once, thanked my hosts for their tea and cake and left early when I detected that the interview was turning into a chat.
Would a collegiate interviewing model not work better for an intellectually driven organisation like Google? Each team interviewing for their own positions, but with some form of 'tenure track' process for the longer term?
Microsoft has more employees and the three times I interviewed with them (and got accepted) it was a great experience, with perfect communication from their recruiters and interviewers. The one time I interviewed with Google (and got accepted, but I rejected them for MS) I pretty much went through a similar experience as the blog post, although the interviews themselves weren't bad, just the recruiting process.
So yea, size isn't an excuse.
Whenever I pointed out that the bigger the company, the more teams there would be to absorb and place incoming employees, the googlers in question would just ignore the response and emphasize that blind allocation was necessary because no other method of placing employees would scale to Google's size.
Sigh...
Microsoft's HR departments are completely siloed by business unit, and they don't share notes. If the rec you're applying for dries up, they do F-all to guide you into a new one. Each time you engage with a different BU you're completely back to square one.
I failed the first phone interview spectacularly because he asked about data structures and estimating powers of two, and I haven't done any of that after 4 years in the industry. I guess fair enough; if that's what they expect of their employees, I'm not their man.
Overall, a disappointing experience.
I'm all for CS fundamentals, but in many places it's clearly being used as an approximation of good-code-shipping-ability.
I think part of the problem is that you're not really allowed to interview people in a way that holistically assesses their ability, so you end up doing cargo cult-y things that sort of, kind of sounds like they're relevant. For example, when I was at Amazon, we specifically were disallowed from using real-time typing/sharing tools to conduct coding questions.
Nowadays I find that pairing with someone on a limited-scope coding problem, as well as talking deeply about software design and architectural decisions, is the best way to assess. But then again, I'm also no longer interviewing complete newbies - which I think Amazon/Google/Microsoft's recruiting systems are heavily optimized for.
When faced with a candidate who has a dearth of real-world things to dig into, of course you fall back on data structures and algorithms. When you apply this to experienced professionals, who have a long track record that they can talk in depth about, it becomes silly.
When he eventually called back and started the interview, he did not even seem to respond my answers to his questions - it honestly sounded like he was playing a computer game on the other end of the line...
It was blatant disrespect towards me and my time. I'm glad I found an opportunity elsewhere.
Out of curiosity, was there a reason you decided to continue the interview process after this?
They have a post-interview review process, and I gave the recruiter an appropriately negative review.
Some companies have a mythology that every job in their company is like that, even if the actual job being interviewed for is the opposite.
Hardly limited to megacorp CA tech companies. No different than a boring old bank requiring janitor interview candidates to wear a suit and tie.
To be fair, these were "Data Structures 101" type questions. One was literally design a graph structure and write a deep-copy procedure, and that's it. Not exactly "novel." Since I haven't done these in ages, and didn't even pay that much attention when I had the class, I did badly.
Another was a simple string manipulation question that I bombed because I was already stressed out from failing the first so badly, similar to your situation.
I was head-hunted by them initially. Had a casual phone interview within the week. Then scheduled and re-scheduled a technical interview (their fault, three more weeks). Then two weeks later I had another casual phone interview. Then waited two weeks for the on-site six-interview bonanza. I finished those 4th thru 9th interview two weeks ago, and recruiter just told me yesterday to wait for the hiring committee to give a decision in another week.
First, given you understand your limitations as an interview, you're probably a better interviewer than most -- including myself :-)
An employer I worked for made it very difficult (but certainly not impossible, implausible, or even socially unaccepted) to stop interviewing altogether. Instead, they'd take a different approach: in addition to trying to match interviewers with candidates, they would also perform analysis on interviewer's previous feedback (e.g., are they constantly voting down candidates that go on to receive an offer after additional review, or vice-versa?) and weigh the feedback accordingly.
I'd be highly surprised if Google doesn't do this.
I do agree that usual "watch an experienced candidate do the interviews" approach to training is insufficient: this is much like expecting one to become a better candidate by watching a strong quickly "get" an algorithmic question with an a-ha insight, it looks easy when you already know the answer. I love the anagrams example from Programming Pearls -- it appears as "aha" problem, seems obvious to those who already know the answer -- but the book describes in detail on how it represents an entire class of problems and how to achieve that seeming insight using a more structured approach.
As an aside I actually finding interviewing others to be much harder than being interviewed myself -- if I screw up as a candidate worst thing that can happen is I don't get an offer, if I screw up as an interviewer people other than myself (the candidate, the company) will be affected. There's plenty of sites that talk about how to prepare for being interviewed, candidates spend dozens of hours before going for an interview, but there's less material out there for individual engineers who want to become better interviewers. Joel and Yegge are prominent exceptions, but most other pundits say only the obvious, e.g., "ask questions that can tell you if the candidate can do the job?"
I have a good friend who works at google and compares the recruiting team to being "the hot girl in highschool" (no intended sexism). Since google recruiters are at one of the elite companies in the world, they can treat people disrespectfully. If you don't like it, there will be a million people more people to choose from. I actually didn't get this vibe from them, but I only dealt with a couple recruiters.
I wouldn't call this gaming the system. Doing a year of such training would raise your actual skill.
Linked list questions are a favored choice of this class of interviewer despite the fact that 90%+ of programmers will never have a good reason to write a linked list - or even use one, for that matter. It's a CS fundamental and it's important to understand, just like other data structures, but evaluating a candidate's ability to rattle off a particular linked list algorithm on the board doesn't tell you anything about their ability to solve problems customers care about.
If you can't write basic algorithms to manipulate linked lists (traversal, reversal, etc) on demand, you almost certainly aren't a good coder. These kinds of questions are a good weed-out pass. They don't correlate with many necessary skills of a good programmer (organization, communication, thoroughness), but at least can detect lack of critical thinking or basic coding chops. They also lead to good follow-up questions that further explore a prospect's critical thinking skills.
These questions shouldn't be used to find human compilers. Oversights like minor syntax errors and the like should be ignored. Answers should be interpreted generously. Even then, you might be surprised how many candidates I've seen that were beyond incorrect. They weren't even in the right ballpark.
You shouldn't be expected to know Floyd's algorithm [1]. But reversing a linked list? Come on, the solution is 50-100 lines of code, 90% of it boilerplate.
1. http://en.wikipedia.org/wiki/Cycle_detection#Tortoise_and_ha...
The problem is expecting a candidate to have them memorized and be able to rattle off a particular algorithm from memory in a 15-30 minute interview window, when in the REAL WORLD if you don't remember the exact details of an algorithm, you look it up or grab it from a library instead of writing a busted implementation yourself.
That's why these questions are unrealistic: They're evaluating a candidate's ability to do something you almost never want them to actually do.
Yes, a candidate who can't understand linked lists is probably a bad choice. I never said otherwise. It's lazy to make the leap from that to 'thus, asking a candidate to write a complex data structure utilizing linked lists on the board in 30 minutes is a good idea'. Only if it's something they should actually be able to rattle off like it's no problem...
There are lots of ways to evaluate critical thinking and problem solving skills that don't rely on a candidate having memorized the contents of a CS textbook.
A better interview question is one that focuses on solving a real problem for a hypothetical customer, because that's what most engineers actually get paid to do. If the problem happens to be optimally solved with a linked list, you can see if the candidate arrives at that conclusion naturally, or guide them towards it if they don't.
function mklist(v, ...)
if v==nil then return nil end
return {value=v, next=mklist(...)}
end
function listeq(a,b)
if a==nil or b==nil then return a==b end
if a.value==b.value then return listeq(a.next, b.next) end
return false
end
function revlist(list, sofar)
if list == nil then return sofar end
local next = list.next
list.next = sofar
return revlist(next, list)
end
function test()
assert(mklist(1,2,3).next.next.value==3)
assert(mklist(1,2,3).next.next.next==nil)
assert(listeq(mklist(1,2,3),mklist(1,2,3)))
assert(not listeq(mklist(1,2,3),mklist(1,2,5)))
assert(not listeq(mklist(1,2,3),mklist(1,2)))
assert(listeq(mklist(1,2,3), revlist(mklist(3,2,1))))
assert(not listeq(mklist(1,2,3), revlist(mklist(1,2,3))))
endBob Floyd had more than one algorithm named after him. I thought you were referring to his beautiful algorithm for sampling without replacement [1], described by Jon Bentley in his CACM "Programming Pearls" column in 1987 [2]. If you don't know that one, it's worth studying for the techniques it reveals.
[1] http://math.stackexchange.com/questions/178690/whats-the-pro...
[2] http://dl.acm.org/citation.cfm?id=315746&dl=ACM&coll=DL&CFID...
And yet it's a somewhat common interview question
You can always game a test that you know ahead of time by prepping, it has no correlation on your non-prepping abilities though.
Hardly,
Building something would be your actual skill. Taking a product from an idea, finishing it, having some real users use it. Selling the product, and monetizing.
Those are the skills that matter.
Coming to storing trivia in your brain. Any decent guy who gets things done can read and work on such stuff. Its an utter waste of time to spend years putting text book knowledge in your brain, unless your profession is teaching.
This isn't exclusive to Google. It is the result of an inexperienced, untrained, interviewer. I like to refer to them as feral engineers.
If you click on Community->Developer it gets a little less confusing and shows a variety of contests. You can find some algorithm contests at Competitions->Algorithm->Single Round Matches->Launch Arena.
When I try this, I get an error message related to Java. When I last used the site, I ended up installing Java WebStart, downloading a JAR file for the arena, and running the JAR file from the commandline.
Overall TopCoder seems like more of a hassle to get started with than it should; fortunately, other sites like YC-funded HackerRank exist, although I'm not sure how the actual content and community compare.
Fast forward 3 years, and I had another poor interview experience with google. I flew up there this time, and got to interview in person. It was fun to see the google plex. I had 5 interviews in person scheduled. I felt like I ace'd 3 of them, 1 of them I did OK, and 1 I bombed. 2 days later google informed that that I was not a "culture fit".
I am not sure what the deal was. I felt like I had rapport with all of the interviewers, and I also had 2 internal recommendations. So, maybe that was some canned response way of saying no. Or maybe it was literal.
At any rate, I will never try to apply to google again, even though I too am contacted by a google recruiter no less than every 6 months. Sigh.
In addition to having been in IT for a very long time I am also very knowledgeable on capital markets having successfully taken CFA (Chartered Financial Analyst) tests. The CFO of the company that interviewed me was shocked that someone in IT passed those tests. The IT people, it was all algorithms and programming minutia. After the interview, they strung me along for weeks and then I just stopped calling them to check up on status and they stopped calling me. Then they would call me every few months asking me to interview again. I finally asked them to stop calling me.
The reason I bring this up is because I think sometimes candidates are excellent candidates for a $100,000 to $150,000 salary position. The only problem is the candidate is already making $250,000 and the prospective employer knows it after you fill out the application. I may be just thinking this to make myself feel better but I just thought the issue with the company was that I made too much. I probably would've had to literally walk on water and bring their dead relatives back to life to justify what they would've had to pay me to steal me from my current company.
Maybe that's the problem Google had with you?
The tests are the hardest thing you'll ever do. With little finance background, expect to study about 400 hours for each test and be aware that each test has a 30%-40% pass rate depending on the year it's given.
I'm not interviewing now, but honestly they're just trying to figure out a way to cut me out of the picture without torpedoing the business I support. Eventually they'll find a way though realistically it's another year away. I have one fall back company I can go to in a snap at equal pay and I do side consulting about 15-20 hours per week so I'm not worried enough at this point to be interviewing.
Then, a few weeks ago, shortly after I'd accepted a new position that I'm actually quite happy with, I received another similar email from a different Google recruiter. I wrote her back and told her about the other recruiter that had recently reached out to me and then went silent after I responded. She promptly called me and we talked. She agreed it was strange, said she didn't see anything in the system about it, but she did apologize and - we had a discussion about Google, the interview process and what it's like now (as opposed to 2007). If anything, it sounded like it would be incredibly long, bureaucratic, drawn out, and fairly ridiculous. I said I'd keep in touch with her if indeed I did want to re-apply to google, but I think I do not.
Instead, my last communication with Google was a phone call where I was told that one of the interviewers still hadn't handed in their written review. It's now three months later, and that's the last I heard.
That left a sour taste in my mouth. I wasn't expecting to get the job, and really it was just a backup plan in case Algorithmic.ly didn't work out, but you'd think they'd have the common courtesy to get back to me. I'm sort of expecting that 6 months from now I'll hear from them out of the blue...that's how disorganized the process is.
One thing though; the interview feedback from each interviewer is only for the hiring committee, never for the candidate.
1) Larger companies get away with inefficient recruiting because they can. If the same company abuses you twice, and you go back a third time, what's that say about you? It certainly goes a long way to explain why they can do it.
2) If you're considering going back on an offer, or interviewing just days after starting a new job, you don't have much room to complain about bad behavior on the company's part.
Perhaps another reason that Google contacts many people the same time is their heuristics. They have analyzed what good potential hires look like, and instruct their recruiters (who all use the same few online resources) to screen for it.
I would disagree. I interviewed with MS, Google & Amazon multiple times. MS & Amazon are definitely much more organized and very prompt in following up with decision.
It would be interesting to see if any of their recent VIP hires had similar headaches, or if this is just junior employees.
As I said elsewhere, this is surprising because everyone I know there is very straightforward.
For what it's worth, my one experience with Google recruiting last year was the polar opposite. They were curious and professional, of more knowledgeable recruiters I've dealt with, and timely in scheduling interviews. I had my first and only phone interview within a couple weeks if contract (which I needed and used to go through the extensive list of prep material they provided). Then I had an onsite interview a couple weeks later. Bam. Done.
- We would be interested in having you at/as ... but before the specifics, you signed an NDA, right?
- No, I have not.
- Oh, then good luck, bye.
For what it's worth, I had an overall positive experience interviewing with Google.
http://webcache.googleusercontent.com/search?q=cache:http://...
I know a couple of googlers, talented programmers, but they ended up as "yet another CRUD" python devs there.
Sometimes I wonder what all these engineers do every day. Their main apps are not getting exponentially better, and they have fewer of them. Why is all this algorithmic knowledge really needed? Do they spend all day optimizing or engineering and planning new features?
Not trying to insult Google, but I'm not seeing a ton of new features that would justify this kind of indepth theoretical knowledge. The ability to actually code, to do so efficiently and quickly, and to properly unit test and profile it, seems more important than any algorithmic knowledge. Mastery of the toolchain and the language, and that comes down to - "What have you produced?"
Maybe this is why Google hasn't had a new hit product in what seems like awhile. It doesn't need one as long as they maintain their position as search leader, but it doesn't seem like they have one.
Most of these apps listed above are not CRUD apps. The service based ones have significant and non-trivial data processing on the backend, lots of machine-learning, or algorithmic data processing.
Google apps have been getting better over the years, but Google updates them almost continuously and incrementally because they are web based, and so most of the changes go unnoticed like a frog slowly being boiled in water.
Is Google Search the same as it was 5 years ago? No, it has Google Instant, voice search, Knowledge Graph, direct answers, better spam filtering, it's index is far fresher, etc. For example, just the interactive chart knowledge panels (https://www.google.com/#fp=9a975e048e4bd6d6&q=population+of+...)
Google Maps has gotten radically better, and the latest beta maps is probably the most complex and sophisticated web application ever engineered.
Google search within G+ and Drive actually does object recognition with neural networks. (http://googleresearch.blogspot.com/2013/06/improving-photo-s...) This is a huge improvement in image search, and most people are totally unaware of it. It just works and they don't notice that it found it image without even needing descriptive text or tags.
Google apps are slowly getting smarter each and everyday but there's no "Jobsnote" to laud them, so the improvements are invisible.
Believe me, I notice. GMail and GMaps get slower and slower every day. I can't actually use GMail anymore; clicking anything takes several seconds. Wasn't this way in 2005, and I had a crappier computer then.
Knowledge graph and instant search are amazing feats, but with thousands of engineers working all day at Google, each of these products seem to be only incrementally improving, as you say, and I would almost expect quantum leaps forward in terms of new products. But Google probably has all sorts of things in their pipeline.
These products were already incredibly impressive, as well as huge hits, and I use them every day, so I'm not really dissing them so much as I'm noticing a lack of new, hit products.
It seems disingenuous to have the achievements of those companies be co-opted by/as Google/'s
Agreed there have been few home grown innovation from Google, those are all from early days.
Current achievements are all leveraging on their existing user base, and are not necessarily due to the merit of their products.
They promote many of these changes via Google I/O (although I think the audience may be smaller).
But I have had the experience of co-workers transferring off my team to other teams and semi-regular turnover, so it may be a matter of finding the right place at the right time.
Ah but from the linked article, if the only selection criteria is ability to answer weird 5-minute-depth trivia questions about data structures, not actually knowing anything about GEO/GIS wouldn't even be discovered, much less an impediment.
Of course, they might have a totally different, less pathological system for internal transfers than for external hiring...
Even if you take Google's ad platforms, they use machine learning techiques on the backend, as does YouTube.
I'd say the actual experience of the interview can be a good thing, but the process as a whole is a huge waste of the candidate's time - especially if you don't fit the stereotypical niche of what a Google employee is (4+ years of CS education, thinks writing linked lists and trees is exciting, etc. etc.) Their decision to intentionally avoid giving any feedback to candidates probably stops people from gaming the interview process, but it also makes it a net negative for candidates who don't meet the unstated criteria Google is after - criteria that could often be screened for before a candidate ever sets foot on campus. They refuse to interview candidates for a position or a role beyond generalizations like 'software engineer', despite the huge breadth and depth of problems solved at Google - if you're lucky they'll quiz you on the stuff you actually know, but most likely they won't, and the questions will be very mundane. This despite the fact that actual hiring choices ARE partitioned to some degree (as much as they seem to want to pretend they aren't).
Most of the time interviewing with a good company is a 'why not' scenario: The only thing you have to lose is some time, and you'll learn some useful things from most interview experiences (even if occasionally the only thing you learn is 'this company is awful'). Google's interview process feels precisely engineered to avoid letting candidates learn anything whatsoever.
Companies like Microsoft or Amazon or Zynga all at least have a pretense of evaluating a candidate's specific strengths and weaknesses to figure out whether they're useful - if you're a compiler engineer MS will probably have some Visual Studio/DevDiv people grill you with compiler engineering questions, if you're a games dev Amazon will have you talk to people from their games department, and if you're a database guy Zynga isn't going to ask you game design questions. For Google interviews it seems entirely one-size-fits-all, despite the fact that they have core products that obviously depend on niche knowledge and experience.
I had a Google recruiter contact me once when I was actively looking for a job. Her initial email was just the basic, "we saw your CV and thought your skills in XYZ would be a good fit. Would you be interested in setting up an interview?"
I replied within about 15 minutes to tell her I was interested. My next contact with her was almost five months later, and incredibly, she just said, "Sorry for the delay, I've been really busy. Are you free on Thursday?" At that point I kindly told her I had already accepted an offer somewhere else. I wanted to tell her the new company had treated me well over the ensuing years, that I had worked hard and advanced to a respectable middle management position, retired, and was currently traveling the world with my grandkids, but I thought that might have been a bit precious.
I went through several rounds of interviews with a couple different startups, and two of them were non-responsive to the point it was annoying. I can understand startups being less "professional", but some of them treat you more like a number than some of the bigger corporates I've worked for.
Yes. In the NYC/DC tech scene usually available engineers are snapped up in half a week, tops.
Not in those scenes myself, but have seen/heard enough stories.
The crazy thing is they don't give feedback, then call back in a few months and ask if you want to interview again for the same position like the OP said. Talk about completely confusing people. . .
I did learn that in my last round of interviewing (about a year ago) that to play the game you need to review the junk that you'll never need to keep in your brain, that you know but don't have at command. Sure, you'll most likely never use it at the position you apply for, but that's the rub.
I worked with a bad brilliant developer who just couldn't produce production code to save his life. We all saw where he was going with his code but he couldn't get there. We'd all end up cleaning up his code to get it into a better place. He would've aced interviews like at Google.
In the end you need people who can deliver.
Why those employees would be put in a position to interview with such a short time frame of professional experience, let alone recruiting experience, is beyond me.
I was asking myself while reading the article, my god, what kind of job was he applying for, AP test author, programing language standard library author, puzzle book author, or what exactly?
I haven't gone into a cold interview in many years; its always previous relationship based now. Are cold interviews where no one already knows anyone, like that now, focused on weird algos and trivia questions and nothing to do with the actual job?
You're interviewing the workplace as much as they're interviewing you, and I'm smart but I have no idea how to evaluate a possible employer based on their selection of weird trivia questions. Something that at least vaguely relates to the actual job would be interesting.
Not nearly enough people realize this. If they're asking you corny questions in the interview, how does that reflect on their company? OP said they didn't even ask him questions about his resume - just these corny trivia questions. If I was there, I would've asked how someone thinks this is relevant to doing my job at Google.
After the past three years I've done a ton of interviewing and have learned the only way to know if the company is good fit is to grill the interviewer on stuff that matters to you. I've had interviews at fortune 50 companies with people who had no idea who their competition was or where they wanted their IT department to be in 5 years. If you're not invested in your company, what makes you think I should??
The other idea that popped into my head is we could develop a new "secret geek code" for HN readers where asking candidates endless queuing theory questions means we're secretly warning the interviewee about long lines in the cafeteria, lots of tree data structure trivia questions means a warning about an intensely hierarchical management style, weird trivia questions about designing thread safe interrupt handling routines means you'll be pestered a lot when you're trying to work which you may or may not be cool with, that kind of thing.
General etiquette for this sort of sitch seems to be to allow the person with more leverage to lead. Most of the formulaic/cold interviews I've had they'll get to the end and then ask you if you've got any questions.
Most importantly HR told me in advance exactly what to expect, and that is what happened. I wasn't expecting much discussion of my experience or previous projects - but the algorithm questions turned up right on schedule, and they were on the topics I'd been told to review.
Surely everyone knows the drill by now. If Google interview you, you'll get a bunch of random algorithm questions and you either get hired or you don't and they won't tell you why. Your CV and your experience only serve to get a foot in the door. After that its all down to those algo questions. This is not a secret - I think they are pretty up front about the way it works.
PS - I didn't get hired.
You know, sometimes, I feel like that's a personality trait that's often under-rated.
I didn't get the job, but now Google keeps calling me for interviews. I keep telling them no, that I'm not 'Google material' whatever the fuck that is. Not me. Love Google, awesome tools, great stuff.. don't think I could work there.
Particularly the unpredictable callbacks and repeated contacts despite being within the 18 month period and complete lack of feedback post-interview.
Additionally, there was plenty of confusion about which position I was being asked to interview for. Initially, it was something completely outside my skill set, later it was a bit more refined, but not at all specific.
I did encounter some questioning where the interviewer seemed to be looking for one rather specific answer, but nothing nearly as bad as "I wanted you to use a priority queue. We will just move to another question." or "Time's up. Maybe you can ask your friend there what the answer is."
Amusingly, a friend of mine who interviewed there not too long ago ended up receiving and declining an offer only to be called and asked about his "start date" months later.
That said, my experience was generally positive and I'd do it again given the chance as most of my difficulties came from the recruiting end.
After the initial screenings and interviews with two different recruiters (one from Dublin and the second one from Switzerland) I finally get to the first technical interview. I struggled a bit with some questions, but I did get to the optimal solution in the end. I felt I could do better, but the second recruiter assured me that I did really well. He even sort of apologized because he needed to schedule a second phone interview, before inviting me on site.
The second interview, as far as I can tell, went the same as the first. I made some mistakes along the way, but I did get to an optimal solution at the end. The interviewer told me I'll get the results by the end of the week. Two weeks pass and still no word from Google. I decided to send an email to the recruiter, asking for an update. Still nothing. After a month I decided to send a friendly email to my first recruiter asking for an update - I didn't know what else to do. The second recruiter replied the next day telling me it was a "close call" and that I should re-apply in 12 months. No thanks :)
The idea here that Google might be leveraging knowledge from a hopeful dupe, is echoed by their annual code challenges. The company wants to know things. It's hungry for knowledge.
My feeling that leading on applicants is the best way to be ignored when you need one because when you cry wolf, only the wolves answer the call eventually.
I'm glad that Google doesn't just blindly look at credentials alone. If you got a PhD, and got featured in a CS publication, but couldn't answer their questions, then you probably shouldn't be accepted. That said, OP just had bad bad luck. My phone screen question was FAR easier (I still messed up on it, and got to the on-site too).
Disclaimer: I went to a Google interview last week (got rejected)
I'd note that when Google was first solving those problems, their luminaries who are now untouchable at the company probably tried those exact same reasonable answers at first until iterating on them into their current form.
However IMHO the author should have told them NO, and why, much earlier.
Shame on you google - take dozen emu eggs, break into a bowl, whip up and apply to face.
And of course there's always the "if you say 'no', there's always someone who will take your spot happily."
As a sorta balancing out here, my experience interviewing with Google(June 2012) was fantastic IMHO. We agreed right off the beginning what role exactly I'm interviewing for(Test Engineer), different from what I applied for(SDET) and went with it. Note, that I was holding them off for about 2 years. They'd email/call me every 6-8 months, and I'd say "Hold on, gimme a few more months". Eventually stuff happened that caused me to email them back and say "Okay, let's do this." I had the first typical phone-screening, talking about myself 'n such, why I'm looking for another job, why Google, etc. They gave me a bunch of blog links to "Life as a TE at Google" 'n stuff. 2nd phone screening was a programming thing that was kinda hard but not out-of-bounds PhD stuff. I was a bit intimidated by the fact I spent the whole hour on a question that was labeled "Question#1". I asked about it, the SoftEng. told me "Oh, don't worry about that". I asked if there were more questions, he said again not to worry... hmm. I did talk a lot though so he knew what I was thinking while trying to code. Anyways, a week later I get an email from a Google recruiter saying the SoftEng thought I knew what I was doing so we set up the MTV visit with 5 or 6 people. I was super-excited I made it to the on-site visit. Did you know Google Maps on mobile behaves differently if you're on campus? :) Everything happened on time. The interview questions and conversations we had for those 6 hours were great, eye-opening for me. I will say that I went into this whole Google thing with an open mind and with the assumption that all these people had more intelligence in their toe-nail than I'd ever obtain in my life. In the end, 2 weeks later, I was told that they "wouldn't be going forward with me". Of course I was bummed, I didn't even tell my family I was interviewing with Google. I wanted it to be a surprise. But, they showed me my weaknesses and I fixed 'em. Now I have an awesome job(SDET2) and I think the only reason I was able to get through this job's interview process is because Google's interview improved me significantly.
day count = [last 23 hour buckets] + hour count
hour count = [last 59 minute buckets] + minute count
minute count = [last 59 second buckets] + second count
second count = <running count cleared every 1 second>
You end up losing a small amount of accuracy, the worst being for keeping track of the second counts. You can avoid that by using an actual list of counter values for the seconds bucket and dumping those out when they get older than a second, or maybe by introducing another subdivision -- 1/10th of a second probably is good -- so that you actually have .9 seconds worth of data and can interpolate the last bit.It's a lovely exercise in algorithm tradeoffs. In this case it's mainly accuracy vs. memory, with lots of opportunity to explore implementation optimizations.
You have a shared channel which contains the pending requests, and a goroutine per server that simply loops doing: read from the shared channel, perform the request, wait for the sleep period, and continue the loop.
And that's all. Each server will get requests as fast as it can consume them.
The reason interviewers ask these questions is so they get a sense of whether you'd be able to implement Go, starting from first principles. (Or actually, it's because before Go many servers and load-balancers were written in C++ using async callbacks, and so this is a very pragmatic question that comes up a lot in real-world usage.)
I actually intended this as a way to "assign work" rather than having the servers pull. Each goroutine "owns" a server and forwards all requests to it, but it's just part of the one load balancer process, and the load balancer does nothing but balance.
IMO, defeating the purpose of a question is how you solve problems in real life.
Now if you wanted a harder question, you could follow that with: OK, that solution will give the servers time to do their thing, but there's no guarantee it won't just end up dumping all the load on a few servers, straining infrastructure and under-using the other machines, because there's no guarantee Go's scheduler is fair. So please develop two competing solutions. First, a fair scheduler that spreads the load evenly. Second, as an alternative, an unfair scheduler that always fills 100% of the time on the first machine before moving on to the second, and so on, and reports how many machines it's using so we can take the others out of the pool and repurpose them.
Google is probably more interested in hiring people who can answer that rather than your answer.
"There's a library for that" is a great answer for 99.9% of businesses out there, but google's problems aren't that of the 99.9%. (Nor in fact are they in the 99.9% of the remaining 0.1%)
The vast majority of people aren't writing the things that get, or would get if they were publicly available, research papers at Google.
They're using those things, written by the 1% of the 1%, to do things really, really generic, like display advertisements or store emails. There are some people in language development (Dart, Go, probably some others and some DSLs), there are some people doing hardcore database design, they probably have some people working on hard problems in their datacenters, from reducing latency on commodity hardware to networking infrastructure.
Are the majority of Google employees writing things that only the 0.1% of the 0.1% can solve? No, they don't even employ enough software engineers for that to be the case.
My justification for asking algorithmic interview questions is because I believe that engineers using libraries should understand exactly how they work, so they know what design compromises the implementation chose and how that affects their higher-level application. Just because you aren't going to be writing a database doesn't mean you shouldn't know the various levels of transaction isolation that exist.
The hardest of the above would be C++, because boost::threadpool isn't officially part of Boost--though it works fine--and otherwise you'd have to get a little creative with boost::thread_group (but in doing so it'd probably be only slightly more complex than the Go version).
I mean, it's a nice feature, albeit bolted to a language with a lot of issues. But unless you have pressing reasons to look at Go, something like that sounding easy probably won't really trip your trigger. =)
I’d even guess that a JavaScript implementation would be more efficient than Go. A goroutine has an overhead measured in kilobytes; a JavaScript timer is presumably smaller.
Anyway when it came to my conversion interviews the person who was supposed to interview me wasn't at the office. I ended up waiting around for someone to interview me, and when they came in 15 minutes late we had to trek across campus to get a room. I was asked a fairly difficult problem and botched it pretty hard, and of course didn't have the complete time to attempt to solve it.
I thought I nailed the next interview though! After I answered a couple pretty complex problems the interviewer literally said there is no way you're not getting an offer, and we just ended up chatting a bit.
I got rejected a few days later, not totally unexpected as I knew I botched that first interview. When I asked my host about it later he said the second interview wasn't even on record.
C'est la vie, I guess. I'd still love to try again, I had a lot of fun working there, the people are top notch - even of the hiring process is extremely hit or miss.
Seriously, if a company I interview at is genuinely threatened by me talking about my interview and questions, maybe they should reconsider their viability as a business--things being so precarious and all.
NDAs for employees generally seem to be bad signs for places worth doing business at.
If the timestamp is same second as last increment everything, if not increment where appropriate and rotate everything else to 0.
What am i missing?
So when he mentions he can't bound memory, it's because he can't easily discretize the counters.
Seeing ambiguities in specifications is an important part of software engineering.
Imagine an infinite time line, with a marker moving across the line at the speed of time. Every time increment is called, that marker is saved on the timeline. When getCountInLastX is called, one must return the number of marks on the timeline from the current time to the current time minus X.
I interviewed with Amazon once, I reached only the phone part and failed (most part for my own reason... I fumbled a lot)
But I was really bothered, that they setup "X" to interview me, and when I got the call, it was "Y" because "X" travelled, and that "Y" was not related to the position I applied at all, AND was a newbie at Amazon and thus failed to answer the questions I had about it, AND did not knew any languages I knew, making the coding part of the interview very weird.
I also saw similar stories here in HN many times... I wonder, wazzup with those companies that setup interviews and then send the interviewers somewhere else?
I was the surprise interviewer in the exact same scenario (well, not at Amazon, but same general idea) and was later cross examined, mostly by HR, about how well I thought he'd be able to help me if I came to him. The HR cross examination about his ability was all touchy-feely questions not technical (did what he say sound nice, not, did what he say make logical sense when passed thru the well known engineer BS filter). Position had one of those estimates of 25% helping other people with problems and group work, and he would have been hanging out near me although somewhat different kind of work, so it seemed fair for me to ask him noob questions about his expertise, just to see how he would talk to someone on the team from a different background. He was an expert in C++ if I recall correctly.
All went pretty well with me, although they didn't hire him (donno why)
The part of the story that was weird is I was an old-timer at that employer not a noob. Why they'd assign a noob to evaluate indicates either extreme trust or extreme desperation WRT the noob. Or he was playing you. If you really needed a question answered HR would take care of it.
Is there some kind of renegade JavaScript going on here?
I assume experiences at large companies vary widely depending on the group, but I was definitely impressed with Bing's interviewing process.
They seriously need to work on their culture in this aspect. It seems like such a trivial problem to fix inside of google. What is the hold up? I'm certain there are more good interviewing experiences than bad interviewing processes, but it does seem to be a common theme over there.
One very important purpose it serves is to see how well you can identify problems in algorithms. Probably I'm guessing it's not even important that you get it perfect, just that you can recognize and talk through the challenges.
One challenge relates to understanding the requirements. It needs to return the count for the preceding period of duration N, whether N is a second or a day. It could and usually does start in the middle of the preceding second, day, etc. It's a constantly moving window. That means if you just reset the counter each time you pass the absolute boundary of the next N (1:00, 1:01, etc.), you lose accuracy.
So that suggests that you might have to track each individual increment() somehow. But there's the next challenge, memory usage. If you just store all the timestamps, that's linear memory growth every time increment() is called.
So it seems to me like the solution is a tradeoff between memory usage and accuracy. If you don't call increment() very much or have a lot of memory, you can get perfect accuracy.
So that's the "theory". Now here's where it gets more interesting from an engineering perspective. Optimal implementations. Here's what I came up with in about 15 minutes.
First you minimize memory usage by storing offsets instead of the complete timestamp. Do this in 2 arrays, one for the preceding interval and one for the current one. This makes it easy to exploit our knowledge of when we've crossed the interval boundary, e.g. via now().getSecond(), to clear out old data.
(I am only considering one type of interval like seconds here.. you could extend this to minutes, hours, days by duplicating this method, or perhaps theres some way to consolidate more optimally.)
Anyway, increment() takes the offset from the fixed start of the current interval, i.e. the nanoseconds since the start of the current second, and appends it to the Current array. It also checks if we've passed into the next interval, in which case it reassigns the Current array to the Preceding array and starts a new Current array. The getter functions also do this.
To get the count, the getter simply
1) Finds the nearest offset in the Preceding array to the current offset (could just loop over it, start in the middle, etc.)
2) Subtracts that index from the array length to count the number of in-scope increments from that preceding interval (this works because the array is naturally sorted)
3) Adds that to the length of the Current array (because everything in the current array is in-scope)
SO, that should be a pretty fast way to do it with minimal memory requirements. If memory's going to be a problem,
A) you could spend a little more computation to do a kind of garbage collection. In step 2, resize the array to clear out the out-of-scope indexes. (Maybe you'd want a more optimized kind of data structure than a vanilla array for this.)
B) reduce accuracy by quantizing the offsets.
Ok am I hired yet? I'll go wait by the phone.
Just kidding, I'm sure this is wrong in many ways. But the point I'm trying to make is that it's a great problem for exploring tradeoffs, yet easy to understand what's being asked and requires no special technical knowledge.
Here's the hardware I want added to the computer running the counter server: 4 lasers capable of pulsed operation at a rate of up to one billion pulses per second with a pulse width under 0.1 nanoseconds, 4 light detectors capable of detecting such pulses, and 4 corner reflectors.
The corner reflectors shall be placed 1/2 light second, 30 light seconds, 30 light minutes, and 12 light hours away from the computer, and each laser aimed at a different one of the corner reflectors. The detectors should be placed next to the lasers so as to detect the return pulses from the corner reflectors.
The computer then maintains 4 counters. When increment is called, each of the counters is incremented, and a pulse is sent toward each corner reflector. The return pulses decrement the counters, with the detector associated with the first reflector detecting the one second counter, and so on.
I realize there are some practical problems here, such as one of the corner reflectors needing to be placed approximately 90 AU from the computer. Of course the path could be folded using reflectors, and maybe could be sent through a medium with a high index of refraction to further reduce the distance needed, but my guess is that it would still be a bit out of range of current technology.
var second = 100000000
, minute = second * 60
, hour = minute * 60
, day = hour * 24
, current = 0
, lastIncrement = 0
, increments = [];
function increment(){
current = timer.time();
increments.push( current - lastIncrement );
lastIncrement = current;
}
function getCountInLastSecond(){
var copy = increments.slice()
, total = 0
, count = 0;
while( ( total <= second ) && ( amount = copy.pop() ) ){
total += amount;
count++;
}
return count;
}Incidentally someone else posted a round robin database solution. It's probably the way to go. That's more or less where I was headed with quantizing offsets.