Don't write on the whiteboard | Hacker News Reader

Don't write on the whiteboard

jperla.com

213 pointsljlolel111 comments

Sorry OP, I realize that you're just trying to be helpful sharing what's worked for you and I appreciate that, but frankly, I hate posts like this...

I think the best preparation for any interview is to simply get good at what you do. All the rest is window dressing that distracts from that goal.

Every minute spent practicing interviewing would be better spent building stuff. The natural byproduct of this will be exercising those skills that will be evaluated.

What you're proposing is unnatural and unnecessary. You're focusing on the details of the process instead of the real issue of knowing your stuff.

Good interviewers won't care if you're fundamentally solid but a little light on the presentation side. And they won't be fooled by a great presenter who is weak under the hood. Sure, you may fool a weak interviewer, but what does that say about the company you may be joining?

We all want to be solid in both fundamentals and presentation, but I prefer to focus my limited resources on getting better than I am, not appearing to be better. Best to just be good, be yourself, and trust that it will show naturally, no matter how you are evaluated.

I'm glad the author mentioned Project Euler... I've never heard of it. Anyone else have experience with these problems? Is it a good way to improve your development skills?

It's a very good way indeed.

One good thing about it is that there are different levels of success.

The problems usually come with a simplified version to which the result is provided. That way you can confirm your solutions works. Then, the real problem scales it and you have to improve the algorithm to achieve the performance goal of less then 1min cpu time.

It's also o good way to learn a different language. You can compare your solutions in different languages and evaluate their strengths and weaknesses.

They’re interesting problems, a good way to improve your coding skills, and an amazing way to train for interviews.

It's been useful for me. Back in high school, I raced to 50 problems against a friend and learned a lot along the way. Sure, you can get problems elsewhere, but the site has a nice way of continuously upping the complexity to enable self-learning.

Whenever I recommend Project Euler to people wishing to practise coding I always caveat it by saying "the first 50 problems are useful". After that Project Euler quickly becomes more mathematical, which is great if you wish to practise your maths skills, but may not be what you're looking for. There are exceptions, of course, and some questions may require implementing an important algorithm, but it is difficult to tell at first glance if you will be learning some esoteric area of number theory or something useful to your coding skills.

TopCoder, CodeChef, SPOJ may be what you're looking for.

(Having said that, PE is great fun if you're interested in maths per se).

Thanks for the advice... I was looking at the last pages and I've got no clue what's going on.

If your someone who isn't very experienced in mathematics, it's better to do them in order (easiest to harder) that's how your suppose to progress. If you're starting with the last one, it's normal you feel lost, it's like starting mountain climbing with the Mount Everest.

Here's a list of sites I keep for ACM ICPC preparation or problem solving for fun:

http://livearchive.onlinejudge.org

http://coj.uci.cu/OnlineJudge

http://www.spoj.pl

http://uva.onlinejudge.org

http://acm.timus.ru

http://acm.sgu.ru

http://acm.zju.edu.cn

http://plg.uwaterloo.ca/~acm00

http://cs.stanford.edu/group/acm

http://dwite.ca

https://www.facebook.com/careers/puzzles.php

http://code.google.com/codejam/contests.html

http://projecteuler.net

http://www.codechef.com

http://www.interviewstreet.com

You left out Berkeley's annual programming contest:

http://www.cs.berkeley.edu/~hilfingr/programming-contest/

The bottom of the page also has links to problem sets from a bunch of other contests.

Thanks, I was unaware of that one.

I'd add TopCoder and Codeforces to the list:

http://community.topcoder.com/tc

http://codeforces.com/

Both of these sites run a few algorithm competitions every month.

Sorry Ed, but the best preparation for any interview is not simply getting good at what you do. Being good at what you do is a given. But there is an art to interviewing. I have bombed interviews not because of a lack of ability, but because of my failure to understand interview dynamics.

This may be true, to an extent, but to me, the best interviews do a good job at honing in on how good you are at what you do.

Good interview skills only benefit you in one area -- how good you are at interviewing. Once somebody hires me, how good I am at interviewing serves no purpose to my employer. And smart companies recognize this, and adjust their interviewing process to get to what's important.

Is there anything I wrote that requires you to spend hours on something that is only useful for interviewing?

I specifically say the opposite, don't practice whiteboard interviewing.

Edit: who would down vote this? Edit edit: thanks for the explanation jader

My post wasn't a direct response to your article, but rather thebandrews' point about preparing for interviews.

And I'm not saying you shouldn't prepare for interviews. I'm just saying that companies that evaluate a candidate based on how they "perform" in an interview vs. trying to really get to the root of how they would perform in a job are doing themselves a disservice, and may be losing some good candidates because of it.

And if this is happening, that company should change their interviewing strategy to focus more on what's important, and get rid of anything that may get in the way of evaluating that.

Take your point on writing code on a whiteboard vs. writing on a notepad, just for example. To your point, it may be unnatural to code on a whiteboard. But, to me, it's also unnatural to code on a notepad. Actually, I hate handwriting altogether. I prefer typing a thousand times over. So in order for a company to really see how I code, they would hand me a laptop, or even better, allow me to use my own.

Of course, there are arguments to whether that would even be a truly accurate evaluation. My point is -- and again, this isn't necessarily in direct response to your post -- that good employers know how to get to the root of someones abilities, without letting these interview-specific strategies get in the way.

Edit: Disclaimer, I did not vote you down. :)

