Permalink
Switch branches/tags
Nothing to show
Find file
Fetching contributors…
Cannot retrieve contributors at this time
1480 lines (1306 sloc) 42.5 KB
# coding: utf-8
from collections import defaultdict, Counter
from pprint import pprint
# TODO: hanoi, 5.2, 5.7, 7.x, 19.9
# known bugs: 19.6 doesnt do "and"
def oneone(s):
'Implement an algorithm to determine if a string has all unique characters.'
chars = set()
for c in s:
if c in chars:
return False
chars.add(c)
return True
def oneone2(s):
'What if you can not use additional data structures?'
if not s:
return True
le = len(s)
for i in range(le-1):
for j in range(i+1, le):
if i != j and s[i] == s[j]:
return False
return True
def onetwo(s):
'''Write code to reverse a C-Style String.
(C-String means that “abcd” is represented as five characters, including the null character.)'''
# lets pretend Python has mutable strings
s = list(s)
max_idx = len(s) - 1
for i in range(len(s)/2):
t = s[i]
s[i] = s[max_idx - i]
s[max_idx - i] = t
return ''.join(s)
def onethree(s):
'''
Design an algorithm and write code to remove the duplicate characters in a string
without using any additional buffer. NOTE: One or two additional variables are fine.
An extra copy of the array is not.
'''
# note this doesnt do unicode or any other fanciness
s = list(s)
# pretend bit vector
bitvector = [False] * 128
cur_idx = 0
for c in s:
pos = ord(c)
if not bitvector[pos]:
bitvector[pos] = True
s[cur_idx] = c
cur_idx += 1
return ''.join(s[:cur_idx])
def onefour(s, t):
'Write a method to decide if two strings are anagrams or not.'
# We could of course do
# sorted(s) == sorted(t)
# Counter(s) == Counter(t)
# this is more in the spirit of the book
d = {}
for c in s:
if not c in d:
d[c] = 0
d[c] += 1
for c in t:
if not c in d or not d[c]:
return False
d[c] -= 1
return not any(d.values())
def onefive(s):
'Write a method to replace all spaces in a string with ‘%20’.'
# this is stupid
return s.replace(' ', '%20')
def onesix(matrix):
'''
Given an image represented by an NxN matrix, where each pixel in the image is 4
bytes, write a method to rotate the image by 90 degrees. Can you do this in place?
'''
# go in layers and do a 4-way swap on pixels
if not matrix:
return matrix
n = len(matrix[0])
for layer in range(n/2):
first = layer
last = n - 1 - layer
for i in range(first, last):
offset = i - layer
# top = matrix[layer][i]
# left = matrix[last-offset][layer]
# right = matrix[i][last]
# bottom = matrix[last][last-offset]
# temp = top
temp = matrix[layer][i]
# top = left
matrix[layer][i] = matrix[last-offset][layer]
# left = bottom
matrix[last-offset][layer] = matrix[last][last-offset]
# bottom = right
matrix[last][last-offset] = matrix[i][last]
# right = temp
matrix[i][last] = temp
return matrix
def oneseven(matrix):
'''Write an algorithm such that if an element in an MxN matrix is 0, its entire row and
column is set to 0.'''
if not matrix:
return matrix
N = len(matrix)
M = len(matrix[0])
null_hori = set()
null_vert = set()
for i in range(N):
for j in range(M):
if matrix[i][j] == 0:
null_hori.add(i)
null_vert.add(j)
for i in range(N):
for j in range(M):
if i in null_hori or j in null_vert:
matrix[i][j] = 0
return matrix
def oneeight(s1, s2):
'''
Assume you have a method isSubstring which checks if one word is a substring of
another. Given two strings, s1 and s2, write code to check if s2 is a rotation of s1 using
only one call to isSubstring (i.e., “waterbottle” is a rotation of “erbottlewat”).
'''
return s1 in s2+s2
def twoone(node):
'''
Write code to remove duplicates from an unsorted linked list.
'''
seen = set()
prev = None
while node is not None:
if node.value in seen:
prev.next = node.next
else:
seen.add(node.value)
prev = node
node = node.next
def twoone2(node):
'''FOLLOW UP
How would you solve this problem if a temporary buffer is not allowed?'''
while node is not None:
val = node.value
run_prev = node
run_ahead = node.next
while run_ahead is not None:
if run_ahead.value == val:
run_prev.next = run_ahead.next
run_prev = run_ahead
run_ahead = run_ahead.next
node = node.next
def twotwo(node, n):
'''Implement an algorithm to find the nth to last element of a singly linked list.'''
run_ahead = node
for _ in range(n):
if run_ahead is None:
raise ValueError('Linked list is shorter than n')
run_ahead = run_ahead.next
while run_ahead is not None:
node = node.next
run_ahead = run_ahead.next
return node
def twothree(node):
'''
Implement an algorithm to delete a node in the middle of a single linked list, given
only access to that node.
EXAMPLE
Input: the node ‘c’ from the linked list a->b->c->d->e
Result: nothing is returned, but the new linked list looks like a->b->d->e
'''
if node.next is None:
raise ValueError('need at least one element following to delete this node')
prev = node
node = node.next
while node is not None:
prev.value = node.value
prev = node
node = node.next
prev.next = None
class Node(object):
def __init__(self, value=None, next=None):
self.value = value
self.next = next
def __repr__(self):
return 'Node(%s, %s)' % (self.value if self.value is not None else '', self.next)
def twofour(node1, node2):
'''
You have two numbers represented by a linked list, where each node contains a sin-
gle digit. The digits are stored in reverse order, such that the 1’s digit is at the head of
the list. Write a function that adds the two numbers and returns the sum as a linked
list.
EXAMPLE
Input: (3 -> 1 -> 5) + (5 -> 9 -> 2)
Output: 8 -> 0 -> 8
'''
carry = 0
start = None
while True:
v1 = v2 = 0
if node1 is not None:
v1 = node1.value
if node2 is not None:
v2 = node2.value
new_value = v1+v2+carry
if not new_value:
break
carry, digit = divmod(new_value, 10)
new = Node(digit)
if start is None:
start = current_new = new
else:
current_new.next = new
current_new = new
if node1 is not None:
node1 = node1.next
if node2 is not None:
node2 = node2.next
current_new.next = None
return start
# n1 = Node(value=3, next=Node(value=1, next=Node(value=5)))
# n2 = Node(value=5, next=Node(value=9, next=Node(value=2)))
# print twofour(n1, n2)
def twofive(node):
'''Given a circular linked list, implement an algorithm which returns node at the begin-
ning of the loop.
DEFINITION
Circular linked list: A (corrupt) linked list in which a node’s next pointer points to an
earlier node, so as to make a loop in the linked list.
EXAMPLE
input: A -> B -> C -> D -> E -> C [the same C as earlier]
output: C
'''
seen = set()
while node is not None:
if node in seen:
return node
seen.add(node)
node = node.next
return False
def threeone():
'''Describe how you could use a single array to implement three stacks.'''
# Give each stack a third of the array.
# Alternative idea: If speed doesnt matter, grow one from the front,
# one from the end, one from the middle, alternating between left and right :)
def threetwo():
'''
How would you design a stack which, in addition to push and pop, also has a function
min which returns the minimum element? Push, pop and min should all operate in
O(1) time.
'''
# for every element keep track of the min of all the elements beneath it
class Stack(object):
def __init__(self, values=None):
self.stack = []
self.mins = []
if values is not None:
for v in values:
self.push(v)
def push(self, value):
try:
cur_min = self.min()
except IndexError:
cur_min = float('inf')
self.mins.append(min(cur_min, value))
return self.stack.append(value)
def pop(self):
self.mins.pop()
return self.stack.pop()
def peek(self):
return self.stack[-1]
def min(self):
return self.mins[-1]
def __repr__(self):
return repr(self.stack)
return Stack
def threethree():
'''
Imagine a (literal) stack of plates. If the stack gets too high, it might topple. There-
fore, in real life, we would likely start a new stack when the previous stack exceeds
some threshold. Implement a data structure SetOfStacks that mimics this. SetOf-
Stacks should be composed of several stacks, and should create a new stack once
the previous one exceeds capacity. SetOfStacks.push() and SetOfStacks.pop() should
behave identically to a single stack (that is, pop() should return the same values as it
would if there were just a single stack).
'''
class SetOfStacks(object):
def __init__(self, values=None, maxlen=10):
self.maxlen = maxlen
self.stacks = [[]]
if values is not None:
for v in values:
self.push(v)
def push(self, value):
if len(self.stacks[-1]) >= self.maxlen:
self.stacks.append([])
self.stacks[-1].append(value)
def pop(self):
if len(self.stacks) == 1 and not self.stacks[0]:
raise IndexError('pop from empty stack')
if not self.stacks[-1]:
self.stacks.pop()
return self.stacks[-1].pop()
def peek(self):
if not self.stacks[-1]:
return self.stacks[-2][-1]
return self.stacks[-1][-1]
def threethree2():
'''
FOLLOW UP
Implement a function popAt(int index) which performs a pop operation on a specific
sub-stack.
'''
class SetOfStacks(object):
def __init__(self, values=None, maxlen=10):
self.maxlen = maxlen
self.stacks = [[]]
if values is not None:
for v in values:
self.push(v)
def push(self, value):
for stack in self.stacks:
if len(stack) != self.maxlen:
stack.append(value)
return
self.stacks.append([value])
def pop(self):
if len(self.stacks) == 1 and not self.stacks[0]:
raise IndexError('pop from empty stack')
if not self.stacks[-1]:
self.stacks.pop()
return self.stacks[-1].pop()
def popAt(self, stack_num):
return self.stacks[stack_num].pop()
def peek(self):
if not self.stacks[-1]:
return self.stacks[-2][-1]
return self.stacks[-1][-1]
def threefour(A, B=None, C=None):
'''In the classic problem of the Towers of Hanoi, you have 3 rods and N disks of different
sizes which can slide onto any tower. The puzzle starts with disks sorted in ascending
order of size from top to bottom (e.g., each disk sits on top of an even larger one). You
have the following constraints:
(A) Only one disk can be moved at a time.
(B) A disk is slid off the top of one rod onto the next rod.
(C) A disk can only be placed on top of a larger disk.
Write a program to move the disks from the first rod to the last using Stacks.
'''
pass
def threefive():
class MyQueue(object):
def __init__(self, values=None):
self.stack = []
self.other = []
if values is not None:
for v in values:
self.put(v)
def put(self, value):
self.stack.append(value)
def get(self):
while self.stack:
self.other.append(self.stack.pop())
elem = self.other.pop()
while self.other:
self.stack.append(self.other.pop())
return elem
def __repr__(self):
return repr(self.stacks[self.state])
return MyQueue
def threesix(stack):
'''
Write a program to sort a stack in ascending order. You should not make any assump-
tions about how the stack is implemented. The following are the only functions that
should be used to write this program: push | pop | peek | isEmpty.
'''
Stack = threetwo()
other = Stack()
other.push(stack.pop())
while not stack.isEmpty():
elem = stack.pop()
moved = 0
while other.peek() > elem:
stack.push(other.pop())
moved += 1
other.push(elem)
for _ in range(moved):
other.push(stack.pop())
return other
# Stack = threetwo()
# class SS(Stack):
# def isEmpty(self):
# return not self.stack
# s = SS([5,3,2])
# print threesix(s)
def fourone(root):
'''
Implement a function to check if a tree is balanced. For the purposes of this question,
a balanced tree is defined to be a tree such that no two leaf nodes differ in distance
from the root by more than one.
'''
fourone.minh, fourone.maxh = float('-inf'), float('inf')
def walk(node, depth=0):
if node is None:
return
if not node.left and not node.right:
fourone.minh = max(depth, fourone.minh)
fourone.maxh = min(depth, fourone.maxh)
walk(node.left, depth+1)
walk(node.right, depth+1)
walk(root)
return abs(fourone.maxh - fourone.minh) <= 1
# from node import Node, tree
# print fourone(tree)
def fourtwo(n1, n2):
'''Given a directed graph, design an algorithm to find out whether there is a route be-
tween two nodes.
'''
seen = set()
stack = [n1]
while stack:
node = stack.pop()
if node in seen:
seen.add(node)
else:
continue
for c in node.children:
if c is n2:
return True
stack.append(c)
return False
def fourthree(arr):
'''
Given a sorted (increasing order) array, write an algorithm to create a binary tree with
minimal height.
'''
class Tree:pass
tree = Tree()
def insert(arr):
if not arr:
return
middle = len(arr)/2
tree.insert(arr[middle])
insert(arr[:middle])
insert(arr[middle+1:])
insert(arr)
return tree
def fourfour(tree):
'''
Given a binary search tree, design an algorithm which creates a linked list of all the
nodes at each depth (i.e., if you have a tree with depth D, you’ll have D linked lists).
'''
levels = defaultdict(list)
def walk(node, depth):
if node is None:
return
levels[depth].append(node)
walk(node.left, depth+1)
walk(node.right, depth+1)
walk(tree, 0)
return levels
def fourfive(node):
'''
Write an algorithm to find the ‘next’ node (i.e., in-order successor) of a given node in
a binary search tree where each node has a link to its parent.
'''
'''
5
/ \
4 10
/ / \
1 8 12
/ / \ / \
0 6 9 11 13
'''
if node.right:
walk = node.right
while walk.left:
walk = walk.left
return walk
if node.parent.left is node:
return node.parent
if node.parent.right is node:
node = node.parent
while True:
if node is None:
# we got the last node
return False
if node.parent.left is node:
return node.parent
node = node.parent
return False
def foursix(tree, n1, n2):
'''Design an algorithm and write code to find the first common ancestor of two nodes
in a binary tree. Avoid storing additional nodes in a data structure. NOTE: This is not
necessarily a binary search tree.
'''
def depth(root, node):
depth.found = -1
def walk(root, dep):
if root is None:
return
if depth.found != -1:
return
if root is node:
depth.found = dep
walk(root.left, dep+1)
walk(root.right, dep+1)
walk(root, 0)
return depth.found
d1 = depth(tree, n1)
d2 = depth(tree, n2)
lower, higher = n1, n2
if d1 < d2:
lower, higher = higher, lower
print d1, d2
for _ in range(abs(d2-d1)):
higher = higher.parent
while n1 is not None:
if n1 is n2:
return n1
n1 = n1.parent
n2 = n2.parent
return False
def fourseven(t1, t2):
'''
You have two very large binary trees: T1, with millions of nodes, and T2, with hun-
dreds of nodes. Create an algorithm to decide if T2 is a subtree of T1.
'''
def inorder_stringify(tree):
node_strings = []
def walk(node):
if node is None:
return
walk(node.left)
node_strings.append(str(node.value))
walk(node.right)
walk(tree)
return ','.join(node_strings)
s1 = inorder_stringify(t1)
s2 = inorder_stringify(t2)
return s2 in s1
def foureight(tree):
'''You are given a binary tree in which each node contains a value. Design an algorithm
to print all paths which sum up to that value. Note that it can be any path in the tree
- it does not have to start at the root.
'''
zero_paths = []
def walk(node, sofar=0):
if node is None:
return
p = node.parent
path = []
sofar_up = node.value
while p:
sofar_up -= p.value
path.append(p)
if sofar_up == 0:
zero_paths.append(path[::-1])
p = p.parent
walk(node.left, sofar+node.value)
walk(node.right, sofar+node.value)
return zero_paths
def fiveone(N, M, i, j):
'''
You are given two 32-bit numbers, N and M, and two bit positions, i and j. Write a
method to set all bits between i and j in N equal to M (e.g., M becomes a substring of
N located at i and starting at j).
EXAMPLE:
Input: N = 10000000000, M = 10101, i = 2, j = 6
Output: N = 10001010100
'''
# all 1s
ones = 2 ** 31 + 1
left = ones - (1 << (j - 1))
right = 1 << (i - 1)
mask = left | right
return (N & mask) | (M << i)
def fivetwo():
'''Given a (decimal - e.g. 3.72) number that is passed in as a string, print the binary rep-
resentation. If the number can not be represented accurately in binary, print “ERROR”
'''
def fivethree(i):
'''
Given an integer, print the next smallest and next largest number that have the same
number of 1 bits in their binary representation.
'''
s = bin(i)[2:]
all_ones = all(c == '1' for c in s)
if all_ones:
return False, '10' + s[1:]
big = s.rfind('01')
if big == -1:
bigger = s + '0'
else:
bigger = s[:big] + '10' + sorted(s[big+2:], reverse=True)
small = s.rfind('10')
if small == -1:
smaller = False
else:
smaller = s[:small] + '01' + sorted(s[small+2:])
return smaller.lstrip('0'), bigger
def fivefour():
'''Explain what the following code does: ((n & (n-1)) == 0).'''
# base 2
def fivefive(a, b):
'''
Write a function to determine the number of bits required to convert integer A to
integer B.
Input: 31, 14
Output: 2
'''
# Levenshtein is cooler
# from Levenshtein import distance
# return distance(bin(a)[2:], bin(b)[2:])
xor = a ^ b
return sum(bool(xor & (1 << i)) for i in range(32))
def fivesix(a):
'''
Write a program to swap odd and even bits in an integer with as few instructions as
possible (e.g., bit 0 and bit 1 are swapped, bit 2 and bit 3 are swapped, etc)
'''
to_the_left = (int('01' * 16, 2) & a) << 1
to_the_right = (int('10' * 16, 2) & a) >> 1
return to_the_left | to_the_right
def fiveseven():
'''
An array A[1...n] contains all the integers from 0 to n except for one number which is
missing. In this problem, we cannot access an entire integer in A with a single opera-
tion. The elements of A are represented in binary, and the only operation we can use
to access them is “fetch the jth bit of A[i]”, which takes constant time. Write code to
find the missing integer. Can you do it in O(n) time?
'''
# meh
def eightone(n):
'''Write a method to generate the nth Fibonacci number.'''
if not n:
return 0
a = b = 1
for _ in range(n-2):
c = a + b
a = b
b = c
return b
def eighttwo(N, offlimits=None):
'''
Imagine a robot sitting on the upper left hand corner of an NxN grid. The robot can
only move in two directions: right and down. How many possible paths are there for
the robot?
FOLLOW UP
Imagine certain squares are “off limits”, such that the robot can not step on them.
Design an algorithm to get all possible paths for the robot.
'''
paths = []
def walk(x, y, path=None):
if x >= N or y >= N:
return
if (x,y) in offlimits:
return
if path is None:
path = []
path = path[:]
path.append((x,y))
if x == N - 1 and y == N -1:
paths.append(path)
walk(x+1, y, path)
walk(x, y+1, path)
if offlimits is None:
offlimits = []
offlimits = set(offlimits)
walk(0, 0)
return paths
def eightthree(s):
'''
Write a method that returns all subsets of a set.
'''
if len(s) <= 1:
return [s]
subs = []
for i in range(len(s)):
li = s[:]
li.pop(i)
subs.append(li)
subs.extend(eightthree(li))
return set(map(tuple, subs))
def eightfour(s):
'''Write a method to compute all permutations of a string.'''
if len(s) <= 1:
return [s]
if len(s) == 2:
return [s, s[::-1]]
permuts = eightfour(s[:-1])
result = []
for p in permuts:
for i in range(len(p)+1):
result.append(p[:i] + s[-1] + p[i:])
return result
def eightfive(N):
'''
Implement an algorithm to print all valid (e.g., properly opened and closed) combi-
nations of n-pairs of parentheses.
EXAMPLE:
input: 3 (e.g., 3 pairs of parentheses)
output: ()()(), ()(()), (())(), ((()))
'''
def walk(s, l, r):
if l > 0:
walk(s + '(', l-1, r)
if r > l:
walk(s + ')', l, r-1)
if not l and not r:
print s
walk('', N, N)
def eightsix(screen, point, color):
'''
Implement the “paint fill” function that one might see on many image editing pro-
grams. That is, given a screen (represented by a 2 dimensional array of Colors), a
point, and a new color, fill in the surrounding area until you hit a border of that col-
or.’
'''
max_x = len(screen[0])
max_y = len(screen)
seen = set()
x, y = point
orig_color = screen[y][x]
def walk(x,y):
if x < 0 or y < 0 or x >= max_x or y >= max_y:
return
if (x,y) in seen:
return
else:
seen.add((x,y))
if screen[y][x] != orig_color:
return
screen[y][x] = color
walk(x+1,y)
walk(x,y+1)
walk(x-1,y)
walk(x,y-1)
walk(x,y)
def eightseven(n):
'''
Given an infinite number of quarters (25 cents), dimes (10 cents), nickels (5 cents) and
pennies (1 cent), write code to calculate the number of ways of representing n cents.
'''
quantities = 25, 10, 5, 1
all_ways = set()
def walk(current):
if sum(current) == n:
all_ways.add(tuple(sorted(current)))
return
for q in reversed(quantities):
if sum(current) + q > n:
break
walk(current[:] + [q])
walk([])
return all_ways
def eighteight(N=8):
'''
Write an algorithm to print all ways of arranging eight queens on a chess board so
that none of them share the same row, column or diagonal.
'''
def xitout(board, x, y):
def exo(board, x, y):
if x >= 0 and y >= 0 and x < N and y < N:
board[y][x] = 'X'
for i in range(N):
board[y][i] = 'X'
board[i][x] = 'X'
for i in range(1, N):
# diagonal
exo(board, x+i, y+i)
exo(board, x+i, y-i)
exo(board, x-i, y+i)
exo(board, x-i, y-i)
initial_board = [[' ' for _ in range(N)] for _ in range(N)]
all_arrangements = []
def walk(board):
queens = [(x,y) for y in range(N) for x in range(N) if board[y][x] == 'Q']
if len(queens) == N:
all_arrangements.append(queens)
for y in range(N):
for x in range(N):
if board[y][x] != ' ':
continue
# make a new board
new = [row[:] for row in board]
# X it out
xitout(new, x, y)
# place a queen
new[y][x] = 'Q'
walk(new)
walk(initial_board)
return set(map(tuple, all_arrangements))
def nineone(A, B, last_valid_a):
'''
You are given two sorted arrays, A and B, and A has a large enough buffer at the end
to hold B. Write a method to merge B into A in sorted order.
'''
idx = len(A) - 1
a_idx = last_valid_a
b_idx = len(B) - 1
while a_idx >= 0 and b_idx >= 0:
a, b = A[a_idx], B[b_idx]
if a > b:
A[idx] = a
a_idx -= 1
else:
A[idx] = b
b_idx -= 1
idx -= 1
while b_idx >= 0:
A[idx] = B[b_idx]
b_idx -= 1
idx -= 1
return A
def ninetwo(arr):
'''
Write a method to sort an array of strings so that all the anagrams are next to each
other.
'''
return sorted(arr, cmp=lambda a,b: cmp(sorted(a), sorted(b)))
def ninethree(arr, value):
'''
Given a sorted array of n integers that has been rotated an unknown number of
times, give an O(log n) algorithm that finds an element in the array. You may assume
that the array was originally sorted in increasing order.
EXAMPLE:
Input: find 5 in array (15 16 19 20 25 1 3 4 5 7 10 14)
Output: 8 (the index of 5 in the array)
'''
l = 0
r = len(arr) - 1
while l <= r:
middle = (l + r) / 2
if arr[middle] == value:
return middle
if arr[l] <= arr[middle]:
if value > arr[middle]:
l = middle + 1
elif value >= arr[l]:
r = middle - 1
else:
l = middle + 1
elif value < arr[middle]:
r = middle -1
elif value <= arr[r]:
l = middle + 1
else:
r = middle - 1
return -1
# print ninethree(map(int, '15 16 19 20 25 1 3 4 5 7 10 14'.split()), 5)
def ninefour():
'''
If you have a 2 GB file with one string per line, which sorting algorithm would you use
to sort the file and why?
'''
# external sort
def ninefive(arr, value):
'''
Given a sorted array of strings which is interspersed with empty strings, write a meth-
od to find the location of a given string.
Example: find “ball” in [“at”, “”, “”, “”, “ball”, “”, “”, “car”, “”, “”, “dad”, “”, “”] will return 4
Example: find “ballcar” in [“at”, “”, “”, “”, “”, “ball”, “car”, “”, “”, “dad”, “”, “”] will return -1
'''
l = 0
r = len(arr) - 1
while l <= r:
middle = cur = (l + r) / 2
while arr[cur] == '':
if cur <= 0:
cur = middle + 1
while arr[cur] == '':
if cur >= len(arr):
break
cur += 1
break
cur -= 1
if arr[cur] == value:
return cur
if arr[cur] <= value:
r = middle - 1
else:
l = middle + 1
return -1
def ninesix(arr, value):
'''
Given a matrix in which each row and each column is sorted, write a method to find
an element in it.
'''
n = len(arr[0])
m = len(arr)
x = n - 1
y = 0
while x >= 0 and y < m:
if arr[y][x] == value:
return x,y
if arr[y][x] <= value:
y += 1
else:
x -= 1
return -1
def nineseven(people):
'''
A circus is designing a tower routine consisting of people standing atop one anoth-
er’s shoulders. For practical and aesthetic reasons, each person must be both shorter
and lighter than the person below him or her. Given the heights and weights of each
person in the circus, write a method to compute the largest possible number of peo-
ple in such a tower.
EXAMPLE:
Input (ht, wt): (65, 100) (70, 150) (56, 90) (75, 190) (60, 95) (68, 110)
Output: The longest tower is length 6 and includes from top to bottom: (56, 90)
(60,95) (65,100) (68,110) (70,150) (75,190)
'''
maxed = []
people = sorted(people)
coll = []
for p in people:
if not coll:
coll.append(p)
continue
last = coll[-1]
if p[0] >= last[0] and p[1] >= last[1]:
coll.append(p)
else:
maxed = max(maxed, coll, key=len)
coll = []
return maxed or coll
def nineteenone(a, b):
'''Write a function to swap a number in place without temporary variables.'''
a = a ^ b
b = a ^ b
a = a ^ b
return a,b
def nineteentwo(board):
'''Design an algorithm to figure out if someone has won in a game of tic-tac-toe.'''
def won(three):
X = set(['X'])
O = set(['O'])
return set(three) in (X, O)
hori = board
verti = zip(*board)
diago = [[
board[0][0],
board[1][1],
board[2][2],
], [
board[0][2],
board[1][1],
board[2][0],
]]
return any(won(three) for threes in (hori, verti, diago) for three in threes)
def nineteenthree(n):
'''Write an algorithm which computes the number of trailing zeros in n factorial.'''
return n / 5 + n / 25
def nineteenfour(a, b):
'''
Write a method which finds the maximum of two numbers. You should not use if-
else or any other comparison operator.
EXAMPLE
Input: 5, 10
Output: 10
'''
return [a, b][bool((a - b) & (1 << 31))]
def nineteenfive(guess, solution):
'''
The Game of Master Mind is played as follows:
The computer has four slots containing balls that are red (R), yellow (Y), green (G) or
blue (B). For example, the computer might have RGGB (e.g., Slot #1 is red, Slots #2 and
#3 are green, Slot #4 is blue).
You, the user, are trying to guess the solution. You might, for example, guess YRGB.
When you guess the correct color for the correct slot, you get a “hit”. If you guess
a color that exists but is in the wrong slot, you get a “pseudo-hit”. For example, the
guess YRGB has 2 hits and one pseudo hit.
For each guess, you are told the number of hits and pseudo-hits.
Write a method that, given a guess and a solution, returns the number of hits and
pseudo hits.
'''
pseudos = len(guess) - len(Counter(solution) - Counter(guess))
hits = 0
for a,b in zip(guess, solution):
if a == b:
pseudos -= 1
hits += 1
return pseudos, hits
def nineteensix(n):
'''
Given an integer between 0 and 999,999, print an English phrase that describes the
integer (eg, “One Thousand, Two Hundred and Thirty Four”).
'''
nums = dict((i, num) for i, num in enumerate('One Two Three Four Five Six Seven Eight Nine Ten Eleven \
Twelve Thirteen Fourteen Fifteen Sixteen Seventeen Eighteen Nineteen'.split(), 1))
for i, num in zip(range(20, 101, 10), 'Twenty Thirty Forty Fifty Sixty Seventy Eighty Ninety Hundred'.split()):
nums[i] = num
# 912 Nine hundred and twelve
# 1299 One thousand two hundred 99
# 123 One Hundred and Twenty three
# 241,123 Two Hundred Thousand One Hundred and Twenty Three
def thousand(n):
if not n:
return []
if n in nums:
return [nums[n]]
if n >= 100:
div, name, multi = 100, ['Hundred'], 1
else:
div, name, multi = 10, [], 10
first, remainder = divmod(n, div)
return [nums[first*multi]] + name + thousand(remainder)
if not n:
return 'Zero'
if n < 1000:
result = thousand(n)
else:
first, second = map(thousand, divmod(n, 1000))
result = first + ['Thousand,'] + second
r = ' '.join(result[:-1]) + ' ' + result[-1]
return r.rstrip(',')
def nineteenseven(arr):
'''
You are given an array of integers (both positive and negative). Find the continuous
sequence with the largest sum. Return the sum.
EXAMPLE
Input: {2, -8, 3, -2, 4, -10}
Output: 5 (i.e., {3, -2, 4} )
'''
maxed = -1
for start in range(len(arr)):
su = arr[start]
if su < 0:
continue
for curr in range(start+1, len(arr)):
su += arr[curr]
maxed = max(maxed, su)
return maxed
def nineteeneight(text, word):
'''Design a method to find the frequency of occurrences of any given word in a book.'''
return Counter(text.split())[word]
def nineteennine():
'''
Since XML is very verbose, you are given a way of encoding it where each tag gets
mapped to a pre-defined integer value. The language/grammar is as follows:
Element --> Element Attr* END Element END [aka, encode the element
tag, then its attributes, then tack on an END character, then
encode its children, then another end tag]
Attr --> Tag Value [assume all values are strings]
END --> 01
Tag --> some predefined mapping to int
Value --> string value END
Write code to print the encoded version of an xml element (passed in as string).
FOLLOW UP
Is there anything else you could do to (in many cases) compress this even further?
'''
# lol wat
def nineteenten():
import random
rand = lambda: random.randrange(0, 6)
while True:
n = rand() * 5 + rand()
if n <= 21:
return n % 7
def twentyone(a,b):
'''
Write a function that adds two numbers. You should not use + or any arithmetic op-
erators.
'''
result = 0
carry = 0
mask = 1
for i in range(32):
aa = int(bool(a & mask))
bb = int(bool(b & mask))
here = carry ^ aa ^ bb
anded = aa & bb
ored = aa | bb
carry = (anded | (carry & ored))
result |= (here << i)
mask = mask << 1
return result
def twentytwo(arr):
'''
Write a method to shuffle a deck of cards. It must be a perfect shuffle - in other words,
each 52! permutations of the deck has to be equally likely. Assume that you are given
a random number generator which is perfect.
'''
import random
for i in reversed(range(1, len(arr))):
j = int(random.random() * (i+1))
arr[i], arr[j] = arr[j], arr[i]
def twentythree(arr, m):
'''
Write a method to randomly generate a set of m integers from an array of size n. Each
element must have equal probability of being chosen.
'''
import random
if m > len(arr):
return
result = []
used = set()
while len(result) < m:
idx = int(random.random() * len(arr))
elem = arr[idx]
if idx in used:
continue
else:
result.append(elem)
used.add(idx)
return result
def twentyfour(n):
'''Write a method to count the number of 2s between 0 and n.'''
if n < 2:
return 0
if 2 <= n < 10:
return 1
first = int(str(n)[0])
ll = 10 ** (len(str(n))-1)
remainder = n % ll
twos = 0
if first == 2:
twos += remainder
elif first > 2:
twos += ll
return twos + twentyfour(ll-1) * first + twentyfour(remainder)
def twentyfive(words, a, b):
'''
You have a large text file containing words. Given any two words, find the shortest
distance (in terms of number of words) between them in the file. Can you make the
searching operation in O(1) time? What about the space complexity for your solu-
tion?
'''
a_idx = -10000000
b_idx = -10000000
best = 10000000
for i, word in enumerate(words):
if word == a:
a_idx = i
best = min(a_idx, b_idx)
if word == b:
b_idx = i
best = min(a_idx, b_idx)
return best
def twentysix(numbers):
'''
Describe an algorithm to find the largest 1 million numbers in 1 billion numbers. As-
sume that the computer memory can hold all one billion numbers.
'''
class MinHeap:pass
heap = MinHeap()
it = iter(numbers)
for _ in range(10**6):
heap.insert(it.next())
for num in it:
heap.insert(num)
heap.remove_min()
return list(heap)
def twentyseven(text):
'''
Write a program to find the longest word made of other words in a list of words.
EXAMPLE
Input: test, tester, testertest, testing, testingtester
Output: testingtester
'''
all_words = set(text.split())
def composed(word, accu=None):
if word in all_words:
return word
for i in range(1, len(word)):
prefix = word[:i]
if prefix in all_words:
suffixed = composed(word[i:])
if suffixed:
return prefix + " " + suffixed
return max([composed(word) for word in all_words], key=len)
def twentyeight(s, T):
'''
Given a string s and an array of smaller strings T, design a method to search s for each
small string in T.
'''
class Node(object):
def __init__(self, value):
self.value = value
self.children = []
def __repr__(self):
return repr(self.children)
class SuffixTree(object):
def __init__(self, string):
self.root = Node('')
for i in range(1, len(string)+1):
self.insert(string[:i])
def find(self, value, insert=False):
try:
self._find(value, insert)
except IndexError:
return False
else:
return True
def _find(self, value, insert):
def walk(root, s):
if not s:
return
found = False
for child in root.children:
if child.value == s[-1]:
found = True
break
if not found:
if insert:
child = Node(s[-1])
root.children.append(child)
else:
raise IndexError
walk(child, s[:-1])
walk(self.root, value)
def insert(self, value):
return self._find(value, insert=True)
tree = SuffixTree(s)
result = []
for t in T:
res = tree.find(t)
if res:
result.append(t)
return result
def twentynine():
'''
Numbers are randomly generated and passed to a method. Write a program to find
and maintain the median value as new values are generated.
'''
class Heap(object):
pass
class MinHeap(Heap):
def cmp(a, b):
return cmp(a, b)
class MaxHeap(Heap):
def cmp(a, b):
return cmp(b, a)
mini = MinHeap()
maxi = MaxHeap()
def fun(number):
if number > mini.min():
mini.insert(number)
else:
maxi.insert(number)
if len(maxi) + len(mini) % 2 == 0:
median = (maxi.max() + mini.min()) / 2
else:
median = maxi.max()
return median
def twentyeleven(arr):
'''
Imagine you have a square matrix, where each cell is filled with either black or white.
Design an algorithm to find the maximum subsquare such that all four borders are
filled with black pixels.
'''
def is_square(x, y, size):
ll = x, y + size
ur = x + size, y
lr = x + size, y + size
return all(arr[y][x] == 'B' for x, y in ((x,y), ll, ur, lr))
maxed = float('-inf')
maxed_coords = []
x = 0
N = len(arr)
while N - x > maxed:
for y in range(N):
size = N - max(x, y) - 1
while size > maxed:
if is_square(x, y, size):
maxed = size
maxed_coords = x, y, size
size -= 1
x += 1
return maxed_coords
def twentytwelve(arr):
'''
Given an NxN matrix of positive and negative integers, write code to find the sub-
matrix with the largest possible sum.
'''
# this is N^4 + N^4 and can be optimized to N^2 + N^4
N = len(arr)
d = {}
for y1 in range(N+1):
for x1 in range(N+1):
d[(x1, y1)] = sum(arr[y][x] for y in range(y1) for x in range(x1))
maxed = float('-inf')
maxed_coords = []
def subsum(x1, y1, x2, y2):
return d[(x2, y2)] - d[(x1, y2)] - d[(x2, y1)] + d[(x1, y1)]
for y1 in range(N):
for x1 in range(N):
for y2 in range(y1, N):
for x2 in range(x1, N):
area = subsum(x1,y1,x2+1,y2+1)
if area > maxed:
maxed = area
maxed_coords = x1, y1, x2, y2
return maxed_coords, maxed
# print twentytwelve([
# [-100,2,3],
# [4,5,6],
# [7,8,9]])
def twentythirteen():
'''
Given a dictionary of millions of words, give an algorithm to find the largest possible
rectangle of letters such that every row forms a word (reading left to right) and every
column forms a word (reading top to bottom).
'''