- Solve more problems to increase the probability of clearing interview.
- quick sort is divide and conquer algorithm where a pivot element needs to be selected
- partition array based on pivot element in two sub array
- in the new arrays choose a pivot element again and repeat the steps of keeping partitioning
- keep repeating till only one element length array are left
- def quick_sort(arr): if len(arr) ⇐ 1: return arr else: pivot = arr[0] left_arr = [x for x in arr[1:] if x < pivot] right_arr = [x for x in arr[1:] if x >= pivot] return quick_sort(left_arr) + [pivot] + quick_sort(right_arr)
- Longest common subsequence problem
- consider all the subsequence of a string
- a string of length 3 will have 3 factorial subsequence
- longest common substring problem is about contiguous elements
- problem with buying ticket for music concerts. Solved by selling nft which prove your identity and you are fan of club, with that identity verification
- proof of attendence
- backtracking is about solving every permutation
- backtracking mainly optimises over naive solution