## Techie Delight¶

### Node of a Doubly Linked List¶

In [5]:
# linked list: double linked list
class Node:
def __init__(self,val, nxt_node=None, prev_node=None):
self.val = val
self.nxt = nxt_node # the pointer initially points to nothing
self.prev = prev_node

def __repr__(self):
return ('{}'.format(self.val)) #if self.val else ' '


In [6]:
'Singly Linked List'

#node.prev = None

def walk(self):
toprint = ' '
while cur:
toprint+=str(cur.val)
cur = cur.next
return int(toprint)

def reverse(self):
prev = None
while (current):
nxt = current.next
current.next = prev
prev = current
current = nxt
return self

def getSize(self):
count = 0
while cur is not None:
count += 1
cur = cur.next
return count


In [7]:
class DoubleLinkedList(object):
def __init__(self, node=None):

def size(self):
count = 0
while cur:
count += 1
cur = cur.next
return count

def insert(self, node):
'O(1) worst case time'
node.prev = None

def search(self, val):
'O(n) worst case time'
while (node and (node.val is not val)):
node = node.next
return node

def reverse(self):
prev = None
while cur:
nxt = cur.next
cur.next = prev
prev = cur
cur  = nxt
return self

def deleter(self, node):
'O(1) worst case time'
if node.prev:
node.prev.next = node.next
else:
if node.next:
node.next.prev = node.prev

def walk(self):
'O(n) worst case time'
while cur:
print('{}'.format(cur))
cur = cur.next

for i in range(6, 0, -1):
ll.insert(Node(i))
print(ll.walk())

1
2
3
4
5
6
None


### Doubly Linked List With Sentinel¶

In [11]:
class Sentinel(object):
def __init__(self):
self.prev = self
self.next  = self

def is_valid(self):
return isinstance(self.next.key, int)

self.position = 0

def size(self):
count = 0
while cur:
count += 1
cur = cur.next
return count

def insert(self, node):
'O(1) worst case time'
self.position += 1

def search(self, val):
'O(n) worst case time'
while ((node is not self.head) and (node.val is not val)):
node = node.next
return node

while pos !=-1:
cur = cur.next
pos -= 1
return cur

def deleter(self, node):
'O(1) worst case time'
if node.prev is not None:
node.prev.next = node.next
else:
if node.next is not None:
node.next.prev = node.prev

def reverse_in_btwn(self, m, n):
'reverse elems from m to n, m << n'
# advance pointer to node m
while cur is not node_m.next:
cur = cur.next
# start reversing from current node m all the way to node n
prev = cur
while cur is not node_n.next and not isinstance(cur, Sentinel):
nxt = cur.next
cur.next = prev
prev = cur
cur = nxt
return self

def walk(self):
'O(n) worst case time'
while cur and not isinstance(cur, Sentinel):
print(' cur_node: {}'.
format(cur))
cur = cur.next


### Reverse sum of linked lists¶

• You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list. You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example:

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4) Output: 7 -> 0 -> 8 Explanation: 342 + 465 = 807.

In [15]:
import copy

class Solution:
@classmethod
l1sz, l2sz = l1.getSize(), l2.getSize()
assert l1sz==l2sz, "size not equal"

carry = []
while cur_1 and cur_2:
cur_val = cur_1.val + cur_2.val + carry[-1] if carry else cur_1.val + cur_2.val
if cur_val<=9:
del carry[::]
else:
tostore = int(str(cur_val)[-1])
carry.append(int(str(cur_val)[-2]))
cur_1, cur_2 = cur_1.next, cur_2.next

#rl = returnList.reverse()
return returnList

# Tests

sol = Solution()
print('l1: ', l1.walk(), 'l2: ', l2.walk(),
' res: ', res.walk(), ' res reversed: ', res.reverse().walk())
print()

# Test2
#

sol = Solution()
print('l1: ', l1.walk(), 'l2: ', l2.walk(),
' res: ', res.walk(), ' res reversed: ', res.reverse().walk())

l1:  991 l2:  991  res:  398  res reversed:  893

l1:  342 l2:  465  res:  807  res reversed:  708


# Stacks and Queues¶

• Stack: LIFO Policies

• Queues: FIFO Policies

In [16]:
import os

class stack(object):
def __init__(self, contents=None):
self.contents = [] if contents is None else contents

def is_empty(self):
# O(1) time
if self.contents:
return False
else:
return True

def push(self, x):
# O(1) time
self.contents.append(x)

def pop(self):
# O(1) time
if self.is_empty():
return os._exit(0)
else:
popped = self.contents[-1]
self.contents=self.contents[:-1]
return popped