Exactly.

It's just like marketing. You can have the best product in the world (in this case, yourself). But, if you can't market it well, other products will be used instead (IE: you won't get hired).

Learning how to market myself is the single best thing I've learned how to do and it's definitely helped me get jobs.

I'm sorry, but where does the OP reference anything about practising interviewing? In fact, his point seems to focus more on fundamentals than anything.

My takeaway was along the lines of removing the junky presentation layer (whiteboard, etc.), and making sure that you SHOW your fundamentals. Working on Project Euler helps build those fundamentals, writing code comfortably during your interview helps show your fundamentals. In terms of presentation, I didn't feel like he was doing 'window dressing', you definitely want to show your interests, projects and your opinions, these are part of the fundamentals.

No matter what, there is always a base line of presentation that you must meet in an interview to show your fundamentals. I feel like this post is encouraging you to meet that base line, as well as increase your fundamentals.

Exactly. A lot of these replies try to summarize my points into one sentence like "show off your skills." That short phrase is insufficiently descriptive to be useful.

I give specific advice for what you can actionably do.

The ideal candidate is not just competent, they're able to demonstrate and communicate that competence.

Many technical startups struggle with promotion, naively believing that simply being better is enough. It's not. You need to be able to clearly explain and demonstrate your value. If you can't do this you're leaving money on the table.

If somebody told you that 20% of your lifetime earnings will be based on your effectiveness during interviews and non-technical conversations with your boss, would you ignore that? Because that's true.

Would you argue that students should not study for standardized tests (e.g., SAT, GRE, ACT) as well, because they should have learned the (restricted set of) material on the test in their classes?

That's how I've always felt, personally.

What you're saying is how interviews should work: a pure talent evaluation, unaffected by any non-job-related skills. However, in practice, interviews don't necessarily work that way. Spending a couple of minutes training on presentation skills can make you much more effective at communicating just how awesome your actual abilities are, far more than the equivalent time expenditure in getting marginally more awesome.

You can pretend that the world is perfect, or you can take steps to deal with the fact that it is not. Now tell me, which of those behaviors would you want from the programmer you want to hire? ;)

How often do you hear of a programmer saving a company millions of dollars/thousands of man-hours and receiving no reward for it? All the time!

Excellent performance (saving the company ~$3MM) at my last job merited me a 15% raise. Learning and applying negotiation skills made that an 80% raise. Presentation matters.

The first time I read your comment I thought it was disagreeing with the parent post. Upon thinking about it, I now believe that you are agreeing with him. Right?

I'm not trying to criticize your post, but I hope someone could point out why I read it so wrongly -- if there are attributes why make it more likely to be read that way, or if there's something flawed in my perception.

I am agreeing with the parent and disagreeing with the grandparent post.

I think the confusion comes from the "How often do you..." which is frequently used sarcastically-although in my case I meant it literally.

This is the first article I've seen which mentions something that should be fairly obvious to interviewers — expecting people to code on whiteboards is a common mistake. As an interviewer, I totally cringe when I imagine filtering out good people this way.

(I say that as someone who enjoys interview puzzles, and have always succeeded at them. But that pleasure's probably pathological. For many people, it's a nerve-wracking ritual which pointlessly damages self-esteem. As a gatekeeper, my job is to help them succeed at my silly little games. Assist them in reaching their limits.)

