-
Notifications
You must be signed in to change notification settings - Fork 1
Home
The following is a list of topics to study and a brief summary and important notes on each topic and list of good/useful questions. (I wrote the list from Cracking the coding interview, also using the following references: Cheat Sheet, Gainlo, Google TechDev) We'll keep updating this wiki as we go through each topic.
Definition
Stores data elements based on a sequential, most commonly 0 based, index.
Key points
Optimal for constant access to specific indices. Bad for finding specific elements. Arrays can have constant size or they can dynamically resize. If a dynamic array is full, it copies it's contents to a larger array. A good way to do this is to double the size when array is full, this way (it can be proved) that the amortized cost of insertion is still O(1).
Big O efficiency
Index access: O(1) Find an element: O(n)(If array is sorted, O(log n) with binary search) Insertion: O(1) if at the end of the array, O(n) otherwise
C++ Implementation notes
Arrays can be implemented either as fixed or dynamic sized arrays (e.g int a[10];) or we can use stl vectors.
List of coding problems for this topic (mostly from leetcode probably) + maybe some points on each question
Warm up:
Shortest unsorted continuous subarray (Our Code)
Medium:
Hard:
Using C++ STL, we can use ordered or unordered map:
unordered_map<int, int> my_map;
Useful functions: insert, find, count