- Job Search Process
- Tips and Tricks
- Practice Questions
- Recommended Reading
Traditional resumes DON'T WORK.
Learn how to write a dev resume
the right way to get hired fast.
Interviewers are very interested in whether or not you understand the efficiency of your algorithm, in both running time and space constraints.
Efficiency is usually measured using Big-O analysis, which estimates the worst case scenario of the time it takes for an algorithm to run given an input size of n.
Big-O represents worst case analysis, Big-Theta represents average case, and Big-Omega represents best case. As programmers, we are almost always interested in the worst case scenario, so we'll focus on Big-O analysis.
Big-O analysis is very useful because it allows a programmer to predict an algorithm's running time without having to implement it and run benchmarks.
Since Big-O analysis only cares about the asymptotic running time of the algorithm, it is a rough guess, but the advantage is in not having to worry about the minute details.
|O(1)||Insertion and deletion for arrays due to random access.
Insertion and deletion of the head element in linked lists.
Insertion and deletion of the root element in heaps.
|O(log n)||Binary search in arrays.
Insertion, deletion, and balancing of binary search trees.
|O(n)||Linked list traversal.|
NP complete problems are of this class.
Steps for performing Big-O analysis:
NOTE: Some algorithms require Big-O notation using two or more variables: for example, graph algorithm running times are often expressed as O(ve), v for the number of vertices and e for the number of edges.
You should be familiar with the Big-O running time for all of the popular algorithms out there and understand why it takes that long. Keep in mind that the underlying data structure used by an algorithm may change the running time.
|Insert into array||O(1)|
|Delete entry from array||O(1)|
|Search in sorted array||O(log n)|
|Insert to head of linked list||O(1)|
|Insert to tail of linked list||O(n)|
|Search in linked list||O(n)|
|Insert into binary search tree||O(log n)|
|Balance binary search tree||O(log n)|
|Search for element in binary search tree||O(log n)|