A lot of the mind is in one's hands, as many emacs users might tell you. That intelligence can disappear in the alien environment of the whiteboard, for those unused to it. Many bright people maybe can't even afford a decent whiteboard, and haven't worked in an environment which uses them.

There's a huge amount of good tips for good people to get past the gatekeepers — and negotiate good terms. If you can not just beat the interview, but kill it, you'll often have a more powerful bargaining position.

I'm ok with coding on a whiteboard in an interview but I prefer it to be at a casual-ish level. I want to get high level data out of the process, not running code. I want to see how someone thinks through the process of transitioning from problem solving to coding. I want to see how they firm up requirements for the solution. I want to see people's code habits, I want to see their abilities to analyze and critique their own code. I tend to use pretty easy problems for such things (like factorial) so I can focus on those other bits. I find it works pretty well.

I disagree. Experts are known to perform quite badly when they are distracted by stress. In the case of job interview, doing anything out of the ordinary (such as writing on a white board) can cause stress. This diminishes the capacity of your working memory due to increased attention focused on stressors.

Wow, couldn't disagree more. "Ask for paper" may be the single most pragmatic and useful interview tip I've ever gotten on this site. I grinned ear-to-ear when I realized that was the point he was making.

The Project Euler stuff I could go either way on, but I thought this was such a great post.

I actually agree with Ed here. You should worry about things in your control rather than thinking about things beyond your control. I understand that interviews aren't fair etc. but I still believe keeping it simple is the best way to success.

Simplicity is the ultimate sophistication.-- Leonardo Da Vinci

  > I think the best preparation for any interview is to
  > simply get good at what you do

Isn't that exactly the problem? How often are you asked to do the stuff you do best in the interview? Coding algorithms on the whiteboard is not what I do best.

From an interviewer's perspective, the whiteboard gives me a chance to intervene to correct, explain, or provide hints, to the interviewee sooner/at the right time, which is not possible in pen-paper solutions, as I cannot see what the interviewee is doing till she shows me her work, unless I sit at the same side of the table as herself, which is odd for general discussion/talking.

My advice to interviewees:- Practice on a whiteboard. It is not that difficult.

There is no practice that simulates anxiety. Anxiety is mostly incompatible with the mental effort one usually applies in coding.

As you have put it, the white board is convenient for the interviewer, but that is missing the point of the interview which is to assess the candidate.

If you do not find if that difficult, than consider yourself privileged because most people feel differently. Some people cannot speak to a small audience while some love to give presentations.

An interview is already an anxiety-packed situaton where the candidate is under the spotlight. Putting them on the whiteboard solving problems only puts more pressure on and will often lead to sub-performance. Since the interviewer does not follow through when the candidate leaves, they may think that the candidate did his best.

I for one think that there should be an effort to emulate real working conditions and not performatic settings.

>There is no practice that simulates anxiety.

Ah, but there is. Once you go through few interviews you get less anxious about the next one. Which means, that if this is a serious problem for you, and you expect some important interview in the future, then you have to go and interview with some other companies before to gain practice, and may be even get some job offer you'll like more than the one you are hoping for.

The whole point of the parent argument is that there are conscious steps you can take to make whiteboard writing not stressful for you. Just practice for ten hours solving problems on it and it will be as natural as writing on paper.

>> Once you go through few interviews you get less anxious about the next one.

That's not really practice, it's actual experience.

It's also not guaranteed to improve your skills, it might make it worse if you have a bad experience. When that happens it's easy to make generalisations about the next ones. That's actually somewhat descriptive of where anxiety really comes from, antecipating the unknown.

That's not really practice, it's actual experience.

All practice is merely experience. The only way to practice any skill is to use that skill and get better at it.

But there's a great deal of difference between shooting targets and real combat, punchbags and live oponents, ball throwing machine and live adversary just as much as doing whiteboard problems by yourself and during an interview.

It's not the same experience.

Then interview more :) I had the fortunate experience of being forced to go through 50+ job interviews during college, and nowadays it's not the least bit stressful. I think I get more anxious driving than interviewing.

I'm dumbfounded by the mentality of "I don't do XYZ" when you're going to an interview. Guess what? They'll find that arrogant.

If you really do suck at using a whiteboard, here's a really far-out incredibly expensive and time consuming idea: Go to Office World and buy a small one for $10.

