Master the Coding Interview

# 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()