Thursday, November 18, 2010

A Google Interviewing Story

A few years ago I was entering the Silicon Valley job market and at that time looking for senior engineering positions. A good rule of thumb about interviewing if you haven't done it in awhile is to at least somewhat accept that you'll probably make a few mistakes on your first few tries. Simply, don't go for your dream job first. There are a million nuances to interviewing that you've forgotten, and a few up-front, not-so-important interviews first will educate (or re-educate) about them.

One of the first places I interviewed was a company called As far as I know - gofish is an utterly different company now than when I interviewed there. I'm almost sure that everyone I met there no longer works there, so the actual company isn't terribly relevant to the story. But the interviewer is. My technical interview there was with a guy named Guy.

Guy wore leather pants. Its a well-known fact that interviewers in leather pants are "extra" scary. And Guy was by no means a let down. He was also a technical crack-shot. And he was a technical crack-shot in leather pants - seriously, I didn't have a chance.

One question he asked me I'll never forget. In truth, its a pretty innocuous question - but it's also pretty standard fare for silicon valley interviewing questions at that time.

Here it is:

Say you have one string of alphabetic characters, and say you have another, guaranteed smaller string of alphabetic characters. Algorithmically speaking, what's the fastest way to find out if all the characters in the smaller string are in the larger string?

For example, if the two strings were:


You'd get true as every character in string2 is in string1. If the two strings were:


you'd get false as Z isn't in the first string.

When he asked the question I literally jumped to my feet. Finally, a question I could answer with some confidence. (Note my answer to him was solely considering the worst cases as there are plenty enough nuances there for an interview question).

The naive way to do this operation would be to iterate over the 2nd string once for each character in the 1st string. That'd be O(n*m) in algorithm parlance where n is the length of string1 and m is the length of string2. Given the strings in our above example, thats 16*8 = 128 operations in the worst case.

A slightly better way would be to sort each string and then do a stepwise iteration of both sorted strings simultaneously. Sorting both strings would be (in the general case) O(m log m) + O(n log n) and the linear scan after that is O(m+n). Again for our strings above, that would be 16*4 + 8*3 = 88 plus a linear scan of both strings at a cost of 16 + 8 = 24. Thats 88 + 24 = 112 total operations. Slightly better. (As the size of the strings grow, this method would start to look better and better)

Finally, I told him the best method would simply be O(n+m). That is, iterate through the first string and put each character in a hashtable (cost of O(n) or 16). Then iterate the 2nd string and query the hashtable for each character you find. If its not found, you don't have a match. That would cost 8 operations - so both operations together is a total of 24 operations. Not bad and way better than the other solutions.

Guy wasn't impressed. He showed it by rustling his leather pants a bit. "Can you do better?" he asked.

What the heck? What did this guy want? I looked at the whiteboard and turned back to him. "No, O(n+m) is the best you have - I mean, you can't do this without looking at each character at least once - and this solution is looking at each character precisely once". The more I thought about it, the more I knew I was right.

He stepped up to the whiteboard, "What if - given that we have a limited range of possible characters - I assigned each character of the alphabet to a prime number starting with 2 and going up from there. So A would be 2, and B would be 3, and C would be 5, etc. And then I went through the first string and 'multiplied' each character's prime number together. You'd end up with some big number right? And then - what if I iterated through the 2nd string and 'divided' by every character in there. If any division gave a remainder - you knew you didn't have a match. If there was no remainders through the whole process, you knew you had a subset. Would that work?"

Every once in awhile - someone thinks so fantastically far out of your box you really need a minute to catch up. And now that he was standing, his leather pants weren't helping with this.

Now mind you - Guy's solution (and of course, needless to say I doubt Guy was the first to ever think of this) was algorithmically speaking no better than mine. Even practically, you'd still probably use mine as it was more general and didn't make you deal with messy big integers. But on the "clever scale", Guy's was way, way, (way) more fun.

I didn't get the job. Or I think they offered me some trial position or something that I refused, but it didn't matter. I was on to bigger and better things.

Next, I interviewed at After a phone interview with the CTO he sent me a "programming assignment". It was a bit over the top - but in retrospect, worth the 3 days it took me to complete. I got an interview and a job offer - but the biggest value was what the programming assignment forced me to go out and learn. I had to build a web-crawler, a spellchecker/fixer, and a few other things. Good stuff. In the end however, I turned down the offer.

