Master the Coding Interview
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280
# Given two arrays, create a function that
# lets a user know (true/false) whether
# these two arrays contain any common items.
import time
# Brute force solution
def doArraysHaveCommonItems1(x, y):
for i in range(len(x)):
for j in range(len(y)):
if x[i] == y[j]:
print("True")
return True
return False
# Optimized solution
def doArraysHaveCommonItems2(x, y):
# Create a set from first array
x_set = set(x)
# Only loop through one array
for item in y:
if item in x_set:
print("True")
return True
return False
a = [1, 2, 4, 7]
b = [3, 5, 7, 8]
start = time.time()
doArraysHaveCommonItems1(a, b)
end = time.time()
t1 = end - start
print(str(t1) + " secs")
start = time.time()
doArraysHaveCommonItems2(a, b)
end = time.time()
t2 = end - start
print(str(t2) + " secs")
# Create a function that reverses a string.
def reverseString(s):
l = 0
r = len(s) - 1
s = list(s)
while l < r:
s[l], s[r] = s[r], s[l]
l += 1
r -= 1
return ''.join(s)
# Merge two sorted arrays
def mergeSortedArrays(a, b):
res = []
i = j = 0
while i < len(a) and j < len(b):
if a[i] < b[j]:
res.append(a[i])
i += 1
elif b[j] < a[i]:
res.append(b[j])
j += 1
else:
res.append(a[i])
res.append(b[j])
i += 1
j += 1
return res
class HashTable:
def __init__(self, size):
self.size = size
self.data = [[]] * (size)
def _hash(self, key):
hash_value = 0
for i in range(len(key)):
hash_value = (hash_value + ord(key[i]) * i) % len(self.data)
return hash_value
def set(self, key, value):
address = self._hash(key)
if not self.data[address]:
self.data[address] = []
self.data[address].append([key, value])
return self.data
def get(self, key):
address = self._hash(key)
currentBucket = self.data[address]
print(currentBucket)
if currentBucket:
for i in range(len(currentBucket)):
if currentBucket[i][0] == key:
return currentBucket[i][1]
return None
def keys(self):
keysArray = []
for i in range(len(self.data)):
if self.data[i]:
keysArray.append(self.data[i][0][0])
return keysArray
# First recurring character
def firstRecurringCharacter(vals):
items = {}
for i in range(len(vals)):
if not items[vals[i]]:
items[i] = vals[i]
else:
return vals[i]
return None
# Implement a linked list
class Node:
def __init__(self, value):
self.value = value
self.next = None
class LinkedList:
def __init__(self, value):
self.head = Node(value)
self.tail = self.head
self.length = 1
def append(self, value):
node = Node(value)
self.tail.next = self.node
self.tail = node
self.length += 1
return self.head
def prepend(self, value):
node = Node(value)
node.next = self.head
self.head = node
self.length += 1
return self.head
def printList(self):
array = []
currentNode = self.head
while currentNode:
array.append(currentNode.value)
currentNode = currentNode.next
return array
def insert(index, value):
if index == 0:
return self.prepend(value)
elif index >= self.length:
return self.append(value)
node = Node(value)
currentNode = self.head.next
prevNode = self.head
count = 1
while currentNode:
if index == count:
prevNode.next = node
node.next = currentNode
self.length += 1
break
prevNode = currentNode
currentNode = currentNode.next
count += 1
return self.printList()
def remove(index):
if index == 0:
self.head = self.head.next
self.head.prev = None
self.length -= 1
return self.printList()
currentNode = self.head.next
prevNode = self.head
count = 1
while currentNode:
if index == count:
prevNode.next = currentNode.next
self.length -= 1
break
prevNode = currentNode
currentNode = currentNode.next
count += 1
return self.printList()
def reverse(self):
currentNode = self.head
prevNode = None
self.tail = self.head
while currentNode:
temp = currentNode
currentNode = currentNode.next
temp.next = prevNode
prevNode = temp
self.head = temp
return self.printList()
class Node:
def __init__(self, value):
self.value = value
self.prev = None
self.next = None
class DoublyLinkedList:
def __init__(self, value):
self.head = Node(value)
self.tail = self.head
self.length = 1
def append(self, value):
node = Node(value)
self.tail.next = node
node.prev = self.tail
self.tail = node
self.length += 1
return self.head
def prepend(self, value):
node = Node(value)
node.next = self.head
node.prev = None
self.head = node
self.length += 1
return self.head
def printList(self):
array = []
currentNode = self.head
while currentNode:
array.append(currentNode.value)
currentNode = currentNode.next
return array
def insert(index, value):
if index == 0:
return self.prepend(value)
elif index >= self.length:
return self.append(value)
node = Node(value)
currentNode = self.head.next
prevNode = self.head
count = 1
while currentNode:
if index == count:
prevNode.next = node
node.prev = prevNode
node.next = currentNode
currentNode.prev = node
self.length += 1
break
prevNode = currentNode
currentNode = currentNode.next
count += 1
return self.printList()
def remove(index):
if index == 0:
self.head = self.head.next
self.length -= 1
return self.printList()
currentNode = self.head.next
prevNode = self.head
count = 1
while currentNode:
if index == count:
prevNode.next = currentNode.next
currentNode.next.prev = prevNode
self.length -= 1
return self.printList()
prevNode = currentNode
currentNode = currentNode.next
count += 1
return self.printList()
Python
INFO