[stevebot]

Edit: Why the downvote? Disagree? I would love to hear more about why this attitude is helpful.

I love algorithms, AND I think they are necessary in interviews, but I feel like the tech community has become ridiculous in how they interview for them lately.

Example problem: Given two words in a dictionary, transform one word into another, changing one character at a time, using only words in the dictionary.

A good interview would recognize most people have no clue how to solve this, give hints and still pass candidates who make a reasonable attempt but fail. Now it seems to be that most places will just fail you, if you don't know the most optimal answer and can't write it out without any syntax mistakes.

This is ridiculous, and I have experienced it and this attitude around major tech companies. What this has resulted in is Algorithm trivia. Your ability to succeed is your ability to memorize every algorithm question and approach in existence.

[dang]

> Edit: Why the downvote? Disagree?

Please don't do this. The HN guidelines ask you to "resist commenting about being downvoted" because "it makes for boring reading and never does any good". It isn't that we don't understand how provocative it can be to have a comment downvoted for no apparent reason—we know the feeling all too well. Hence the word "resist".

https://news.ycombinator.com/newsguidelines.html

[cloakandswagger]

It's easy to see why: algorithms are foundational, and they're the kind of right or wrong test that give binary, merit-based substance to the nebulous process of assessing a candidate.

Still, I agree that they're overused. The truth is, the vast majority of modern programming doesn't even involve intensive algorithm writing and is more focused on the design and construction of apps that are nothing more than CRUD operations and business logic.

[perdunov]

I think this is actually not a problem of overusing algorithms, but a problem of correctly separating the job titles related to software development.

There are software developers whose work actually requires no knowledge of algorithms, mathematics, or even CS besides their language, framework, and some architectural concepts.

On the other hand, there are "software developers" whose primary work is to develop algorithms and computational methods.

For historical reasons those roles are not always properly and clearly separated.

This can be one of the reasons why we have intimidating algorithmic interviews that are irrelevant to the actual work of the developers who are being interviewed.

[perdunov]

If you don't have a library of algorithms and methods memorized, you won't be as productive in solving real-world problems as the one who does. Often the difference can be dramatic.

Many good algorithms are quite counter-intuitive and non-obvious, so there is very little chance that you would come up with one yourself during the course of working on a problem. In practice, people who haven't spent enough time memorizing algorithms tend to choose the wrong path while solving real-world problems, as they can't even anticipate the direction in which the correct solution lies because, again, many good algorithms are non-obvious and can't be thought out on the spot.

[jameshart]

I think it's more important to be aware of the kinds of problems for which you don't need to reinvent the wheel, and to know the terminology and domain keywords which will help you evaluate the correct approach in a given situation when you encounter it. The useful knowledge is not the specific implementation details of the algorithm, but the ability to look at a real problem and realize 'this is like looking for the longest matching substring' or 'this is similar to finding a convex hull'. Then you can go and try to find the best way to implement a convex hull calculation in your particular circumstances. Just because you don't know an optimal convex hull algorithm off the top of your head doesn't tell me much.

What I'm looking for in asking somewhat algorithmic questions in an interview is the ability of the coder to reduce a problem to one which has probably already been solved. A separate but interesting problem is, given such a solution, how well can you implement it - but that's more of a fizzbuzz exercise in many cases.

[perdunov]

Sure, I agree about reduction to known problems, but still, understanding algorithms completely is more powerful than manipulating them as "black boxes", as the former allows to build upon ideas of algorithms and produce variations of algorithms, and generally gives a lot of insights and patterns of algorithmic problem solving. The relation is kind of like below:

(No algo) < (Blackbox algo) < (Whitebox algo)

[sireat]

Is this supposed to be a bad interview question?

To me this seems like a good one only because it gave me immediately some talking points to put on a whiteboard.

- Build graph with vertices being words and edges being all words differing by one character - search graph for shortest path between given two words

Implementation would be another matter as there are a number of complexity gotchas. This would be a job for hitting CLRS.

This seems like something most people could come up with to start as it seems pretty obvious but a single graph theory course I took some years ago must have biased me a bit.

[nojvek]

> Implementation would be another matter as there are a number of complexity gotchas.

I interviewed at an internet darling company. They had the main interviewer (who was a bit rude) and another shadow interviewer who takes notes on everything you do an say. All interviews are like this.

The coding gotchas quickly make you super nervous as everything you do and say is recorded. You have 15 minutes. Plus whiteboard is not an editor. I don't code linearly like writing a text book.

I have come to a realization that fresh out of university me performs better at interviews than 7 year experienced me.

[tripzilch]

I just took a shot at solving this puzzle for the /usr/share/dict wordlist (70k words when filtered to strictly alpha), using Python.

Assuming the "first build a graph" approach is the most efficient one, it's definitely taking me longer than 15 minutes to get a reasonably efficient solution. Just for the graph-building part. I'm taking a two-step approach, first connect the matching words that differ in length by one, so filtering for (a == b[1:] or a == b[:-1]), assuming a is always the shorter word of the pair. Checking all words of length N vs length N+1 that way took a few minutes on my (not very powerful) netbook. Not entirely happy with it, but no way I could optimize that further in 15 minutes anyway (if there is an even better algorithm), and that part of the calculation is done.

edit: just thought of a better way

    aa = sorted([words of length N])
    bb = [words of length N+1]

    # now make a sorted list of the longer words, truncated on either side,
    # (paired with the original for retrieval later)
    bb1 = sorted([(w[1:], w) for w in bb] 
        + [(w[:-1], w) for w in bb])

    # now we can do a merge operation on aa and bb1, and find 
    # the matches in O(len(aa)+len(bb1)) instead of O(len(aa)*len(bb))
    #
    # a merge operation that I can't be arsed to write out here, but I
    # promise it'll involve some super clever usage of the itertools module
    #

Now for step 2, words of equal length...

[GhotiFish]

I think the reason you may of being downvoted is that, this is just an instructional course on algorithms. It's not a discussion about obnoxious interview questions. There are plenty of such discussions on Hacker News, but here it seems very inappropriate.

I would agree with that, you're contributing to a discussion to be sure, just the wrong one, I'd rather read about this somewhere else.

[jimmaswell]

>Given two words in a dictionary, transform one word into another using only words in the dictionary.

What's that supposed to mean? Search the dictionary for other words that contain the letters you want and put them into the source word, while also taking out unwanted letters from the source word?

[_nt_]

It indeed is interesting question. The solution which comes first to mind is creating a graph, with words as vertices, edges will be only if two words have a difference of single character. Once this graph is created, it's matter of running shortest path algo between two vertices. However, creating the graph itself could be a bitch, depending on size of dictionary.

[stevebot]

You have the additional requirement that you change one character at a time, and end up building a graph of neighbors and doing BFS on it.

[bmelton]

I've never heard this question before, but I assume it's finding words with the lowest Levenshtein distance between wordA and wordB and then wayfinding the route from wordA to WordB using the least steps possible?

[stevebot]

correct, I think it is actually a good interview problem for discussion and don't mind it. What I do mind is the attitude of some of my colleagues that if a candidate can't immediately jump to the optimal answer, then they are a pass.

[chenglou]

Can you englihten me on how edit distance helps here? I don't see why insert/remove/move is relevant in this case.

[bmelton]

Sounds like something I'd likely fail. Without putting pen to paper, I can get from taking the two words and expanding Lev distances until we find a word in common, and then mapping a a route from A to that word, then from that word to B, but whatever I wrote would probably be horribly inefficient, at best.

I would also wager that whomever was asking that sort of question would probably be looking for some optimal form of the answer, and having never encountered it, oh well.