10 ms·

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 fo

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.

boyter 13y ago
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.
- gizmo686 13y ago
  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.
  - boyter 13y ago
    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.
    - jtheory 13y ago
      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.
  - doktrin 13y ago
    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.
    - pacaro 13y ago
      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.
- mseebach 13y ago
  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)
  - boyter 13y ago
    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.
    - mseebach 13y ago
      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.
      - boyter 13y ago
        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.
        yuliyp 13y ago
- pbiggar 13y ago
  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.
  - boyter 13y ago
    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.
  - rhizome 13y ago
    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.
    - philwelch 13y ago
      Big-O notation takes five minutes to comprehend. I don't see the problem.
      - rhizome 13y ago
        I'll take that as a "no."
- iguana 13y ago
  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.
  - boyter 13y ago
    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.
  - idupree 13y ago
    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.
    - epochwolf 13y ago
      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. )
- deleted 13y ago
  [deleted]
- jng 13y ago
  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.
- army 13y ago
  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.
  - boyter 13y ago
    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.
    - philwelch 13y ago
      It's not an either-or. Competent developers and teams can do both.
- aidenn0 13y ago
  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.

boyter 13y ago

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.

gizmo686 13y ago
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.
- boyter 13y ago
  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.
  - jtheory 13y ago
    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.
- doktrin 13y ago
  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.
  - pacaro 13y ago
    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.
mseebach 13y ago
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)
- boyter 13y ago
  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.
  - mseebach 13y ago
    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.
    - boyter 13y ago
      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.
      - yuliyp 13y ago
pbiggar 13y ago
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.
- boyter 13y ago
  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.
- rhizome 13y ago
  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.
  - philwelch 13y ago
    Big-O notation takes five minutes to comprehend. I don't see the problem.
    - rhizome 13y ago
      I'll take that as a "no."
iguana 13y ago
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.
- boyter 13y ago
  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.
- idupree 13y ago
  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.
  - epochwolf 13y ago
    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. )
deleted 13y ago
[deleted]
jng 13y ago
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.
army 13y ago
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.
- boyter 13y ago
  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.
  - philwelch 13y ago
    It's not an either-or. Competent developers and teams can do both.
aidenn0 13y ago
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.