For some reason that company insisted on only doing interviews at 7:00 AM, and my brain doesn't come fully online until after 9:00 anyway. I felt annoyed later when the answer came to me that afternoon, too late: put the list in a hashtable, add all pairs of numbers for O(N^2) complexity, and check if each answer occurs in the hashtable.

Much later after that, I realized that all the other red flags I'd picked up on while interviewing there added up to an impression that their corporate culture was seriously f'ed up, and that I probably dodged a bullet by getting passed over quickly in the process.

They were probably looking for the answer of, "Lets talk through it and figure out a better answer". Coders are often under a mistaken impression that interviewers care about your answer. They don't. They care about how you approach it, how you think through it, what you do when challenged, etc.

So from their perspective, they asked you to try harder on a problem, and you just said, "No." And they dropped you for it.

FWIW, I had similar questions in some interviews where we hashed through similar problems, and together collaborated down to a "No" answer... but we spent 15 minutes exploring the problem and seeing how well a couple coders can work through it before saying no. And I got the offer despite an otherwise rusty performance.

This isn't always true. Some interviews are really about solving the problems as fast as possible. And lots of interviewers are looking for exactly the answer they have on hand, and will think you're doing it wrong if you come up with a different, but equally valid (or better!) solution.

I was asked to sketch the proof for the irrationality of sqrt(2) in a quant programming interview. I kind of froze, and explained that though I had learned it, I could not recall.

He prompted me with "Well, what does it mean to be irrational?", and with that little hint I did the rest. Though ultimately I did not end up working there, it was very satisfying to have answered it.

Well, in one case (me), all the information the interviewer had was "this guy happens to know how to implement a quick sort by heart. K.".

In the other case (my friend), he got "this guy is able to understand and implement an algo he never saw before in a reasonable time", which is much more impressive

> We now show that the equation (1) p^2=2 is not satisfied by any rational p. If there were such a p, we could write p=m/n where m and n are integers that are not both even. Let us assume this is done. Then (1) implies (2) m^2=2n^2. This shows m^2 is even. Hence m is even (if m were odd, m^2 would be odd), and so m^2 is divisible by 4. It follows that the right side of (2) is divisible by 4, so that n^2 is even, which implies that n is even. > The assumption that (1) holds leads to the conclusion that both m and n are even, contrary to our choice of m and n. Hence (1) is impossible for rational p.

Assume sqrt(2) is rational and has the reduced form (x/y). Thus we are assuming that x and y are integers and that gcd(x,y) is 1. You square it and get x^2/y^2 which are somehow simultaneously coprime integers and also reducible to 2/1...

Huge asterisk that as long as you arrive to the correct solution with minimal help. I've had plenty of algo/ds interviews and it seems like needing help to see the trick in the question pretty much means you're out.

In many of the places that do claim this, even if you solve the problem "correctly" you still get more brownie points than someone who got a less efficient answer or didn't get an answer. Meaning that they /do/ actually care. I do get that some places are smarter with regards to this than others but it's depressingly common in my experience. "You didn't get the O(n) solution that has weird edge cases and was published as a paper in the 70s? Too bad, because some other person did, because they remember the solution from some programming interview book!"

At my last company, we would sit a candidate down at a pairing station. We'd offer them about 5 problems to choose from, and together we'd pair program on the problem for 2 hours. Using the internet, the IDE, anything they want was totally fair game. No system is perfect, but this was by far the best one I've ever experienced.

My immediate solution: Sort the two strings and then compare them:

  (defn anagrams? [x y] (= (sort x) (sort y))) 

"Ok, what's the efficiency of that solution?"

"Well, assuming the library sort functions I'm using are sane, I'll take a guess and say O(n log n)"

"Can you come up with a more efficient solution."

Off the top of my head, on the spot, I couldn't. Later, during the plane ride home, the obvious occurred to me: Don't sort the strings, just scan through each string once and build a hash table, keeping track of the number of occurrences of each letter in each string. Then compare the occurrences for each string. Not as elegant to express in code, but faster.

As it turns out, they later declined to hire me, giving me an excuse that made it clear they weren't really serious about hiring anyone for the position (as is the case at least half the time, it seems).

