CC189 - Cracking the Coding Interview

In [1]:

    

from __future__ import print_function
from __future__ import division
from __future__ import absolute_import
from __future__ import unicode_literals


    

In [ ]:

    

### Implementation using Python list

# class LinkedList:
#     def __init__(self):
#         self.items = []
#     def add(self, data):
#         self.items.appendAtEnd(data)
#     def search(self, data):
#         if data in self.items:
#             return self.items.index(data)
#     def remove(self, data):
#         if data in self.items:
#             i = self.items.index(data)
#             self.items = self.items[:i] + self.items[i + 1:]


    

In [1]:

    

class Node:
    def __init__(self, data=None):
        self.data = data
        self.next = None
        self.end = None
    def traverse(self):
        n = self
        while n != None:
            print(n.data)
            n = n.next
    def appendAtEnd(self, data):
        if not self.data:
            self.data = data
        else:
            n = self
            while n.next != None:
                n = n.next
            n.next = Node(data)


    

In [2]:

    

def delNode(node, d):
    n = node
    
    # delete head
    if n.data == d:
        return head.next
    
    while n.next != None:
        if n.next.data == d:
            n.next = n.next.next
            return node
        n = n.next
    return node


    

In [3]:

    

node = Node(12)
for i in range(13, 18):
    node.appendAtEnd(i)
node.traverse()


    

    




12
13
14
15
16
17

In [4]:

    

node = delNode(node, 15)
node.traverse()


    

    




12
13
14
16
17

In [5]:

    

from collections import defaultdict


    

In [6]:

    

def removeDups(node):
    n = node
    previous = None
    nodeMap = defaultdict(bool)
    while n != None:
        if nodeMap[n.data]:
            previous.next = n.next
        else:
            nodeMap[n.data] = True
            previous = n
        n = n.next
    return node


    

In [7]:

    

node = Node(12)
for i in range(11, 13):
    node.appendAtEnd(i)
node.traverse()


    

    




12
11
12

In [8]:

    

node = removeDups(node)

node.traverse()


    

    




12
11

In [9]:

    

def kthToLast(node, k):
    while k > 1:
        node = node.next
        k -= 1
    return node


    

In [10]:

    

node = Node(12)
for i in range(11, 17):
    node.appendAtEnd(i)
node.traverse()


    

    




12
11
12
13
14
15
16

In [11]:

    

kthToLast(node, 3).traverse()


    

    




12
13
14
15
16

In [12]:

    

def deleteNode(n):
    if n is None or n.next is None:
        return False
    n.data = n.next.data
    n.next = n.next.next
    return True


    

In [13]:

    

node = Node(12)
for i in range(11, 17):
    node.appendAtEnd(i)
node.traverse()


    

    




12
11
12
13
14
15
16

In [14]:

    

node.next.next.next.data


    

    
Out[14]:





13

In [15]:

    

deleteNode(node.next.next.next)


    

    
Out[15]:





True

In [16]:

    

node.traverse()


    

    




12
11
12
14
15
16

In [30]:

    

# store values in two lists and then merge them
# time: O(n); space: O(n)
def partition(node, x):
    before, after = Node(), Node()
    n = node
    while n != None:
        if n.data < x:
            before.appendAtEnd(n.data)
        else:
            after.appendAtEnd(n.data)
        n = n.next
    return [before, after]


    

In [31]:

    

x = 13
node = Node()
for i in range(11, 17):
    node.appendAtEnd(i)
node.traverse()


    

    




11
12
13
14
15
16

In [32]:

    

before, after = partition(node, x)


    

In [33]:

    

before.traverse()


    

    




11
12

In [34]:

    

after.traverse()


    

    




13
14
15
16

In [53]:

    

def sumLists(n1, n2):
    n3 = Node()
    flow = 0
    while n1:
        d1, d2 = n1.data, n2.data
        d3 = (flow + d1 + d2) % 10
        n3.appendAtEnd(d3)
        flow = (d1 + d2) // 10
        n1, n2 = n1.next, n2.next
    return n3


    

In [54]:

    

n1, n2 = Node(), Node()
for digit in [7, 1, 6]:
    n1.appendAtEnd(digit)
n1.traverse()
for digit in [5, 9, 2]:
    n2.appendAtEnd(digit)
n2.traverse()


    

    




7
1
6
5
9
2

In [55]:

    

output = sumLists(n1, n2)

output.traverse()


    

In [ ]: