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

311–320 of 352 posts

Re: An Algorithm for Passing Programming Interviews (2020)

#311

Post by xtracto »

troutwine wrote: post #73

There’s also two additional programming techniques you should be aware of: * Dynamic Programming How often do folks here use dynamic programming techniques in their professional lives? My own niche is systems programming. Dynamic programming is an important technique, sure, but given how rarely I see it used in practice compared to, say, statistical estimation it feels very overrepresented in interviews. But, maybe t…

An interesting point. I think most of today's systems tend to be "stateless" store state in a Database, which would make DP pretty cumbersome if not impossible to manage.

The only places were such types of processing will be required is when doing specific kind of processing, which for most scenarios you'd be better using an algorithm previously implemented on an existing library.

Re: An Algorithm for Passing Programming Interviews (2020)

#312

Post by meribold »

mrkentutbabi wrote: post #101
malisper wrote: post #32

Earlier quoted context omitted.

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…

But heap gives you O(1) max/min and Binary tree gives you O(log(n)) of max/min. Am I wrong?

In C++ (for example) getting the minimum and maximum is an O(1) operation [1][2]. I guess this is probably enabled through some extra bookkeeping and many other languages may do the same.

[1]: https://en.cppreference.com/w/cpp/container/set/begin

[2]: https://en.cppreference.com/w/cpp/container/set/rbegin

Re: An Algorithm for Passing Programming Interviews (2020)

#313

Post by GistNoesis »

gsliepen wrote: post #295
GistNoesis wrote: post #103

Earlier quoted context omitted.