Finally, I had an interview at Google. I've written before that the Google interviewing process does tend to live up to the hype. Its long - its rigorous and in all honesty, pretty darn fair. They do as best they can to learn about you and your abilities in an interview setting. By no means is that an exact science, but I'm convinced they give it a good try.

My 4th technical interview at Google was with a woman engineer that honestly seemed a bit bored of interviewing. I had done well in all my previous interviews there and was feeling pretty good about my chances. I was confident that if I did nothing ridiculously silly - I'd get the job.

She asked me a few softball questions about sorting or design, I'm not sure. But towards the end of our 45 minutes she told me "I have one more question. Let's say you have a string of alphabetic characters of some length. And you have another, shorter string of characters. How would you go about finding if all the characters in the smaller string are in the larger string?"

Woah. Deja-Guy.

Now, I could have probably stopped the interview right there. I could have said "Ahee! I just got this question a few weeks ago!" which was true. But when I was asked it a few weeks previous - I did get it right. It truly was a question I knew the answer to. Almost as if Guy had been one of my study partners for this very interview. And heck, people study interview questions on the internet all the time - by me non-chalantly answering the question I wouldn't be "lying" in any way. I did know the answer on my own!

Now you might think, that in the instant after her asking, and before the moment of time that I began speaking that the entire last paragraph sequenced through my thought process rationalizing that I was, indeed, morally in the right to calmly answer the question and take credit for the answer. But sadly, that wasn't the case. Metaphorically, it was more like she asked the question and my brain immediately raised its hand and started shouting "Me! ooh! ooh! ooh me! I know! ask me!" My brain kept trying to wrestle mouth-control away from me (which happens plenty) but only by stalwart resolve was I able to retain composure.

So I answered. Calmly. With almost unearthly grace and poise. And with a purposeful demeanor - with, I think, a confidence that only someone with complete and encyclopedic knowledge of this timeless and subtle problem would hold.

I breezed over the naive solution as if it were unworthy. I mentioned the sorting solution as if it were wearing a red-shirt on an early episode of Star Trek. And finally, nonchalantly, almost as if I had invented all things good and algorithmically efficient, mentioned the O(n+m) linear solution.

Now mind you - despite my apparent poise - the entire time I was fighting my brain who, internally, was screaming at me -- "TELL HER THE PRIME NUMBER SOLUTION YOU DIMWIT !"

I ignored his pitiful pleas.

As I finished the linear solution explanation, her head dutifully sank with complete non-surprise and she started writing in her notes. She had probably asked that question a hundred times before and I'd guess most people got it right. She probably wrote "yep. boring interview. got boring string question right. no surprise. boring guy but probable hire"

I waited a moment. I let the suspense build as long as possible. I am truly convinced that even a moment longer would have resulted in my brain throwing itself fully into an embolism resulting in me blurting out unintelligible mis-facts about prime numbers.

I broke the calm. "You know, there is another, somewhat cleverer solution"

She lethargically looked up with only a glimmer of hope.

"Given that our range of characters is limited. We could assign each character to a prime number starting at 2. After that we could 'multiply' each character of the large string and then 'divide' by each character of the small string. If the division operation left no remainder, we'd know we have a subset."

I'm guessing that at this point, she looked pretty much as I did when Guy had said the same thing to me. General loss of composure, one pupil was dilated, slight spitting while talking.

After a moment, she blurted "But.. wait that wouldn'... yes it would! But how.. what if.. wow. wow. that works! Neat!"

I sniffed triumphantly. I wrote down "She gave me a 'Neat!'" in my interviewing notes. I'm pretty sure I was getting the job before that question, but it was pretty clear that I was in for sure now. What's more, I'm pretty confident that I (or more precisely, Guy) had just made her day.

I spent 3 years working at Google and had a great time. I quit in 2008 to CTO a new startup and have subsequently started another of my own after that. About a year ago I randomly met Guy at a start-up party who had no idea who I was but when I recounted this story he nearly peed his leather pants laughing.

Again, if there is a moral here - it's to never chase your dream job before you chase a few you're willing to fail at. Apart from the interviewing experience you'll gain, you never know who might just get you ready for that big interview. In fact, that rule just might work for a lot of things in life.

And seriously, if you get the chance and you're looking to hire a crackshot engineer - you could do far worse than hiring Guy. That dude knows things.

