6 ms·

You can pass some interviews by blindly memorizing, but it's unnecessary. If you understand a concept, then you can reason its big O. Memorization implies a sup

by wting 13y ago

You can pass some interviews by blindly memorizing, but it's unnecessary. If you understand a concept, then you can reason its big O. Memorization implies a superficial understanding that may be revealed later. If you don't understand something, spend a few hours and implement it. "I hear and I forget. I see and I remember. I do and I understand." - Confucious

nutjob123 13y ago
This was my immediate reaction. It is very easy and common for an interviewer to make a subtle change to how a common data structure or algorithm would work and then ask for complexity. Ex: Changing the quicksort pivot selection method.
mitchi 13y ago
My friend was interviewed by a video game company not long ago and they gave him an algorithmic problem. He asked what the complexity of the algorithm was and the interviewer said O(n). Good hint to have! He passed the interview.
mixedbit 13y ago
Agree, buy a good book (for example Cormen), learn the algorithms and implement them to get a good understanding. Try to use the table to answer a following question: what is a time complexity for finding a next item (according to a key) to a given one in a hash table? Memorizing such stuff does not make much sense, but if you understand basic concepts, you will figure it out quickly. There are basic errors in the table: BFS, DFS are for graphs, not just trees, and their complexity is not b^d (what is b and d anyway?). Quick sort expected complexity is nlogn and this is different than average complexity. You can also make quicksort worst-case complexity to be nlogn. You can't sort anything with space smaller than number of items you are sorting. You can use buble and insertion sort not only for arrays but also for lists and time complexity does not suffer.
- paulolc 13y ago
  You can contribute and fix the table yourself :). The author welcomes it . https://github.com/ericdrowell/BigOCheatSheet/blob/master/Tables.html https://github.com/ericdrowell/BigOCheatSheet/blob/master/Ta...
- derleth 13y ago
  > what is a time complexity for finding a next item (according to a key) to a given one in a hash table? Problem ill-stated as posed: Does not specify if the 'next' key is hashed, or even what 'next' means in this context.
  - mixedbit 13y ago
    Say, the smallest item in a hash table for which item.key is larger than given_item.key. Assume larger-than relation for keys is defined, so for example keys are integeters.
    - sillysaurus 13y ago
      Say, the smallest item in a hash table for which item.key is larger than given_item.key. Well, keys in a hash table are hashed. This implies that unless you're searching for a specific key (e.g. "42") rather than a condition (e.g. "smallest key greater than 42") then the time complexity is necessarily O(N).
      - mixedbit 13y ago
        Correct :)
- sbov 13y ago
  > You can't sort anything with space smaller than number of items you are sorting. I assume it's referring to extra space used. Most analysis of space I've seen is referring to this, not the space required to store the elements.
- devcpp 13y ago
  >what is b and d anyway? Breadth and depth. These could apply to graphs as well, since these algorithms draw a tree while traversing the graph.
- glass_of_water 13y ago
  Yeah BFS/DFS are O(n) for graphs and trees.
- rttlesnke 13y ago
  > You can also make quicksort worst-case complexity to be nlogn. Quicksort in the worst take can take O(n^2) time, not O(nlogn).
  - amalcon 13y ago
    If one takes the time to select optimal pivots it becomes O(nlogn). The selection is free from a big-O perspective, because it's O(n) immediately before the O(n) list division step. Of course, nobody does this, because the selection is not really free. The constant factor cost of choosing the optimal pivot hurts the average case, making the modified quicksort tend to do worse than heapsort or introsort.
  - gamegoblin 13y ago
    You can use a randomized selection algorithm to find the median in linear time, and if you use the median as a pivot you will never get worst case n^2 behavior. This is not used in practice because the probability of getting worst case behavior is extremely slim if you do some clever, and cheap, tricks.
    - kolistivra 13y ago
      Randomized selection algoritm is actually O(N^2) in the worst case. Median of medians is the O(N) worst case selection algorithm.
- popol 13y ago
  > BFS, DFS are for graphs, not just trees BFS and DFS are applied to graphs, but the search space is indeed a tree.
- voltagex_ 13y ago
  $81 for http://www.amazon.com/Introduction-Algorithms-Thomas-H-Cormen/dp/0262033844 http://www.amazon.com/Introduction-Algorithms-Thomas-H-Corme... No legal DRM free option as far as I can see. Fifth link was a direct to the PDF.