Even easier: write on a window. I've used this to practice talks in hotel rooms, where you really won't find a whiteboard.

Personally, I would not be bothered by this. If the candidate really won't use a whiteboard, yeah, that's strange, but it's not going to sway my opinion one way or the other. Ultimately, interviews stress people out, and I take that into account when I'm analyzing someone's performance. I care about the programming ability of the person I'm interviewing, not their interviewing ability. The worse interviewing ability, actually, the less chance there is that they're going to leave. So actually, asking to not use the whiteboard might count in their favor :)

Perhaps I'm just neurotic, but I do find it uncomfortable to write code with someone scrutinizing my work. When figuring out how to implement an efficient algorithm, I find that it's often helpful to perform exploratory steps before actually writing the algorithm. For instance, when I attempt a projecteuler puzzle that I don't immediately know the solution to, I'll usually try to compute the desired result for a few simple inputs, or I'll quickly write down the first (naive) approach that comes to mind and then trace through it to see where it fails, etc.

I know that those are all things that I can still do during a whiteboard interview, but having the interviewer look at my intermediate work, assume that I'm making mistakes and try to correct me tends to disrupt the process. I'm confident that the algorithms that I'll ultimately produce will be good, and I'm confident that I'll produce them at a good speed, but it will still look worse to the interviewer if I write down a bunch of noise before outputting a polished algorithm.

On the other hand, on paper, I can quickly churn through some of those early steps and then show the interviewer a solid, finished product without them having to see the crude intermediate steps. Again, it's possible that my anxiety about this isn't really justified, but I can't help but get the feeling that working in this way will leave the interviewer with a worse impression of my abilities than if I have the option to "hide" the rough work and just show them the output.

As an interviewer, I'd much rather see your intermediate steps - the messy parts, etc. I feel like I can get a better idea about how you work and think. Interview questions (for me) aren't about "can you solve this" they're more about trying to see how you work. I ask questions about decisions you made, and I like it if you can talk about what you're thinking.

Interview problems are contrived. I don't care if you stumble a little bit. Heck, I'm always happy when I see someone start off the wrong way, notice that something's wrong, take a step back and go a better path.

If you go off with a paper and pen and just give me an answer, I miss out on a lot of that. And even though the anxiety might not show how you normally interact (and I totally understand that) - I can't possibly get any sense as to how you work in a collaborative environment.

I've never had anyone ask to do problems on paper instead of a whiteboard, and I wouldn't refuse it to them - but I just get a feeling that I'd be less likely to be inclined to hiring them - not because of the paper, but because there's no way to see the things that I most like to see.

That sounds more like a visit with Froyd than a programmer interview.

Freud?

I don't like the fact that my observations affect what I'm observing, as an interviewer. If someone wishes to yak with me at each step, fine. Alternately, if they wish to silently cast about a bit in non-rational gestalt, maybe ask me odd questions or play with the data to get familiar with it, then converge on a bulletproof solution... also fine. I do not need to stick my probes in their mind to observe each step. There exist other methods to demonstrate how they collaborate.

I love it when someone starts attacking my whiteboard problem by writing down something other than code, such as sample input/output pairs to test their algorithm against.

So then sit at the same side of the table...

The title doesn't do the article justice. As an interviewer myself I think it's terrible advice. Certainly if you think it'll make or break your interview go ahead and ask to write on paper, but thinking through problems and expressing them on a whiteboard is an important skill at a lot of companies.

Many of his other points are good, although a lot of it boils down to being a top notch developer and letting it show in the interview. Being a top notch developer is the hard part, and good interviewers (at places a top notch dev would want to work at) will typically identify your skills even if you don't follow this specific advice.

+1 for using python--it's great for getting through coding questions quickly and efficiently, allowing exploration of various twists the interviewer may throw at you.

Thanks for not just talking about Whiteboards! That's just the hook and intro!

I agree. I think high-level planning and design is a great use of whiteboards in the workplace. Code under time pressure, not as much.

A pretty good array of interview tips which can be summarized as follows:

(1) Make yourself as comfortable as you can, so that you can:

(2) Make it clear what you're thinking and how you think (which is the point of the interview).

I'm not signing on for the concept of always doing your interview in Python, however. Do your interview in the language you're most comfortable in, unless it's something so esoteric that it's likely to throw the interviewer off balance. Python is a great language for these sorts of exercises if you know it, but don't force the issue if you don't, because then you're violating (1) above. I know Python well myself, but I'd do an interview in Java because that's "home" to me, and you need all the "home" you can get during an experience as alienating as your standard interview.

