Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

An Algorithm for Passing Programming Interviews (2020)

malisper.me

Post reply on HN
Print view View original

231–240 of 352 posts

Re: An Algorithm for Passing Programming Interviews (2020)

#231

Post by dvirsky »

LewisVerstappen wrote: post #2

> After being given the algorithm problem, ask for the specific runtime your solution will need to have. Almost certainly, the interviewer will tell you. In my experience, interviewers will rarely tell you the runtime of the optimal solution. Regardless, very interesting blog post.

Exactly. The only scenario in which I actually reveal the optimal complexity is when they got the best solution and are still struggling to see if there's a better one. It's better if they understand that it is optimal but I don't let people waste more than a minute or two on this. If their solution is not optimal I just say something like "Is this optimal?" or "Is there a better way?", and take it from there as a dialog.

Re: An Algorithm for Passing Programming Interviews (2020)

#232

Post by noiwillnot »

46756e wrote: post #117
o10449366 wrote: post #112

Earlier quoted context omitted.

Software engineers that QQ about how unfair algorithm interviews are are clearly out of touch with how difficult and truly unfair interviews are for other high paying industries like law or medicine (in the US) where getting interviews is based on pedigree and getting one or two rejections can permanently deny you from top firms/positions. There are always things that can be improved about interview processes, but ma…

Not especially experienced with interviewing, but definitely agree with this. Leetcode sucks, but I’ll take it over how finance jobs are where it’s all about connections and where you interned when you were 19.

> but I’ll take it over how finance jobs are where it’s all about connections and where you interned when you were 19

Is this different than Big Tech really? If you do not go to the right schools, internships, whatever it can take years to have the right employers in your CV to be called for an interview.

Re: An Algorithm for Passing Programming Interviews (2020)

#233

Post by angarg12 »

Almost all advice online about interviewing is written from the point of view of the candidate. Sometimes this is good advice, but sometimes it devolves into some kind of astrology, where candidate are just guessing how things work.

I've done +300 interviews at FAANG so I can share bit of advice from the interviewer's side. The caveat is that this is based on how I conduct interviews, so YMMV with other people.

* Always ask clarifying questions. Almost all problems have some level of ambiguity that you need to clarify. This is intended. The more senior you are, the more important this becomes.

* Explain your approach before you begin, and even while you code. This gives the interviewer a chance to help you if you are down the wrong path, or even just understand what you are up to.

* If you get stuck, ask for help! think of this as a pair programming session rather than an interview. I much prefer a candidate who gets stuck, ask for hints, gets unblocked and writes good code, rather than one that doesn't ask for help and writes not-so-good code.

* Caveat: There is a tension with asking questions. There is such a thing as too much help, e.g. I need to explicitly tell you how to solve the problem. Use judiciously.

* Take interviewer's hints. The interviewer has probably asked this question dozens of times and knows it inside out. If they give you a hint, 99% of times they are on to something.

* Personally I don't like "hard LC" problems. Instead I prefer medium difficulty problems, and spend extra time probing the candidate's coding skills. This includes:

1. Write tests.

2. Handle corner cases/incorrect inputs.

3. Discuss how to scale the code.

4. Discuss how to refactor the code.

* If nothing else, write the simplest brute force solution you can think of. As an interviewer I need a coding sample to evaluate the candidate. Trying to and failing to implement an optimal solution is worse than implementing a correct brute force one.

Re: An Algorithm for Passing Programming Interviews (2020)

#234

Post by branko_d »

feoren wrote: post #228

Am I crazy or is the first answer terrible? I sat down and wrote out and answer for the problem and I initialized one integer and one timestamp. It should be O(1) time and O(1) memory easily, right? I'm seeing comments saying they'd use an array or a hash table -- why are you using any data structure? You don't need to remember how many times it was called 61 seconds ago; just keep a timestamp and the last time you r…

I don't think you can have a "sliding window" of time just based on that.

The next time you call the function, you need to count how many of the old calls are still "unexpired". This number (potentially) gets lower with each passing quantum of time.

How can you do that without holding a timestamp for each call? Please clarify if I misunderstood you.

Re: An Algorithm for Passing Programming Interviews (2020)

#235