s = stack(contents=[15,6,2,9])
print('orig contents: ', s.contents)
s.push(17)
s.push(3)
print('post push contents: ', s.contents)
print('popped: ', s.pop())
print('new contents: ', s.contents)

orig contents:  [15, 6, 2, 9]
post push contents:  [15, 6, 2, 9, 17, 3]
popped:  3
new contents:  [15, 6, 2, 9, 17]


### Queues¶

In [17]:
class Queue(object):
def __init__(self):
self.tail = 0
self.Q = []

def enqueue(self, x):
self.Q.insert(self.tail, x)
if self.tail == len(self.Q):
self.tail = 1
else:
self.tail += 1

def dequeue(self):
else:
return x

In [18]:
q = Queue()
contents=[15,6,2,9]
for i in contents:
print('enqueuing ', i, q.Q)
q.enqueue(i)
print('orig contents: ', q.Q)
q.enqueue(17)
q.enqueue(3)
print('post push [17, 3] contents: ', q.Q)
print('popped: ', q.dequeue())
print('new contents: ', q.Q)

enqueuing  15 []
enqueuing  6 [15]
enqueuing  2 [15, 6]
enqueuing  9 [15, 6, 2]
orig contents:  [15, 6, 2, 9]
post push [17, 3] contents:  [15, 6, 2, 9, 17, 3]
popped:  15
new contents:  [6, 2, 9, 17, 3]


# Hash Tables¶

An effective data structure for implementing dictionaries. While searching for an element in a hash table might take as long as O(n) just as a linked list in worst case, in practice, hashing performs extremely well. Under reasonable assumptions, the average time to search for an element in a hash table is O(1). Directly addressing into an ordinary array makes effective use of our ability to examine an arbitrary position in an array in O(1) time. When the number of keys actually stored is small relative to the total number of possible keys, hash tables become an effective alternative to directly addressing an array, since a hash table typically uses an array of size proportional to the number of keys actually stored. Instead of using the key as an array index directly, the array index is computed from the key. Basic ops require only O(1) time on average. Perfect hashing can support O(1) worst case time, when set of keys being stored is static

In [19]:
class DirectAddress(object):
'''
Note: Only works well if the Universe of
keys is reasonably small
'''
def __init__(self, T=None):
self.T = T

def search(self, k):
# O(1) op
return self.T[k]

def insert(self, x):
# O(1) op
T[x.key] = x

def delete(self, x):
# O(1) op
del T[x.key]

# resolve collisions by chaining
class ChainHash(object):
def __init__(self, T=None):
self.T = T

def insert(self, x):
# O(1) time
T[hash(x.key)] = x

def search(self, k):
while T[h(k)] != T[k]:
T[h(k)] = T[h(k+1)]
return T(h[k])

def delete(self, x):
pass

class Hash(object):
'Note this is a prelim impl. Needs revisiting'
def __init__(self, T=None, m = None):
self.T = T
self.m = m

def insert(self, k):
i = 0
while i < m:
j = h(k, i)
if not T[j]:
T[j] = k
return j
else:
i += 1
# add error hash table overflow here

def search(self, k):
i = 0
while T[j] or i == self.m:
j = h(k, i)
if T[j]==k:
return j
i += 1
return None


### Binary Search Trees¶

For any node x, the keys in the left subtree of x are at most x.key, and the keys in the right subtree of x are at least x.key. This is the so-called binary search tree property: For a node x in the tree, if y is a node in the left subtree of x, then y.key <= x.key. If y is a node in the right subtree of x, then y.key >= x.key

### Bundle¶

Bundles many types similar to a named tuple

In [23]:
class Bundle(object):
def __init__(self, variables):
for var, val in variables.items():
object.__setattr__(self, var, val)

In [24]:
class Sentinel(object):
'''Place holder for root nodes. I prefer this to None
as an ad hoc python pointer in place of C\'s Null'''
def __init__(self, key=None):
self.left = self
self.right  = self
self.key  = key
self.p = Bundle({'key': key,
'left': self.left,
'right':self.right})

class BSTNode(object):
def __init__(self, key=None):

self.left = None
self.right  = None
self.key = key
self.p = Bundle({'key': key,
'left': self.left,
'right':self.right})

def __repr__(self):
return '{}'.format(self.key)

class BST(object):
def __init__(self, root=None):
self.root = root
self.show = False

def transplant(self, u, v):
'''replaces one subtree as a child of
its parent with another subtree. node u’s parent
becomes node v’s parent, and u’s parent ends up
having v as its appropriate child'''
print('Transplanting {} with {}'.format(u, v))
if not u:
self.root = v
elif u == u.left:
u.left = v
else:
u.right = v
if v:
v = u

