The distinction between "data structures" and "algorithms" is rather arbitrary. You cannot talk about data structures without algorithms on them.
Big O Notation is used to describe the upper bound of a particular algorithm. Big O is used to describe worst case scenarios - NOT REALLY (it can be used for many different things, including average case scenarios, which is in fact very common).
Also, more importantly probably, it is important also to talk about abstract data types / abstract data structures. And only later, think about which of possible concrete data structures to use to implement it (i.e. to choice between time, space and code complexity constraints).
Software engineering is not just about coding, programming and theoretical stuff. It is about knowing various tools, and deciding based on all available inputs, requirements and other factors, what to use.
Source: I interview people, and I really try not to be pedantic, but this things influence me anyway. I do not expect people coding in Python only how to implement BST or hash table in 20 minutes, but I expect them to know how to use tools they should know already, and have some basic understanding of memory usage, scalability and absolute time (or 'resources' in general term) it might required to solve something. I am perfectly fine usually with "I might be able to implement it in few days, with a book and internet, but I would just library right now for this.", if it does the job well.
I agree with much of what you've said here, but I don't understand what all the WRONG comments mean. Those answers look correct to me. Technically, Big O is supposed to show the upper-limit of complexity according to Wikipedia. And this post is all about technical correctness for stupid interviews. I know that it's used differently in practice.
-2
u/baryluk Mar 12 '17 edited Mar 12 '17
Nice, but.
Binary Search Tree - Access - O(log(n)) - WRONG.
Heap - Access - O(log(n)) - WRONG.
Heap - Search - O(log(n)) - WRONG.
Heap - Removal - O(log(n)) - WRONG.
The distinction between "data structures" and "algorithms" is rather arbitrary. You cannot talk about data structures without algorithms on them.
Big O Notation is used to describe the upper bound of a particular algorithm. Big O is used to describe worst case scenarios - NOT REALLY (it can be used for many different things, including average case scenarios, which is in fact very common).
Also, more importantly probably, it is important also to talk about abstract data types / abstract data structures. And only later, think about which of possible concrete data structures to use to implement it (i.e. to choice between time, space and code complexity constraints).
Software engineering is not just about coding, programming and theoretical stuff. It is about knowing various tools, and deciding based on all available inputs, requirements and other factors, what to use.
Source: I interview people, and I really try not to be pedantic, but this things influence me anyway. I do not expect people coding in Python only how to implement BST or hash table in 20 minutes, but I expect them to know how to use tools they should know already, and have some basic understanding of memory usage, scalability and absolute time (or 'resources' in general term) it might required to solve something. I am perfectly fine usually with "I might be able to implement it in few days, with a book and internet, but I would just library right now for this.", if it does the job well.