Hacker News Reader

Comment by philwelch | Hacker News Reader

Sorry, if I ask you to write a function that determines whether two given words are anagrams of each other, "I need to get into my comfortable space for my creative process to work" is an evasion. No one's asking for a masterpiece, just a demonstration of basic competence.

View on HN

What kills me with Do Work While We Stare At You interviews is my process is all over the place. I tend to draft something, try it, find my five mistakes, try more things, etc.

That doesn't fly in an interview. At least, I don't feel it does. Interviewers expect mostly right and mostly very fast. I end up standing there trying to pre-think the entire problem so something correct comes out the first time, which, to them, is just dead time with me staring at the wall.

The other option is to "dive in" and backtrack a lot, but the people watching can't tell the difference between actual incompetence and just figuring it out.

That doesn't fly in an interview.

Actually, it does.

I've been interviewing a lot lately, and I'm totally fine with people trying something, changing their mind, fixing mistakes, etc. When they get stuck, I help them out. All decent interviewers know that being interviewed is stressful and that you need to cut candidates some slack.

Speaking personally, I don't care much about speed. I care about things like how much fluency do you have with your programming language (is writing a for loop something you have to struggle with?), do you know how to use a hash table (you'd be amazed at how many people don't), can you explain what the tradeoffs are when you make design choices and compare them to the alternatives, etc.

Also, since I can, I'm going to complain about my pet peeve: candidates who want to write a solution in C++ or C or java (I let them choose any language they want) but who refuse to use a container library. They'll insist on using arrays, even when the problem pretty clearly requires something like std::vector. And then they'll tie themselves in knots to make static fixed size arrays work. Now, if you can justify why you don't want to use a @#$! container library, that's fine, but usually the justifications are garbage ("it will be too slow...no, I've never measured that"). What really gets me is that a good sw engineer should be able to see that rewriting stl::vector by hand in every application intertwining its code with your application code (vector's client) is a maintenance and performance nightmare.

And here's the rub: Running an interview this way is hard to do RIGHT. The questions have to be tractable for the given time, not too oblivious that the candidate blows through them, not too domain-specific that the interviewer ends up giving a lecture to education the interviewee on the domain. Then there's the proctoring of the question.

Show of hands here: Who here has worked a companies where they used white boarding as part of their process? Did any of the following happen?

* Interviewers asked pet questions instead of using a vetted list of questions * Interviewers never tried any of the questions in interview conditions * Interviewers were never trained/practiced giving these sorts of interviews * Random developers were pulled into interviews to proctor a white boarding.

Guess what? The development team is learning how to interview candidates by interviewing candidates! Not prepping a team on how to interview seems very common. Maybe candidates are expendable and ultimately are the ones that need to prove themselves.

I have to wonder how many times qualified candidates get bypassed because they didn't whiteboard just so to the interview's liking. More concerning, how many times have unqualified candidates buffalo inexperienced interviewers with hand-waves or by luck of having seen the problem before, and end up weighing down the team with incompetence.

> What kills me with Do Work While We Stare At You interviews is my process is all over the place. I tend to draft something, try it, find my five mistakes, try more things, etc.

Well yeah, that's exactly how those interviews generally go. You have to kind of narrate what you're doing, and that can be awkward at first but coming up with the optimal answer in the end is not the only goal of the interview. By all means show your work.

My process is similarly all over the place, but DWWWSAY suffers from the additional problem that 80% of my thinking power is taken up with social crap in a situation like this, so the interviewer is essentially seeing me at 20% speed. This may be why I have never gotten a job after being asked to demonstrate coding something on a whiteboard. :)

Here is a first go at it:

https://gist.github.com/rilindo/6575580

Essentially, I just checked to see if the characters in the first string exists in other string and exits out of the code. It probably won't cover every use case (in other words, probably very buggy), but it is a start.

However, I have the luxury of relaxing while looking up the functions online, writing the code by my lonesome and then verifying it by running it directly. Last I checked, not any of these things are likely not present or available in a white board interview.

EDIT: I should at least put it in a function. :D

You might want to try something like 'return set(x)==set(y)'. Or, a better solution might be 'return set(collections.Counter(x).items())==set(collections.Counter(y).items())'.

The point of the question isn't to see if you've memorized every single stdlib function. If you can describe a stdlib function but can't remember it, a good interviewer will tell you about it.

Be careful using sets -- what about "banana" and "ban"

The OP's solution didn't deal with letter counts at all; my first expression was to show him a similar solution that was more succinct to illustrate the principle at work. My second solution deals with multiplicity properly.

