I think this is one of the most inane things to be asked during an interview. personally, I've never found myself in a situation where I truly needed to choose between a vector/map/list/hashmap. Or had to find the O(x^n) and replace it with O(x^2)
Obviously it depends on the application, but many jobs are simply maintenance coding: find bug, fix bug, test fix. Often times it makes absolutely no difference whether you use a list or a vector, or else you'll get the paradoxical "vector-is-always-faster" because of locality of reference.
In my (admittedly limited ) experience, most of the effort is spent simply making it work, not being bogged down because you used a map instead of a hashmap, or didn't know about some esoteric, bleeding-edge probabilistic data structure.
I've seen this plenty of times. I've worked both on a trading platform and a large website, and both times encountered many performance issues that were solved with a more appropriate algorithm or data structure. I've even seen this with a list as small as 10 items - a O(n^3) algorithm was making multiple network calls each time; changing it to O(N) alone made a huge improvement in speed.
But I think it's more telling if a programmer knows how to profile his program and find the performance bottlenecks, recognize them for what they are, then fix them appropriately than if they can recall a specific optimization for a specific use case on demand.
Most of my work on an ecommerce platform doesn't need much attention to algorithmic complexity, but everyone on my team still curses the guy who wrote an O(n^4) algorithm in our checkout pipeline (discounts, promos, shipping, tax, etc). More than a couple items in your cart and you couldn't checkout because the thread would spin forever. I want to work with a team of people who can recognize these things immediately, even if it's not an absolute requirement for the job.
That has a lot more to do with mechanical sympathy, and awareness of when you've exchanged cleverness for complexity disguised as cleverness, than it does with knowing the big-O of operations on a datastructure.
What you want the person to identify is that they've made your simple iterative checkout process into multiple unbounded tree traversals with no circuit breaker.
Knowing that searching the tree is O(log(n)) isn't very helpful when your problem is an inability to identify that you've made (n) an unnecessarily huge problem space.
Most likely you think about it, though. When you're coding, and you have a triple loop, do you think, "Oh, this is O(n^3). Is n going to be too big here?"
It may be something that's so intuitively obvious to you, that you don't even think about it. So you naturally use the hashmap, where someone else might try a list and then start doing a lookup in a loop. Then while that particular instance might not break things, it'll slow things down, so overall the application feels sluggish instead of snappy.
I've never found myself in a situation where I truly needed to choose between a vector/map/list/hashmap. Or had to find the O(x^n) and replace it with O(x^2)
This entirely depends on the kind of product you are working on. When you get to a large scale with any programming project, optimizing computational resources will cut costs, and can often add value to the customer as well.
This is special pleading, though, right? It being relevant to "any" large scale project really just means that projects can get big enough for it to matter, but how many jobs involve this family of software? How many interviews for positions directly related? Very few, I would guess.
I find myself having to think about efficiency at least a couple times a week. I'm working on database implementation, and in the query processor we have to consider all the time how to evaluate various things efficiently.
I would say it starts becoming important for any application that has multiple concurrent users. If it's a single user running it on some device and there's no shared resource (I.E. back end), then chances are it's not going to be an issue.
"Or had to find the O(x^n) and replace it with O(x^2)"
The other thing that really seals the deal for me as an inferior interview question is that you don't need to have a clue what O(x^n) is to wrap some code in a simple time call, see that the code you think ought to run in microseconds is running in seconds, by visual inspection notice stupid nested loops, and fix it. Self-taught programmers may not be able to say "O of exx to the enn" but that doesn't stop them from fixing it.
So... seriously, what good is the question anyhow?
I would recommend going through some undergrad CS datastructures and algorithms lectures to any self taught programmer. My process of reading code improved dramatically. And the big O concept is, once you wrap your head around it, an intuitive way to think about speed. Also once you've timed your code and found the slow bits you need to know how to speed it up, not all speed ups are as simple as unnesting loops.
Same here. last week I was sent a Codility test, tried the demo and failed miserably.
Then I noticed the test was expressing constraints using time/space complexity, concepts I was completely unaware about for my previous 15+ years in the profession.
So now I am reading about algorithm theory face-palming at the realization I have reinvented the wheel many times during my career instead of just re-using a PhD. researched algorithm.
What if it isn't stupid code? What if it is straight forward and simple and looks correct but is just slow because it has to traverse a list instead of using a hash-table or some other data-structure. You can't get there by intermediate steps, you have to rip out the code that uses it and rewrite it with a hashmap. You can only do that if you know the space complexity and when a hash and a list is appropriate.
"You can only do that if you know the space complexity and when a hash and a list is appropriate."
You seem to be confusing "knows how to say 'oh of enn squared'" with "the loop gets slow when I iterate over a lot of things". One is generally a product of education, the other, merely experience.
The idea that a thing can only be learned in a classroom is perhaps in the top ten most pernicious ideas in the modern world, and probably one of the more surprising ones to show up in that list. You do not need special courses to discover that your code runs slowly, and as I've seen often enough, having had those special courses does not confer immunity against writing slow code.
Now, I am also a believer that formal education has its place, and if you are going to get a formal education in computer science, big-O analysis absolutely must be part of it or you are literally missing out on an entire rather important sub-discipline. But the idea that it's some sort of touchstone between Good and Bad programmers is just ludicrous nonsense. Slow code is slow. There are abundant tools that can be used to figure out why. If you can't work out why your O(n^3) loop is running slowly after a couple of years of practicing the art, you don't need formal education, you need a different job.
I've found that employees who are able to discuss the benefits of certain data structures and their associated time complexity are generally able to solve problems quicker than those who struggle to discuss these fundamentals. That said, the thing that matters most to me when hiring programmers is proof that they can write decent code.
This is a very under-appreciated point. If you profile a program on non-pathological input, the profiler won't tell you what's going to explode later on when your program hits a rare case that you hadn't expected. Theoretical upper bounds don't have this problem.
The most fundamental tool of the trade is a profiler. The tool which is used in reality to find performance problems, unlike BigO, which is used in theory to find performance problems. Does BigO help? Sure. Is it the silver bullet people seem to think it is? No.
The tool which is used in reality to find performance problems, unlike BigO, which is used in theory to find performance problems.
Sorry, but this is just wrong.
I can guarantee you that BigO is very often used not "in theory", but in practice, to find real-world performance problems. And not having "situational awareness" of certain commonly occurring complexity profiles can be a significant source for performance headaches and technical debt.
One trivial-seeming, but frequently occurring example: not knowing when to use hash maps.
In fact, many people solve performance problems (including both those where order-of-magnitude performance really is the most important factor, and various other kinds) not by using a profiler but by, you know, understanding the code and thinking about it. Being as profilers, while they can tell you a lot about certain kinds of performance issues, are still generally quite limited in what they can tell you.
Is it the silver bullet people seem to think it is? No.
Of course not, and I've never heard anyone saying that it was, either.
It's not a silver bullet, it's only a model of the problem. If you profiler tells you some code is slow, you can model why it must be slow by using big-O. In fact it's the standard way of explaining such things. Without it, you must spend your time babbling about special cases.
It's like, yeah, you don't "technically" need to know any 2+ syllable words to be a programmer, but you're really not helping yourself by avoiding them.
Big O took about 15 minutes to teach. Sure, it went on and on a bit because a rigorous class will introduce proofs, but you are absolutely right - it's a trivial concept, and often flawed in practice (list is supposed to be faster for random inserts/deletions according to big O, but in practice they are almost always slower).
Honestly, I consider an instinct for complexity analysis the most important thing I learned in school, and the thing that I've gotten the most use out of. I don't know what case you're making here: are you saying that high-level architecture is so hard that choosing a map or a hashmap should be a coinflip, or the one you see first? Having had some criteria for making the choice makes my life a lot better when everybody is panicking because something is running like shit and no one understands why.
To me it was a bunch of rote memorization, just like a biology course. I never - never - have needed to know how bubblesort/heapsort/mergesort actually work, except to appease interviewers.
I'm not saying I'm pro writing-inefficient-code, but if you want to talk big-O during an interview, I"m going to roll my eyes about as much as you asking me who the 19th president was.
I ask such questions at the end of an interview, but mostly to see the sanity/reaction or thinking process - wrong answer would do, rolling eyes - would not :)
Oh shit, my code is O(1), looking at it in the profiler tells me that it's not a bottleneck (it says < 5ms). Yet this single function call somehow takes 78ms in wall time when it should at worst be 1ms (and even that is too much). The reason? JVM classloading/JITing. This quite annoying when you have shortlived applications.
That's fine, as long as you _never_ need to trust said dev to do anything complex. It's fine to have mediocre developers perform mediocre tasks, but if you want more from them someday you may be in trouble.
That's not really fair, people don't grow unless they're challenged.
Some people really do never advance past a certain point, but a lot of people write someone off as mediocre when they're just still in the process of gaining skill. Also, they only assess ONCE, which is pretty bad if we're trying to establish how good you are forever and always.
That's true, but how do you discern between someone who has potential and has not yet been challenged, and someone who simply doesn't care? In my experience, the best will challenge themselves to learn new things on their own.
to me, complex, and complex-ITY are entirely different matters. I want a smart programmer who can figure out really complex bugs (something you cant figure out from google/wikipedia). Not someone who memorized the big-O performance tables of 8 different data structures (something you CAN look up on wikipedia ).
Exactly. I once identified memory leaks in a managed runtime implementation, worked around them, and showed that third party networking libraries from the hardware vendor were causing irrecoverable crashes but I can't spout off runtime complexity of algos. The former saved a multi million dollar contract and my company's reputation, the latter is something I look up when I need it.
Optimally, I would like both. I agree that wrote memorization is not a very useful skill, but I'd like to know that they can grasp concepts, and I find it hard to believe that there are a bunch of skilled devs out there with great potential who don't or can't understand algorithmic complexity. Interviewing is hard though, I'm not trying to say that any one question or metric should necessarily rule someone out.
Here's how you should reply: "Sorry, I don't have those complexities memorized. When I really need to look them up (which is nearly never), I refer to bigocheatsheet.com."
This can happen even on small systems. I once replaced a O(n^4) with O(n^2*ln(n)) on an embedded target which made a minutes long user facing process take seconds. The catch is that the original used a good algorithm, but made an implementation error which I caught in profiling. So complexity analysis is good, but the only way to get better at something is to measure it.
You should have an intuitive idea around complexity and when it makes sense to optimise.
I don't think though you need to know that for example fastsortx is n log n in the best case off the top of your head in an interview situation. You should be able to reason your way through why it is faster than some other sort though.
What the heck is fastsortx? This is another problem I have. I study all these algorithm books then when I get to the interview they ask something that either isn't in the books or they've come up with some nickname for it and expect me to know it.
That's how I failed my Google interview - they said they expect programmers for any position to have good knowledge of algorithms, yeah, well... :) Frankly I don't like trivia-style interviews.
I think it's easy enough to ask for this skill if the job would require the interviewee to apply this skill.
If your job is mostly frontend, yeah, you probably won't need to worry about this problem. But if you're hiring somebody to work on graphics? You better be doing complexity estimates in your sleep.
Exactly. Performance issues happen. Most of them can be solved by re-indexing a database or adding caching. If I really need speed at the algorithm level I can look it up.
That guy in Google who screwed up Android thought just like you. Now, as the number of text messages stored on your phone grows, the entire system slows down. Such a pity that cretin was not screened out on an interview!
I think this is one of the most inane things to be asked during an interview. personally, I've never found myself in a situation where I truly needed to choose between a vector/map/list/hashmap. Or had to find the O(x^n) and replace it with O(x^2)
Obviously it depends on the application, but many jobs are simply maintenance coding: find bug, fix bug, test fix. Often times it makes absolutely no difference whether you use a list or a vector, or else you'll get the paradoxical "vector-is-always-faster" because of locality of reference.
In my (admittedly limited ) experience, most of the effort is spent simply making it work, not being bogged down because you used a map instead of a hashmap, or didn't know about some esoteric, bleeding-edge probabilistic data structure.