Month: August 2011

A few days ago, our CEO Jeff Weiner led a session at LinkedIn on how to “close” candidates — that is, how to persuade candidates to join your team once you have found and interviewed them. Since not everyone has the opportunity to work at LinkedIn and experience Jeff’s leadership first-hand, I thought I’d share some of his wisdom here.

The key take-away  was that closing a candidate is not about selling the job or company to the candidate, but rather working with the candidate to figure out what the candidate wants and whether the job will help him or her achieve that desire. As an employer, you need to do three things to close a candidate:

1) Figure out what is the candidate’s dream.
2) Determine if job and candidate are the right fit.
3) Communicate your own passion.

Let’s take these one at a time.

Dream.

As I’ve written here in the past, we have to dare to dream. Most of us rely on jobs to sustain us and our loved ones — and for some a job is nothing more than that. There’s no shame in having a dream that is unrelated to a job — Franz Kafka famously worked in a variety of “bread jobs” in order to pay the bills while he wrote novels. Others find their calling as humanitarians, activists, or care givers. It’s easy for many of us to forget that life isn’t always about work.

But the great thing about working in technology is that you can get paid to fulfill your own dream. Look at Larry and Sergey, who set out to organize the world’s information. Or Steve Jobs, whose dream has been to create innovative products. Not everyone is as specific in their dreams or as successful in realizing them, but, as the saying goes, you have to be in it to win it.

Convincing a person to accept a job offer works best when that job brings the person closer to fulfilling his or her dream. My own decisions to go to Google and then LinkedIn are good examples. Working at Endeca drove me to pursue a vision of HCIR — to optimize the way people and machines work together to solve information seeking and exploration tasks. At Google, I hoped to bring exploratory search to the open web. I’ll concede that I did not make much headway, but I’m glad that I tried.

And at LinkedIn, I work on problems that not only stretch the boundaries of information science, but whose solutions help millions of other people achieve their dreams by making them more successful professionally. My dream is to truly reduce HCIR to practice so that people can lead better and more productive lives. Once the folks at LinkedIn understood my dream, closing me was just a matter of offering me the keys to make that dream a reality.

If you want someone to work at your company, get to know that person’s dreams. If the job you are offering can’t help him or her realize those dreams, be honest about it. It’s better for both of you, and for a world that is better off with people devoting their lives’ work to fulfilling their dreams.

Fit.

Fit is a two way street: the candidate should be right for the job, and the job should be right for the candidate. The interviewing process typically focuses on establishing the former, but we often forget that the candidate’s decision focuses on the latter. Just because someone is capable of doing a job doesn’t mean it’s the right job for that person.

For me, fit means many things. A work environment where people work hard and take the company’s success personally. Incentives that allow everyone to win, rather than a zero-sum game where people compete for scarce opportunities. Openness, since I’m someone who lives most of my life in public. I could go on — but I hope you get the general idea. Fit is the set of functional and non-functional requirements that determine whether someone will enjoy a job. And people who enjoy their jobs tend to be productive and stay a while.

If you are trying to persuade someone to accept a job offer, you have to see the decision from that person’s point of view. In other words, ask yourself — and convincingly answer — why the job is the right fit for the candidate. That means accepting the possibility that is isn’t the right fit, and doing right by the candidate even if that means backing off.

Passion.

Choosing a job is one of the most important life decisions that people make. It’s not quite up there with getting married or having a child, but it’s a a decision that most people take (and should take) very seriously. Some people create spreadsheets of the pros and cons to compare opportunities and try to frame their decision as an optimization problem. Others go with their gut.

Those who know me personally — whether from face-to-face or online interaction — know that I wear my passion on my sleeve. I can’t understand how someone could get up in the morning and go to work without being passionate about his or her job. I know that many people don’t have a choice in the matter, and I pity them. In a country where most people take subsistence for granted, having a job you love strikes me as a necessity, rather than a luxury.

But what is clear is that if you, as an employer, are not passionate about what you do, you have no business expecting a candidate to take such a big leap of faith with you. Moreover, passion is hard to fake. As it should be — I’m not suggesting that employers should pretend to be excited about their jobs. Rather, your own sincere excitement is a baseline for those you hope to attract to your team. Passion is contagious, and passion is the raw material for making dreams come true.

Dream. Fit. Passion.