Post by acedio »

feoren wrote: post #228

Am I crazy or is the first answer terrible? I sat down and wrote out and answer for the problem and I initialized one integer and one timestamp. It should be O(1) time and O(1) memory easily, right? I'm seeing comments saying they'd use an array or a hash table -- why are you using any data structure? You don't need to remember how many times it was called 61 seconds ago; just keep a timestamp and the last time you r…

That's a better solution in general IMO, but the author's approach can guarantee that you'll never go over N calls in a sliding window rather than fixed windows. I don't believe that's possible with the timestamp + count solution. Gotta bring up both solutions and ask the interviewer what they want :)

Re: An Algorithm for Passing Programming Interviews (2020)

#236

Post by krtwllndr »

shinazueli wrote: post #199
renewiltord wrote: post #138

Earlier quoted context omitted.

Google translate is sufficient. They’ll do it pretty carefully, complete with “pretend you get stuck at this specific point and if you get asked why to use a hashmap, act baffled for a moment, and then say X”

It’s ridiculously obvious when people have seen the question before. The way we do it is like this: we have like 3 or 4 different small variations on each question. Such that the solution is measurably different, in quite telling ways, but that the given problem looks almost identical. In one specific case the given is identical, but there are 3 variations to the question based on how the candidate asks questions abo…

Having been on both sides of interviews but fortunate enough to no have to do leetcode interviews I have a genuine question for those that do.

Why do them?

Are you really facing those problems frequently enough at FAANG to have know them? Is it uppity engineers? Gatekeeping? Or are you just getting so many applicants that you have to filter somehow and leetcode interviewing has some nice properties (easy to apply remotely, can be done by engineers, strong pass/fail criteria).

Genuine interest. Ignore the negative subtext, that's just me on this subject.

Re: An Algorithm for Passing Programming Interviews (2020)

#237

Post by branko_d »

malisper wrote: post #32
avl999 wrote: post #12

I would also add heaps/priority queues to this list. They don't come up as often as HashTables/LinkedLists but come up often enough. If you wanna be thorough (esp if you are applying at companies known for harder interviews) I would add practicing backtracking problems where you are doing a full exhaustive search of the problem space as well (often O(k^n) or O(n!) complexity). Yes these are often mostly just DFS + Re…

There's a specific reason I didn't mention priority queues in the post. In most cases, anything you can do with a heap you can do with a binary tree instead! A binary tree has O(log(n)) insert and deletion which is the same as a traditional heap. The only advantage a traditional heap has is you can construct a heap in O(n) time whereas a binary tree takes O(nlog(n)) time. Of course there are even more niche data stru…

One more thing: a heap can be easily packed contiguously in memory, while the tree nodes are typically dynamically allocated.

This helps with allocation pressure, which is often the "hidden" cost people don't pay enough attention to, especially in garbage-collected languages where the allocation might appear to be almost "free" (often a simple bump allocator), but the deallocation price is paid at later indeterminate time (when the GC runs).

Re: An Algorithm for Passing Programming Interviews (2020)

#238

Post by foreigner »

LewisVerstappen wrote: post #2

> After being given the algorithm problem, ask for the specific runtime your solution will need to have. Almost certainly, the interviewer will tell you. In my experience, interviewers will rarely tell you the runtime of the optimal solution. Regardless, very interesting blog post.

Agree. When I'm interviewing I'm trying to evaluate if the candidate will be able to do a real job. In the real world you're coming up with answers to a novel problem. There's no way to know what the complexity of the optimal solution is (unless you can prove it, which doesn't happen outside of a classroom).

Re: An Algorithm for Passing Programming Interviews (2020)

#239

Post by foreigner »

rrradical wrote: post #79

For the second problem, I had an idea for a different hash function. Basically map each letter to a prime number (e.g. c = 5, d = 7) and then multiply the values in a word together. I guess depending on the length of the words it might overflow. But I thought it was interesting.

I gave this very solution in Google interview many years ago. It does assume that the input characters are of a limited set, e.g. English alphabet. The interviewer said they hadn't heard that answer before. It wasn't what they were expecting and took them a while to be satisfied it would work. I was offered the job but didn't end up taking it.
Post reply on HN