anoncow 13y ago
I hear and I forget. I see and I remember. I do and I understand. Confucius
- msvan 13y ago
  That's Xunzi, not Confucius. Good quote though. </chinese geek>
  - ralph 13y ago
    http://en.wikiquote.org/wiki/Xun_Zi http://en.wikiquote.org/wiki/Xun_Zi doesn't seem to have it; perhaps an update's required?
    - ivan_ah 13y ago
      Check out: http://www.barrypopik.com/index.php/new_york_city/entry/tell_me_and_i_forget_teach_me_and_i_may_remember_involve_me_and_i_will_lear/ http://www.barrypopik.com/index.php/new_york_city/entry/tell... it has a bunch of translations and transliterations of this quote.
dllthomas 13y ago
Still, not a bad reference for checking up on possibly dated knowledge. Memorizing the chart without an understanding of the algorithms will not be terribly useful, but running through the chart, trying to produce the O() values in your head, and checking them against the key, and knowing where to dig deeper, could be a good approach.
jiggy2011 13y ago
Don't memorize, memoize.
Goladus 13y ago
If you understand a concept, then you can reason its big O. Memorization implies a superficial understanding that may be revealed later. Interestingly enough this works both ways. To say more accurately, memorization MAY imply superficial understanding. Memorization (and associated intuitive pattern-matching) may also lead to understanding. A cheat sheet like this is also good shortcut refreshing one's memory of the concepts if this knowledge is not used on a regular basis.
- jiggy2011 13y ago
  I agree, our brains are good at recognizing patterns. So some amount of rote memorization of data can help us see these patterns. I remember learning the 9 * table as a child and suddenly realizing that n * 9 = (n * 10) - n , thinking "hmm, does n * x = n * (x + 1) - n" why yes it does!