There you have it: dream, fit, passion. And remember, closing isn’t selling. Do right by the people you try to hire. After all, jobs are short, but careers are long. Celebrate everyone’s professional success, and take your losses in stride. I can tell you from experience that it all works out for the best.

Interviewing software engineers is hard. Jeff Atwood bemoans how difficult it is to find candidates who can write code. The tech press sporadically publishes “best” interview questions that make me cringe — though I love the IKEA question. Startups like Codility and Interview Street see this challenge as an opportunity, offering hiring managers the prospect of outsourcing their coding interviews. Meanwhile, Diego Basch and others are urging us to stop subjecting candidates to whiteboard coding exercises.

I don’t have a silver bullet to offer. I agree that IQ tests and gotcha questions are a terrible way to assess software engineering candidates. At best, they test only one desirable attribute; at worst, they are a crapshoot as to whether a candidate has seen a similar problem or stumbles into the key insight. Coding questions are a much better tool for assessing people whose day job will be coding, but conventional interviews — whether by phone or in person — are a suboptimal way to test coding strength. Also, it’s not clear whether a coding question should assess problem-solving, pure translation of a solution into working code, or both.

In the face of all of these challenges, I came up with an interview problem that has served me and others well for a few years at Endeca, Google, and LinkedIn. It is with a heavy heart that I retire it, for reasons I’ll discuss at the end of the post. But first let me describe the problem and explain why it has been so effective.

The Problem

I call it the “word break” problem and describe it as follows:

Given an input string and a dictionary of words,
segment the input string into a space-separated
sequence of dictionary words if possible. For
example, if the input string is "applepie" and
dictionary contains a standard set of English words,
then we would return the string "apple pie" as output.

Note that I’ve deliberately left some aspects of this problem vague or underspecified, giving the candidate an opportunity to flesh them out. Here are examples of questions a candidate might ask, and how I would answer them:

Q: What if the input string is already a word in the
   dictionary?
A: A single word is a special case of a space-separated
   sequence of words.

Q: Should I only consider segmentations into two words?
A: No, but start with that case if it's easier.

Q: What if the input string cannot be segmented into a
   sequence of words in the dictionary?
A: Then return null or something equivalent.

Q: What about stemming, spelling correction, etc.?
A: Just segment the exact input string into a sequence
   of exact words in the dictionary.

Q: What if there are multiple valid segmentations?
A: Just return any valid segmentation if there is one.

Q: I'm thinking of implementing the dictionary as a
   trie, suffix tree, Fibonacci heap, ...
A: You don't need to implement the dictionary. Just
   assume access to a reasonable implementation.

Q: What operations does the dictionary support?
A: Exact string lookup. That's all you need.

Q: How big is the dictionary?
A: Assume it's much bigger than the input string,
   but that it fits in memory.

Seeing how a candidate negotiates these details is instructive: it offers you a sense of the candidate’s communication skills and attention to detail, not to mention the candidate’s basic understanding of data structures and algorithms.

A FizzBuzz Solution

Enough with the problem specification and on to the solution. Some candidates start with the simplified version of the problem that only considers segmentations into two words. I consider this a FizzBuzz problem, and I expect any competent software engineer to produce the equivalent of the following in their programming language of choice. I’ll use Java in my example solutions.

String SegmentString(String input, Set<String> dict) {
  int len = input.length();
  for (int i = 1; i < len; i++) {
    String prefix = input.substring(0, i);
    if (dict.contains(prefix)) {
      String suffix = input.substring(i, len);
      if (dict.contains(suffix)) {
        return prefix + " " + suffix;
      }
    }
  }
  return null;
}

I have interviewed candidates who could not produce the above — including candidates who had passed a technical phone screen at Google. As Jeff Atwood says, FizzBuzz problems are a great way to keep interviewers from wasting their time interviewing programmers who can’t program.

A General Solution

Of course, the more interesting problem is the general case, where the input string may be segmented into any number of dictionary words. There are a number of ways to approach this problem, but the most straightforward is recursive backtracking. Here is a typical solution that builds on the previous one:

String SegmentString(String input, Set<String> dict) {
  if (dict.contains(input)) return input;
  int len = input.length();
  for (int i = 1; i < len; i++) {
    String prefix = input.substring(0, i);
    if (dict.contains(prefix)) {
      String suffix = input.substring(i, len);
      String segSuffix = SegmentString(suffix, dict);
      if (segSuffix != null) {
        return prefix + " " + segSuffix;
      }
    }
  }
  return null;
}

