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

How to Rock an Algorithms Interview

blog.palantir.com

Post reply on HN
Print view View original

101–110 of 169 posts

Re: How to Rock an Algorithms Interview

#101

Post by VladRussian »

mcantor wrote: post #93
VladRussian wrote: post #86

Earlier quoted context omitted.

>"Jeez, this thing takes forever to boot up" this "forever" consists of myriad of "a fraction of a second"-s, with each fraction individually not being "notieably slow" and thus not "prematurely optimized". And if not optimized "prematurely" (ie. written efficiently from the start), then after-the-fact optimization, if happens at all, would shave only a fraction out of the "forever" - thus it frequently doesn't happe…

> And if not optimized "prematurely" (ie. written efficiently from the start), then after-the-fact optimization, if happens at all, would shave only a fraction out of the "forever" - thus it frequently doesn't happen at all because of such low projected ROI. My personal experience completely contradicts what you're saying. Despite the cushy comforts of server-side scripting languages, I have experienced the occasiona…

man, i'm talking about complex systems (2G+ of source code for example) that are already well past several low-hanging-fruit passes, component- and system-wise. Their performance after that reflects the overall average emphasis on performance and skills of developers through the life of the project. And no amount of after-the-fact optimization would make Windows into Linux performance-wise.

Re: How to Rock an Algorithms Interview

#103

Post by jules »

rcfox wrote: post #39
mcantor wrote: post #21

FTA: You should know these data structures inside and out. What are the insertion/deletion/lookup characteristics? (O(log n) for a balanced binary tree, for example.) How does one achieve this? Not just being familiar with data structures and algorithms (I am), but being fluent in them, to the extent that you can produce the Big O complexity for different operations off the top of your head. I didn't have a tradition…

There aren't too many things to remember in order to be useful: - Operations that take the same amount of time regardless of the input are O(1). ie: 1+1 takes just as long as 10000+10000 (okay, not really, but it's a reasonable assumption.) - Doing a small sequence of operations runs in O(maximum of all operations). Doing 5 adds (which are O(1)) runs in O(1). Doing an O(n) operation followed by an O(k) (where k > n)…

1+1 does really take the same amount of time as 10000+10000 on nearly all CPUs.

Re: How to Rock an Algorithms Interview

#104

Post by glenjamin »

strlen wrote: post #91
mcantor wrote: post #21

FTA: You should know these data structures inside and out. What are the insertion/deletion/lookup characteristics? (O(log n) for a balanced binary tree, for example.) How does one achieve this? Not just being familiar with data structures and algorithms (I am), but being fluent in them, to the extent that you can produce the Big O complexity for different operations off the top of your head. I didn't have a tradition…

> I work predominantly with server-side, interpreted languages, and I just don't run into the bottlenecks and performance problems that Big O-knowledge seems to mitigate. Algorithmic complexity isn't about performance, it's about scalability. A hand-written implementation in assembly that's O(N^2) will be slower than an implementation in Basic that's O(N) (or even O(N log N)) for a sufficiently large N. I suggest pic…

The problem with this is, in most cases you're not dealing with sufficiently large N - plus the high-level language of choice will already come with an efficient sorting algorithm for whatever lsit type it provides.

Whenver you do start to approach values of N for which you need to fine tune, you're going to be researching and profiling and optimising the hot code anyway.

I'm not saying you don't need to know algorithms, but you don't need to know the big O for every sorting algorithm / insertion cost to each type of tree off the top of your head. A rough idea of whats terribly inefficent is fine for most tasks.

Re: How to Rock an Algorithms Interview

#105

Post by pjscott »

Homunculiheaded wrote: post #49
mcantor wrote: post #21

FTA: You should know these data structures inside and out. What are the insertion/deletion/lookup characteristics? (O(log n) for a balanced binary tree, for example.) How does one achieve this? Not just being familiar with data structures and algorithms (I am), but being fluent in them, to the extent that you can produce the Big O complexity for different operations off the top of your head. I didn't have a tradition…

The good thing is that most operations on most data-structures (as well as many of the more common algorithms) don't require solving recurrence equations to determine their asymptotic growth, usually our intuition based on counting tends to be pretty close. Sketch out your basic data structures on a piece of paper, then just use your finger to trace out how you could do insert, delete, search, etc you can usually tel…

Your post needs to be, not only upvoted, but also put on the syllabus of every data structures class.

Re: How to Rock an Algorithms Interview

#106

Post by georgieporgie »