def inorderwalk(self, node):
# O(n) time: Prints key of root of a subtree between the left and right subtree: ascending order
if isinstance(node, BSTNode):
self.inorderwalk(node.left)
print('inorderwalking node with key', node)
self.inorderwalk(node.right)

def preorderwalk(self, node):
# O(n) time: Prints key of root of a subtree between the left and right subtree: ascending order
if isinstance(node, BSTNode):
print('preorderwalking node with key', node)
self.preorderwalk(node.left)
self.preorderwalk(node.right)

def postorderwalk(self, node):
# O(n) time:
if isinstance(node, BSTNode):
self.postorderwalk(node.left)
self.postorderwalk(node.right)
print('postorderwalking node with key', node)

def delete(self, z):
print('Deleting: {}'.format(z))
if not z.left:
self.transplant(z, z.right)
elif not z.right:
self.transplant(z, z.left)
else:
y = self.minimum(z.right)
if y.p is not z:
self.transplant(y, y.right)
y.right = z.right
y.right.p = y
self.transplant(z, y)
y.left = z.left
y.left.p = y

def search(self, node, key):
# O(h) time where h is tree height
if isinstance(node, Sentinel) or key == node.key:
return node

if key < node.key:
return self.search(node.left, key)
else:
return self.search(node.right, key)

def unrollsearch(self, node, key):
while isinstance(node, Sentinel) and key != node.key:
if key < node.key:
node = node.left
else:
node = node.right
return node

def minimum(self, node):
while node.left:
node = node.left
return node

def maximum(self, node):
if isinstance(node, Sentinel):
return node.right
while node.right:
node = node.right
return node

def successor(self, node):
if isinstance(node.right, BSTNode):
return self.minimum(node.right)
node_r = node.p
while isinstance(node_r, BSTNode) and node==node_r.right:
node = node_r
node_r = node.p
return node_r

def insert(self, node):
y = Sentinel()
x = self.root
while isinstance(x, BSTNode):
y = x
if node.key < x.key:
x =  x.left
else:
x = x.right
node.p = y

if isinstance(y, Sentinel):
self.root = node  # empty tree
elif node.key < y.key:
y.left = node
else:
y.right = node
if self.show:
print('This node.key: {} || Tree: [p.key: {} left: {}, right: {}]'.format(node.key, node.p.key, node.p.left, node.p.right))


In [25]:
import random
root=Sentinel(key=14)
binary_tree = BST(root)
nodes = [BSTNode(key) for key in [14, 10, 15,2, 54, 58, 83, 81, 47, 32, 19, 28, 68, 89, 82]]

for node in nodes:
binary_tree.insert(node)

In [27]:
binary_tree.inorderwalk(nodes[0])

inorderwalking node with key 2
inorderwalking node with key 10
inorderwalking node with key 14
inorderwalking node with key 15
inorderwalking node with key 19
inorderwalking node with key 28
inorderwalking node with key 32
inorderwalking node with key 47
inorderwalking node with key 54
inorderwalking node with key 58
inorderwalking node with key 68
inorderwalking node with key 81
inorderwalking node with key 82
inorderwalking node with key 83
inorderwalking node with key 89

In [28]:
binary_tree.unrollsearch(nodes[0], 45)

Out[28]:
14
In [29]:
binary_tree.maximum(nodes[0])

Out[29]:
89
In [30]:
binary_tree.minimum(nodes[0])

Out[30]:
2
In [31]:
binary_tree.delete(nodes[-1])

Deleting: 82
Transplanting 82 with None

In [32]:
binary_tree.inorderwalk(nodes[0])

inorderwalking node with key 2
inorderwalking node with key 10
inorderwalking node with key 14
inorderwalking node with key 15
inorderwalking node with key 19
inorderwalking node with key 28
inorderwalking node with key 32
inorderwalking node with key 47
inorderwalking node with key 54
inorderwalking node with key 58
inorderwalking node with key 68
inorderwalking node with key 81
inorderwalking node with key 82
inorderwalking node with key 83
inorderwalking node with key 89


### Insert Sort¶

In [18]:
def insertSort(A):
# O(n^2) worst case
for j in range(1, len(A)):
key = A[j]
i = j -1
while i > -1 and A[i]>key:
A[i+1]=A[i]
i-=1
A[i+1] = key
return A

insertSort([50, -30, 11, 8, 45 ])

Out[18]:
[-30, 8, 11, 45, 50]

### Heap Sort from CLRS¶

• Heap sort: An O(n lg (n) algorithm): Like insert sort, it sorts in place. See pg 152-160 nin CLRS
In [19]:
from math import floor
import random

def exchange(A, el1, el2):
temp = A[el1]
A[el1] = A[el2]
A[el2] = temp

def max_heapify(A, i):
# runs in O(lg n) time
global heapsize
l, r = (i<<1), (i<<1)+1
#print('i: {}, l: {}, r: {}, heapsize: {} A: {}'.format(i, l, r,  heapsize, A))
if (l < heapsize) and (A[l]>A[i]):
largest = l
else:
largest = i
if (r < heapsize) and (A[r] > A[largest]):
largest = r
if largest != i:
exchange(A, i, largest)
if heapsize == len(A):
heapsize = len(A)
max_heapify(A, largest)

def build_max_heap(A):
#O(n) algorithm
for i in range(floor(len(A)/2), -1, -1):
max_heapify(A, i)

def heapsort(A):
# O(n lg(n)) algorithm
global heapsize
build_max_heap(A)
for i in range(len(A)-1, 0, -1):
exchange(A, 0, i)
heapsize -= 1
max_heapify(A, 0)

A = [random.randint(0, 20) for i in range(10)]
print('A before: ', A)

heapsize = len(A)
heapsort(A)
print('A after: ', A)

A before:  [20, 9, 1, 9, 12, 10, 3, 0, 1, 13]
A after:  [0, 1, 1, 3, 9, 9, 10, 12, 13, 20]


### Merge Sort¶

In [20]:
'MergeSort'
import math
def merge(A, p, q, r):
L, R = A[p:q+1], A[q+1:r+1]
i, j = 0, 0
k = p
while i < len(L) and j < len(R):
if L[i] < R[j]:
A[k]=L[i]
i+=1
else:
A[k]=R[j]
j+=1
k += 1
if j==len(R):
A[k:r+1]=L[i:]

def mergesort(A, p, r):
if p<r:
q = math.floor((p+r)/2)
mergesort(A, p, q)
mergesort(A, q+1, r)
merge(A, p, q, r)

import random
A = [random.randint(-102, 100) for i in range(10)]
print('B4 ', A)
mergesort(A, 0, len(A))
print('after: ', A)

B4  [-31, 25, -16, -11, -74, 52, -50, 34, -13, 22]
after:  [-74, -50, -31, -16, -13, -11, 22, 25, 34, 52]


### Counting Sort¶

In [21]:
''' Counting sort: See pg 195, CLRS.
Note this only works for nonegative array elements
Sorts in O(k+n) time
'''
# import numpy as
def count_sort(A, B, k):
C = [0 for i in range(k+1)]
for j in range(1, len(A)):
C[A[j]] += 1
# C[i] now contains num of elements equal to i
for i in range(1, k+1):
C[i]+=C[i-1]
# C[i] now contains number of elements less than or equal to i
for j in range(len(A)-1, -1, -1):
B[C[A[j]]] = A[j]
C[A[j]] -= 1
A = [2, 5, 3, 0, 2, 3, 0, 3]
B = [0 for i in range(len(A))]
k = max(A)
count_sort(A, B, k)
print(B)

[0, 0, 2, 2, 3, 3, 3, 5]


In [22]:
'See 8.3 in CLRS'

'''
assume each element in the n-element array A has d digits,
where digit 1 is the lowest-order digit and digit d is the
highest-order digit.

Radix-sort sorts n d-digit numbers in which each digit can
take on up to k possible values in O(d(n+k)) time if stable
sort takes O(n+k) time
'''
B = [0 for i in range(len(A))]
for i in range(d):
# use a stable sort such as count-sort to sort A on digit i
count_sort(A, B, max(A))
return B
print(B)

[0, 0, 2, 2, 3, 3, 3, 5]


### Bucket Sort¶

See my implementation from CLRS 8.4/pg 201 Bucket sort assumes that the input is drawn from a uniform distribution and has an average-case running time of O(n)

