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

331–340 of 352 posts

Re: An Algorithm for Passing Programming Interviews (2020)

#331

Post by Dylan16807 »

vlovich123 wrote: post #315
Dylan16807 wrote: post #216

Earlier quoted context omitted.

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

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

When you want to grow your hash table, go ahead and allocate a bigger but blank chunk of memory. (You can either design your memory allocation system to make this fast, or you can prerequest the memory when you're x% away from full.)

Put your new item in the big chunk of memory.

Every time you search for something, check both chunks.

Every time the hash table has to allocate a new slot, move over four items from the small chunk of memory to the big chunk.

Eventually the big chunk of memory will be 65% full and the small chunk will be empty, and then you deallocate the small chunk.

And that'll work forever just fine.

The ability to shrink is only slightly more complicated, exercise for the reader.

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

Either use methods that won't abort, or use a secure hash and tune the hash table so you can make a statistical guarantee that the chance of an emergency resize is a million times smaller than the chance of the computer spontaneously self-destructing.

Edit:

> C++ STL and Wikipedia

It's no surprise the STL wouldn't so something as fussy as keeping two most-of-a-hash-tables behind the curtain. As for Wikipedia, it has a whole section talking about how you don't have to resize all-at-once. The O(n) at the top is an oversimplification.

Re: An Algorithm for Passing Programming Interviews (2020)

#332

Post by MauranKilom »

ficklepickle wrote: post #327
MauranKilom wrote: post #272

Earlier quoted context omitted.

I program in C++ daily and wouldn't know the currently accepted way to read lines from a text file in it off the top of my head. It's simply not something I ever have to do. A good candidate should still manage to figure it out in 30 minutes, but your programming experience is most likely a lot less universal than you think.

They didn't specify needing to read the file line-by-line. You could read the whole file at once. There might not even be any new line characters in the file. You invented a requirement.

They specified "strings", which I interpreted as lines in a text file. But it doesn't actually matter, because I could make fundamentally the same comment no matter how words (or "strings") are separated.

Re: An Algorithm for Passing Programming Interviews (2020)

#333

Post by troutwine »

bradlys wrote: post #322
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…

Most things in interviews are wildly overrepresented compared to their usage though. I haven’t done any shortest path, binary search, topological sort, or many other things in most of my time in industry. I would have a hard time remembering even one instance for many algorithms.

What niche do you work in, if you don't mind my asking?

Re: An Algorithm for Passing Programming Interviews (2020)

#334

Post by troutwine »

hinkley wrote: post #154
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…

More than my coworkers, not often enough, and not very often. Many people think DP and caches are synonymous, unfortunately.

What niche do you work in?

Re: An Algorithm for Passing Programming Interviews (2020)

#335

Post by qDnbBcCnsZneEJg »

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…

A priority queue is the easy answer to virtually any “top k” problem so is still worth mentioning.

Re: An Algorithm for Passing Programming Interviews (2020)

#336

Post by titanomachy »

hinkley wrote: post #325
titanomachy wrote: post #186

Earlier quoted context omitted.

I usually reach for caching first because it’s more intuitive (for me and my reviewers) and because we often have well-known size bounds and relaxed enough performance requirements that make an “analytical” solution unnecessary.

Caching creates a mature product, no matter what your product roadmap says. If a rewrite is the tool of last result, caching is the second to last. Like pruning shears, once you use them, your world of options collapses considerably. All of those opportunities are gone and nature won't let you put them back. Critically, caches are global shared state. That's why cache invalidation is the hardest thing. Global state a…

All great points! For the type of work I'm thinking of (mostly offline data processing) I use caches in a much more limited way than you suggest. A short-lived local LRU cache on an expensive pure function over immutable data can significantly reduce our resource costs without adding significant complexity to the code. In some cases, DP would be more efficient but would require a mode of thinking and abstraction that's very different from most of our code.

Re: An Algorithm for Passing Programming Interviews (2020)

#337

Post by milanove »

titanomachy wrote: post #180
smallnamespace wrote: post #115

Earlier quoted context omitted.

No matter what the filtering process is, the average person in [industry] will be mediocre by definition.

Sure. But I’m (by my own estimation) a mediocre software engineer who is very above-average at solving fun coding puzzles, and therefore at interviewing. Usually these threads are full of people complaining that they are good engineers who aren’t good at interviews; I’m suggesting that the opposite isn’t uncommon, even if it’s more rarely admitted.

Getting something working in the beginning feels very different from a coding puzzle. During the next phase of optimizing something is where it gets interesting. Understanding the hardware and figuring out the right way to make full use of it via memory tricks or specialized processor instructions always felt more like a puzzle. Unfortunately, I feel engineers are seldom given the opportunity to go deep down the optimization route once something is working reliably, since it's already getting the job done.

Re: An Algorithm for Passing Programming Interviews (2020)

#338

Post by bradlys »

troutwine wrote: post #333
bradlys wrote: post #322

Earlier quoted context omitted.

Most things in interviews are wildly overrepresented compared to their usage though. I haven’t done any shortest path, binary search, topological sort, or many other things in most of my time in industry. I would have a hard time remembering even one instance for many algorithms.

What niche do you work in, if you don't mind my asking?

I don’t have a niche. I’m full stack. I do everything related to web apps and been at six companies doing that all in different fields. (Seed startups to large public companies)

Maybe if I was in computer vision then I’d use some of these algos more often. But those usually require a special masters or PhD to get an interview anyway. So, not really applicable to the overall industry tbh.

Re: An Algorithm for Passing Programming Interviews (2020)

#339

Post by vlovich123 »

Dylan16807 wrote: post #331
vlovich123 wrote: post #315

Earlier quoted context omitted.

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

> 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). When you want to grow your hash table, go ahead and allocate a bigger but blank chunk of memory. (You can either design your memory allocation system to make this fast, or you can prerequest the…

That's a really neat idea. I don't think I've seen any containers that implement this idea. Wonder why.

Re: An Algorithm for Passing Programming Interviews (2020)

#340

Post by bonoboTP »

dnpp123 wrote: post #208
malisper wrote: post #151

Earlier quoted context omitted.

> It's not specified in the article? From the article: > The function should have expected O(1) performance. > Do that for rate limiting and it'll be super easy to DoS you How so? The rate limiter has the same performance as, for example, a hash table. Operations are usually O(1), but are periodically O(n). It's not like every service that uses a hash-table is DoS-able.

Geniusly curious: does "expected" in English necessarily means average? My understanding was that expected is dependent of the application domain, so it can mean best or worst or average. If you have an implementation that is O(N) in worst case it's (theoretically) DoSable since an attacker would always hit that case - so the expected complexity in case of an attack is O(N). A trivial solution in O(60)=O(1) for worst…

"Expected value" or "expectation" is a precise mathematical term in probability theory that corresponds to "average-case", always.
Post reply on HN