Yes and I appreciate it.

https://gist.github.com/rilindo/6576017

New toy to play with. :)

Python's Counters can also be compared directly. No need to drop them in a set; `Counter([1, 1, 2, 3]) == Counter([1, 2, 3, 1])`.

Using Counters is actually pretty cool... it's basically a sparse histogram. Can't believe I've never used 'em before -- all I've ever used from collections is OrderedDicts.

Actually... I prefer the parent's solution using set(counter.items()). This way, you know that the equality tests are ordering-agnostic. It's not clear if that's the case for counters... even the docs are unclear AFAICT: http://docs.python.org/2/library/collections.html#collection...

At that point, might as well just do `sorted(list(x)) == sorted(list(y))`.

Counters are effectively building a sparse histogram by going through each element in x, and then each element in y. Ignoring the test for equality, the Big-O for histograms is O(x+y). For sorting in general, the Big-O is O(x·log(x)+y·log(y)). In other words: the sorting solution is correct but less efficient.

What an interviewer will usually be looking for on a whiteboard interview is not knowledge of a library, but that the interviewee can reason that there's a better solution that works much faster than this solution.

Remembering the standard library isn't the competency being tested for, but rather the soundness of your solution. Your first solution has two problems from an interview-question standpoint: first, it's incorrect (it misses the case where two words use all the same letters but aren't anagrams, like "banana" and "nab"), and second, you're looping through each character of the second string for each character of the first string so it's a slow algorithm. I would probably try and get you to figure these out with probing questions, but the expectation is that you can figure it out and fix it.

There's a much easier way to solve this problem than what you've done. And this is sorta/kinda the point of the article, where you will do well at a technical interview if you know some tricks in programming, whether it be through academic study or just on-the-job stuff.

To find if two words are anagrams of each other, do this:

sort(word1) == sort(word2)

done.

The trick is knowing that an anagram has a signature, and that signature can be found if you sort a word's characters alphabetically. Then you do the same to the other word and compare both of their signatures together. Voilá.

    "genuine class" == "alec guinness"
    because
    "aceegilnnssu" == "aceegilnnssu"

In Ruby you'd write your own alphabetic sorting function first, then apply it to each word.

    def sortAZ (word)
      word.downcase.unpack("c*").sort.pack("c*")
    end

    def is_anagram (word1, word2)
      sortAZ(word1) == sortAZ(word2)
    end

    puts "is_anagram(ARGV[1], ARGV[2])"

I recall seeing this trick in a Ruby book (probably PickAxe or something) and thought it was cool because I had never thought about finding an anagram in this way. Regardless, it stuck with me so, if this was asked in an interview, I'd be able to answer the question easily and look like a rockstar...when really it's just knowledge that stuck with me.

By the way, the alphabetic sorting here is done by unpacking each character into its number representation and then sorting the resulting numbers.

An even easier way is to check StackOverflow.

http://stackoverflow.com/questions/9321654/java-anagram-find...

One of the comments mentions: "Just had a phone interview with Amazon and this was the exact question they asked. Interesting problem if you have more than 10 minutes to solve it. – Javamann Jun 14 '12 at 20:46"

So....do you store this knowledge in your back pocket in case you need to check anagrams at work (which will be never), or do you toss it aside knowing you can hit StackOverflow if/when you need it?

It seems like the only time this stuff is "used" is on technical interviews.

I readily concede you can't substitute StackOverflow for general competence, but an algo for checking for anagrams doesn't seem like general competence.

The whole point of the question is that you don't already know the solution. If you already knew the solution the question would be less useful.

Another easy solution is to just make a histogram of characters in each word and to compare the histograms.

Anyway, if anagram questions were all that were asked in technical interviews, I really doubt we'd have so much critique and analysis here. I've never been asked such a simple question in any technical interview. The closest would be the first phone screen I had for a Google internship, which had (arguably) simpler questions (like raise one integer to an integer power efficiently) but there were like three or four of them that you had to get right.

The anagram question is a phone screen question, yeah. I believe the histogram solution is better performing than sorting, because storing the histograms as hash tables is O(n) on both words while the sorting solution is O(nlogn).

If the interviewer expects a correct answer off the bat, or rates candidates based on the time they got the solution, then the interview process is bad.

But the question is legitimate. If you're a programmer then you should be able to come up at least with a naive (but correct) solution. You don't need any tricks for that. Then you estimate the efficiency of your naive solution and see if you can improve it.

That said, there's still the problem that OP and several comments here mention, that the interviewer might get nervous, freeze, etc, even for problems that they would normally have no problem solving.

I think the general approach in an interview would be to ask the person being interviews "can you explain what time function that runs in".. "can you improve it", and see if they work out the "sort" trick by themselves.

That's how it was done to me anyway (although I talked it through before I started writing, and by the time I got actually writing anything down I'd worked out the trick).

