Software Engineer Interview | Latest
Edition
Arrays - ANSWER ✅ The worst case is the average case for arrays.
Access in O(1)
Search in O(n)
Insert in O(n)
Delete in O(n)
Takes O(n) space.
Stack/Queue/Linked List - ANSWER ✅ Stacks are FILO lists.
Queues are FIFO lists.
Linked Lists are lists that keep track of the head and tail, and each element/node
has a value as well as a pointer to the next element/node (doubly linked lists also
have a pointer to the previous node).
The worst case is the average case for these data structures.
Access in O(n)
Search in O(n)
Insert in O(1)
Delete in O(1)
Takes O(n) space.
Skip List - ANSWER ✅ Skip lists are composed of multiple lists that act as
"layers", where higher level layers have less items than lower level layers,
,determined by probability of appearance/use. It is navigated starting at the top and
checking adjacent values--if the desired value is not found, drop to the current
element but on the next layer down and repeat.
All actions on average take O(log(n)) time.
All actions in the worst case take O(n) time.
Takes O(nlog(n)) space.
Hash Table - ANSWER ✅ [Hash Table definition is covered on another card]
On average, each operation takes O(1) time.
In the worst case, each operation takes O(n) time.
Takes O(n) space.
Note: hash tables don't have access-by-location.
Binary Search Tree (NOT Binary Tree) - ANSWER ✅ Starting from the root,
each element of a BST has 2 children, the left of which is less than or equal to its
own value, and the right of which is greater than or equal to its own value.
Each operation takes, on average, O(logn) time.
Each operation takes, at worst, O(n) time.
Quicksort - ANSWER ✅ Choose a pivot at random and split the list by values
greater than the pivot and less than (or equal to) the pivot, then sort the two lists on
either side of the pivot recursively.
This runs in O(nlog(n)) on average.
It runs in O(n^2) at worst.
It uses O(log(n)) space.
, Mergesort - ANSWER ✅ Divide the unsorted list into n sublists containing 1
element each, then consider 2 of those lists and merge them together by order of
value. Do this for each sublist, then recursively repeat it for the new sublists until
they are all merged back into one sorted list.
Both average and worst case scenarios take O(nlog(n)) time.
It uses O(n) space.
Heapsort - ANSWER ✅ Build a heap out of the list, then repeatedly extract the
max value from the heap.
Runs in O(nlog(n)) for both average and worst cases.
It uses O(1) space.
Note: Heapsort is not safe (it is possible for two equivalent items to end up in
swapped positions relative to each other after a heapsort is run).
Bubble Sort/Insertion Sort/Selection Sort - ANSWER ✅ Bubble Sort: Go through
the list and compare each adjacent element, swapping their positions if they are out
of order. Repeat until sorted.
Insertion Sort: Go through list until you find an element that is less than the
element previous to it. Take the element and place it in sorted position in the
earlier portion of the list (the "sorted" portion). Repeatedly do this until all sorted.
Note: Insertion sort is adaptive (it is very fast for lists that are already mostly
sorted).
Selection Sort: Repeatedly go through the list and find the smallest element and
move it to the front of the list.
All of these have average and worst cases of O(n^2).
All of these use O(1) space.
Edition
Arrays - ANSWER ✅ The worst case is the average case for arrays.
Access in O(1)
Search in O(n)
Insert in O(n)
Delete in O(n)
Takes O(n) space.
Stack/Queue/Linked List - ANSWER ✅ Stacks are FILO lists.
Queues are FIFO lists.
Linked Lists are lists that keep track of the head and tail, and each element/node
has a value as well as a pointer to the next element/node (doubly linked lists also
have a pointer to the previous node).
The worst case is the average case for these data structures.
Access in O(n)
Search in O(n)
Insert in O(1)
Delete in O(1)
Takes O(n) space.
Skip List - ANSWER ✅ Skip lists are composed of multiple lists that act as
"layers", where higher level layers have less items than lower level layers,
,determined by probability of appearance/use. It is navigated starting at the top and
checking adjacent values--if the desired value is not found, drop to the current
element but on the next layer down and repeat.
All actions on average take O(log(n)) time.
All actions in the worst case take O(n) time.
Takes O(nlog(n)) space.
Hash Table - ANSWER ✅ [Hash Table definition is covered on another card]
On average, each operation takes O(1) time.
In the worst case, each operation takes O(n) time.
Takes O(n) space.
Note: hash tables don't have access-by-location.
Binary Search Tree (NOT Binary Tree) - ANSWER ✅ Starting from the root,
each element of a BST has 2 children, the left of which is less than or equal to its
own value, and the right of which is greater than or equal to its own value.
Each operation takes, on average, O(logn) time.
Each operation takes, at worst, O(n) time.
Quicksort - ANSWER ✅ Choose a pivot at random and split the list by values
greater than the pivot and less than (or equal to) the pivot, then sort the two lists on
either side of the pivot recursively.
This runs in O(nlog(n)) on average.
It runs in O(n^2) at worst.
It uses O(log(n)) space.
, Mergesort - ANSWER ✅ Divide the unsorted list into n sublists containing 1
element each, then consider 2 of those lists and merge them together by order of
value. Do this for each sublist, then recursively repeat it for the new sublists until
they are all merged back into one sorted list.
Both average and worst case scenarios take O(nlog(n)) time.
It uses O(n) space.
Heapsort - ANSWER ✅ Build a heap out of the list, then repeatedly extract the
max value from the heap.
Runs in O(nlog(n)) for both average and worst cases.
It uses O(1) space.
Note: Heapsort is not safe (it is possible for two equivalent items to end up in
swapped positions relative to each other after a heapsort is run).
Bubble Sort/Insertion Sort/Selection Sort - ANSWER ✅ Bubble Sort: Go through
the list and compare each adjacent element, swapping their positions if they are out
of order. Repeat until sorted.
Insertion Sort: Go through list until you find an element that is less than the
element previous to it. Take the element and place it in sorted position in the
earlier portion of the list (the "sorted" portion). Repeatedly do this until all sorted.
Note: Insertion sort is adaptive (it is very fast for lists that are already mostly
sorted).
Selection Sort: Repeatedly go through the list and find the smallest element and
move it to the front of the list.
All of these have average and worst cases of O(n^2).
All of these use O(1) space.
