Sliding window

System design . system design questions

Merging 2 sorted arrays

into 1st array where 1st array has the capacity for both

private void merge(int[] a, int n, int[] b, int m) {
	int i = n - 1;
	int j = m - 1;
	int k = n + m - 1;
	while (j >= 0) {
		if (i>=0 && a[i] > b[j])
			a[k--] = a[i--];
			a[k--] = b[j--];

# Python program to determine if two trees are identical 
# A binary tree node has data, pointer to left child 
# and a pointer to right child 
class Node: 
    # Constructor to create a new node 
    def __init__(self, data): = data 
        self.left = None
        self.right = None
# Given two trees, return true if they are structurally 
# identical 
def identicalTrees(a, b): 
    # 1. Both empty 
    if a is None and b is None: 
        return True 
    # 2. Both non-empty -> Compare them 
    if a is not None and b is not None: 
        return (( == and 
                identicalTrees(a.left, b.left)and
                identicalTrees(a.right, b.right)) 
    # 3. one empty, one not -- false 
    return False
# Driver program to test identicalTress function 
root1 = Node(1) 
root2 = Node(1) 
root1.left = Node(2) 
root1.right = Node(3) 
root1.left.left = Node(4) 
root1.left.right = Node(5) 
root2.left = Node(2) 
root2.right = Node(3) 
root2.left.left = Node(4) 
root2.left.right = Node(5) 
if identicalTrees(root1, root2): 
    print "Both trees are identical"
    print "Trees are not identical"
# This code is contributed by Nikhil Kumar Singh(nickzuck_007) 


minhash minhash Дерево отрезков Succinct data structures Visual information theory union-find (disjoint-set) design distributed cache design twitter quick sort Radix sort Шахматный Bitboard HyperLogLog for approximate count distinct Facebook Разбор задачи с собеседования Google: поиск соотношения Hash

Algebraic data types Algebraic data types

Fibonacci Computing Fibonacci Numbers In O(log n) using matrices and eigenvalues


Algo interview . Inteview Merkel’s tree Cycle detection . Competitive programming book Algo Book Algo book fenwick string algo Бинарные деревья поиска LCA алгоритм Хаффмана heap Разбор задачи с собеседования в Google: синонимичные запросы Use “rachit” as coupon code to get 30% off Visitor design pattern red black tree

Dynamic programming

disjoint set union (DSU) или Union-Find. создать быструю структуру, которая поддерживает следующие операции:

MakeSet(X) — внести в структуру новый элемент X, создать для него множество размера 1 из самого себя. Find(X) — возвратить идентификатор множества, которому принадлежит элемент X. В качестве идентификатора мы будем выбирать один элемент из этого множества — представителя множества. Гарантируется, что для одного и того же множества представитель будет возвращаться один и тот же, иначе невозможно будет работать со структурой: не будет корректной даже проверка принадлежности двух элементов одному множеству if (Find(X) == Find(Y)).

Unite(X, Y) — объединить два множества, в которых лежат элементы X и Y, в одно новое. Bloom filter look fo links here! . Radix tree . Radix trees . Tree traversal using 2 threads (Java)

LCA Running mediam in stream Max sub-sequence in string . Favorite algos Book Book

< Local sensitive hash

Google interview Non-symmetric dime simulation Judy array

Egg drop

Find 1st element in rotated sorted array

def bs(lst, start, end):
   print ("start=",start, "end=", end)
   if start == end:  return start
   m = (start+end)//2
   print ("middle=",m, lst[m])

   if m < end and lst[m+1] < lst[m]:
      return m+1
   if m > start and lst[m] < lst[m-1]:
      return m

   if lst[end] > lst[m]:
      return bs(lst, start, m -1)
      return  bs(lst, m+1, end)

def find(l):
  i= bs(l, start, end)
  return i

if __name__ =="__main__":
  print ("main")
  l1=[5,10,20, 1,2,3,4]
  print ("index=",i)

  l2=[20, 1,2,3,4]
  print ("index=",i)

Hash function and hashtable

Consistent Hashing Consistent hashing

Locality sensitive hashing duplicates in array, dual pivot sort

Dynamic programming

Dynamic Programming- Python implementation of Min Cost Path on grid problem

def minCost(cost, m, n):

# Instead of following line, we can use int tc[m+1][n+1] or 
# dynamically allocate memoery to save space. The following 
# line is used to keep te program simple and make it working 
# on all compilers. 
R = 3
C = 3
tc = [[0 for x in range(C)] for x in range(R)] 
tc[0][0] = cost[0][0] 
# Initialize first column of total cost(tc) array 
for i in range(1, m+1): 
    tc[i][0] = tc[i-1][0] + cost[i][0] 
# Initialize first row of tc array 
for j in range(1, n+1): 
    tc[0][j] = tc[0][j-1] + cost[0][j] 
# Construct rest of the tc array 
for i in range(1, m+1): 
    for j in range(1, n+1): 
        tc[i][j] = min(tc[i-1][j-1], tc[i-1][j], tc[i][j-1]) + cost[i][j] 
return tc[m][n] 

Driver program to test above functions

cost = [[1, 2, 3], 
        [4, 8, 2], 
        [1, 5, 3]] 
print(minCost(cost, 2, 2)) 

Count number of ways to reach mat[m-1][n-1] from mat[0][0] in a matrix mat[][]

Returns The number of way from top-left to mat[m-1][n-1]

def countPaths(m, n):

dp = [[0 for i in range(m + 1)]  
         for j in range(n + 1)] 
for i in range(1, m + 1): 
    for j in range(1, n + 1): 
        if (i == 1 or j == 1): 
            dp[i][j] = 1
            dp[i][j] = (dp[i - 1][j] + 
                        dp[i][j - 1])              
return dp[m][n] 

Driver code

if name ==”main”:

n = 5
m = 5
print(countPaths(n, m)) 

Dynamic programming



Regular expression

Inerpretators Compiles