>> No one's asking for a masterpiece, just a demonstration of basic competence.

Once the candidate demonstrates the basic competence, what would be a good next step? How should one evaluate the higher level of thinking like creativity, (higher-level) problem solving, etc., which may be just as important for the position at hand as the basic competence?

If you do have a good answer to the above, the next question could be if you could have tested this higher-level thinking without the basic coding competence if (and only if) so were the nature of the job.

These kind of FizzBuzz stuff is not an issue I believe (although, "going blank" during the phone call or in similar situation is as well legitimate).

The main problem is that interviewers (BigCo's) ask questions that require inventing Knuth-Morris-Pratt algorithm or K-D trees on the spot, whereas researches spent months... Of course I assume that the interviewee is not aware of these a priori (or it's been a decade since he last heard about these).

https://gist.github.com/MichaelMorett/6576434

I think I'd get yelled at in an interview for this one since I didn't punch down to String manipulation (which is probably what they're really looking for).

Are you thinking of palindromes?

LOL!!! I coughed up my beer on that comment. I feel so dumb. Yes, I was thinking palindromes.

Either way, I blew that interview. :-)

>> if I ask you to write a function that determines whether two given words are anagrams of each other

I've no college degree, I've been writing software earning me a comfortable living for 2 decades and for fun for 3 decades. I've solved a lot of problems in software and never heard of Big O until recently on HN. If you ask me about college quiz stuff like fuzzbuster (fizzbuster?) or anagrams I have to Google what an anagram is in the first place. I've never seen anyone paid to write them, never had a manager ask me to write one.

Anagrams aren't some sort of classic CS problem domain, it's just a relatively simple example. One would start the question by making sure you knew what an anagram was. Two words are anagrams you can rearrange the letters in one of them to make the other, like "Mary" and "army".

Phil, the point is who gives a flying f in production about anagrams. Noone has to deliver a meaningful abstraction in < an hour (or 15 minutes as a "simple" example of "puzzle" testing), and interviewing for that is truly ridiculous.

You and others might find it meaningful but after two decades of development I really have to question those who do.

Like you - I've never needed to solve an anagram in production.

I think many are missing the point. In an interview situation, the anagram problem gets the person to write some basic, naive code (ie, proves that can track loops) which I think we would both agree is reasonable.

Then the interviewer gets you to look at how to improve it. Hopefully you'll notice that iterating over both strings isn't very efficient, and reason about ways to improve that.

It's that reasoning process that is important, not the knowledge of how to write an anagram solver.

To be fair, though - most programmers should be able to solve it with a couple of hints.

If anything, not being a real problem is a feature. Very few candidates will have ever actually had to solve anagram problems, so most candidates will be equally unfamiliar with the question, making it a fair measure of the candidate's ability to solve simple problems they haven't seen before.

Here's an example of an interview question that doesn't have this feature: "How would you serialize a tree?" The Lisp programmers will get that one right away. Even people with a passing familiarity with XML will get it right away. You don't know if they would have been able to figure it out themselves, all you know is that they've seen serialized trees before.