angelbob wrote: post #83
georgieporgie wrote: post #76

Earlier quoted context omitted.

The companies who ask these questions do so because their engineers deal with these kinds of scaling challenges every day I'm skeptical of that statement. Some of the engineers at, say, Google, deal with code complexity and scaling every day. Most probably don't. Certainly, most at the non-Googlish companies hardly ever deal with this. Yet the majority of interviews I've gone to over 12+ years have involved significa…

I've worked at a long series of companies that deal with these at least every week or so. Maybe not daily. But I'm writing code where it matters most days. Maybe I'm unusually hardcore? I'm definitely not all about the algorithms, but I work on a lot of systems programming. The other thing is that often you don't realize that what you're doing requires thinking of this until somebody else has to go fix what you wrote…

I've worked at a long series of companies that deal with these at least every week or so

And I've worked at a long series of companies that don't. That's the thing: different strokes for different folks, as it were.

Maybe I'm unusually hardcore?

I think it's less about degree-of-core-ness and more about platform and domain knowledge. Personally, if I were hiring for what I consider to be a fairly typical company, I would be looking mostly for ability to consistently get functional, bug-free code running. I would likely seek stronger algorithmic knowledge in some small ratio of employees.

I guess I feel strongly about this because I think it's fundamentally disrespectful to all coders, and ignores the tremendous variety of tasks and skills out there. A self-taught hacker who can get a great product going in a short time may be just as important and valuable to a company as the algorithm-strong coder who catches scaling problems before they come up. When it comes down to it, the goal is to create product and value, and that happens in many, many different ways.

The fix will even look very simple. The insight going into the fix isn't as simple, though.

That's true of the majority of bugs I've written or come across, whether its related to performance, crashing, or unpredictable behavior. In fact, looking at fixes that coworkers make to your own code can be a tremendously enlightening (and humbling) experience.

Re: How to Rock an Algorithms Interview

#107

Post by 99tokens »

- Start writing on the board. : start making diagrams on what you think the problem is. Most of the time this half solves the problem

- Talk it through : Sometimes interviewer will prod you into right direction, if you are just off. And sometimes get more impressed with the way you are thinking, then the final problem. Worst case: interviwer get stuck on his pre-defined solution.

- Think algorithms, Think data structures : This go hand in hand.

- Think about related problems you’ve seen before and how they were solved : This is would do after you have broken down the problem in smaller parts

- Modify the problem by breaking it up into smaller problems : do this before 5: mostly 1 step will help you here

- Don’t be afraid to backtrack: start with the worst case solution, but obvious, then optimize the heck out of it!

Re: How to Rock an Algorithms Interview

#108

Post by pjscott »

tedunangst wrote: post #40
mcantor wrote: post #21

FTA: You should know these data structures inside and out. What are the insertion/deletion/lookup characteristics? (O(log n) for a balanced binary tree, for example.) How does one achieve this? Not just being familiar with data structures and algorithms (I am), but being fluent in them, to the extent that you can produce the Big O complexity for different operations off the top of your head. I didn't have a tradition…

On like the very first day of algorithms class there was a table with a bunch of data structures down the side and insert, lookup, delete across the table with a bunch of n's and lg n's in the cells. There was also a table very much like it on the first exam, except the cells were empty.

The sad thing is, I bet a lot of people memorized those instead of learning enough about the data structures to be able to fill out the table on the fly.

Re: How to Rock an Algorithms Interview

#109

Post by pjscott »

Blunt wrote: post #71

Frankly, I find this type of interview insulting. Let's face it. Unless you work with "algorithms" on a dialy basis, I'm willing to bet that most who do not cannot regurgitate a red black tree at the drop of a hat. I work in this field off in on as an embedded developer and I'm always going to various texts on the subject to align my thinking with the code I'm writing (C++ in my case). It's one thing to talk through…

I don't think anybody's asking you to write a red-black tree of the top of your head, but it would be nice if everybody knew what a balanced tree was and why they might be useful.

Re: How to Rock an Algorithms Interview

#110

Post by ericmoritz »

mcantor wrote: post #21

FTA: You should know these data structures inside and out. What are the insertion/deletion/lookup characteristics? (O(log n) for a balanced binary tree, for example.) How does one achieve this? Not just being familiar with data structures and algorithms (I am), but being fluent in them, to the extent that you can produce the Big O complexity for different operations off the top of your head. I didn't have a tradition…

Read Chapter 4 of this book: http://shop.oreilly.com/product/9781565924536.do
Post reply on HN