Hacker News Reader

Comment by arghbleargh | Hacker News Reader

It's clear that the author is very motivated and probably pretty smart, but I wonder if there might be some gaps in his knowledge foundation. I was surprised for example that he was learning about information theory, and yet he had trouble analyzing the computational complexity of a function that he coded.

View on HN

Not sure if that's really relevant. Unless you are applying for a job where time is money stock trading or some such I don't see how knowing a method you are writing is O(log N) rather then O(N2) is useful. Its something to keep in mind sure, but I would rather have the slower method integrated into the code base faster.

Yes performance is a feature but realistically you can get away with some fairly awfully performing code for a long time in most situations.

I remember a conversation a while ago where people we asking if you could have a language that offered X increase in performance over C for X increase in processing time what value of X would you pick? In most cases people are willing to trade a lot of performance for a lot of productivity.

Knowing the time complexity a given function you write is generally not important. However, the skill to analyze the complexity is an important one to have, because when performance issues to come up, it is often a very powerful tool to have.

Agreed. However it would probably be better to show someone some code with a loop in a loop and ask them why it could potentially be a problem.

If they can tell you in Big O notation why its bad for large inputs then great, but so long as they can tell you why that's what really matters.

Right -- Big O notation is a useful formalization of a thinking process that in practice usually includes more information.

That is -- anytime you write a loop, you'd better think about what's inside it (and how long those things will take), and -- given the amount of data you might be sending through that loop -- if that's a problem or not.

I want someone to notice that they're making a remote call in a loop when it could be batched, cached, etc.. I don't want them to spend 2 days optimizing an algorithm tinkering with a bit of text that yes, is inefficient, but in practice is only going to take a few milliseconds anyway and isn't a hotspot.

My read was that he froze during the interview. Perhaps I was injecting my own experience, which once very literally went like this :

interviewer : "what's the time complexity of blah"

me : "hmm... O(1)"

interviewer : "what's the space complexity?"

me : "fuck, oh, I don't know"

interviewer : "well, think about it. no stress"

me (2 seconds later) : "oh, right, yeah, O(n)... of course"

Not saying I'm proud of not taking the time to think a problem through, but sometimes people act really weird when under the gun.

I'm drawn to this for several reasons...

Trite though it is, admitting that you don't know truly is on the path to wisdom.

Not taking time to think things through is endemic in the workplace, not just an interview quirk.