Tree serialization seems reasonable - basically you end up looking at tree walking algorithms and some recursion, right? (I can't remember the costs & benefits of depth first vs breadth first traversal, but I'm sure I'd work something out).

OTOH, I was once asked to write a Sudoku solver in an interview. I'd never really solved a Sudoku myself at the time (although at least I knew how it worked), so I had to try and work out an approach to solving the puzzle as well as how to write the code. I found that pretty tough.

Tree serialization is a reasonable question, but it's one where lots of people have already seen the solution, hence my mentions of Lisp and XML.

The purpose of a question like this, and of the classic FizzBuzz question, is to be a lightweight test of whether a candidate can actually write code or not. That's all. It provides a negative signal if they fall completely to get anywhere close, and nothing more.

There are alternatives, you could ask them to explain a piece of code they wrote on their own before the interview, any piece of code would do. I suppose that could be gamed which is why most companies opt for FizzBuzz.

Personally, once I started thinking about these kinds of questions like this, I had less issue with them. Interviewing people who failed to write FizzBuzz opened my eyes too.

Since a reply link isn't available for spacemanaki's comment, I'll stick it here:

"The purpose of a question like this, and of the classic FizzBuzz question, is to be a lightweight test of whether a candidate can actually write code or not. That's all. It provides a negative signal if they fall completely to get anywhere close, and nothing more."

I disagree. Vehemently. Provide me an email address and I'll mail you tons of code I've written. You cannot, cannot conclude with any accuracy that the inability to code up a method/function to check an anagram means that the person cannot write code. What you can conclude is that they cannot write up a method/function to check an anagram.

You're making an assumption. If a = b and b = c, then a = c. That works in math class but not here. The test is not one of syntax or knowledge of the language but of knowledge of a specific problem. Some here have used the word "trick". I don't even need to go there. Once you have the answer to this anagram exercise, you can back into why it's a good question, what it supposedly shows, etc. At that point you're justifying the question and defending it.

But you missed the entire point of the exercise: you're supposedly screening candidates for knowledge of a language and how they might have used it in their past experience, but letting it all come down to whether they solve your specific problem on the spot with all of Pamela's concerns about stress, etc.

It's easier to ask about an anagram than to ask about a candidate's past and what they did on their projects. If not an anagram, there are others. There will always be "solve this now" rather than "tell me about..." That's just the game.

> You cannot, cannot conclude with any accuracy that the inability to code up a method/function to check an anagram means that the person cannot write code. What you can conclude is that they cannot write up a method/function to check an anagram.

If you can't check an anagram given the definition of an anagram and the programming language of your choice, what problems can you solve? It's not a hard question and if you can't come up with a correct solution at all, I dare say you lack the ability to program.

So, I understand and am incredibly sympathetic to the stress problem some folks have. I also occasionally freeze up when put on the spot, though I fortunately tend to recover after a minute or so of verbal stumbling.

That said, hiring quality engineers is HARD, and often ends up coming down to a numbers game. If I've got 100 applicants to go through and know (from past experience) that over 80% of them couldn't code their way out of a wet paper bag, then I need short, deterministic interview techniques that will identify those candidates who are actually worth my time. Thus: fizzbuzz. I've met lots of folks who talk a great game, have all kinds of experience listed on their resume, and yet somehow can't write up a linked list or fizzbuzz solution in any language.

So, I accept that there will be some false negatives in order to more quickly narrow the focus down to those few rare folks that can actually code. It sucks: it isn't entirely fair to folks who struggle with stress/nerves, but I need a 5-15 minute litmus test that can be done remotely and I haven't found anything else more effective.

Short of wasting everyone's time with take-home projects (which I often employ in later stages of the interview process), what other options are out there?

That's the $64,000 question. If I knew the answer, that would be my startup. It's a tough problem. It almost makes one beg for some sort of one-off certification (bar exam?) so we can put that to rest for ever after. I'll go out on a limb and say that most lawyers, especially the senior ones, probably couldn't pass the bar exam again. Developers have a mini bar exam every time they interview (hence the studying).

That said, there's one thing you wrote I took interest in: "I've met lots of folks who talk a great game, have all kinds of experience listed on their resume, and yet somehow can't write up a linked list..."

Umm...that would be me. I've never written a linked list. Guilty as charged. Java has a LinkedList class and I've never bothered to look at the implementation nor have I ever been curious enough to (re)write one from scratch.

I wish you would have said "...and yet somehow don't know when to use a linked list." That moves it from an academic exercise mostly applicable to CS students who might have written one 6 months ago, to a meaningful real world scenario and more than legitimate. Choosing the appropriate data structure, knowing when and why, is both realistic and important. I don't know how a candidate can bullshit their way thru a discussion of data structures where they can articulate, accurately, which one to use, when, and why.

Salient points all, I wish I could have stated my views as eloquently.

I'll ask you a slightly different question then: when is it appropriate to use a linked list? In which of those cases might it still be inappropriate and why?

These things can be memorized of course but I find that if one has a reasonable understanding of the underlying machine and knows how to implement a range of data structures and algorithms the answer to these questions (for most of the less specialized data structures) becomes quite straightforward. Whether that is relevant very much depends on the job being interviewed for however.

> I've never written a linked list. Guilty as charged. Java has a LinkedList class and I've never bothered to look at the implementation nor have I ever been curious enough to (re)write one from scratch.

Good! You're right: the JDK's implementation is perfectly acceptable, and you'd be crazy to write your own. I certainly haven't, either.

But if you have any CS education, I'll bet you know what a linked list is at a high level. And I can probably verbally walk you through turning that into a "spec" that's good enough for a basic whiteboard implementation of one that supports a couple of basic operations. It's (hopefully) just another fizzbuzz: a simple problem to demonstrate that you can code something/anything. The overwhelming majority of applicants can't.

I really have to question those who find the question so difficult they would rather rationalize why they shouldn't have to answer it or handwave about how they can't possibly solve even simple programming problems in anywhere less than an hour.

HN seems to lack reply links in some messages so I need to answer you here.

"If you can't check an anagram given the definition of an anagram and the programming language of your choice, what problems can you solve? It's not a hard question and if you can't come up with a correct solution at all, I dare say you lack the ability to program."

Here's your anagrams checker tough guy:

  static boolean anagram(String word1, String word2) {
    char[] chars1 = word1.toCharArray();
    char[] chars2 = word2.toCharArray();
    Arrays.sort(chars1);
    Arrays.sort(chars2);
    return Arrays.equals(chars1, chars2);
  }

I was speaking in the abstract, but you made it personal.

Would you like me to build a search engine next?

Reply links take longer to generate on HN as comment threads get deeper in order to deter people from losing their temper and flaming each other. In your case I would say that didn't quite work. My comment was not meant personally but as a general statement. If you had kept your composure and waited for the reply link to show up instead of flying off the handle about it and replying to an unrelated comment, perhaps we would be having a more productive conversation right now.

Then please accept my apologies. I enjoyed the anagram thing as it forced me into looking into it.

Okay, now make it faster.

I'm not trying to be obnoxious, but your answer is not optimal. Which is not a big deal, and it would give us a chance to talk about ways of optimizing code. Sooner or later we'd figure out if you knew what a hash table is and how to use it (no real points off if you never really got, under the pressure of an interview, the hash table solution to this problem), how you would go about profiling code, how you might solve this if they weren't strings but social security numbers, and so on. It's a launching off point to more interesting discussions. At least that's how I'd use it in an interview. Before long we'd be talking about a, I dunno, search engine or something.

Lol!! You're killing me. I need to work tomorrow and you're gonna have me up all night thinking how to optimize this thing. It's only 5 lines of code.

Hashtable, huh? I don't like them because they're synchronized, but let's use a HashMap instead. Regardless, I'm stumped.

Let me think out loud. You'd probably want me to stick two entries in there with the words being the values. I suspect the keys are irrelevant. But I need the values themselves sorted prior to being placed in the map. Lets assume I stick the char arrays in the map. I still can't see how the map helps. Unless, I abandon the HashMap and go with a TreeMap instead. That negates the need to explicitly sort and maybe that's the time savings, but....

My head hurts. :-)