(a bit of nitpicky technical detail for the fusty: characters may repeat so strings can be very long and thus counts must be kept. The naive solution can remove a character when it finds it from the large string to do that but its remains O(n*m). The hashtable solution can keep a count as the value of the key->value. Guy's solution still works just fine)

Edit: 11/30/10 - Guy from the story has found this post and gave some clarification in the comments. Worth the read.

Thursday, June 17, 2010

The Young Man's Business Model

I've had an idea bouncing around in my head for awhile that randomly came together recently. And given I have a blog, I thought I'd write it down. This idea came from 3 experiences I've had - and here they are:

Mini-story #1:

In my early 20's I pretty much did 2 things. Ride motorcycles and code. Oh, and given my motorcycles were always sort of junky and I beat the snot out of them, I spent plenty of time fixing motorcycles too - I guess that's 3 things then. (If you think I forgot dating or went to bars or some such - nope. We're good. 3 things).

Every now and then we needed an "old man" (like in his 40's or something) to help us fix something when it was beyond our self-taught abilities. Now when I say "old man" here and throughout this article, I don't necessarily mean "old" (and I don't necessarily mean "man") - I mean "experienced". Experienced at whatever I'm interested in at the time - or more specifically, experienced at what I wasn't experienced in at the time.

And as far as fixing motorcycles, what struck me was the way he'd go about it.

A rather common case would be something like there being one final screw holding on some engine part that we needed to replace, but it was buried deep inside the engine - i.e. you could barely see it. My first reaction was to wedge a screwdriver in there as far as I could - and see if, with luck, brute force, and karma, I could turn it enough to get it out.

The old guy on the other hand never went this route. He merely looked at it a moment, then immediately started taking off the neighboring easy-to-remove piece of the engine. Once that was off, he then effortlessly put his screwdriver in to remove the now exposed screw. Now mind you, the old-guy's way was my back-up plan - but I was betting that my brash exuberance would payoff in a slightly quicker result. Sometimes it did - sometimes it didn't - and sometimes I broke screwdrivers.

This trade-off of investment up-front versus brute-force hope became so obvious that my friends and I used it as vernacular. "Do you want to try this the 'young man' way or the 'old man' way?". It was surprising how without any further explanation we would know all the precise steps involved in both for whatever situation.

Ok. That was mini-story #1, here's mini-story #2. This is a business story but its actually surprisingly similar to the previous one whether you know it or not.

In 1997, I was writing a Java optimizer (this made a lot of sense when Java was interpreted) called DashO. Somewhere along the line I was introduced to a guy at Adobe, who (I was told) wanted exactly what I was building.

When I finally spoke to him, it turned out that the Adobe guy didn't really want Java optimization at all. What he wanted, was Java application size reduction. It had literally become a show-stopper for what he was developing. He was clear that money wasn't a problem - if I could solve his issue, he was a customer.

Wanting to please my newfound (big-time) customer I said "Sure! I can add that in!". Then I shrewdly secured the Adobe guy as a beta tester. This changed the direction that my product took and added about 2-3 months of development, but given the payoff, it seemed worth it.

About mid-way through those 2-3 months my partners and I had lunch with a veteran ("old man") business guy that for some reason seemed to like us and liked to keep tabs on our progress. As I excitedly told him the story of Adobe waiting anxiously for our product, his reaction wasn't as I expected. I thought he'd be excited for us, but instead he had a look of disappointment on his face.

Me: What? What's wrong - this is awesome - Adobe is our first customer!
Old-guy: So you spoke to Adobe. Directly to an internal guy that's a customer
Me: yeah!
Old-guy: And he has plenty of money to solve his problem.
Me: yeah, tons!
Old-guy: And how much of that money are you going to get in the best case?
Me: erm. um. We'll sell a copy.
Old-guy: Right. A copy. Maybe a few if you're lucky.

Old-guy went on to discuss how that deal should have gone. Adobe had effectively contracted me to build them a product that didn't exist (this was true). It was possible that no other customers would ever want that functionality (possible). Simply put, they had a specific business need, lots of money to solve it, and had hand-picked me to be the solver.

I should have structured the deal as a contracting agreement. Charging on a per-hour basis to develop their product using what we already had as a base. Then, give them a discount rate on the hourly rate in exchange for full-rights to further develop and sell the product as our own. This would have been a 6-figure deal which would have meant a lot at that time. What's worse is you might be thinking that I missed an opportunity to fleece a customer - but I argue you're wrong. In fact, that arrangement would have actually brought more value to the Adobe.

In the old-guy's arrangement, Adobe would have then had a hand in guiding the project and making sure all the features they wanted were in the soup. Not to mention, if I didn't build this for them, they simply would have had to hire someone else to do it - probably spending lots more.

Once in awhile, you have a fucking-duh moment - and for me, this was one. If you're thinking "well obviously" then clearly you've done this before, at that time - I hadn't.

Story 3 - a recent breakfast.

I recently had breakfast with a guy I met at an entrepreneur event. He was CTO of a pretty popular website. When he first described his site, I liked the business model a lot. His site fed him data that allowed him to refine his real product: pre-built server boxes which he sold to companies that allowed them to use his software internally.

Visions of sugar-plums and multi-million dollar deals immediately started dancing in my head. As he talked, the rolodex in my mind quickly flipped from person to person. I thought of potential customers, potential partners and even maybe people appropriate to join his team. His product was good, and not that he asked me to, but I couldn't help forming a deal network in my head.

I asked about his sales infrastructure. His answer left me wanting but I figured he was probably still fleshing it out (a very hard task). I almost rhetorically asked about the sales cycle. There wasn't one. Now I was getting confused.

As we talked more it became clear that he and his company were following what I'd call the young-man's business model.

He was basically building a (good) product, then laying it out on the web for all to see and hoping to get a million eyeballs. The viewpoint of the business is to get eyeballs, often from things like Digg or Techcrunch, and then figure out how to keep them. And then amazingly often, this really is the step where entrepreneurs have no clue what happens except they are sure the next step is "and then Profit!".

This is an extremely innocent look at business - and in some sense, its the most logical one if you simply have no other avenues.

This model isn't wrong but now to me (who has of course only recently come to rather shocking self-realization that I am... an "old-man" at how I view business) it seems like a business model without considering connections. Deciding to make connections for your business of course isn't conscious. When something happens, the first thing that pops in your head is "Boy, Fred needs to hear about this". And depending on how many Freds you know dictates how often that idea pops in your head. (and of course, the more Freds you know, the more Freds you will know).

My old-man/young-man nomenclature may not be perfect but it might be statistically correct. Its probably safe to say that on average a 30 year old has a generally more business connections than a 20 year old. From there people simply follow business plans as they occur to them.

To me, my friend at breakfast had a sure winner if he had put together a solid sales and marketing infrastructure. His product should have been selling inside 6 figure deals with several month sales cycles. Now clearly, this model doesn't apply to everything. And plenty of new Web 2.5 startups don't fit this mold - but I also think many people underestimate the idea. So far it seems the evolution of all businesses, even something so webby as Facebook eventually becomes about making deals with big partners at least as much as its about eyeballs.

It wasn't so long ago that saying your new startup was monetized by ads wasn't scary. Some companies go right from eyeballs to ads and to sell-out. Thats great work if you can get it. But the number of eyeballs is limited. Its scary to think that, but on the web, we tend to give value away and "make it up on volume". The only problem is you need a hell of a lot of volume to make up for free. And 6 billion people isn't all that many when it comes down to it.

Personally I think web businesses are growing up. The eyeball business model is getting to be like Market street in San Francisco. Everyone is pierced, shaved, screaming, or on fire. They're crying for attention and they have to keep shouting louder than everyone else to get it.

I have plenty of opinions about business models, but to me, the best business model is one that makes your customer money. I didn't say "saves" them money - big difference. Also, its better yet if that customer is a business. You need less businesses as customers to be successful than if you had individuals as customers. A common sweet-spot is BtoBtoC. Supply to businesses that supply to consumers (and of course, make them money).

If you don't have a ton of business experience, try this - think about your next great web app, then imagine the slickest (or sleaziest, your call) old-man salesperson you ever met sitting in front of you. Picture the idea that this guy is really good at persuasion and networking. He can't code, you may not like him, and he wears shoes you wouldn't wear on halloween, but he's good at what he does. Then imagine handing the old-man 5% of the company (I know its hard, try - remember, its just pretend). You need him truly on your side.

If you had access to the old-man and his imaginary immense rolodex of connections. How else could you sell this? What value could you bring to some customers that currently you can't reach?

Your real business model might be hiding like that last screw holding on part of the engine. Despite you stubbornly breaking screwdrivers, you might not get to what you need. It might just be worth asking yourself, "WWTOMD" - What would the old man do?