5 ms·

I was with him until he started complaining about being asked how to implement a hashmap and how this implied that the interviewer had reimplemented Java.utils.

by taybin 14y ago

I was with him until he started complaining about being asked how to implement a hashmap and how this implied that the interviewer had reimplemented Java.utils. How would you know when to use a hashmap and when to use a list if you don't know anything about big-O notation?

nixarn 14y ago
Agreed. The Data Structures courses we had were among the best courses we had. I think it's great to learn how to implement them once.
didgeoridoo 14y ago
I think he addresses this point pretty well -- you can learn good programming practices through apprenticeship/experience without understanding the deeper fundamentals. You won't be creating the next MapReduce, but you'll be able to remix and hack up existing functionality in new and creative ways.
- sophacles 14y ago
  From the other end though, this can result in a lot of cargo-cult programming. "this is how to do it" can create a ton of redundancy (the bad kind) if the underlying mechanisms are not understood sufficiently.
  - beersigns 14y ago
    Even having the underlying ability to understand something sufficiently doesn't imply you'll automatically do so. There are plenty of times even a properly educated person on the subject matter at hand will miss opportunities to apply their knowledge. Recognition of a given scenario is a test of your analytic ability, not sheer know-how.
lukejduncan 14y ago
I like the question. I would never expect a candidate to know a perfect implementation but they better understand the general concepts. It's hard to tell the tone from his writing, but if a candidate was snarky about "why not java utils" I'd be less inclined to want to work with them. The question can be answered many ways without being hostile to the interviewer.
gnaritas 14y ago
You can have an intuitive sense of how many operations you're performing without knowing big-O notation.
- carb 14y ago
  Of course, but part of the benefit from studying CS is that you'll be able to recognize intuitively when there is or there should be a better solution. Let's say you want a data structure that performs three operations. Insert, Delete, and Find (as in, 'is this in the database?'). The intuitive sense may come from saying, "Linked-Lists would be horrible for this! Each operation would be slow." (O(n)) The practiced programmer may say, "I can keep the data sorted and use an Array. Those would probably be faster." (O(lg n)) However, if you learned a little more CS and how hashes work, you would know that they are constant time for all three operations. You never had to waste time thinking about which choice to make because you know how hashes are implemented and that they specialize on those operations running in constant time. Besides, big-O notation takes no time at all to learn. I learned it's theory as a freshman in high school during algebra II when we wanted to know which of two polynomials grew faster. Take the most significant part, rip off the constants, and that's its growth rate.
  - lordlicorice 14y ago
    "Take the most significant part, rip off the constants, and that's its growth rate." Well, it's an upper bound on its growth rate. And only after some possibly-gigantic n.
    - carb 14y ago
      Yeah I understand. I was describing how I did it in Algebra II. They would give up f(n) = 5x^3 +4x + 8 and we would know that it was O(x^3). We also understood that it was as n -> infinity, hence why f(n) = 2x^4 would have a larger growth rate than g(n) = x^2 + 5000. When you're talking about scalability when programming, you're going to have to understand big-O, how constant factors come into play (why Floyd-Warshall at O(n^3) is often better in practice), and how big-\Theta works. If not, you're eventually going to make a mistake and slow everything down.

by taybin 14y ago

nixarn 14y ago

Agreed. The Data Structures courses we had were among the best courses we had. I think it's great to learn how to implement them once.

didgeoridoo 14y ago

I think he addresses this point pretty well -- you can learn good programming practices through apprenticeship/experience without understanding the deeper fundamentals. You won't be creating the next MapReduce, but you'll be able to remix and hack up existing functionality in new and creative ways.

sophacles 14y ago
From the other end though, this can result in a lot of cargo-cult programming. "this is how to do it" can create a ton of redundancy (the bad kind) if the underlying mechanisms are not understood sufficiently.
- beersigns 14y ago
  Even having the underlying ability to understand something sufficiently doesn't imply you'll automatically do so. There are plenty of times even a properly educated person on the subject matter at hand will miss opportunities to apply their knowledge. Recognition of a given scenario is a test of your analytic ability, not sheer know-how.

lukejduncan 14y ago

I like the question. I would never expect a candidate to know a perfect implementation but they better understand the general concepts. It's hard to tell the tone from his writing, but if a candidate was snarky about "why not java utils" I'd be less inclined to want to work with them. The question can be answered many ways without being hostile to the interviewer.

gnaritas 14y ago

You can have an intuitive sense of how many operations you're performing without knowing big-O notation.

carb 14y ago
Of course, but part of the benefit from studying CS is that you'll be able to recognize intuitively when there is or there should be a better solution. Let's say you want a data structure that performs three operations. Insert, Delete, and Find (as in, 'is this in the database?'). The intuitive sense may come from saying, "Linked-Lists would be horrible for this! Each operation would be slow." (O(n)) The practiced programmer may say, "I can keep the data sorted and use an Array. Those would probably be faster." (O(lg n)) However, if you learned a little more CS and how hashes work, you would know that they are constant time for all three operations. You never had to waste time thinking about which choice to make because you know how hashes are implemented and that they specialize on those operations running in constant time. Besides, big-O notation takes no time at all to learn. I learned it's theory as a freshman in high school during algebra II when we wanted to know which of two polynomials grew faster. Take the most significant part, rip off the constants, and that's its growth rate.
- lordlicorice 14y ago
  "Take the most significant part, rip off the constants, and that's its growth rate." Well, it's an upper bound on its growth rate. And only after some possibly-gigantic n.
  - carb 14y ago
    Yeah I understand. I was describing how I did it in Algebra II. They would give up f(n) = 5x^3 +4x + 8 and we would know that it was O(x^3). We also understood that it was as n -> infinity, hence why f(n) = 2x^4 would have a larger growth rate than g(n) = x^2 + 5000. When you're talking about scalability when programming, you're going to have to understand big-O, how constant factors come into play (why Floyd-Warshall at O(n^3) is often better in practice), and how big-\Theta works. If not, you're eventually going to make a mistake and slow everything down.