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

21–30 of 352 posts

Re: An Algorithm for Passing Programming Interviews (2020)

#21

Post by samspenc »

Good stuff. A couple of comments to the post:

Rate limiter: I would probably use a hash table of this structure -- called[yyyy-mm-dd][hh-mm] and then increment the hashtable for that minute, for example, called[2022-01-02][22-01]++ and drop any entries for the last day at the end of the day.

Post doesn't mention this, but one other common pattern I've seen requires a tree data structure, and those interview questions can be solved with recursion. Basically once you have a tree data structure, you write a f(node) that will simply call f(left) & f(right) recursively -- or for-each(child in children) { f(child) } for non-binary trees.

Re: An Algorithm for Passing Programming Interviews (2020)

#22

Post by sk5t »

bonoboTP wrote: post #7
aurelianito wrote: post #4

The first example test given (rate limiter) gives a bad answer. I wouldn't use this method.

Elaborate?

The solution described in the article is likely to be extremely wasteful in both time and memory, by allocating a queue entry for each call, and then O(n) scanning and dropping stale entries on each successive call.

Tabulating call count by division(s) of time would be less obviously problematic.

Re: An Algorithm for Passing Programming Interviews (2020)

#24

Post by dmurray »

There's a bit of a "draw the rest of the owl" thing going on here. If you have the experience to confidently eliminate the likely approaches that don't work, then you must know quite a bit about those approaches and their applications.

And in particular, I'm not sure I can agree on eliminating recursion in the anagrams problem. He just says

> Recursion – No way to apply recursion to the problem.

but...there is? One plausible approach, I sort each of the strings and put them in a trie. A fancy sounding thing, but really just a data structure which allows me to rephrase "someString in myTrie" as the recursive "someString is null || (head(someString) in myTrie.keys && rest(someString) in myTrie[someString])". I'm not arguing that this is better than a hash table, though I think it probably is on some workloads - just that it's not possible to rule this out and solve the problem by pure process of elimination.

Re: An Algorithm for Passing Programming Interviews (2020)

#25

Post by taeric »

sk5t wrote: post #22
bonoboTP wrote: post #7

Earlier quoted context omitted.

Elaborate?

The solution described in the article is likely to be extremely wasteful in both time and memory, by allocating a queue entry for each call, and then O(n) scanning and dropping stale entries on each successive call. Tabulating call count by division(s) of time would be less obviously problematic.

Probably safe to say you aren't having to rate limit over a thousand endpoints from a single spot, so the linear scan sounds like a non issue. That said, I'd hesitate to get to fancy in client rate limiting. Sounds like an area that will hide bugs that are stupid hard to deal with.

Re: An Algorithm for Passing Programming Interviews (2020)

#27

Post by bradleybuda »

samspenc wrote: post #21

Good stuff. A couple of comments to the post: Rate limiter: I would probably use a hash table of this structure -- called[yyyy-mm-dd][hh-mm] and then increment the hashtable for that minute, for example, called[2022-01-02][22-01]++ and drop any entries for the last day at the end of the day. Post doesn't mention this, but one other common pattern I've seen requires a tree data structure, and those interview questions…

I agree with your answer on the rate limiter, but I think it depends on whether the spec is for rolling or fixed one-minute windows. The question is ambiguous, but the sample answer implies that we want to track rolling windows.

If that's the case, an improvement on the answer is to use a ring buffer instead of a linked list, which allocates a fixed set of memory up front (slower to initialize) but then is allocation-free on each invocation.

Re: An Algorithm for Passing Programming Interviews (2020)

#28

Post by aix1 »

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.

> In my experience, interviewers will rarely tell you the runtime of the optimal solution.

I agree. As an interviewer, I genuinely want each candidate to do well and I think that, on balance, setting a specific complexity goal is likely to do more harm that good.

For a strong candidate, it could limit their opportunity to shine by narrowing down the solution space and discouraging them from exploring tradeoffs (e.g. runtime vs memory).

For a weaker candidate, it could mean no solution at all instead of a suboptimal solution. I generally choose my problems such that they admit multiple solutions of varying degrees of efficiency/sophistication. It is generally not a hard requirement that a candidate find the optimal solution in order for me to score the interview favourably.

Re: An Algorithm for Passing Programming Interviews (2020)

#29

Post by yawgmoth »

This might get you OK marks on the "problem solving" portion of a coding interview. But a programming interview will also look for signals of other skills -- did you communicate your approach? Really good candidates will verbally communicate their solution before writing code. The best often write out how a particular data structure changes with some iteration.

If you're a senior engineer, a coding interview should include some demonstration of correctness. Maybe you write one primitive test harness for a positive test case and add comments or empty methods enumerating a few other test cases.

Re: An Algorithm for Passing Programming Interviews (2020)

#30

Post by gannon- »

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.

+1, got me thinking about this one Elon quote that's roughly about how we're trained in school to solve the problem given to us, even if it's not a valuable problem to solve. Can save a lot more time and complexity by realizing the 'problem' isn't really a problem than any solution.
Post reply on HN