And thus ended my latest round of failed interviews. I cancelled the last one I had scheduled (probably another fake) and decided to take a break for a while (I mean, I do have a job right now, so it isn't urgent).

You’re right.

So I think something silly like: character_code = len(string)*len(alphabet)^character_index should work.

ac = 1 + 3 = 4 bb = 2 + 2 = 4

Still, consider the word ‘abe’ with a = 2, b = 3, c = 5, d = 7 and e = 11.

abe would then be 2^1 * 3^1 * 5^0 * 7^0 * 11^1. ‘abba’ would be 2^2 * 3^2. Each anagram would have a distinct value.

See also Gödel numbering and FRACTRAN.

I wasn't rejected but I've been asked to retake a phone interview. Apparently, the interviewer had very good feelings about me, but found that I was "out of practice" as far as coding goes.

I wonder if my age is an issue (40+) or if they have a really high level of expectation. Are most other candidates super fast at solving these kinds of problems. I'm a bit disappointed because I'm not sure that I've got much room for improvement at that stage.

They want 23 year olds who just did their finals. You know, real stallions.

You know, real pegacorns.

The answer to that is almost always yes.

Maybe the interviewer was biased and led to think I was "out of practice" because he knew I was on the older side. But I'll give them the benefice of the doubt. I believe it's a competitive position and I simply wasn't in the right percentile to qualify.

Now, would my former self 20 years ago be more competitive for this kind of interviews? slightly faster perhaps, but I don't feel I'm at a disadvantage compared to younger candidates.

It sounds to me like you did pretty well so don't give up.

From my perspective that is only about 3% of what I expect from a software engineer. Writing readable, easy to maintain code that is well tested, collaborating with product and other developers for how a feature should work, influencing technical designs, giving good feedback are things I value much higher than how quickly someone can write a snippet of code that works.

This is _a_ metric but I wouldn't bet too much on it. I know lots of people that come to optimal solutions to "algorithm type" _much_ faster than I do. I'm pretty slow at that type of stuff. But... its just such a small part of what makes someone a good programmer. Building out a medium to large application requires balancing a lot of trade offs and figuring out how to keep things simple. I know seasoned, quality algorithm solvers who honestly just repeatedly churn out garbage applications. And they can tank the productivity of an entire team of developers in their wake. I don't know how you test for that, but I can promise phone screening for problem solution time isn't it.

How did you arrive at that conclusion? Is it based on data or does it "feel" right based on an easily-measured metric?

Translated: "the one that did it much faster is a more recent graduate and exploitable for 100-hour weeks at below-par pay, hire that one".

Congratulations, now you know how to hire at a tech company!

The skill takes a long time to practice, and quickly evaporates once you stop doing it. Yet none of our work is anything like that. a more real world situation is reading documentation or SO for the function concat_ws that will turn an array column to a concatenated string.

however, the system that is, and one that you seem to think is ok, is one that discriminates people on many levels. Its a skill you do not get good at by working, so you must practice this in your free time. Now you just discriminated against men and women with families, people from less fortunate backgrounds, and others who otherwise do not have the time in the day to dedicate to a skill that is only useful to coding interviews.

as far as a comment above, I was a DBA for 10 years and can do pretty complicated queries off the top of my head, know how to optimize my indexes, worked with both structured and unstructured data in the multi tb size, ect ect, but I have no recollection on what ACID stands for. I dont really care. Sure, you may hire someone who memorizes useless crap, but then they have no idea why the IO has gone through the roof when inserting IDs out of order on a clustered index.

I just look up joins when I need them, and it's straight forward, but ask me in an interview and I sound like an idiot.

For many tech companies where they get a lot more candidate applications than they have positions for, the goal of the interview process isn't to avoid losing good candidates, it's to not hire bad candidates.

So much more goes into software engineering than "Can solve tiny example problems in an examination system"

True that software engineering is more than that, but those other things largely depend on in-house company processes, tools and policies so you would learn them afterwards.

It annoys me that the good answer if you actually encounter the problem during the job is never accepted during an interview.

They aren't looking for people who don't know to start by doing some research, they're looking for people who won't be completely stuck when that research doesn't turn up the answer.

Which means what they're really saying is not "we want problem solvers". What they're really saying is "the bare minimum for entry level work here is being able to, in 30 minutes and on the spot, out-perform top-tier theoretical CS researchers".

Which in turn really boils down to "be a recent CS graduate who memorized this algorithm in advance so as to 'derive' it later on command".

So then I try and give them a O(n^3) solution (or something).

Of course this isn't accepted as there's a better O(n^2) solution, which can always be found by googling, and I fail the interview.

The "turtle and the hare" problem of finding a loop in a single linked list in O(n) time and O(1) memory is the perfect example. It's easy if you know the answer (or can google) but basically impossible if you don't.

What did the interviewer do when I said I couldn't do better than a hashmap? He laughed and said "not many can".

The gist of it is: walk the list and after each step, multiply the previous node’s pointer by negative one.

If the current node’s pointer is negative you’ve found a loop (because you colored it by inverting the pointer in a previous step).

Clean up by starting at the beginning and multiplying all pointers by negative one until you reach the last one you inverted. Then return your answer (true).

If you reach a null pointer there is no loop because you’ve gotten to the end of the list. Clean up by going through again and multiplying all the nodes by negative one. Then return your answer (false).

Your worst case running time is 2n (if there is no loop) which reduces to O(n) and you use O(1) memory because you’re coloring the list by using the already existing pointers in the list.

The problem that I have with those problems is, they always assume it's easy to answer after seeing the solution. But if you're working on them for the first time, it's a terrible environment. The minute that they stop asking you, as the canidate, are on a timeline to finish. (Also, to finish as well)

The answer to that item would be: (with scala)

> datasource.window(3,1).filter((a,b,c)=> a+b == c)

I mean if you knock it out of the park and know the internals of window.. then asking the bar raiser question is appropriate as a curiousity.

There are other problems as well: Those are the ones where they have an expected answer, response, and reiterate. I've seen that with tree problems. That's where they would low-key ask for the recursive version and then get you to say stackoverflow exception.

Reminds me of my final round at Amazon, which they always do in Seattle. I woke before 4 AM west coast time having flown out the night before from the East, and 12 hours later was still coding on a white board. After writing (to my surprise) a correct merge sort, they asked my to write a program to do basic math with, IIRC, binary numbers. I was like, um. I'm out.

And if you throw in distributed databases, there is yet another understanding of "consistency" (vis-a-vis the CAP theorem), which really means "linearizability".

Sorry, didn't mean to be super-pedantic but consistency as a concept may seem simple to the uninitiated but is easy to get tripped up on, especially for folks who are aware there is a deeper layer of understanding associated with the concept, but can't articulate it right off the bat.

All this is to say filtering people truly is a hard thing. The extremes are easy to tell apart, but people who hover around the average are much less differentiated.

[1] https://en.wikipedia.org/wiki/Consistency_(database_systems)...

And I have similar anecdotes related to candidates who claimed years of distributed systems architecture experience, and were yet unfamiliar with CAP (and when explained, could not tell me even at a high level whether, in the event of a partition, their system was CP or AP, let alone the specifics of how that actually exhibited itself).

One of my mentors said that about an interview he conducted a while back. I found a lot of truth in that line. I run my tech interviews by starting very green and let the candidate dictate how fast I ramp it up. I've gotten pushback from managers before that you can't start with basic questions, but I've equally gotten positive feedback from candidates (even one's who've been failed the interview). In the end, programmers want to see an algorithm that allows them to judge an interviewee. I don't believe one exists.

Once you start working on a particular database, and are working on all of the specific details of that db, how often does ACID come into things, really? It just doesn't.

If you legitimately did the work without picking up -any- of the terminology, -and- respond confidently to questions you should know you don't know the answer to (rather than admitting ignorance and asking for follow-up questions, or declaring assumptions, i.e., "Well, I would assume it has to do with the behavior that if a constraint is violated or something similar in a transaction, the transaction will be rolled back instead of committing"), I don't want you. Because it means you both did not have formal training in, AND didn't seek out information or knowledge in the domain you were expected to be -senior level- in.

And while atomicity and durability are just characteristics of a relational DB (and so adminning one doesn't really require you to understand them), isolation and consistency both have definite relevance, because the isolation level is configurable, and that affects the consistency guarantees of the system. I expect someone saying they were a -senior level DBA- to be able to talk intelligently about those behaviors, and yes, to understand the words, because just reading the docs would have introduced the words.

Otherwise, I think we simply disagree in some respect, although I think it's over emphasized due to the topic. I think both perspectives have a level of truth to them, and have their flaws. It really depends on the candidate, and what they really know. Perhaps my particular circumstances are sufficiently odd enough that they aren't useful in a broader context. Who knows.

I don’t think it’s essential to know this, but I’d be surprised if a web dev interviewed with us and didn’t know at least the basic version I’ve given above.

Just my experience, perhaps I live in another world.

I think this is partially what I'm referring to. I use these terms in conversation with others when designing systems because they are useful in describing very specific properties of databases.

There were people who were bad at (possibly some because they were under pressure), it but nobody who couldn't do it at all.

I wasn't giving out a trivial question either.

I'd suggest a widely-accepted professional certification could help a lot, like doctors and lawyers have with the medical board exam or the bar exam. Easier said than done, but what we have today, where the candidate pool is overflowing with impostors with great resumes is not working.

"i passed the bar exam!" and nothing else doesn't get you a legal job you want.

and your medical boards, if i recall correctly, just mean you're qualified to go be a slave, er, uh, resident, some place for a few years.

Find me good certifications that are actually meaningful and relevant to my career, and I’ll do the study work and get them.

I have yet to find any.

(I've had that happen several places)

Go long enough interviewing hundreds, you'll see a few no matter what. Have a crappy enough filter in front and you'll see them right away.

Asking the right questions at interviews are crucial for finding the right people. If a candidate for a programming job knows binary trees but doesn't listen to other peoples views I would say he's less worth to us than a listener that easily learns new concepts but is currently not familiar with binary trees.

BTW, leaving a candidate in tears is not professional recruiting. Please let someone with more people skills accompany you to your interviews, you might leave people with scars that takes years to heal.

I'm sure it's used under the hood in a lot of code I write and have written but so is XOR, manual memory management and a bunch of other lower level implementations that I don't need to spend time on when developing on a higher abstraction level.

Not sure why you would expect all programmers to know about binary trees specifically.

I'll bet, even with this feedback, you'll continue to ask that question, just because.

I mean, look at this thread; would it be better to start with "Here are some example tables, please write the SQL that will return me (etc)" and turn it into a coding exercise? Because I honestly don't care that much about that from anyone espousing a senior level of knowledge.