How bad is the code I want to write even though I know it is wrong : initialize : double credit = N At every request : penalty = (elapsedTime / window_size) - (1/N) gain = N* (elapsedTime / window_size) credit = min( credit + gain - (penalty if( credit < 0 ) throw exception

I wouldn't call it penalty, but cost, and if credit = N, then I assume the cost of one call would just be 1. So: gain = N * (elapsedTime / window_size); credit = min(credit + gain, N); if (credit >= 1) { credit--; log(...); } else { return; /* not enough credits */ } Your approach has the nice property that after the initial burst, you get regularly spread out log messages, whereas the linked list approach will stay…

I was trying to express the sliding window constraint as a violation of the pigeon-hole principle : to violate the constraint you have to have at least N+1 intervals that are shorter than window_size/N over the window_size.

But I'm not really sure of the value it adds over simply taking a cost of 1 as you suggest. When time beween requests are spreaded more than window_size/N they don't cost credit. This mean you have a smaller number of "hot" clients (clients who are not full credit) to monitor.

The second idea that often occurs in problems with sliding windows is the telescoping sum which is hiding implicitly in the sum of elapsed Times.

Re: An Algorithm for Passing Programming Interviews (2020)

#314

Post by itronitron »

krtwllndr wrote: post #236
shinazueli wrote: post #199

Earlier quoted context omitted.

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 rem…

Because if you otherwise like the candidate you can help them along and if you don't like them you can just watch them sweat, but then claim your interview process has some level of technical rigor.

Re: An Algorithm for Passing Programming Interviews (2020)

#315

Post by vlovich123 »

Dylan16807 wrote: post #216
vlovich123 wrote: post #137

Earlier quoted context omitted.

Not sure I understand your concern. Are you asking about worst case? All hash tables I believe are O(n) worst case because of the possibility of collisions (or the need to resize in the case of an insert). Most people talk about amortized performance though (ie when you are successful at reducing the likelihood of worst case to a rare event). Amortized time is obviously dangerous if you’re in a real-time system (eg g…

It's possible to gradually resize a hash table to prevent spikes. For collisions, if you use a good hash then you can adjust your load factor and chaining strategy to make sure it's never a problem. Where 'never' is 'less likely than the computer spontaneously self-destructing'.

> It's possible to gradually resize a hash table to prevent spikes.

Can you provide details? The only trick I know of is the same one as with arrays where you overallocate. That still doesn't get rid of spikes and the C++ STL and Wikipedia both list worst case time as O(size of hash table). It's also not enough to just have capacity - often times hash tables will abort finding a slot if gone far enough in favor of resizing & rehashing the table.

> For collisions, if you use a good hash then you can adjust your load factor and chaining strategy to make sure it's never a problem. Where 'never' is 'less likely than the computer spontaneously self-destructing'.

Yes, but the vast majority of implementations don't do a good job here. Howard's "Types Don't Know #"[1] paper is extremely well thought out and I have yet to see this adopted (except for Rust - Rust has a good track record of adopting good ideas like this and having the benefit of coming late to the game). I think it's safe to say that most hash tables don't have good worst case times (which when combined with resizing behavior of insertions, means you have super-linear worst case times on insertion).

[1] http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n398...

Re: An Algorithm for Passing Programming Interviews (2020)

#316

Post by itronitron »

bryanrasmussen wrote: post #254
jsiaajdsdaa wrote: post #141

Earlier quoted context omitted.

As someone who has studied and passed before in this manner, and is now an interviewer, I have a simple solution that other companies should follow: for at least one round of interviewing, let me (the interviewer) use my own custom question, where the goal is not so much to solve it but rather to reason outloud collaboratively about many different aspects of the question. I like to use 3d graphics as a domain that ca…

Are you very knowledgeable in 3d graphics yourself, some of the replies here suggest that you may have a superficial knowledge (which is what I would have), if you choose an example domain that you have some knowledge about but not deep knowledge what happens if by accident your interviewee has significantly deeper knowledge than you? I worry that person might end up sounding overly technical or even like they're BS'…

There is also another way of creating 3D graphics that does not involve the use of faces and vertices, so developers with that background would be at a loss (or win depending on your viewpoint.)

Re: An Algorithm for Passing Programming Interviews (2020)

#317

Post by vanusa »

thaumasiotes wrote: post #222
vanusa wrote: post #212

Earlier quoted context omitted.

The interviewer's goal is to evaluate the interviewee accurately. More specifically: the interviewer's goal is to minimize (1) false positives and (2) the expenditure of the company's resources. Meanwhile, candidates hope to be evaluated "fairly", which is in direct conflict with criterion (1). They also naively expected to be treated "decently", which is in direct conflict with criterion (2) and which explains why e…

> which is in direct conflict with criterion (2) and which explains why employer-side ghosting is so widespread, along with other abusive practices like piling on lengthy take-homes, etc. I don't think concerns about resource expenditure actually explain ghosting. I think that happens despite what the company would prefer, because the people involved find it unpleasant to notify candidates of a rejection. Lengthy tak…

Because the people involved find it unpleasant to notify candidates of a rejection.

"Unpleasant" to send a standard form letter? I don't buy that.

I do agree though that it's what they prefer. As a reflection of how they are, and how they look at people.

Re: An Algorithm for Passing Programming Interviews (2020)

#318

Post by ivanche »

strstr wrote: post #13
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.

I’d turn that question back around at the candidate, unless it were for a junior candidate. I’ll give hints if the candidate is struggling, but I won’t just come out and tell them something like this. If they pushed me hard enough at the start, I would tell them and then fail them on the algorithms/reasoning component of the interview.

Sorry but this sounds like "I want to see something, you don't know what it is, I won't tell you, and if I don't see it it's game over bye!"

Re: An Algorithm for Passing Programming Interviews (2020)

#319

Post by emotional_fool »

angarg12 wrote: post #301
Jaygles wrote: post #288

Earlier quoted context omitted.

Have you ever passed someone who wrote brute force algorithms?

Of course. Contrary to popular belief you don't need to ace all interviews to get an offer. It's fairly common to make a hire decision with one person not inclined.

So your assessment was "inclined no hire" when the person gave brute force solution, am I wrong?

Re: An Algorithm for Passing Programming Interviews (2020)

#320

Post by arduinomancer »

Jensson wrote: post #209
arduinomancer wrote: post #69

Earlier quoted context omitted.

Wouldn't that mean you have to implement the binary tree as part of your solution? Seems way easier/time efficient to just use the built-in heap/priority queue of the language standard lib

C++ has built in binary trees with fast iteration. The C++ binary tree is my favourite standard library data structure of any language I've used, it isn't the fastest out there but it has so many useful things you can do with it. You can use it as a heap, you can use it as a dictionary, you can use it to sort things, you can insert items at the same time you iterate through it and if they are after where you are in t…

Oh interesting, I'll have to try that, didn't know there was a built-in one
Post reply on HN