Seems to be a divide between those who like using whiteboards and not. I can think of several contributing factors:

* academics vs non-academics

* those who enjoy thinking on their feet vs those who enjoy thinking in a text editor

* good handwriting vs not

* right vs left handed

Regarding the last, writing left-handed on a whiteboard means you're either manipulating the pen uncomfortably from the far end, or you're smearing what you wrote. You're also tending to obscure the audience's view of what you just wrote with your hand, arm, and body.

I'm sure all of the above are part of why I prefer to avoid whiteboards, and would be much happier with my laptop on a projector. Although if I'm communicating with trusted peers I have no shame in putting up a smeared, slanted, and mostly illegible scrawl.

You should read the article. Whiteboards are just the first point, and I only denigrate them in the artificial context of interviewing.

When I teach, whiteboards are fantastic.

Every conference room whiteboard should be paired with a mirror, so that lefties can write backwards.

If you haven't tried it, writing backwards with your left hand is surprisingly easy when you first try it. (easier than writing forwards eith the left hand, or backwards with the right hand, as a rightie) It's just a more natural way to move your hand.

> writing left-handed on a whiteboard means you're either manipulating the pen uncomfortably from the far end, or you're smearing what you wrote

I'm left handed, and I hold the dry-erase marker comfortably and write without my hand touching the board. Certainly it takes a degree of coordination, but is this uncommon?

It's funny, I think every interviewee who has apologized for their bad handwriting has been at least 50th percentile in handwriting legibility.

Thanks for writing this up, it'll be quite useful to me.

I found your last line quite amusing: "I want to learn how to push the boundaries of knowledge, not just apply what I learned in these books."

When I quit my PhD to do a startup, my thinking was the exact opposite: "I want to apply what I know to solve real problems out there, not just keep learning and write more books which no one will read."!

First, let me just mention that I think it's fantastic when others offer to share their personal experiences with interviewing, particularly when what's shared is unique and interesting to read or look at.

As others pointed out, there's more to this article than the whiteboard title, and some great points (particularly a fan of the python one) are made. I can't agree with the whiteboard concept, unfortunately. Maybe it's because of my teaching background, but when I interviewed for a startup engineering position a long time ago, they loved my whiteboard usage. It was clear, easy to follow, and effective. In some respects, it's (part of) what got me the job offer.

That said, the main point between whiteboard or pen and paper: make sure you can express yourself clearly to your interviewers. It was crucial in all the essays I graded, and a key skill to attain no matter your profession.

I like seeing interviewees write on a whiteboard because I can see how they're thinking and help them out if I see that they're running into trouble. The point when I give a whiteboard question is to engage interactively with them over the course of ~15 minutes while they solve a problem, not to sit around and be handed a piece of paper at the end.

In addition, communicating with peers via whiteboard is a skill that is actually handy in day-to-day work life; it's not just some artificial interview skill.

> communicating with peers via whiteboard is a skill that is actually handy in day-to-day work life; it's not just some artificial interview skill.

Exactly.

So sit next to the person while they write...

The natural posture, position, and size of writing on paper discourages that. It's also essentially impossible for me to step in and point to/mark up their code (and then erase it). The paper takes away any of the collaboration that can occur during an interview. Your code might be better, but I have trouble seeing that you'd be able to project as a positive impression as if you used the whiteboard.

Parents of children and teachers don't seem to have a problem with paper.

I don't have a problem with paper - I just feel like it would work against a candidate - not because "Oh...they used paper", but because some of the things that I think are signs of a good candidate don't show through.

I've never interviewed a candidate that asked me to use paper, so I can't be sure - it's just my instinct.

It might be completely biased though - I far prefer to use whiteboards - I love the space, I love how easy it is to erase without a trace. I can throw thoughts up there and the manipulate them.

What do you do when your too tall for the whiteboard because some short stubby interviewer placed it lower than normal to accomodate his stubbiness.

Trying to write code on a whiteboard is not the same as communicating with peers via a whiteboard. I've never written or seen written anything more code-like than function prototypes on a whiteboard outside an interview session.

Design and flows get thrown on whiteboards a lot, but those are not code, and their creation is not remotely like coding. You are "testing" exactly the wrong thing.

