# 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 ' '
'Singly Linked List'
class SingleLinkedList(object):
def __init__(self, head=None):
self.head = head
def addNode(self, node):
node.next = self.head
if self.head:
self.head.prev = node
self.head = node
#node.prev = None
def walk(self):
cur = self.head
toprint = ' '
while cur:
toprint+=str(cur.val)
cur = cur.next
return int(toprint)
def reverse(self):
prev = None
current = self.head
while (current):
nxt = current.next
current.next = prev
prev = current
current = nxt
self.head = prev
return self
def getSize(self):
count = 0
cur = self.head
while cur is not None:
count += 1
cur = cur.next
return count
class DoubleLinkedList(object):
def __init__(self, node=None):
self.head = node # start with an empty list
def size(self):
count = 0
cur = self.head
while cur:
count += 1
cur = cur.next
return count
def insert(self, node):
'O(1) worst case time'
node.next = self.head
if self.head:
self.head.prev = node
self.head = node
node.prev = None
def search(self, val):
'O(n) worst case time'
node = self.head
while (node and (node.val is not val)):
node = node.next
return node
def reverse(self):
prev = None
cur = self.head
while cur:
nxt = cur.next
cur.next = prev
prev = cur
cur = nxt
self.head = prev
return self
def deleter(self, node):
'O(1) worst case time'
if node.prev:
node.prev.next = node.next
else:
self.head.next = node.next
if node.next:
node.next.prev = node.prev
def walk(self):
'O(n) worst case time'
cur = self.head
while cur:
print('{}'.format(cur))
cur = cur.next
ll = DoubleLinkedList()
for i in range(6, 0, -1):
ll.insert(Node(i))
print(ll.walk())
class Sentinel(object):
def __init__(self):
self.prev = self
self.next = self
def is_valid(self):
return isinstance(self.next.key, int)
class DoubleLinkedListSentinel(object):
def __init__(self, head=Sentinel()):
self.head = head # start with an empty list
self.position = 0
def size(self):
count = 0
cur = self.head
while cur:
count += 1
cur = cur.next
return count
def insert(self, node):
'O(1) worst case time'
node.next = self.head.next
self.head.next.prev = node
self.head.next = node
node.prev = self.head
self.position += 1
def search(self, val):
'O(n) worst case time'
node = self.head.next
while ((node is not self.head) and (node.val is not val)):
node = node.next
return node
def advance_to_pos(self, pos):
cur = self.head
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:
self.head.next = node.next
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'
node_m = self.advance_to_pos(m)
node_n = self.advance_to_pos(n)
# advance pointer to node m
cur = self.head
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'
cur = self.head.next
while cur and not isinstance(cur, Sentinel):
print(' cur_node: {}'.
format(cur))
cur = cur.next
Example:
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4) Output: 7 -> 0 -> 8 Explanation: 342 + 465 = 807.
import copy
class Solution:
@classmethod
def addTwoNumbers(self, l1=None, l2=None):
l1sz, l2sz = l1.getSize(), l2.getSize()
assert l1sz==l2sz, "size not equal"
returnList = SingleLinkedList()
cur_1, cur_2 = l1.head, l2.head
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:
returnList.addNode(Node(cur_val))
del carry[::]
else:
tostore = int(str(cur_val)[-1])
returnList.addNode(Node(tostore))
carry.append(int(str(cur_val)[-2]))
cur_1, cur_2 = cur_1.next, cur_2.next
#rl = returnList.reverse()
return returnList
# Tests
l1 = SingleLinkedList()
for num in [1,9,9]: l1.addNode(Node(num))
l2 = SingleLinkedList()
for num in [1,9,9]: l2.addNode(Node(num))
sol = Solution()
res = sol.addTwoNumbers(l1, l2)
print('l1: ', l1.walk(), 'l2: ', l2.walk(),
' res: ', res.walk(), ' res reversed: ', res.reverse().walk())
print()
# Test2
l1 = SingleLinkedList()
for num in [2,4,3]: l1.addNode(Node(num))
#
l2 = SingleLinkedList()
for num in [5,6,4]: l2.addNode(Node(num))
sol = Solution()
res = sol.addTwoNumbers(l1, l2)
print('l1: ', l1.walk(), 'l2: ', l2.walk(),
' res: ', res.walk(), ' res reversed: ', res.reverse().walk())
Stack: LIFO Policies
Queues: FIFO Policies
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)
class Queue(object):
def __init__(self):
self.tail = 0
self.head = 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):
x = self.Q[self.head]
self.Q = self.Q[self.head+1:]
if self.head == len(self.Q):
self.head = 1
else:
self.head += 1
return x
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)
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
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
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
Bundles many types similar to a named tuple
class Bundle(object):
def __init__(self, variables):
for var, val in variables.items():
object.__setattr__(self, var, val)
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))
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)
binary_tree.inorderwalk(nodes[0])
binary_tree.unrollsearch(nodes[0], 45)
binary_tree.maximum(nodes[0])
binary_tree.minimum(nodes[0])
binary_tree.delete(nodes[-1])
binary_tree.inorderwalk(nodes[0])
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 ])
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)
'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)
''' 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)
'See 8.3 in CLRS'
def radix_sort(A, d):
'''
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
B = radix_sort(A, 8)
print(B)
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.
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))
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
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
Given a binary tree, find the total number of paths in the tree that add up to a target
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
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))
See: https://www.hackerrank.com/challenges/designer-pdf-viewer/problem
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.
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))
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)
'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)
Write a function that returns whether two words are exactly "one edit" away An edit is:
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.
'''
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]))
See https://www.hackerrank.com/challenges/ctci-array-left-rotation/problem
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
def rotLeft(a, d):
iter = 1
shiftee = a[0]
while iter <= d:
a = a[1:]+[shiftee]
shiftee = a[0]
iter += 1
return a
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.
Q5: Given list of people with birth years and death years (so population changes over time), find highest population.
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.
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
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)]
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)]
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.
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)))
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
'''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))
Given an input string (s) and a pattern (p), implement regular expression matching with support for '.' and '*'.
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.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*.")]])
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)
"""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)
'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")])
'find factorial with recursive array'
def fact(n):
if n == 1:
return 1
return n * fact(n-1)
print(fact(6), fact(5))
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
'''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))
"""
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)