Categories
Basic

Data Structure and Algorithms 1

Big O Notation

Evaluate the performance of an algorithm (the worst case scenario)

| Notation      | Name            |
|---------------|-----------------|
| O(1)          | constant        |
| O(log(n))     | logarithmic     |
| O(n)          | linear          |
| O(n^2)        | quadratic       |
| O(n^c)        | polynomial      |
| O(c^n)        | exponential     |

Space Complexity

Only calculate the additional space relative to the size of the input.

Arrays

Array
  • Lookup by Index O(1): The items of a array are stored sequentially in memory, looking up item in an array with their index is super fast
  • Lookup by value O(n)
  • Insert O(n): Need to know the size of the array ahead, otherwise when overflow, have to create a new array and copy the old items into the new one
  • Delete O(n): When the item is at the first position

In JavaScript and Python, Array is dynamic; while in Java, Array is static, ArrayList is dynamic.

Linked Lists

Linked List
  • To store a list of objects in sequence. Unlike array, linked lists can grow and shrink automatically.
  • Each node has a value and an address which is the reference to the next node.
  • Lookup O(n) by value & by index
  • Insert
    • O(1) at the end & at the beginning
    • O(n) in the middle (search the position O(n), insert operation O(1))
  • Delete
    • O(1) from the beginning
    • O(n) from the end, have to traverse the list all to the tail to find the node before last node
    • O(n) in the middle (search the position O(n), insert operation O(1))
  • Doubly: Delete from the end O(1)
Doubly
  • Circular
Circular

Array vs Linked List

  • Space
    • Static arrays have a fixed size
    • Dynamic arrays grow by 50-100%, may waste memory
    • Linked lists don’t waste memory, but need extra memory for keep address for next node
    • Use arrays when you know the number of the items to store

Stacks

  • Use cases:
    • undo feature
    • build compilers(syntax checking)
    • evaluate expression (1 + 3 * 2 )
    • navigation forward / back
  • Last In First Out (LIFO)
  • Operations O(1)
    • push(item): add item on top of the stack
    • pop(): return the item on top and remove it from the stack
    • peek(): return the item on top without removing it
    • isEmpty()
  • Exercise:
    • Reverse a string
    • check if a string is a balanced string
    • Two stacks in one array: stack 1 starts from head, stack 2 starts from end
    • A stack that retrives the minimum value in constant time: a min stack holds the minimums
if(item < minStack.peek()) {
  minStack.push(item);
}

Queues

  • First In First Out
  • Use cases:
    • Printers
    • Operating systems
    • Web servers
    • Live support systems
  • Operations: O(1)
    • enqueue: add an item to the back of a queue
    • dequeue: remove an item at the front of a queue
    • peek: get the item at the front without removing it
    • isEmpty
    • isFull
  • Implementation:
    • Circular Array: with front and rear pointers, instead of reallocating when overflow to save the time complexity, the index map is the remainders of division by array length.
    • Stack: two stacks, one for enqueue and one for dequeue, which is the reverse of the first stack
  • Priority Queues: sorted queue, shift the items when insert a new item

Hash Tables

  • Use cases:
    • Spell checkers
    • Dictionaries
    • Compilers
    • Code editors
  • Implementation in different languages
    • HashMap -> Java
    • Object -> JavaScript
    • Python -> Dictionary
    • Dictionary -> C#
  • Key-Value pairs, connected by hash function
  • Deterministic: Always give the same result value when input is same
  • Operations: O(1)
    • Insert
    • Lookup
    • Delete
  • If hash map allows null key or null values. Yes of both.
  • Exercises:
    • First non-repeating character
  • Set: only keys and non-duplicated
  • Every character in computer is represented by a number internally.
  • Collision: two distinct keys generate the same hash value.
    • Chaining: using a linked list to store multiple items in the same array index
    • Open Addressing:
      • linear probing: (hash(key) + i ) % table_size
        generate cluster, result in slow inserting
      • quadratic probing: (hash(key) + i² ) % table_size
        may result in infinite loop
      • double hashing: hash2(key) = prime – (key % prime)
        (hash1(key) + i * hash2(key)) % table_size
  • Command query separation: a function should either be queries that return answers, or be commands that change the values

Leave a comment