Great article with lots of valuable info in there. The part about the actual whiteboard is almost irrelevant. Most of the comments here are getting too worked up about that.

"Learn Python and use it during your interview." Python is expressive, a high level and kind of writes like pseudo code. Just write pseudo code. The point isn't syntax anyways.

"The highest value problems I know of are on Project Euler." I do enjoy running through Project Euler problems but I have no evidence that's making me better at my day job, only better at answering Project Euler problems.

Many companies (including the one in question) want to see actual code in a language that they use at the company. The fact that Python happens to look like pseudo-code is a bonus.

Maybe you already knew all the lessons in Project Euler, but for me, I became a much better programmer. How elegant are your solutions? Have you tried writing them in a different style than you're used to? Say, in a functional style? With Haskell?

But if companies want to see actual code in a language they use, then learning python to use simply for interviewing wouldn't really work either right? So your only options would be "use any language but not just pseudo code" or interview for python jobs only.

Oh no, I certainly didn't know all the lessons and I haven't done all of them.

"How elegant are your solutions? Have you tried writing them in a different style than you're used to?" That's a great point, so I suppose it's less about the actual Project Euler problem, and more about optimizing, refactoring and trying them in different languages.

> That's a great point, so I suppose it's less about the actual Project Euler problem, and more about optimizing, refactoring and trying them in different languages.

Exactly. Make it better.

[Disagree]

Whiteboarding is a very, very valuable skill. The ability to effectively convey your ideas to a group of people, while presenting what amounts to an extemporaneous speech, is a tremendous asset.

>> is a tremendous asset

That is also essential for the applied position?

In the case of me hiring my replacement, yes.

Did anyone get the O(document size) solution? I can't see how it would work without checking each word against the list.

Use a bloom filter?

http://en.wikipedia.org/wiki/Bloom_filter

Thank you! This is Hacker News! Why isn't everyone trying to solve the problem?!

At first glance I don't think you can achieve O(document size) without some form of preprocessing. Each word in the vocabulary has to be looked at, so a natural lower boundary seems to be O(document size + vocabulary size).

Also it is unclear what will count as an atomic operation. Although the description reads as if word comparisons were counted, this makes for another simplification, as words could be of arbitrary size.

Also: I only checked the HN comment section to see if someone got the solution and I am amazed that others stuck to that part as well.

Yes, you use pre-processing.

I framed the problem in a very real-world scenario. Use that. It's not a trick question. How would you solve my real-world problem efficiently?

Setup a hashtable of keyword -> wikipedia link.

Check every word in the document against it. One check per word should be O(word count) ish, shouldn't it?

Hashing every word will have a cost, but will be roughly the same for each word so I'll brush it aside as a constant, setting up the hash will have a cost, but shared over the number of documents to check. Checking every word sounds expensive but so does looking every word up in any data structure or searching every dictionary word in the document keywords and links have to be stored somehow.

My biggest hesitation is it can't be that easy or all you and the interviewer would be saying it, so I must be glossing over some big cost somewhere, right?

That works if each phrase is one word. Many (most?) of the terms in the vocabulary are multi-word phrases. How would your algorithm work for multiple word phrases? What is its running time?

It would have to be altered; let's see:

Create hashtable where the key is the first word and the value is (rest of sentence, link). In the case of collisions, a list of rest of sentences and links.

Checking the document would still go word by word, if no lookup fine, if one result compare the rest of phrase with the following document words, if a list, do that repeatedly.

Runtime varies a lot with distribution of input phrases - if there are 50,000 beginning "phospholipid" that's not good.

I don't know how to estimate the runtime well, best case is no matches or single word phrases, and then as above. Worst case is every document word matches a long list of phrase endings but none of them complete, but even then the searching is only searching a fraction of the phrases in len(longest-phrase) chars of the document.

O(doc_words * num_of_phrases_by_prefix * avg_phrase_length)

I'm uncomfortable here, wishing I had more algorithm/data knowledge to draw on, and maybe wouldn't have gone down this route had I paid attention to many words from the start. Every problem doesn't need a hashtable. Maybe phrase-trees...

In the case of collisions, you need to search for a bunch of possible rest-of-sentence phrases in the text. This is exactly the problem that your algorithm tries to solve! If you apply it recursively, you get, essentially, trie matching with words instead of characters.

http://en.wikipedia.org/wiki/Trie

There is some bunch searching, but most of the document doesn't get searched, and the bits which get searched aren't searched for most of the keyphrases.