ivan_ah 13y ago
As pointed out by msvan, the quote is actually by Xunzi. Here is the original text in Chinese: 不闻不若闻之，闻之不若见之，见之不若知之，知之不若行之；学至于行之而止矣 I know what you are thinking `Why would you post something in Chinese? How could non-Chinese speakers understand?' and the reason is I want y'all to check out this super cool add of for Firefox: https://addons.mozilla.org/en-us/firefox/addon/perapera-kun-chinese-popup-tra/ https://addons.mozilla.org/en-us/firefox/addon/perapera-kun-... With this plugin, the meanings of the words show up onmouseover and you can pretty much get the meaning.

by wting 13y ago

nutjob123 13y ago

This was my immediate reaction. It is very easy and common for an interviewer to make a subtle change to how a common data structure or algorithm would work and then ask for complexity. Ex: Changing the quicksort pivot selection method.

mitchi 13y ago

My friend was interviewed by a video game company not long ago and they gave him an algorithmic problem. He asked what the complexity of the algorithm was and the interviewer said O(n). Good hint to have! He passed the interview.

mixedbit 13y ago

Agree, buy a good book (for example Cormen), learn the algorithms and implement them to get a good understanding. Try to use the table to answer a following question: what is a time complexity for finding a next item (according to a key) to a given one in a hash table? Memorizing such stuff does not make much sense, but if you understand basic concepts, you will figure it out quickly. There are basic errors in the table: BFS, DFS are for graphs, not just trees, and their complexity is not b^d (what is b and d anyway?). Quick sort expected complexity is nlogn and this is different than average complexity. You can also make quicksort worst-case complexity to be nlogn. You can't sort anything with space smaller than number of items you are sorting. You can use buble and insertion sort not only for arrays but also for lists and time complexity does not suffer.

paulolc 13y ago
You can contribute and fix the table yourself :). The author welcomes it . https://github.com/ericdrowell/BigOCheatSheet/blob/master/Tables.html https://github.com/ericdrowell/BigOCheatSheet/blob/master/Ta...
derleth 13y ago
> what is a time complexity for finding a next item (according to a key) to a given one in a hash table? Problem ill-stated as posed: Does not specify if the 'next' key is hashed, or even what 'next' means in this context.
- mixedbit 13y ago
  Say, the smallest item in a hash table for which item.key is larger than given_item.key. Assume larger-than relation for keys is defined, so for example keys are integeters.
  - sillysaurus 13y ago
    Say, the smallest item in a hash table for which item.key is larger than given_item.key. Well, keys in a hash table are hashed. This implies that unless you're searching for a specific key (e.g. "42") rather than a condition (e.g. "smallest key greater than 42") then the time complexity is necessarily O(N).
    - mixedbit 13y ago
      Correct :)
sbov 13y ago
> You can't sort anything with space smaller than number of items you are sorting. I assume it's referring to extra space used. Most analysis of space I've seen is referring to this, not the space required to store the elements.
devcpp 13y ago
>what is b and d anyway? Breadth and depth. These could apply to graphs as well, since these algorithms draw a tree while traversing the graph.
glass_of_water 13y ago
Yeah BFS/DFS are O(n) for graphs and trees.
rttlesnke 13y ago
> You can also make quicksort worst-case complexity to be nlogn. Quicksort in the worst take can take O(n^2) time, not O(nlogn).
- amalcon 13y ago
  If one takes the time to select optimal pivots it becomes O(nlogn). The selection is free from a big-O perspective, because it's O(n) immediately before the O(n) list division step. Of course, nobody does this, because the selection is not really free. The constant factor cost of choosing the optimal pivot hurts the average case, making the modified quicksort tend to do worse than heapsort or introsort.
- gamegoblin 13y ago
  You can use a randomized selection algorithm to find the median in linear time, and if you use the median as a pivot you will never get worst case n^2 behavior. This is not used in practice because the probability of getting worst case behavior is extremely slim if you do some clever, and cheap, tricks.
  - kolistivra 13y ago
    Randomized selection algoritm is actually O(N^2) in the worst case. Median of medians is the O(N) worst case selection algorithm.
popol 13y ago
> BFS, DFS are for graphs, not just trees BFS and DFS are applied to graphs, but the search space is indeed a tree.
voltagex_ 13y ago
$81 for http://www.amazon.com/Introduction-Algorithms-Thomas-H-Cormen/dp/0262033844 http://www.amazon.com/Introduction-Algorithms-Thomas-H-Corme... No legal DRM free option as far as I can see. Fifth link was a direct to the PDF.

anoncow 13y ago

I hear and I forget. I see and I remember. I do and I understand. Confucius

msvan 13y ago
That's Xunzi, not Confucius. Good quote though. </chinese geek>
- ralph 13y ago
  http://en.wikiquote.org/wiki/Xun_Zi http://en.wikiquote.org/wiki/Xun_Zi doesn't seem to have it; perhaps an update's required?
  - ivan_ah 13y ago
    Check out: http://www.barrypopik.com/index.php/new_york_city/entry/tell_me_and_i_forget_teach_me_and_i_may_remember_involve_me_and_i_will_lear/ http://www.barrypopik.com/index.php/new_york_city/entry/tell... it has a bunch of translations and transliterations of this quote.

dllthomas 13y ago

Still, not a bad reference for checking up on possibly dated knowledge. Memorizing the chart without an understanding of the algorithms will not be terribly useful, but running through the chart, trying to produce the O() values in your head, and checking them against the key, and knowing where to dig deeper, could be a good approach.

jiggy2011 13y ago

Don't memorize, memoize.

Goladus 13y ago

If you understand a concept, then you can reason its big O. Memorization implies a superficial understanding that may be revealed later. Interestingly enough this works both ways. To say more accurately, memorization MAY imply superficial understanding. Memorization (and associated intuitive pattern-matching) may also lead to understanding. A cheat sheet like this is also good shortcut refreshing one's memory of the concepts if this knowledge is not used on a regular basis.

jiggy2011 13y ago
I agree, our brains are good at recognizing patterns. So some amount of rote memorization of data can help us see these patterns. I remember learning the 9 * table as a child and suddenly realizing that n * 9 = (n * 10) - n , thinking "hmm, does n * x = n * (x + 1) - n" why yes it does!

ivan_ah 13y ago

As pointed out by msvan, the quote is actually by Xunzi. Here is the original text in Chinese: 不闻不若闻之，闻之不若见之，见之不若知之，知之不若行之；学至于行之而止矣 I know what you are thinking `Why would you post something in Chinese? How could non-Chinese speakers understand?' and the reason is I want y'all to check out this super cool add of for Firefox: https://addons.mozilla.org/en-us/firefox/addon/perapera-kun-chinese-popup-tra/ https://addons.mozilla.org/en-us/firefox/addon/perapera-kun-... With this plugin, the meanings of the words show up onmouseover and you can pretty much get the meaning.