Data Structures, Algorithms and Algorithm Complexity
Candidates must know common data structures: arrays (fixed size, fast index access), linked lists (dynamic size, slow traversal), stacks (LIFO), queues (FIFO), trees (hierarchical, e.g., binary search tree), and hash tables (key-value mapping, average O(1) lookup). Algorithms include searching (linear O(n), binary O(log n) on sorted data) and sorting (bubble O(n^2), merge O(n log n), quick average O(n log n)). Complexity is expressed using Big-O notation, describing upper bound growth. Traps include confusing O(n log n) with O(log n), or assuming binary search works on unsorted data. Also, know that Big-O ignores constants and lower-order terms. Space complexity matters too. A worked example: for a list of 1000 sorted items, binary search takes about 10 comparisons (since 2^10 ≈ 1024), while linear search may take up to 1000. Rule of thumb: if the problem says 'sorted', consider binary search; if it says 'frequent insertions and deletions', consider a linked list. Also, understand that a stack is used for function calls and expression evaluation, and a queue for scheduling. Recursion uses a stack and can cause overflow if base case is missing.