Instead of:

    For phrase in keyphrases:
        If phrase in document:
            pass

This

    For word in document:
        Some_phrases = get_keyphrases_starting[word]
        if document.next_5_words.find(some_phrases)

Instead of searching 100,000 keyphrases in the whole document, this searches 10 rest-of-sentences in the 5 words following a mention of 'phospholipid', 18 rest-of-sentences in the 3 word following 'proteomerase' and nothing in the text about the lab temperature, and never touches most of the keyphrases at all for the document.

Set up a trie containing each phrase in the vocabulary. Repeatedly match phrases starting at the current word against the trie, stopping at the longest matching phrase. Link that and reset from the first non-matching word.

The end result is O(n) in the number of characters in the document.

Yet another approach: Translate the regular expression for the disjunction of the search terms into a DFA. Then traverse each document with the DFA to find all matches. Traversing a string of length n with a DFA takes O(n) time regardless of the DFA's size.

The DFA turns out to be basically the same thing as the trie. Indeed, the standard DFA construction factors out common prefixes of the search terms, just like a trie. But this formulation has the advantage that anyone can implement it in a few minutes with their language's regex library. In Python you might do something like this:

    def searcher(terms):
        pattern = r"(?:^|\s)(%s)(?:$|\s|,|\.|!|\?)"
        dfa = re.compile(pattern % ('|'.join(map(re.escape, terms)),))
        return lambda string: dfa.findall(string)

This snippet also tries to deal properly (if simplistically) with search term occurrences bracketed by whitespace and punctuation.

As a side note, the problem didn't specify whether matches could overlap. Actualy, it isn't even solvable in O(n) time (plus precomputation) if overlapping matches are allowed. Let's say the search terms are "a", "aa", "aaa", etc, and the search string consists of n copies of "a". Then every substring of the string is a match and so there are O(n^2) matches, which obviously cannot be listed in O(n) time.

Most regex libraries don't do determinization (perhaps awk or grep do, but perl doesn't).

You'll want to do better than just "use a trie" - like http://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_string_mat...

Perl will actually use Aho-Corasick string matching for regular expressions like these.

The author brings up some interesting points, but fails to back them up. Why does he prefer not to write on the whiteboard? Why Python? [1] Why interview the interviewer? Sure, there are reasons I can think of, but I'm not convinced, and would like to know why he is.

[1] In later tips, he gets into some things that make Python good, but it needs to be justified more, given that his advice boils down to "use Python even if you've never seen it before".

I think the quote from the interviewer summarizes it best.

"Normally people write it in Java and it takes them a while and it takes up a lot more space on the whiteboard. They spend a lot of time manipulating the input string."

If you're more comfortable with Ruby, it would also be a great alternative. Clean, readable code. You get to focus on solving the problem.

The interviewers don't care. Use paper.

Uh, yeah, we do care. Part of what we're judging is your ability to present and explain your work. How you do your work is your business, but how you share it affects the people you work with. If you think it's all about you, then you're off on the wrong foot already.

We don't commit new code to whiteboards. We commit it to VCS. You know, with such electronic thingies, called computers. And when my interviewers wanted to collaborate they didn't find it too difficult with paper. Even sitting opposite of me (and that is why large tables in conferences are evil).

Use python even if you're a c++ systems guy. Or, you know, you could use the language that's most likely to be used in the job you're applying for. If you're a c++ & systems guy, interviewing for a c++ & systems job, c++ is far more likely to be the language of choice for an interview rather than buzzword-language-of-the-week, be it python, java, ruby, haskell, etc. Of course, if you're interviewing at a place you KNOW uses a lot of python, then yes, python would be a good choice.

Besides, most interviews I've had end up being a phone interview for knowledge and skillset, followed by the lunch interview where they're more concerned with finding out how you'll fit in with the existing team.

> Then take your solution and do it in half the lines. Now, read more of the Python docs (maybe read about generators and list comprehensions and decorators) and make it even shorter.

I don't agree with this. Shorter lines of code don't really express anything beyond how cuthulu-inspired your code will read, and performance is very likely to take a hit. Euler problem 2 solutions that are simply a for-loop rather than take advantage of geometric progression are slow and don't indicate higher-level abstraction of problems or the tools to solve them. Almost any programmer should be able to do the first 50 programs with random brute-force methods that are only a few lines long, but that doesn't do anything other than demonstrate you can have a computer add together numbers based on an if-statement.

