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

51–60 of 352 posts

Re: An Algorithm for Passing Programming Interviews (2020)

#51

Post by vanusa »

sjburt wrote: post #40
MathCodeLove wrote: post #18

Earlier quoted context omitted.

Why??

Because in the real world you don't know the runtime of the optimal solution, except for certain very well studied and simple problems. At best you might know the runtime of the best published solution. But in many cases your problem isn't something that anyone has studied in that kind of detail and it's going to be on you to determine whether your solution is satisfactory or whether you should go back and improve.

Because in the real world you don't know the runtime of the optimal solution,

The question specifically referred to target performance, which IRL is almost always known and freely communicated (in at least ballpark terms).

As in: "Find the median of this array of 10k integers in .01 seconds please. Not 10 billion, just 10k". You say: "OK, sort and done."

IRL if someone at your job says: "Write some code to find the median of an array of integers. I'm not going to tell you how many, even the order of magnitude. Could be 10k, could be 10 billion." You say "WTF?" They say: "I don't care about whether you get the right solution or not! I just want to see how think about a problem."

I think you'd know where to tell them where to put that question.

Re: An Algorithm for Passing Programming Interviews (2020)

#52

Post by malisper »

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.

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

Even if n elements are scanned in the the worst case, the expected time it takes to perform such a scan is O(1). This is because we perform a scan on each insertion and O(n) elements are deleted in a scan of length n. That means the number of elements scanned is proportional to the number of elements inserted.

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

Tabulating call count by division(s) of time doesn't quite work. If a 9 calls are made at the last second of one division of time and 9 more calls are made in the first second of the next division of time, you will hit 18 calls in a two second interval which is over the limit of 10 calls for any one minute interval.

Re: An Algorithm for Passing Programming Interviews (2020)

#53

Post by john_moscow »

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…

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

Why on Earth? Given that the timestamp cannot randomly jump backwards, you can achieve the same results by just storing the timestamp of the first call after a reset, and the number of calls sharing the same date/hour/minute, resetting it to 0 when the minute advances.

That said, it won't be entirely what was asked, since it won't have the rolling behavior.

Re: An Algorithm for Passing Programming Interviews (2020)

#54

Post by Supermancho »

The anagram solution leaves the actual hard part unfinished^. Also, to solve in O(n) you need a bit array (or a database like Postgres that can do an XAND on a string).

> Sort the characters of the words alphabetically. Since anagrams are all made up of the same letters. This will give us the same string for any pair of words that are anagrams of each.

Correct.

> Produce a dictionary of the number of times each letter occurs in each word.

Well, yeah...algorithms aren't the hard part for this kind of question. "Produce a dictionary of the number of times each letter occurs in each word." is heading the wrong direction. You want an encoding that does not care about the number of times each letter occurs in each word.

Take a string of zeroes, which is (maxWordlength*26) long. Each segment of 26 represents a compositional letter from the word. So 100000 00000 00000 00000 00000 is 'a'

Now you can create your dictionary from the sorted word indexes. pin becomes inp becomes 000000 00100 00000 00000 00000 000000 00000 00100 00000 00000 000000 00000 00001 00000 00000 same as nip (becomes inp, etc)

You can add 26 zero sets, to pad out to the length of longest word, if words are variable length.

^We're going to assume normalized words, which are all lower case and no punctuation, comprised of English letters from the 26 character alphabet. Getting the set of all of the possible words of any given length, is also quite an exercise.

Re: An Algorithm for Passing Programming Interviews (2020)

#55

Post by gorbachev »

aurelianito wrote: post #4

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

You think "I'd use a well tested 3rd party library for this problem" would eliminate you from the running on an interview with this question?

This, and many other of these algorithm questions, are asking people to come up with solutions to problems solved umpteen times with well designed and tested libraries available for all of them.

A sign of competence as a software engineer would be to use them.

Re: An Algorithm for Passing Programming Interviews (2020)

#56

Post by mrfusion »

arduinomancer wrote: post #5

Interviews are really a dumb game these days so if you want to really game it you can go with a statistical approach: * Practice questions by company on LeetCode, sort by frequency of last 6 months and work down the list, do maybe 75-100, the list updates once a week * Search for the company on the LeetCode forums and sort by most recent. If a question is not on LC yet it will likely get posted there, so you can get…

I’ve gotten interview questions I’d recently solved and my problem was it was too easy. I had trouble acting like it was the right amount of struggle. Is there a trick for that?

Re: An Algorithm for Passing Programming Interviews (2020)

#58

Post by sk5t »

taeric wrote: post #39
sk5t wrote: post #33

Earlier quoted context omitted.

I don't quite see it that way, although maybe we read the problem as something different. Suppose the rate limit is 500 per second; a client makes a burst of 500 requests in one second, sleeps two seconds, then another burst of 500. Isn't the author's planned approach going to end up doing a bunch of bogus work? - putting 500 timestamps into a queue - inspecting 500 queue entries and removing each - putting 500 new t…

I'd assume a linked list was used to be able to drop a lot in a single shot. In particular, seems safe to assume the queue is sorted by time. Such that as soon as you see a time that is outside the window, you can drop all of the rest in one shot. The page wasn't loading for me, so I can't see the proposal. Just don't let a linear scan scare you, for small n.

There are various approaches that might or might not improve the runtime outlook (maybe a priority queue, maybe a list that supports fast random access for binary or exponential search, etc.) but wouldn't the only "fast" path to drop a bunch of entries hinge on moving the head reference and pushing the work onto the GC? One might start to think about something like a ring at the point where this would start to matter.

Asserting small n seems like a way to wash out of coding interviews that are focused on identifying and avoiding costly naive solutions. Interviewers are like as not to say "okay, now the rate limit is 5,000/sec/customer/operation, and there are 100,000 customers."

Re: An Algorithm for Passing Programming Interviews (2020)

#59

Post by hemloc_io »

travisjungroth wrote: post #46
colechristensen wrote: post #16

Earlier quoted context omitted.

Right? When I’m interviewing I care most about the thought process and the ability to communicate in depth about something technical, the actual solution isn’t really that important at all.

This is the thought process. I use something very similar and have done well in interviews. I found I did better in interviews when I showed my thinking less, or adapted it to the interviewer. Stating the things I'm not doing is useful, but too risky. Just hearing the words "linked list" in a problem that can't be solved with linked lists (even in the sentence "linked list doesn't seem to be right") startles some int…

lol yeah having been through these loops and training to do these loops it really seems like most people say they want to see “thought process”, but what they’re really looking for are the usual cues you see in all the prep info online.

E.g. ask some clarifying questions before coding, write or suggest a brute force, and then write an optimized algo.

Re: An Algorithm for Passing Programming Interviews (2020)

#60

Post by kortilla »

mrfusion wrote: post #56
arduinomancer wrote: post #5

Interviews are really a dumb game these days so if you want to really game it you can go with a statistical approach: * Practice questions by company on LeetCode, sort by frequency of last 6 months and work down the list, do maybe 75-100, the list updates once a week * Search for the company on the LeetCode forums and sort by most recent. If a question is not on LC yet it will likely get posted there, so you can get…

I’ve gotten interview questions I’d recently solved and my problem was it was too easy. I had trouble acting like it was the right amount of struggle. Is there a trick for that?

Empty your bowel into your underwear. It’s all a show anyway, at least make it a good one.
Post reply on HN