Bucket sort runs in O(n) time in the average case. All lines except the inserttion sort line take O(n)time in the worst case. The time taken by the calls to insertion sort is O(n as well.

In [23]:
from math import floor
# fix this later on
def bucket_sort(A):
B = [0 for i in range(len(A)-1)]
n = len(A)
for i in range(n-1):
B[i] = []
for i in range(1, n):
B[floor(A[i])] = A[i]
for i in range(0, n-1):
insertSort(B[i])
ret = []
for i in range(n-1):
ret+=B[i]
return B

# print(bucket_sort(A))



# FB Questions¶

### Taxable Income¶

For a 2D array whose rows are made up of tuples, and the tuples contain the tax amount and a tax bracket.

If you are given an income, find out what the tax should be

TaxBracket: [ [10000, 0.1], [20000, 0.2], [30000, 0.3], [None, 0.4] ]

TaxBracket 2: [ [None, 0.4] ]

If someone has an income of 50k, their tax would be 100+ def getTax(income, bracket): # I gave an O(n) algorithm

In [36]:
def getTax(income, bracket):
i = 0
while i < len(bracket):
if bracket[i][0]:
tax += bracket[i][0]*bracket[i][1]
else:
tax += income*bracket[i][1]
i += 1
return tax



### Spiral Array Elements¶

• spiral an array elements: greedily traverse in each direction until you must stop, then turn around and head in the other direction
In [33]:
import numpy as np

def hit_edge(out, r, c):
return ((r<0) or (c<0) or (r>=len(out)) or (c>=len(out)) or (out[r][c]!=0))

def spiral(n):
out = [[0]*n for i in range(n)] #np.zeros((n,n), dtype=np.int8)
r, c = 0, 0
direc, val = 0, 1
dr = [0,1,0,-1]
dc = [1,0,-1,0]

while val < n**2+1:
out[r][c] = val
r += dr[direc]
c += dc[direc]

if hit_edge(out, r, c):
r -= dr[direc]
c -= dc[direc]
direc = (direc+1)%4
r += dr[direc]
c += dc[direc]

val += 1
return out

print(spiral(5))
print()
print(spiral(8))

[[1, 2, 3, 4, 5], [16, 17, 18, 19, 6], [15, 24, 25, 20, 7], [14, 23, 22, 21, 8], [13, 12, 11, 10, 9]]

[[1, 2, 3, 4, 5, 6, 7, 8], [28, 29, 30, 31, 32, 33, 34, 9], [27, 48, 49, 50, 51, 52, 35, 10], [26, 47, 60, 61, 62, 53, 36, 11], [25, 46, 59, 64, 63, 54, 37, 12], [24, 45, 58, 57, 56, 55, 38, 13], [23, 44, 43, 42, 41, 40, 39, 14], [22, 21, 20, 19, 18, 17, 16, 15]]


### Paths in a Binary Tree¶

Given a binary tree, find the total number of paths in the tree that add up to a target

• I came up witha recursive inorder walk algorithm
6 / \ 4 4 / \ 2 -4 You may assume the tree is balanced; the nodes of the tree have a similarity to Node (){ val = val left = left right = right }
In [ ]:
def num_paths(root, target):
if not root: # in case node is empty
return

paths = 0
target_check = root.val
target_check+=(num_paths(root.left.val, target))
target_check+=(num_paths(root.right.val, target))

if target_check==target:
paths+= 1
target_check = 0

return paths


### Designer PDF Viewer¶

When you select a contiguous block of text in a PDF viewer, the selection is highlighted with a blue rectangle. In this PDF viewer, each word is highlighted independently. For example:

PDF-highighting.png

In this challenge, you will be given a list of letter heights in the alphabet and a string. Using the letter heights given, determine the area of the rectangle highlight in assuming all letters are wide.

For example, the highlighted . Assume the heights of the letters are and . The tallest letter is high and there are letters. The hightlighted area will be so the answer is .

Function Description

Complete the designerPdfViewer function in the editor below. It should return an integer representing the size of the highlighted area.

designerPdfViewer has the following parameter(s):

h: an array of integers representing the heights of each letter word: a string Input Format

The first line contains space-separated integers describing the respective heights of each consecutive lowercase English letter, ascii[a-z]. The second line contains a single word, consisting of lowercase English alphabetic letters.

In [2]:
def designerPdfViewer(h, word):
# caluclate number equivalents of all lowercase letters
lowerletters = [chr(i+97) for i in range(26)]
# make list that corresponds each letter in word to index in lowerletters
wordnums = [lowerletters.index(x) for x in word]
# find the height of the word nums
heights = [h[letternum] for letternum in wordnums]
area = max(heights)*len(word)
return area
# test 1
h, word = [1, 3, 1, 3, 1, 4, 1, 3, 2 ,5, 5, 5 ,5, 5, 5 ,5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5], 'abc'
print(designerPdfViewer(h, word))

9


### Look And Say with Groupby¶

In [3]:
from itertools import groupby
def lookandsay(number):
return ''.join( str(len(list(g))) + k
for k,g in groupby(number) )

numberstring='1'
for i in range(10):
print( numberstring)
numberstring = lookandsay(numberstring)

1
11
21
1211
111221
312211
13112221
1113213211
31131211131221
13211311123113112211


### Look And Say with Non-List Comprehension¶

In [4]:
'Another method'
def lookandsay(number):
result = ""

recurring = number[0]
number = number[1:]+" "
count = 1

for num in number:
if num != recurring:
result += str(count)+recurring
count = 1
recurring = num
else:
count += 1

return result

num="1"
for i in range(15):
print(num)
num = lookandsay(num)

1
11
21
1211
111221
312211
13112221
1113213211
31131211131221
13211311123113112211
11131221133112132113212221
3113112221232112111312211312113211
1321132132111213122112311311222113111221131221
11131221131211131231121113112221121321132132211331222113112211
311311222113111231131112132112311321322112111312211312111322212311322113212221


### One Edit Apart¶

• Write a function that returns whether two words are exactly "one edit" away An edit is:

• Inserting one character anywhere in the word (including at the beginning and end)
• Removing one character
• Replacing one character
• Solution

One optimal solution is to walk each string in unison, tracking if a difference has been encountered. If a second difference is encountered, return false. If one string is longer than the other, then the difference must mean it is an insertion, so skip a character in the longer string and continue. Additionally, there are symmetry and short circuit opportunities.

In [5]:
'''
e.g. OneEditApart("cat", "dog") = false
OneEditApart("cat", "cats") = true
OneEditApart("cat", "cut") = true
OneEditApart("cat", "cast") = true
OneEditApart("cat", "at") = true
OneEditApart("cat", "act") = false
'''
def OneEditApart(s1, s2):
diff = abs(len(s1)-len(s2))
if len(s1) > len(s2):
temp = s1
s1 = s2
s2 = temp
if diff>1:  # more than one xter
return False
saw_diff = False
i, j = 0, 0
while i < len(s1):
if s1[i]!=s2[j]:
if saw_diff:
return False
saw_diff = True
if len(s2) > len(s1):
i -= 1
i += 1
j += 1
return saw_diff or (len(s1) != len(s2))
for x in (zip(("cat", "dog")), zip(("cat", "cats")),
zip(("cat", "cut")), zip(("cat", "cast")),
zip(("cat", "at")),  zip(("cat", "act")),
zip(("wondeer", "wonder"))):
s1, s2 = x
print(s1[0], s2[0], OneEditApart(s1[0], s2[0]))

cat dog False
cat cats True
cat cut True
cat cast True
cat at True
cat act False
wondeer wonder True


### Arrays Left Rotation¶

A left rotation operation on an array shifts each of the array's elements unit to the left. For example, if left rotations are performed on array , then the array would become .

Given an array of integers and a number, perform left rotations on the array. Return the updated array to be printed as a single line of space-separated integers.

Function Description

Complete the function rotLeft in the editor below. It should return the resulting array of integers.

rotLeft has the following parameter(s):

An array of integers . An integer , the number of rotations. Input Format

The first line contains two space-separated integers and , the size of and the number of left rotations you must perform. The second line contains space-separated integers .

Constraints

Output Format

Print a single line of space-separated integers denoting the final state of the array after performing left rotations.

Sample Input

In [6]:
def rotLeft(a, d):
iter = 1
shiftee = a[0]
while iter <= d:
a = a[1:]+[shiftee]
shiftee = a[0]
iter += 1
return a


### Node at a position¶

See https://www.hackerrank.com/challenges/insert-a-node-at-a-specific-position-in-a-linked-list/problem You’re given the pointer to the head node of a linked list, an integer to add to the list and the position at which the integer must be inserted. Create a new node with the given integer, insert this node at the desired position and return the head node.

A position of 0 indicates head, a position of 1 indicates one node away from the head and so on. The head pointer given may be null meaning that the initial list is empty.

### Max Population¶

Q5: Given list of people with birth years and death years (so population changes over time), find highest population.

#### Solution¶

Get last death year. Create histogram from 0 → last death year (this will end up giving us population at each year). Walks through all people For each person, increment histogram for each year they were alive. Walk through histogram to get highest population.

In [7]:
def find_highest_pop(People):
last_death = 0
for person in People: # get last death year
last_death = max(person.death, last_death),

counter = {} #[0 for i in range(last_death)] #Create histogram from 0 → last death year
for person in People:
for year in range(person.birth, person.death):
if year in counter:
counter[year]+=1
else:
counter[year] = 1

# find pop peak
highest_pop = 0
for year in range(len(counter)):
highest_pop = max(highest_pop, counter[year])

return highest_pop


### Fibonacci Numbers¶

In [49]:
def fib(n):
'N tree levels; 2 kids/node; Num Nodes: 1*2*2*2...==> TC: O(2^N), SC: O(N)'
if n==0 or n==1:
return n
else:
return fib(n-1)+fib(n-2)
#test
[fib(i) for i in range(10)]

Out[49]:
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

### Fibonacci Numbers Memoization¶

In [51]:
def fib(n, memo):
'N tree levels; 2 kids/node; # Nodes:  1 + 2 + 2 + … + 2 ==> TC: O(N), SC: O(N)'
if n<0:
return 0
elif n<=1:
return 1
else:
memo = fib(n-1, memo)+fib(n-2, memo)
return memo

#test
memo = None
[fib(i, memo) for i in range(10)]

Out[51]:
[1, 1, 2, 3, 5, 8, 13, 21, 34, 55]

### Unique Paths in a Grid¶

Given a grid of size m * n, let's assume you are starting at (1,1) and your goal is to reach (m,n). At any instance, if you are on (x,y), you can either go to (x, y + 1) or (x + 1, y).

Now consider if some obstacles are added to the grids. How many unique paths would there be? An obstacle and empty space is marked as 1 and 0 respectively in the grid.

In [10]:
def find_unique_path(grid, start_idx):
# create a 2D matrix of same size as grid to hold the results
results = [[0]*len(grid) for i in grid]

# go through the array rowwise and fill it up
if grid[start_idx[0]][start_idx[0]] == 0:
results[0][0] = 1

# if obstacle found, set to 0
for i in range(1, len(grid)):
results[i][0] = results[i-1][0] if grid[i][0]==0 else results[i][0] # no obstacle
for j in range(1, len(grid)):
results[0][j] = results[0][j-1] if grid[0][j]==0 else results[0][j]

# set sum of right and upper values at a position
for i in range(1, len(grid)):
for j in range(1, len(grid[0])):
results[i][j] = results[i-1][j]+ results[i][j-1] if grid[i][j]==0 else results[i][j]
# return last index in new mat
return results[-1][-1]

# test
A = [[0,0,0], [0, 1, 0], [0, 0, 0]]
print(find_unique_path(A, (0,0)))


2


### Maximum Subarray Problem¶

Find the longest increasing subsequence of a given array of integers, A.

In other words, find a subsequence of array in which the subsequence’s elements are in strictly increasing order, and in which the subsequence is as long as possible. This subsequence is not necessarily contiguous, or unique. In this case, we only care about the length of the longest increasing subsequence.

1 <= length(A) <= 2500 1 <= A[i] <= 2000

# Leet Code¶

### Trapping Rain Water¶

In [11]:
'''Trapping rain water'''
def findWater(arr):
n = len(arr)
'''
left[i] contains height of tallest bar to the left of i'th bar including itself
right[i] contains height of tallest bar to the right of ith bar including itself
'''
left, right =  [0 for i in range(n)], [0 for i in range(n)]

left[0] = arr[0]
for i in range(1, n): left[i] = max(left[i-1], arr[i])

right[n-1] = arr[n-1]
for i in range(n-2, -1, -1): right[i] = max(right[i+1], arr[i])

water = 0
for i in range(n):
water += min(left[i],right[i]) - arr[i]

return water
array = [0,1,0,2,1,0,1,3,2,1,2,1]
print(findWater(array))

6


### Regex Pattern¶

Given an input string (s) and a pattern (p), implement regular expression matching with support for '.' and '*'.

• '.' Matches any single character.
• '*' Matches zero or more of the preceding element.
• The matching should cover the entire input string (not partial).

#### Solution explanation¶

• Intuition: If there were no Kleene stars (the * wildcard character for regular expressions), the problem would be easier - we simply check from left to right if each character of the text matches the pattern.

When a star is present, we may need to check many different suffixes of the text and see if they match the rest of the pattern. A recursive solution is a straightforward way to represent this relationship.

Without a Kleene star, our solution would look like the match function below

• With a Kleene star, it will be in the second position pattern[1].

  Then, we may ignore this part of the pattern, or
delete a matching character in the text.
If we have a match on the remaining strings after any of these operations,
then the initial inputs matched.
In [12]:
def match(text, pattern):
if not pattern: return not text
first_match = bool(text) and pattern[0] in {text[0], '.'}
return first_match and match(text[1:], pattern[1:])

class Solution(object):
@classmethod
def isMatch(self, text, pattern):
if not pattern:
return not text

first_match = bool(text) and pattern[0] in {text[0], '.'}

if len(pattern) >= 2 and pattern[1] == '*':
return (self.isMatch(text, pattern[2:]) or
first_match and self.isMatch(text[1:], pattern))
else:
return first_match and self.isMatch(text[1:], pattern[1:])

print([res for res in [Solution().isMatch("aa", "a"),  Solution().isMatch("aa", "a*"),
Solution().isMatch("ab", ".*"), Solution().isMatch("aab", "c*a*b"),
Solution().isMatch("mississippi", "mis*is*p*.")]])

[False, True, True, True, False]


### Multiply two square matrices¶

In [13]:
import numpy as np

def square_mat_mult(A, B):
n = A.shape[0]
C = np.zeros((n,n))
for i in range(n):
for j in range(n):
for k in range(n):
C[i][j]+= A[i][k]*B[k][j]
return C

A = np.arange(25).reshape(5,5)
B = np.arange(25, 0, -1).reshape(5,5)
print(square_mat_mult(A, B))

# For non-square matrices, do:
# 3x3 matrix
X = [[12,7,3],
[4 ,5,6],
[7 ,8,9]]
# 3x4 matrix
Y = [[5,8,1,2],
[6,7,3,0],
[4,5,9,1]]
# result is 3x4
result = [[0]*4 for i in range(3)]
# iterate through rows of X
for i in range(len(X)):
# iterate through columns of Y
for j in range(len(Y[0])):
# iterate through rows of Y
for k in range(len(Y)):
result[i][j] += X[i][k] * Y[k][j]
print()
print(result)

[[ 100.   90.   80.   70.   60.]
[ 475.  440.  405.  370.  335.]
[ 850.  790.  730.  670.  610.]
[1225. 1140. 1055.  970.  885.]
[1600. 1490. 1380. 1270. 1160.]]

[[114, 160, 60, 27], [74, 97, 73, 14], [119, 157, 112, 23]]


### Strassen's algorithm¶

def square_matrix_multiply_recursive(A, B): # see page 76 of CLRS n = A.shape[0] C = np.zeros((n, n)) if n == 1: C[0][0] = A[0][0]*B[0][0] else: # partition the three matrices pass # to be finished

### Indices of array to a target¶

In [14]:
"""Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice."""

class Solution:
'Time Complexity: O(n^2), Space Complexity: O(1)'
@classmethod
def twoSum(self, nums, target):

ret_idx, cur_idx, sol_reached = [], 0, False
for cur in range(len(nums)):
for cur_nxt in range(len(nums)):
if cur == cur_nxt:
continue
if nums[cur] + nums[cur_nxt] == target:
ret_idx.append((cur, cur_nxt))
sol_reached = True
break
if sol_reached:
break

return list(ret_idx[0])

# sol = Solution()
nums, target = [2, 7, 11, 15], 13
idx = Solution.twoSum(nums, target)
print(idx)

[0, 2]


### Greedily remove string¶

In [15]:
'Given a string, reduce the string by removing 3 or more consecutive identical characters. You should greedily remove characters from left to right.'
def drop(arr):
i = 0
while i <= len(arr)-4:

# Removes all repeated chars greater than 3
while arr[i] == arr[i+1] == arr[i+2] == arr[i + 3]:
arr = arr[:i+3] + arr[i+4:]

# Removes repeated chars of 3
if arr[i] == arr[i+1] == arr[i+2]:
arr = arr[:i] + arr[i+3:]

# Checks for repeat chars behind the pointer (i)
if i >= 2 and arr[i] == arr[i-1] == arr[i-2]:
i -= 2

# Steps forward through string
else:
i += 1
return arr

print([drop(x) for x in ("aaabbbc", "aabbbacd", "aabbccddeeedcba", "aaabbbacd", "aaabbbacd")])

['c', 'cd', 'aaa', 'acd', 'acd']


### Factorial¶

In [16]:
'find factorial with recursive array'
def fact(n):
if n == 1:
return 1
return n * fact(n-1)
print(fact(6), fact(5))

720 120


### Array Duplicates¶

Given an array and a positive number k, check whether the array contains any duplicate elements within range k. If k is more than the size of the array, the solution should check for duplicates in the complete array

In [17]:
'''Hash it in O(n) space-time. Traverse the array and store each element along with its index in a dict.
If an element is already found in the map, check if it is repeated within range of k using previous occurences from the map
'''

def hasDuplicates(vector, k):
dictmap = {}
for i in range(len(vector)):
if vector[i] in dictmap.keys():
if (i - dictmap[vector[i]]) <= k:
return True

# store elemenst along their indices
dictmap[vector[i]] = i

return False
# test
A = [5,6,8,2,4,6,9]
print(hasDuplicates(A, 4))

# test2
print(hasDuplicates(A, 2))

# test3
A = [1, 2, 3, 2, 1]
print(hasDuplicates(A, 7))

True
False
True


### Median of two sorted arrays¶

In [24]:
"""
There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

You may assume nums1 and nums2 cannot be both empty.
"""
class MyneSol(object):
def __init__(self):
pass

def findMedianSortedArrays(self, nums1, nums2):

sortedArray = self.mergeSortedArrays(nums1, nums2)  # mergeSort the arrays
midpoint = len(sortedArray)//2
if len(sortedArray)%2==0: # even lenth
median = (sortedArray[midpoint-1]+sortedArray[midpoint])/2
else:
median = sortedArray[midpoint]

return median

def mergeSortedArrays(self, nums1, nums2):
return sorted(nums1 + nums2)