I don't know. I'd have to code this out and experiment a bit. But I like the push. You're forcing me to dig deeper.

PS. I can't build a search engine.

EDIT: A quick search of the net yields at least one answer (don't know if this works):

"We can solve this problem in O(n) time by using hashtable. That is, create a hashtable which record the times that the characters a-Z appear in S1 and create another hashtable for S2. If the two hashtables have the same content, then the strings are identical. This solution requires O(n) time to create two hashtables and compare them, and O(52) = O(1) space to store the hashtable."

I'm so disgusted. I was way off. Not even close. I wasn't even thinking in this direction. Does anyone have the number to that truck driving school?

I'm pretty sure the sort solution would be an order of magnitude faster on any reasonably sized string. Big O's are Big O's : they are irrelevant when n is small, and for anagrams we're talking something like n < 45.

phil already answered you, but to expand a bit, programmers are asked to do anagrams all the time. Except it is not 'does this word have the same letters as this other word, just perhaps in different order', it is "is this list of address the same as this other list?" or what have you. In other words, do two differently ordered sets of items contain the same items? Asking the problem as an anagram just reduces it down to its essence. And, like it or not, there is an important efficiency issue here. The decent solution will be a bit slow compared to the optimal solution, and sometimes that can be important. The naive solution will not work for anything but toy cases. But, you can set the bar for the follow on discussion according to the kind of work you do.

I'm not sure if I think it is a great interview question or not, but it gives the interviewer a chance to see if you can do something basic in your language, and then it opens the discussion to broader contexts where you don't have to code - efficiency concerns if these are string or emails, but 1MB documents, or dealing with Unicode, terminations of strings and so on, algorithm performance, and so on.

Reply on news.ycombinator.com