Many candidates for software engineering positions cannot come up with the above or an equivalent (e.g., a solution that uses an explicit stack) in half an hour. I’m sure that many of them are competent and productive. But I would not hire them to work on information retrieval or machine learning problems, especially at a company that delivers search functionality on a massive scale.

Analyzing the Running Time

But wait, there’s more! When a candidate does arrive at a solution like the above, I ask for an big O analysis of its worst-case running time as a function of n, the length of the input string. I’ve heard candidates respond with everything from O(n) to O(n!).

I typically offer the following hint:

Consider a pathological dictionary containing the words
"a", "aa", "aaa", ..., i.e., words composed solely of
the letter 'a'. What happens when the input string is a
sequence of n-1 'a's followed by a 'b'?

Hopefully the candidate can figure out that the recursive backtracking solution will explore every possible segmentation of this input string, which reduces the analysis to determine the number of possible segmentations. I leave it as an exercise to the reader (with this hint) to determine that this number is O(2ⁿ).

An Efficient Solution

If a candidate gets this far, I ask if it is possible to do better than O(2ⁿ). Most candidates realize this is a loaded question, and strong ones recognize the opportunity to apply dynamic programming or memoization. Here is a solution using memoization:

Map<String, String> memoized;

String SegmentString(String input, Set<String> dict) {
  if (dict.contains(input)) return input;
  if (memoized.containsKey(input) {
    return memoized.get(input);
  }
  int len = input.length();
  for (int i = 1; i < len; i++) {
    String prefix = input.substring(0, i);
    if (dict.contains(prefix)) {
      String suffix = input.substring(i, len);
      String segSuffix = SegmentString(suffix, dict);
      if (segSuffix != null) {
        return prefix + " " + segSuffix;
      }
  }
  memoized.put(input, null);
  return null;
}

Again the candidate should be able to perform the worst-case analysis. The key insight is that SegmentString is only called on suffixes of the original input string, and that there are only O(n) suffixes. I leave as an exercise to the reader to determine that the worst-case running time of the memoized solution above is O(n²), assuming that the substring operation only requires constant time (a discussion which itself makes for an interesting tangent).

Why I Love This Problem

There are lots of reasons I love this problem. I’ll enumerate a few:

• It is a real problem that came up in the course of developing production software. I developed Endeca’s original implementation for rewriting search queries, and this problem came up in the context of spelling correction and thesaurus expansion.
• It does not require any specialized knowledge — just strings, sets, maps, recursion, and a simple application of dynamic programming / memoization. Basics that are covered in a first- or second-year undergraduate course in computer science.
• The code is non-trivial but compact enough to use under the tight conditions of a 45-minute interview, whether in person or over the phone using a tool like Collabedit.
• The problem is challenging, but it isn’t a gotcha problem. Rather, it requires a methodical analysis of the problem and the application of basic computer science tools.
• The candidate’s performance on the problem isn’t binary. The worst candidates don’t even manage to implement the fizzbuzz solution in 45 minutes. The best implement a memoized solution in 10 minutes, allowing you to make the problem even more interesting, e.g., asking how they would handle a dictionary too large to fit in main memory. Most candidates perform somewhere in the middle.

Happy Retirement

Unfortunately, all good things come to an end. I recently discovered that a candidate posted this problem on Glassdoor. The solution posted there hardly goes into the level of detail I’ve provided in this post, but I decided that a problem this good deserved to retire in style.

It’s hard to come up with good interview problems, and it’s also hard to keep secrets. The secret may be to keep fewer secrets. An ideal interview question is one for which advance knowledge has limited value. I’m working with my colleagues on such an approach. Naturally, I’ll share more if and when we deploy it.

In the meantime, I hope that everyone who experienced the word break problem appreciated it as a worthy test of their skills. No problem is perfect, nor can performance on a single interview question ever be a perfect predictor of how well a candidate will perform as an engineer. Still, this one was pretty good, and I know that a bunch of us will miss it.

ps. Check out this post by Behdad Esfahbod that does the problem justice! He also notes that looking up a string in a dictionary isn’t O(1) but has a cost proportional to the string length, which motivates exploring a trie rather than a dictionary to store the strings.