in the real world, many O(N) algorithms are in fact O(I don't know) because of unexpected or unpredicted behavior from language, compiler, interpreter, runtime, os, etc.

You should probably read up on why this is, in fact, important before your next interview. Just a free piece of advice.

O(N^2) means that your operation gets n times slower each time n increases.

2000^2 is 4 million. (n log n = 6600)

200,000^2 is 40 billion. (n log n = 1 million)

I understand Big O.

My point is for a lot of cases it doesn't matter, and just because someone can't throw off the top of their head the O complexity of some algorithm they just wrote in a stressful interview does not mean they don't understand the concepts.

Besides a O(N log N) algorithm over 10 or 100 items is not going to cause any issues. In the case of your standard CRUD application that's what you are going to be dealing with.

You're right that it matters very little if you can deduce the exact complexity right off the bat. But it DOES matter is if you can tell if an algorithm is closer to n^2 than log n. OR identify that n is low enough that it doesn't matter.

> Besides a O(N log N) algorithm over 10 or 100 items is not going to cause any issues. In the case of your standard CRUD application that's what you are going to be dealing with.

I think you mean n^2. n log n is generally considered pretty decent.

But you're wrong, I know from experience that simple CRUD apps can suffer from grindingly poor performance, caused by, let's say, optimistic assertions of data volumes.

Going to have to ask for an example.

I am yet to have seen a basic CRUD app that had performance issues due to a bad coding algorithm. Certainly from poor queries but never from an bad algorithm.

Keep in mind I would say that a simple CRUD app with millions of entries is no longer a simple CRUD app.

What does "poor queries" mean other than queries with poor asymptotic complexity based on the query plan?

Doing something like the following would classify as a poor query in my book with a very simple query plan,

select * from table;

The query plan for that is simple, but the number of bytes transmitted per query is O(size of table) (as is the disk IO on the DB), which should clearly set off a red flag if you know that size of table can get large. You don't need a large exponent; You need to understand the rough cardinality of values, then you need to look at asymptotic complexity.

So, the problem with your exclusion of "non-simple CRUD apps" is that simple CRUD apps have a nasty habit of ceasing to be simple.

But yeah, case in point: I ran a small BB-style web forum a number of years ago. As it grew larger (on the order of 10k posts - hardly earth shattering for a web forum), the load on the server got unsustainable, and the page loads were really slow. It turned out that the algorithm to decide if a user had seen a post was to maintain a list of seen post IDs for each user, and compare them at each page view. For active users, the number of seen posts obviously approaches the number of posts: n^2.

A very easy, common example: given two lists of objects (from a database most likely), find the set of objects contained in both lists. The naive solution is a double for loop over each collection.

If you put an O(N^2) algorithm in production, you'll kill whatever relies on it. If that's our funnel, we're out of business. If its our DB, it'll go on fire. Not being able to reason about complexity is a no-hire for me.

That's only for cases of N over some value. An O(N^2) algorithm over a list of 10 is not going to break anything.

I didn't mention not being able to reason out the complexity, only saying its O(N^2) off the top of your head when presented with some method.

Shouldn't it be OK to have a knowledge of programming that doesn't derive from the theoretical canon? You can learn programming concepts in the context of "not killing the whatever-is-relying-on-it."

To be sure, not being able to reason outside of the canon is a long-standing occupational hazard and trait of the humanities, so there could be something a little more pathological in perpetuating these interviewing techniques.

Big-O notation takes five minutes to comprehend. I don't see the problem.

I'll take that as a "no."

Although understanding the difference is important, the specifics are typically far more relevant in a high performance language than a dynamic scripting language with lots of "magic". OP is interviewing for a C++ gig, so performance was clearly a motivating factor.

Not nearly as relevant for someone using scripting languages and building UIs.

For a C++ I agree hence I mentioned it being important for certain cases, but for something like your standard CRUD app its probably not worth thinking about.

Once I made a Ruby program noticably slow by using "array += items" instead of "array.push *items" in a loop, making it O(n^2) instead of O(n). Once we noted that doubling the input size quadrupled the runtime, I found the bug. (I was a Ruby newbie and didn't know that Ruby's "array += items" is just syntactic sugar for "array = array + items".)

I've used slow web pages that show a lot of items or data. One way to make them slow is O(n^2) DOM manipulation (e.g., inside a loop over items in a page, O(n)-searching the page for something).

Knowing complexity theory isn't the only way to find performance problems, and sometimes isn't even relevant, but it sure is helpful.

Oh shoot. I used array = [array, other_array].flatten to get around the += slowness. Way faster on lists of tens of thsouands that I was throwing around. Totally forgot push. (Granted, my solution was developed on Sunday morning with a hard deadline of Monday morning and I had been working hard all week. )

The real value of someone being able to respond on the time-complexity of a given arbitrary function is that it shows they can build a good mental model of what goes one when the function is run. Building a good mental model of a program is the most important thing when designing it, building int, extending it, or fixing it. So it's not about performance - it's about understanding and abstraction skills. All good things to test for in an interview.

I find it comforting that a coworker isn't going to unknowingly hide lots of superlinear algorithms in the codebase that will blow up without warning when data sets get significantly larger than the test data.

Sometimes you have to make a decision to just go with the inefficient solution, but I'd like it to be an informed decision if the codebase is one I have to work with and maintain in production.

The fact that someone can tell you what the big O of an algorithm is wont prevent that though. You would be better off following a decent peer review process and performance profiling the application.

It's not an either-or. Competent developers and teams can do both.

I know a specific case where a manager was convinced he could do a better job of something than his employee, and coded up an algorithm over the weekend that performed 20% better on the test-data and was only slightly slower.

The employee had to explain that they couldn't deploy this algorithm because it was O(N^3) whereas the (already deployed) one that was doing worse on the test-data was O(N log N). The test-data was two orders of magnitude smaller than what could reasonably be expected while deployed.

Reply on news.ycombinator.com