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.
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.