Assessment 11 Objectives

Assessment Outline: Data Structures

These are all in weighted order, so most important topics are first.

Stacks / Queues / Linked-Lists

• Linked-Lists
  • Big O performance of operations
  • Key difference between a linked-list and an array
  • Implement a linked-list from scratch in JS
  • Learn and tech linked-lists first because they are used by the other data structures
• Understand when to use a queue vs stack
• Be familiar with common interface methods (push, pop, peek)
• How is a stack used by your computer when running your own code (call stack)
  • Why can you get stack overflow?
• Implement a queue
  • using an Array as the underlying storage
  • using a Linked-List as the underlying storage
  • pros/cons for choosing Array vs Linked-List
• What is a priority queue? (Priority Queues are very popular interview questions)
• Note: deque aka double-ended queue is not important to learn

Hash Table

• Why are Hash Tables useful?
  • The basic interface methods (get, set)
  • Know the Big O of hash table operations
• Be able to solve problems that uses JavaScript Map and Set to solve problems
  • Why use a Map vs Set?
• Basic idea behind a hashing function
  • What characteristics make an effective hashing function?
  • You don’t necessarily need to be able to implement one yourself as doing it well is difficult

Trees

• Binary trees are the most important type of tree
  • Searching a binary tree is one of the most core recursive algorithms used
  • If you understand binary search, most other operations will make sense
  • How to implement core methods (add, find) given Node and Tree class skeleton code
• Tries
  • A very useful type of tree, typically with 26 branches (a-z) at each node instead of 2
  • How tries store their information (different than most other trees)
• Examples of tree structures in the wild: DOM, Filesystem

Array Sorting/Searching

• Binary search of a sorted array is one of the most fundemental algorithms
  • you should understand its pseudocode and be able to implement from scratch in JS
• Other Searching algorithms
  • Linear search: its Big O and how to implement it
• Simple sorting algorithms
  • Bubble
  • Selection
  • Know how to implement them
  • Know their Big O
• Fast Sorting Algorithms and their peformance
  • Merge
  • Know its Big O
  • Understand its pseudocode
  • You don’t need to know how to implement from scratch