algos for interview Flashcards
seri = [4, 7, 5, 2, 8, 1, 9, 6, 3]
print qsort(seri) –> [1, 2, 3, 4, 5, 6, 7, 8, 9]
seri = [4, 7, 5, 2, 8, 1, 9, 6, 3]
def qsort(arr):
if len(arr) <= 1:
return arr
else:
return qsort([x for x in arr[1:] if x < arr[0]]) \
+ [arr[0]] \
+ qsort([x for x in arr[1:] if x>=arr[0]])
print qsort(seri) –> [1, 2, 3, 4, 5, 6, 7, 8, 9]
print nextnum( [9, 9, 9] ) --> [1, 0, 0, 0] print nextnum( [1, 0, 9] ) --> [1, 1, 0]
print nextnum( [9, 9, 9] ) --> [1, 0, 0, 0] print nextnum( [1, 0, 9] ) --> [1, 1, 0]
def nextnum(arr):
carry = 1
result = []
for i in arr[::-1]:
sum = i + carry
result.append(sum%10)
carry = sum//10
if carry: result.append(1)
return result[::-1]
def nextnum(arr):
carry = 1
res = []
for i in arr[::-1]:
sum = i + carry
res.append(sum%10)
carry = 1 if sum == 10 else 0
if arr[1:] == arr[:-1]:
res.append(1)
return res[::-1]
first n fibonacci
print fib(5) --> 5 print fibi(5) --> 5
print fib(5) --> 5 print fibi(5) --> 5
# iteration - faster
def fibi(n):
a, b = 0, 1
for i in range(n):
a, b = b, a + b
return a
#recursive - slower
def fib(n):
if n == 0:
return 0
elif n == 1:
return 1
else:
return fib(n-1) + fib(n-2)
recursion
n! –> for 5 –> 12345 –> 120
f(n)+n –> for 5 –> 1+2+3+4+5 –> 15
n! –> for 5 –> 12345 –> 120
f(n)+n –> for 5 –> 1+2+3+4+5 –> 15
def nfac(n):
if n == 0:
return 1
else:
return nfac(n-1)*n
def nsum(n):
if n == 0:
return 0
else:
return nsum(n-1)+n
pascal triangle print tria(5) --> [1, 4, 6, 4, 1]
pascal triangle print tria(5) --> [1, 4, 6, 4, 1]
Recursive
def tria(n):
if n== 1:
return [1]
else:
# this codeblock for else statement will run # from start of else until all of n values are # assigned to the variable which calls recursive # function(prev in this case)
line = [1]
previous_line = tria(n-1)
# this recursion will work until n == 0 then # value of prev will be the return value of # if statement which is [1] # from here function continues to run for this # prev value until another return value executed # each return value will be assigned to prev # respectively (in this case prev will store the # value of each returned tmp value and continue # to run within iteration
for i in range(len(previous_line)-1):
line.append(previous_line[i] + previous_line[i+1])
line += [1]
return line
alternative with list comprehension
def pascal(n):
if n == 1:
return [1]
else:
p_line = pascal(n-1)
line = [ p_line[i]+p_line[i+1] for i in range(len(p_line)-1)]
line.insert(0,1)
line.append(1)
return line
Recursive method explained
temp has a value of an empty list when declaration temp = pascal(n-1) return [] when n is 0. Then for each n value until the first one, function continue to run and execute the code for temp list for n values.
def pascal(n):
if n == 0: return []
temp = pascal(n-1)
temp.append(n)
return temp
print pascal(5) # –> [1, 2, 3, 4, 5]
print n fibonacci using yield
for i in fib(5):
print i
--> 1 1 2 3 5
print n fibonacci using yield
def fib(n):
a, b = 0, 1
for i in range(n):
a, b = b, a+b
yield a
check if an array is sorted - recursive
print issorted([1,1,2,3,5,7]) –> True
print issorted([1,1,2,3,5,7]) –> True
def issorted(arr): n = len(arr) if n == 1 or n == 0: return True return arr[0] <= arr[1] and issorted(arr[1:])
sort an array with binary values
print binarysort([1, 0, 1, 1, 1, 1, 1, 0, 0, 0]) –> [0, 0, 0, 0, 1, 1, 1, 1, 1, 1]
print binarysort([1, 0, 1, 1, 1, 1, 1, 0, 0, 0]) –> [0, 0, 0, 0, 1, 1, 1, 1, 1, 1]
def binarysort(arr):
#return sorted(arr)
zeros = arr.count(0)
return [0]*zeros + [1] * (len(arr)-zeros)
Bubble sort algorithm
def getsorted([7, 3, 1, 8, 6, 0, 5]) –> [0, 1, 3, 6, 7, 8]
Bubble sort algorithm def getsorted([7, 3, 1, 8, 6, 0, 5]) --> [0, 1, 3, 6, 7, 8]
def getsorted(arr):
for i in range(len(arr)):
for j in range(len(arr)-i-1):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
return arr
Insertion sort algorithm
array = [12, 11, 13, 5, 6, 10, 3, 7] print insort(array) --> [3, 5, 6, 7, 10, 11, 12, 13]
Insertion sort algorithm
def insort(arr):
for i in range(1,len(arr)):
pivot = arr[i]
j = i-1
while j >= 0 and pivot < arr[j]:
arr[j+1] = arr[j]
j -= 1
arr[j+1] = pivot
return arr
array = [12, 11, 13, 5, 6, 10, 3, 7] print insort(array) --> [3, 5, 6, 7, 10, 11, 12, 13]
selection sort algorithm
array = [12, 11, 13, 5, 6, 10, 3, 7, 0, -5] print insort(array) --> [-5, 0, 3, 5, 6, 7, 10, 11, 12, 13]
selection sort algorithm
A = [12, 11, 13, 5, 6, 10, 3, 7, 0, -5] print insort(A) --> [-5, 0, 3, 5, 6, 7, 10, 11, 12, 13]
for i in range(len(A)):
# Find the minimum element in remaining
# unsorted array
min_idx = i
for j in range(i+1, len(A)):
if A[min_idx] > A[j]:
min_idx = j
# Swap the found minimum element with
# the first element
A[i], A[min_idx] = A[min_idx], A[i]
def insort(arr):
res = []
for i in xrange(len(arr)):
res.insert(i, min(arr))
idx = arr.index(min(arr))
del arr[idx]
return res
You can just count the jumps between 0’s. Jump is just available for 1 or 2 0’s at a time.
array = [0,0, 1,0,0,0,1,0] print JumpOnClouds(array) --> 4
array = [0,0, 1,0,0,0,1,0] print JumpOnClouds(array) --> 4
def JumpOnClouds(c):
n = len(c)
i = 0
jump = 0
while i < n:
if i < n-2 and c[i+2] == 0: i += 1
jump += 1
i += 1
return jump
Python program for implementation of MergeSort
arr = [43, 3, 9, 7, 5] print mergeSort(arr) # --> [3, 5, 7, 9, 43]
Python program for implementation of MergeSort
arr = [43, 3, 9, 7, 5] print mergeSort(arr) # --> [3, 5, 7, 9, 43]
def mergeSort(arr):
if len(arr) >1:
mid = len(arr)//2 #Finding the mid of the array
L = arr[:mid] # Dividing the array elements
R = arr[mid:] # into 2 halves
mergeSort(L) # Sorting the first half
mergeSort(R) # Sorting the second half
i = j = k = 0
# Copy data to temp arrays L[] and R[]
while i < len(L) and j < len(R):
if L[i] < R[j]:
arr[k] = L[i]
i+=1
else:
arr[k] = R[j]
j+=1
k+=1
# Checking if any element was left
while i < len(L):
arr[k] = L[i]
i+=1
k+=1
while j < len(R):
arr[k] = R[j]
j+=1
k+=1
return arr
