Data Structure Must Know

What is an array?

• ordered collection of items

• every item sits in a numbered position

• Fixed size

• contiguous

Time Complexity of Array given index

O(1)

Important constraint of arrays

• Size is fixed from moment of creation

• Stays fixed since expanding size of arrays is hard because new region of contiguous memory must be found that is of the new size. This is O(n) since all data must be copied over. Similar problem with inserting data as well

Data Structure that is fast to read from but slow and rigid when data keeps changing

Array

examples of where arrays are used

pixels on a screen, frames in a video stream, situations where position of data is fixed and known in advance

What is Linked List?

• data structure made of collection of nodes that contain the value they are meant to store along with reference to the next node

• not contiguous, stays connected via pointers

• easy to insert (so O(1) ) or change size of, harder to read because must start in beginning and traverse node pointers (so O(n))

Slow to read, fast to change

Linked List

What is a Stack?

• data structure

• LIFO (Last item In is First item Out)

• 2 operations: push (adds item to top) and pop (removes item from top) , both operations O(1), no other operations

Stack only cares about data added recently

true

What is Queue?

• Data Structure

• FIFO, think: its like a line at a checkout at a store

• 2 operations: enqueue (adds to back) and dequeue (removes from front), both O(1), no other operations

What is a Deque?

• data structure

• (double ended que) = deque

• can easily add or remove from the front

• can easily add or remove from the back

Deque acting as stack

add or remove only from front or only from back

Deque acting as queue

add to back, remove front (or vice versa)

What is a hash map?

• data structure

• stores data as key value pairs

• retrieve data by searching via relevant key which has desired data aka the value. if key is known, retrieval is instant O(1)

• hash function: takes in key, computes number, number points to specific memory address where associated value is located

What problem does hash map solve?

Problem:

• Huge collection

• involve lots of checking of elements to find desired element

Solution:

• Have a treasure map aka dictionary aka a way to map a key to a value instantly

• possible via hash function.

What has more memory footprint, hashmap or array?

hashmap because they store key,value, and other metadata (the hashcode,pointers to buckets for avoiding collisions,etc)

What is a hashset?

• data structure

• hash map with no values, just keys

• entire purpose: does a particular element exist in set or no

• checking/reading, adding, deleting data is all O(1)

• no duplicates

What is a Tree?

• Data Structure

• hierarchical

• has root, nodes (that can have children nodes) connected via branches, and leaf Nodes at the very bottom with no children

• natural data structure for anything that can be modelled via parent child relationship

Plain Tree

• tree with no rules about where values go

• searching could involve potentially checking every single node thus run time complexity could be O(n)

Binary Search Tree

• tree but with the rule that root and any other node can have at most 2 children

• parent’s left child contains value lesser than parent node’s value

• parent’s right child contains value more than parent node’s value

What happens when you add items to BST in already sorted order?

It acts like a linked list, searching becomes O(n) as in the case of an ordinary linked list

Self Balancing BST

• Type of BST

• solves the problem of encountering data in sorted order by doing rotations of data to make sure no branch is way longer than the other. Uses algorithms like red-black trees and AVL

• search runtime complexity is O(log(n))

What is Heap?

• tree-based data structure that keeps highest priority item at the top

• reorganizes automatically every time new data is added to still have highest priority data at the top as root

• used when the goal isnt search but instant access to most important element

Max Heap

largest value is at root

Min Heap

smallest value is at root

Finding top priority element without heap…..

sort whole list by priority, then find highest priority data. This is inefficient compared to heap for this task.

What are Graphs?

• data structure

• made up of nodes and edges, where nodes connected/related via edges.

Undirected Graphs

involves edges that relate nodes bidirectionally (so no general direction)

Directed Graphs

involves edges that are unidirectional where one node may relate to another but not vice versa

Adjascent Nodes

neighboring nodes connected via edges.

How to store a Graph in memory

• adjascency matrix: rows and columns are nodes, values within stored in 0 or 1, signalling no edge or edge.

• Adjascency List: each node keeps a list of its neighbors. This is more memory efficient

What can be done with graphs?

• search via DFS and BFS

• finding paths between nodes

• checking for cycles between nodes

• detecting nearby nodes

What is a Trie?

• variation of a tree

• each level represents one character in a word

• shows branches to possible chars based on preceding chars typed by user, works like n-gram contex

What is a Disjoint Set aka Union -Find?

• data structure

• purpose is to track group membership efficiently

• every element starts as its own group. When elements get connected, they merge into one group, with each group having a representative called “leaders”.

• to check if two elements in same group, you check if they have same leader. This check is O(1)

What is a bloom filter?

• data structure

• O(1) search

• little memory

• answers yes or no when something is searched. If no, this is a guranteed correct answer (no false negatives), but if yes, there is a chance it is a false positive

how are bloom filters used

used to rule out answers to search query with reasonable certainty. for example bloom filter on search term is used before actual search is done on database to reduce number of database reads

What is LRU (least recently used) Cache?

• data structure

• used in cases where memory is running low and some data must be discarded to make space. Least recently used data is what is made to be discarded or removed from cache

• built from combination of hash map and doubly lined list

• most recently used data is made to be in front, least recently used made to stay in back and discarded when when memory is low

• get(key) and put(key,val) is O(1) time