I once got knocked out of the running by a whiteboard-coding interview question that went something like "How would you find all triples from a list of a million integers, where the first two numbers add up to the third?" I said, "Hmmm that sounds like an O(N^3) problem." Interviewer: "Can you think of any way to do it in smaller big-O?" Me: "Not off the top of my head, no."
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.
> 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.
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.
In which case, I don't think that's a place I'd like to work. Most often the solution an engineer comes up with is _not_ ideal and will be improved either because they come up with a better one later before they commit it or because they go through code review and someone else sees a better way. If you don't leave room for people to improve their solutions you'll just end up with the first, crappy one that comes to mind.
> They care about how you approach it, how you think through it, what you do when challenged, etc.
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.
A friend of mine didn't understand how he could have done better than me in a "write a quick sort" interview (we were still students) when I knew the algo and he never heard of it (and obviously struggled more).
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
Errr in the set of numbers that complete the rationals wrt to standard metric? I guess you have to show it’s not rational so you probably did a proof of upper/lower converging bounds always having nonzero difference for 1/n increments or something? I would definitely not get this in a pressure interview situation.
> 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...
I think here they just meant, show that no rational number is the square root of 2. Not rational = not expressible as a ratio. You assume that sqrt(2) = p/q for some integers p and q, then derive a contradiction.
> Coders are often under a mistaken impression that interviewers care about your answer. They don't.
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.
> 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.
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!"
Then I'd argue they need to make that more clear. The typical interview setting does not suggest it's an "exploratory" environment, it usually feels more like taking an exam.
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.
Had the same thing happen to me. Simple problem: find out if two strings are anagrams of each other.
My immediate solution: Sort the two strings and then compare them:
(defn anagrams? [x y] (= (sort x) (sort y)))
or some such. I was fortunate in that they didn't make me implement the sort (because it's been a long time for me) :)
"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 need not to sort the strings. Create a vector with indices he ascii codes, incrementing for the first string and decrementing the count for the second, and keep a count of the number of chars, if you get a negative number exit false, else if the count of chars is zero then each one is an anagram of the other. (n+m+128) operations n and m are the length of both strings and 128 for creating the vector
on a tangent, one way could be assign a number code to each alphabet. Add the numbers that occur in the strings. IF the sum matches, they are anagrams.
To get decent anagram lengths and complexity, implement the numbers as a dict of repetitions of primes, and implement the multiplication by summing the repetitions. ;-)
In which case you can just compare the dicts without performing the multiplication (which happens to be the costliest part for arbitrary-precision integers).
You would have to make sure the sum of any combination of all characters was unique. For example, if the code was the character number, a=1, b=2, etc, both "abc" and "bbb" would have the same sum.
So I think something silly like:
character_code = len(string)*len(alphabet)^character_index
should work.
Or you could do top 100 questions on leetcode or hackerrank and you would have solved the question in a minute. It's kinda sad that you could remember the top 100 solutions and clear interviews in almost all big tech companies.
I recently interviewed at a big tech company (phone interview). I spent quite some time practicing on leetcode (completed at least 150 problems). During the interview, it took me a few minutes of thinking before completing the assignments with what I think was the expected solution. We discussed the complexity and a few possible variations. The interview sounded satisfied and I really had the feeling that I had nailed these assignments.
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.
I really wonder how age is taken into account. If it were really an issue, they could have rejected my application from the start and not bother with an interview.
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.
As someone that does lots of coding phone interviews I can say that yes, time is a factor. But it's relative, ie I'm comparing you to the time it took other candidates to solve the same problem. After all, we have to evaluate you, over the phone, in the course of less than an hour. If 2 candidates arrive to the optimal solution, the one that did it much faster is the better candidate.
It sounds to me like you did pretty well so don't give up.
> the one that did it much faster is the better candidate.
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.
> If 2 candidates arrive to the optimal solution, the one that did it much faster is the better candidate.
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.
its kinda sad you think professionals should memorize useless tricks that dont generalize to the profession in order to be considered for a job.
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 didn't take the parent's post the same way. The situation is more that if you do leetcode or hackerrank then you pass the interview. So once again the interview process has failed; instead of identifying good candidates you identify candidates that do hackerrank in their free time.
thanks for the clarification, i read it as "its sad they cant do it, whats wrong with them?" kinda way, but what you said is probably what he/she meant
Exactly, I as well have been doing technical work for my whole life, and sitting here right now, I could more easily explain to you how to optimize the planner cache, and what hints are required to get a given result than I could explain to you which joins do what.
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.
I don't read anything about OP's post as saying they think people should memorize or that this practice is okay, as evidenced by their final sentence that it's sad that you could do so and pass many technical interviews.
I would say that if you know the answers to 100 top coding questions (and understand them, a good interviewer will poke you to determine that) then you are a pretty good coder and you should be hired. Seems working as intended :)
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.
Like I said, a good interviewer ensures you understand the solutions of those problems (the problem might even be formulated in a different form than the exact form you learned) not just typing out text verbatim. If you do understand the solutions of top 100 coding questions, I think you have a good start. Part of solving the problem in an interview will also be being able to code, so it's also testing your coding ability in a given programming language.
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.
I'm as critical of how we interview in this industry as anybody, but I've never found this particular criticism compelling or charitable. It's implicit that you know the correct first answer is to seek prior art. Making that explicit is fine but a bit pedantic. The follow-up question is: "ok great, now say that you can't find any satisfying prior art for this on Google, how would you reason through your own solution?".
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.
Maybe but I once had an interview in which I was asked how to find how similar two text strings were (for search). I answered that I would use one of the algorithms from Apache commons text or within Lucerne which implement one or several of the appropriate distance algorithms. He told me he had written his own. I asked why he would do that when these algorithms were written by people who did intense research and the implementations in these libraries have been tested by more eyes than his could ever be. He said “what if I want it to run in Ruby?”...I was interviewing but this is a guy I would not hire. He was wasting time for his own amusement. Never assume people know to do the research on existing solutions. Many developers would rather work on their own toy solutions while avoiding the actual unsolved problems in their domain
Sure, your mileage may vary and there are definitely bad apples, but my claim is that the vast majority of interviewers aren't looking for people who like reinventing wheels, but are rather trying to suss out the extent to which you can reason through a problem. So I think that's the charitable assumption to make.
Are you serious? For any algorithmic question, if googling does not turn up a great answer, you would need to be a genius if you could come up with one on the spot.
We had a CS class at UNH, a state university, where we learned how to express the complexity of an algorithm and then how to refactor algorithms to be less complex, when possible. Although we do not do this type of work for most of our jobs, it is not a stretch to think that half of people with a CS degree might have at one point known how to do this on the spot.
My job often entails reasoning through a solution to a specific problem which is dissimilar enough from the general formulation of some problem that there isn't an obvious way to Google for an exact answer. It may take a genius to devise the best algorithm to solve some general problem, but it does not take a genius to reason through a decent solution to a specific problem using general knowledge and experience.
Except they don't just want a solution, they want a solution with certain performance characteristics. And they want it to be the solution with the best performance.
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".
That's reasonable, but at the same time, unless it's a top-secret clearance job, don't threaten me with doing web development on an air-gapped machine. We both know it's absurd, just don't do it.
> ok great, now say that you can't find any satisfying prior art for this on Google, how would you reason through your own solution?
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".
I’m not familiar with this one but have been thinking about it for a few minutes and think I have an answer (granted I think it will depend on language and OS whether it would work)
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.
That actually sounds like a very reasonable senario to not do so well in.
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.
My personal opinion on what a senior dev interview should be is: open with a fizzbuzz-level 'bozo filter' coding question, then step away from the whiteboard and spend the rest of the interview speaking to each other like normal, functional adults.
I actually implemented fizzbuzz in Scala recently.. It's a lot easier to do it in a language that has good pattern matching. Doing that in c++/Java is pretty annoying
>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.
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.