Grokking Modern System Design Interview for Engineers & Managers
Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.
Randomized algorithms use random numbers or choices to decide their next step. We use these algorithms to reduce space and time complexity. There are two types of randomized algorithms:
Las Vegas algorithms
Monte-Carlo algorithms
Las Vegas algorithms always return correct results or fail to give one; however, its runtime may vary. An upper bound can be defined for its runtime.
Quicksort is a sorting algorithm that uses the divide and conquers technique. A pivot point is selected randomly from an array which is then partitioned so that all elements lesser than the pivot are placed on its left, and more significant elements are placed on its right. These steps are carried out recursively until the whole array is sorted.
Note: Purple indices are selected as the pivot point.
The last index is selected as the pivot point in the example above. In the worst case, the pivot point selected is the maximum or minimum element.
def partition(array, start, end): pivot = array[end] i = start for j in range (start, end): if array[j] < pivot: array[i], array[j] = array[j], array[i] i = i+1 array[i], array[end] = array[end], array[i] return i; def QuickSort (array, start, end): if start < end: pivotelement = partition(array, start, end) QuickSort(array, start, pivotelement - 1) QuickSort(array, pivotelement + 1, end) array=[23,11,43,22,34,42,1] #print(len(array)) QuickSort(array, 0, len(array)-1) print(array)
Line 2: The last element in the array is selected as the pivot
point.
Lines 5–7: If the element array[j]
is lesser than the pivot,
replace it with array[i],
which points to an element more significant than the pivot.
Line 8: Swap pivot
with array[i]
as it is the first array element more significant than the pivot
point.
Line 9: Return index of pivot.
Line 13: Find the pivot
point and place it so that all elements lesser than the pivot
are placed on its left, and more significant elements are placed on its right.
Lines 14–15: Apply QuickSort on both sides of the pivotelement.
The Monte-Carlo algorithms work in a fixed running time; however, it does not guarantee correct results. One way to control its runtime is by limiting the number of iterations.
Freivalds’ algorithm is used to verify the result of matrix multiplication in O($n^2$) time. In this algorithm, three nxn matrices, A,
B,
and C,
are given input, where C = AB.
The algorithm generates a random matrix r
of size n and computes $A x Br - Cr$ to verify the value of C.
If the result is equal to zero, it means that C
is correct, and the result is considered incorrect for non-zero values.
Through Freivalds’ algorithm, we can control the runtime; however, it may produce erroneous results. For example, the result can be zero even though C
is sometimes incorrect.
Note: The resultant matrix
[0,0]
verifies the given input matrixC
.
import numpy as np import random def Freivald(A, B, C): r = ([random.randint(0,50)],[random.randint(0,50)]) Br = np.dot(B,r) Cr = np.dot(C,r) answer = np.dot(A, Br) - Cr return answer A = ([3,6],[2,1]) B = ([4,5],[3,6]) C = np.dot(A,B) result = Freivald(A,B,C); print (result)
Line 5: Generate a random matrix r
of size [n][1].
Lines 6–7: Calculate Br
and Cr
using the built in matrix multiplication function, np.dot(matrix1,matrix2)
.
Line 8: Calculate $ABr - Cr$.
Lines 14–15: Matrix C
is correct if the result
is equal to [0,0].
RELATED TAGS
CONTRIBUTOR
Grokking Modern System Design Interview for Engineers & Managers
Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.