- Choose Language for coding interview 🔗
- Consider Time Complexity 🔗
- Implement Data Structures 🔗
- Implement Sorting algorithms 🔗
- Quick Sort
- Merge Sort
- Bubble Sort
- Insertion Sort
- Selection Sort
- Counting Sort
- Problem solving
Questions for choosing the right language for your coding interview
- Are you interviewing for a language-specific job?
- What is your best language?
- How easy is it to solve algorithmic problems in the language?
- Is the language easy to understand for people who don’t know it?
- Do they use that language at the company?
Resources:
Expected time complexity to perform the operation on the data limit N
within the time limit of 1 to 10 seconds
is as follows.
Limit of Data Size | Expected Time Complexity |
---|---|
N <= 1,000,000 | O(N) or O( n *log(n)) |
N <= 10,000 | O(N**2) |
N <= 500 | O(N**3) |
resources:
- Harvard CS50 - with korean explanation
- Harvard CS50 - Asymptotic Notation (video)
- Big O Notations (general quick tutorial) (video)
- Big O Notation (and Omega and Theta) - best mathematical explanation (video)
- Skiena:
- A Gentle Introduction to Algorithm Complexity Analysis
- Orders of Growth (video)
- Asymptotics (video)
- UC Berkeley Big O (video)
- UC Berkeley Big Omega (video)
- Amortized Analysis (video)
- Illustrating "Big O" (video)
- TopCoder (includes recurrence relations and master theorem):
- Cheat sheet
operation | example | time complexity |
---|---|---|
index | list[i] |
O(1) |
store | list[i] = 0 |
O(1) |
store | list[i] = 1 |
O(1) |
get length | len(list) |
O(1) |
append | list.append(x) |
O(1) |
slice | list[a:b] |
O(k) |
extend | list.extend(iterable) L += K L = L + K |
O(k) |
pop last one | list.pop() |
O(1) |
pop not last one | list.pop(i) |
O(n) |
remove | list.remove(i) |
O(n) |
construction | list(iterable) |
O(n) |
multiply | list*k |
O(n) |
copy | list.copy() |
O(n) |
comparision | list1==list2 list1!=list2 |
O(n) |
search | x in list x not in list |
O(n) |
extreme value | min(list) max(list) |
O(n) |
reverse | list.reverse() |
O(n) |
quick sort | list.sort() sorted(list) |
O(n*log n) |
sum | sum(list) |
O(n) |
append vs insert vs extend more
-
If we want to add an element at the end of a list, we should use
append
. It is faster and direct. -
If we want to add an element somewhere within a list, we should use
insert
. It is the only option for this. -
If we want to combine the elements of another iterable to our list, then we should use
extend
. -
Dictionary.pop(i)
takes O(1)
operation | example | time complexity |
---|---|---|
copy | copy.copy(deque) |
O(n) |
append | .append(x) |
O(1) |
append left | .appendleft(x) |
O(1) |
pop | .pop() |
O(1) |
pop left | .popleft() |
O(1) |
extend | .extend(iterable) |
O(k) |
extend | extendleft(iterable) |
O(k) |
rotate | .rotate(n) |
O(k) |
remove | .remove(x) |
O(n) |
operation | example | time complexity |
---|---|---|
Length | len(s) |
O(1) |
Add | s.add(x) |
O(1) |
Containment | x in/not in s |
O(1) |
Remove | s.remove(..) |
O(1) |
Discard | s.discard(..) |
O(1) |
Pop | s.pop() |
O(1) |
Clear | s.clear() |
O(1) |
check | s != t s == t s <= t |
O(len(s)) |
check | s >= t |
O(len(t)) |
Union | s ∣ t |
O(len(s)+len(t)) |
Intersection | s & t |
O(len(s)+len(t)) |
Difference | s - t |
O(len(s)+len(t)) |
Symmetric Diff | s ^ t |
O(len(s)+len(t)) |
Copy | s.copy() |
O(N) |
operation | example | time complexity |
---|---|---|
Index | d[k] |
O(1) |
Store | d[k] = v |
O(1) |
Length | len(d) |
O(1) |
Delete | del d[k] |
O(1) |
get/setdefault | d.get(k) |
O(1) |
Pop | d.pop(k) |
O(1) |
Pop item | d.popitem() |
O(1) |
Clear | d.clear() |
O(1) |
View | d.keys() |
O(1) |
more: python wiki-Time complexity , UCI- Complexity of Python Operations
time complexity | space complexity | |
---|---|---|
average | O(N log N) |
|
worst | O(N^2) |
O(log N) |
# space complexity in worst case: O(N)
def quickSort(self, nums: List[int]) -> List[int]:
if len(nums) < 2: return nums
pivot = nums[-1]
lower = [ x for x in nums if x < pivot ]
same = [ x for x in nums if x == pivot ]
higher = [ x for x in nums if x > pivot ]
return self.quickSort(lower)+ same + self.quickSort(higher)
const quickSort = (nums) => {
if (nums.length < 2) {
return nums
}
const pivot = nums[0]
const less = nums.filter(x => x < pivot)
const greater = nums.filter(x => x > pivot)
const same = nums.filter(x => x === pivot)
return [...quickSort(less), ...same, ...quickSort(greater)]
}
time complexity | space complexity | |
---|---|---|
average | O(N log N) |
|
worst | O(N log N) |
O(N) |
def mergeSort(self, nums: List[int]) -> List[int]:
if len(nums) < 2: return nums
mid = len(nums) // 2
a, b = self.mergeSort(nums[:mid]), self.mergeSort(nums[mid:])
i, j, res = 0, 0, []
while i < len(a) and j < len(b):
if a[i] < b[j]:
res.append(a[i])
i += 1
else:
res.append(b[j])
j += 1
res = res + a[i:] if i < len(a) else res
res = res + b[j:] if j < len(b) else res
return res
const mergeSort = (nums) => {
if (nums.length < 2) {
return nums
}
const mid = Math.floor(nums.length/2)
const [a, b] = [mergeSort(nums.slice(0, mid)), mergeSort(nums.slice(mid))]
const sortedNums = []
let i = 0, j = 0
while (i < a.length && j < b.length) {
sortedNums.push(a[i] < b[j] ? a[i++] : b[j++])
}
while (i < a.length) {
sortedNums.push(a[i++])
}
while (j < b.length) {
sortedNums.push(b[j++])
}
return sortedNums
}
time complexity | space complexity |
---|---|
O(N^2) |
O(1) |
def bubbleSort(self, nums: List[int]) -> List[int]:
N = len(nums) - 1
for i in range(N):
for j in range(N - i):
if nums[j] > nums[j + 1]:
nums[j + 1], nums[j] = nums[j], nums[j + 1]
return nums
time complexity | space complexity |
---|---|
O(N^2) |
O(1) |
def insertionSort(self, nums: List[int]) -> List[int]:
for i in range(1, len(nums)):
curr = i
for j in reversed(range(i)):
if nums[j] <= nums[curr]:
break
nums[j], nums[curr] = nums[curr], nums[j]
curr -= 1
return nums
time complexity | space complexity |
---|---|
O(N^2) |
O(1) |
def selectionSort(self, nums: List[int]) -> List[int]:
for i in range(len(nums)):
m = i
for j in range(i + 1, len(nums)):
if nums[j] < nums[m]:
m = j
nums[m], nums[i] = nums[i], nums[m]
return nums
time complexity | space complexity |
---|---|
O(A+K) |
O(K) |
- condition: we have to know the range of the sorted values.
- Count the number of each unique elements in the array.
- Iterate through the array of counters in increasing order.
def countingSort(A: List[int],k: int) -> : List[int]:
# A is consisted with integers range 0 to k
n = len(A)
# We need additional memory O(k)
count = [0] * (k+1)
for i in range(n):
count[A[i]] += 1
inx = 0
for i in range(k+1):
for j in range(count[i]): # smaller than O(A)
A[inx] = i
inx += 1
return A