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 ' '

Singly Linked List

In [6]:
'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

Doubly Linked List

In [7]:
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())
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)
        
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

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
    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())
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.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
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]

Radix-Sort

In [22]:
'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)
[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))
    

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

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.

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

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

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.

Problem Link

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)