It especially doesn't show you know how to bring together technologies that are useful for doing things such as building a website.

The poster is right -- don't write on a whiteboard. Instead, bring your laptop, make the font bigger on your favorite editor, and write in that. I've gone through many interviews like this, and only one interviewer insisted I use the whiteboard. And I'm pretty sure that was largely out of wanting to be fair to other candidates who didn't think to bring and use their laptops.

Since you will presumably be writing code on a computer when working at the company, why not write code on a computer when interviewing with one?

It seems a lot of what he's talking about is how to deal with anxiety. One way to do this that I've found extremely useful is just to say "I've gotta be honest, I'm feeling a little anxious about this." Not just in interviewing, but in anything in life. If you are willing to be vulnerable, oftentimes that allows you to breathe and the person you share the vulnerability with will come to your rescue (i.e. help to set you at ease).

That said, don't be needy. Just acknowledge your anxiety.

I've done interviews both ways (paper and whiteboard), on both sides of the fence.

It's never been a big deal.

I /have/ seen candidates fail because they insisted on using a laptop. But these folks were typically very nervous about coding, and had essentially pre-failed the interview in their head. Their laptop was a security blanket, a totem that they hoped would sustain them, and it didn't work.

I don't know whether others are like me but I've spent so much time typing rather than writing that my writing is rather bad. Writing on whiteboard is actually easier than on paper. Perhaps the best is to bring a laptop and type it out?

Understand what you don't know, why you don't know it, have an interest in it

This strikes me as the fundamentals for what someone should look for in an interview for a startup or research position.

You should always have paper and pen anyway to write down ideas

Am I the only one who is not such a fountain of ideas that I can keep it all in my head?

You're definitely not alone. But, I've found that even if you don't do it, you should still try.

During my last interview I brought along a notebook, the day before the interview and the bus ride over to the office I wrote down any question that I could think of in the notebook, even forcing myself to think of extra questions.

It got people's attention, I talked with 6 pairs of people and each one pointed it out in one way or another.

Certainly take notes in preparation for an interview. Certainly bring a notebook to an interview. I just don't see this whole "carry a notebook at all times" thing.

Respectfully, what is the benefit to recording your notes and ideas on paper, and using paper at interviews, instead of using txt files in the dropbox folder of the always-connected smartphone in your pocket?

It's sufficiently painful to express myself on the tiny keyboard that I tend to avoid it. Not to mention if you want to sketch something.

It's way more classy to have & take your interview notes on a legal pad or similar. I would bet money if you kept pulling out your smartphone during your interview, you are not getting a job.

A legal pad looks "prepared". A smartphone looks "distracted".

I could keep everything in my head--the problem is that I'll forget it at some point, whether it's a week from now, a day from now, or 5 minutes from now. Writing stuff down helps.

A hashtable need not have a "set key" or "get key" method. It only needs get(key), and put(key,value)

As a bonus to my upvote, I want to be clear: This is a great read. It inspires people to learn algorithms, know how to back up your assertions, and be confident with an interviewer.

is the OP a professional employee/interviewee or something? the energy spent preparing for (seemingly countless) interviews could have been spent working on things s/he is passionate about.

I have dinged people because they wouldn't write on the whiteboard. To be fair, every time this actually happened, I gave the candidate the chance to write his solution on paper, and I ended up dinged him anyways because his work was sub-par.

At every company I have worked at, from two-person startups all the way to Google, we have used whiteboards extensively. Most meetings and architecture reviews are conducted in front of a whiteboard. The first thing I do when I found a startup is to buy a whiteboard and nail it to the wall. Whiteboards are a necessity for collaborative brainstorming and working together.

I'm not sure I agree with anything the OP says in this article. I think he's trying to sound smart and rationalize the reasons he didn't get hired. I say this not as a troll, but to provide constructive feedback. If you want to get hired by a big company, you have to play by their rules. End of story. There are a few exceptions (like engineers at Google without college degrees), but they are exceptions - most people who work for Google or Facebook or Palantir went to good schools, and did well, and wrote on the whiteboard during their interviews.

You sound like you have confirmation bias, and your whole point seems to be to adhere to the status quo.

The notion that an engineer's ability can be discerned by willingness and comfort at a whiteboard is utterly ridiculous.

Reply on news.ycombinator.com