Interview Cheat Sheets | Sorting and Searching Cheat Sheet
December 21st, 2023
Introduction
This article will serve to further summarize the excellent overview of sorting and searching algorithms from the tech interview handbook.
Summary
- Sorting involves rearranging elements in a sequence in order, numerically or lexicographically, ascending or descending.
- Algorithms with
O(n^2)time complexity are usually avoided in interviews.
Time Complexity Table:
| Algorithm | Time Complexity | Space Complexity |
|---|---|---|
| Bubble sort | O(n^2) | O(1) |
| Insertion sort | O(n^2) | O(1) |
| Selection sort | O(n^2) | O(1) |
| Quicksort | O(n log(n)) | O(log(n)) |
| Mergesort | O(n log(n)) | O(n) |
| Heapsort | O(n log(n)) | O(1) |
| Counting sort | O(n + k) | O(k) |
| Radix sort | O(nk) | O(n + k) |
| Binary search | O(log(n)) | - |
Things to Look Out For:
-
Know the time and space complexity of the language’s default sorting algorithm.
-
JavaScript:
The time complexity of the default sorting algorithm in JavaScript (used by the
Array.prototype.sortmethod) is generallyO(n log(n)), where “n” is the number of elements in the array. The actual sorting algorithm used may vary between JavaScript engines and browsers, but it’s typically an efficient variation of merge sort or quicksort. (Chrome V8 seems to use a merge sort variation called TimSort)It’s worth noting that the JavaScript engine might switch to a different algorithm, such as insertion sort, for small arrays to optimize performance. Documentation should always be checked to understand if any updates to these default algorithms have been made.
-
-
Handle corner cases like an empty sequence, a sequence with one or two elements, and sequences with duplicate elements.
Techniques:
- Utilize binary search for sorted inputs.
- Apply counting sort for inputs with a limited range.
Essential Questions:
- Binary Search: My solution
- Search in Rotated Sorted Array: My solution
Recommended Practice Questions:
- Kth Smallest Element in a Sorted Matrix.
- Search a 2D Matrix.
- Kth Largest Element in an Array.
- Find Minimum in Rotated Sorted Array.
- Median of Two Sorted Arrays.