In [ ]:

    

#3.1 Describe how you could use a single array to implement three stacks


    

In [ ]:

    

class signleArrayStack(object):
    
    def __init__(self):
        self.arr=[]
        
    def push(self,i):
        return self.arr.append(i)
    
    def pop(self,index):
        return self.arr.pop(index)
    
    def peek(self,index):
        return self.arr[index]
    
    def size(self):
        return len(self.arr)
    
    def show(self):
        return self.arr


    

In [ ]:

    

s=signleArrayStack()


    

In [ ]:

    

s.push(1)
s.push(2)
s.push(3)
s.push(4)
s.push(5)


    

In [ ]:

    

s


    

In [ ]:

    

s.size()


    

In [ ]:

    

s.peek(2)


    

In [ ]:

    

s.show()


    

In [ ]:

    

#3.2 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.


    

In [ ]:

    

class signleArrayStack(object):
    
    def __init__(self):
        self.arr=[]
        
    def push(self,i):
        return self.arr.append(i)
    
    def pop(self,index):
        return self.arr.pop(index)
    
    def peek(self,index):
        return self.arr[index]
    
    def size(self):
        return len(self.arr)
    
    def show(self):
        return self.arr
    
    def minimum(self):
        return min(self.arr)


    

In [ ]:

    

s.minimum()


    

In [ ]:

    

#3.3


    

In [ ]:

    

class Stack(object):
    def __init__(self, capacity):
        self.capacity = capacity
        self.size = 0
        self.top = None
        self.bottom = None

    def is_full(self):
        return self.size == self.capacity

    def is_empty(self):
        return self.size == 0

    def join(self, above, below):
        if below:
            below.above = above
        if above:
            above.below = below

    def push(self, v):
        if self.size >= self.capacity:
            return False
        self.size += 1
        n = Node(v)
        if self.size == 1:
            self.bottom = n
        self.join(n, self.top)
        self.top = n
        return True

    def pop(self):
        if not self.top:
            return None
        t = self.top
        self.top = self.top.below
        self.size -= 1
        return t.value

    def remove_bottom(self):
        b = self.bottom
        self.bottom = self.bottom.above
        if self.bottom:
            self.bottom.below = None
        self.size -= 1
        return b.value

class SetOfStacks(object):
    def __init__(self, capacity):
        self.capacity = capacity
        self.stacks = []

    def get_last_stack(self):
        if not self.stacks:
            return None
        return self.stacks[-1]

    def is_empty(self):
        last = self.get_last_stack()
        return not last or last.is_empty()

    def push(self, v):
        last = self.get_last_stack()
        if last and not last.is_full():
            last.push(v)
        else:
            stack = Stack(self.capacity)
            stack.push(v)
            self.stacks.append(stack)

    def pop(self):
        last = self.get_last_stack()
        if not last:
            return None
        v = last.pop()
        if last.size == 0:
            del self.stacks[-1]
        return v

    def pop_at(self, index):
        return self.left_shift(index, True)

    def left_shift(self, index, remove_top):
        stack = self.stacks[index]
        removed_item = stack.pop() if remove_top else stack.remove_bottom()
        if stack.is_empty():
            del self.stacks[index]
        elif len(self.stacks) > index + 1:
            v = self.left_shift(index + 1, False)
            stack.push(v)
        return removed_item


    

In [ ]:

    

#3.4
class Hanoi:
    
    def __init__(self, size):
        self.towers = [[], [], []]
        self.size = size
        self.towers[0] = [x for x in range(size, 0, -1)]

    def playHanoi(self):
        self.printTowers()
        self.moveDisk(self.size, 1, 2, 3)
        self.printTowers()

    def moveDisk(self, size, fr, helper, to):
        if size == 1:
            data = self.towers[fr-1].pop()
            self.towers[to-1].append(data)
            print ("Disk", data, ": Tower", fr, "->", to)      
        else:
            self.moveDisk(size - 1, fr, to, helper)
            self.moveDisk(1, fr, helper, to)
            self.moveDisk(size - 1, helper, fr, to)

    def printTowers(self):
        for i in self.towers:
            print (i)




#----------------test---------------
hanoi = Hanoi(4)
hanoi.playHanoi()


    

In [ ]:

    

#3.5
class Queue(object):
    
    def __init__(self):
        self.q=[]
    
    def isEmpty(self):
        return self.q.size()==0
    def size(self):
        return len(self.q)
    
    def enqueue(self,i):
        return self.q.insert(0,i)
    def dequeue(self):
        return


    

In [ ]:

    




    

In [2]:

    

import sys

def simpleArraySum(n, ar):
    # Complete this function
    sum=0
    for i in ar:
        sum+=i
    return sum



n = int(input().strip())
ar = list(map(int, input().strip().split(' ')))
result = simpleArraySum(n, ar)
print(result)


    

    




6
1 2 3 4 10 11
31

In [ ]:

    

n


    

In [ ]:

    

ar


    

In [27]:

    

def solve(a0, a1, a2, b0, b1, b2):
    # Complete this function
    scores={'Alice':0, 'Bob':0}
    
    if a0>b0:
        scores['Alice']+=1
    elif a0<b0:
        scores['Bob']+=1

    if a1>b1:
        scores['Alice']+=1
    elif a1<b1:
        scores['Bob']+=1
        
    if a2>b2:
        scores['Alice']+=1
    elif a2<b2:
        scores['Bob']+=1
        
    return list(scores.values())


    

In [29]:

    

solve(20,20,30,20,20,50)


    

    
Out[29]:





[0, 1]

In [65]:

    

def twoSum(nums, target):
    """
    :type nums: List[int]
    :type target: int
    :rtype: List[int]
    """
    if len(nums)==0:
        return False
    
    for i in range(len(nums)+1):
        for j in range(i+1,len(nums)):
            if nums[i]+nums[j]==target:
                return [i,j]
     
            
twoSum([3,2,4],6)


    

    
Out[65]:





[1, 2]

In [56]:

    

for i in range(3):
    print(i)


    

    




0
1
2

In [42]:

    

a=[3,2,4]
len(a)


    

    
Out[42]:





3

In [54]:

    

for i in range(len(a)+1):
    for j in range(i+1,len(a)):
        if a[i]+a[j]==6:
            print (i,j)
        else:
            print (False)


    

    




False
False
1 2

In [102]:

    

B=[12,28,46,32,50]
A=[50,12,32,46,28]

[1,4,3,2,0]
d={x: i for i , x in enumerate(B)}


    

In [103]:

    

d


    

    
Out[103]:





{12: 0, 28: 1, 32: 3, 46: 2, 50: 4}

In [99]:

    




    

    
Out[99]:





(1, 4, 3, 2, 0)

In [106]:

    

[d[x] for x in A]


    

    
Out[106]:





[4, 0, 3, 2, 1]

In [142]:

    

def nums(n):

    for i in str(n):
        if i==0 or int(n)%int(i)>0:
            return False
        
    return True
        
nums('14')


    

    
Out[142]:





False

In [145]:

    

def nums(n):

    for i in str(n):
        if i==0 or int(n)%int(i)>0:
            return False
        
    return True

def selfDividingNumbers(left, right):

        ls=[]
        for i in range (left,right+1):
            if nums(i):
                ls.append(i)
        return ls
    

selfDividingNumbers(2,22)


    

    




---------------------------------------------------------------------------
ZeroDivisionError                         Traceback (most recent call last)
<ipython-input-145-429d918af76c> in <module>()
     16 
     17 
---> 18 selfDividingNumbers(2,22)

<ipython-input-145-429d918af76c> in selfDividingNumbers(left, right)
     11         ls=[]
     12         for i in range (left,right+1):
---> 13             if nums(i):
     14                 ls.append(i)
     15         return ls

<ipython-input-145-429d918af76c> in nums(n)
      2 
      3     for i in str(n):
----> 4         if i==0 or int(n)%int(i)>0:
      5             return False
      6 

ZeroDivisionError: integer division or modulo by zero

In [ ]:

    




    

In [ ]:

    




    

In [176]:

    

def arrayPairSum(nums):
    """
    :type nums: List[int]
    :rtype: int
    """
    nums=sorted(nums)
    return sum(nums[::2])
    return sum(sorted(nums[::2]))


    

In [177]:

    

arrayPairSum([1,2,3,2])


    

    
Out[177]:





3

In [223]:

    

def findComplement( num):
        i = 1
        while i <= num:
            i = i << 1
            print (i, (i - 1) ^ num)


    

In [224]:

    

findComplement(5)


    

    




2 4
4 6
8 2

In [303]:

    

def reverseWords( s):
        """
        :type s: str
        :rtype: str
        """
        '''if len(s) == 0:
            return s
        else:
            return reverseWords(s[1:]) + s[0]
        return ([list(reversed(i)) for i in s.split(' ')])'''
        return ' '.join([i[::-1] for i in s.split(' ')])


    

In [304]:

    

reverseWords("Let's take LeetCode contest")


    

    
Out[304]:





"s'teL ekat edoCteeL tsetnoc"

In [ ]:

    




    

In [385]:

    

def findWords( words):
    """
    :type words: List[str]
    :rtype: List[str]
    """
    import re
    pat = re.compile(r'(?i)([qwertyuiop]*|[asdfghjkl]*|[zxcvbnm]*)').match
    return list(filter(pat,words))


    

In [386]:

    

findWords(["Hello", "Alaska", "Dad", "Peace"])


    

    
Out[386]:





['Hello', 'Alaska', 'Dad', 'Peace']

In [376]:

    

filter(re.compile('(?i)([qwertyuiop]*|[asdfghjkl]*|[zxcvbnm]*)$').match, words)


    

    




---------------------------------------------------------------------------
NameError                                 Traceback (most recent call last)
<ipython-input-376-4189729d8551> in <module>()
----> 1 filter(re.compile('(?i)([qwertyuiop]*|[asdfghjkl]*|[zxcvbnm]*)$').match, words)

NameError: name 're' is not defined

In [404]:

    

import random,string


    

In [457]:

    

class codec:
    
    def __init__(self):
        self.url2code={}
        self.code2url={}
    
    def encode(self,longUrl):
        """Encodes a URL to a shortened URL.

        :type longUrl: str
        :rtype: str
        """
        while longUrl not in self.url2code:

            code = ''.join(random.choice(string.ascii_uppercase + string.digits) for _ in range(8))
            if code not in self.code2url:
                self.code2url[code]=longUrl
                self.url2code[longUrl]=code

        return 'http://tinyurl.com/'+ self.url2code[longUrl]
    
    def decode(self,shortUrl):
        
        return self.code2url[shortUrl[-8:]]


    

In [458]:

    

c=codec()


    

In [459]:

    

c.encode('www.google.com')
#c.decode('http://tinyurl.com/9ATNN5FV')


    

    
Out[459]:





'http://tinyurl.com/PHANQKDE'

In [461]:

    

c.decode('http://tinyurl.com/PHANQKDE')


    

    
Out[461]:





'www.google.com'

In [483]:

    

def sol(s):

    sizes=[]
    while s:
        i=1
        while set(s[:i]) & set(s[i:]):
            i+=1
            print (set(s[:i]))
            print (set(s[i:]))
        sizes.append(i)
        s=s[i:]
        
    
    return sizes


    

In [484]:

    

sol('ababcbacadefegdehijhklij')


    

    




{'a', 'b'}
{'a', 'g', 'f', 'k', 'l', 'h', 'b', 'e', 'j', 'c', 'i', 'd'}
{'a', 'b'}
{'a', 'g', 'f', 'k', 'l', 'h', 'b', 'e', 'j', 'c', 'i', 'd'}
{'a', 'b'}
{'a', 'g', 'f', 'k', 'l', 'h', 'b', 'e', 'j', 'c', 'i', 'd'}
{'a', 'c', 'b'}
{'a', 'g', 'f', 'k', 'l', 'h', 'b', 'e', 'j', 'c', 'i', 'd'}
{'a', 'c', 'b'}
{'a', 'g', 'f', 'k', 'l', 'h', 'e', 'j', 'c', 'i', 'd'}
{'a', 'c', 'b'}
{'a', 'g', 'f', 'k', 'l', 'h', 'e', 'j', 'c', 'i', 'd'}
{'a', 'c', 'b'}
{'a', 'g', 'f', 'k', 'l', 'h', 'e', 'j', 'i', 'd'}
{'a', 'c', 'b'}
{'g', 'f', 'k', 'l', 'h', 'e', 'j', 'i', 'd'}
{'e', 'd'}
{'g', 'f', 'k', 'l', 'h', 'e', 'j', 'i', 'd'}
{'e', 'f', 'd'}
{'g', 'k', 'l', 'h', 'e', 'j', 'i', 'd'}
{'e', 'f', 'd'}
{'g', 'k', 'l', 'h', 'e', 'j', 'i', 'd'}
{'e', 'f', 'g', 'd'}
{'k', 'l', 'h', 'e', 'j', 'i', 'd'}
{'e', 'f', 'g', 'd'}
{'k', 'l', 'h', 'e', 'j', 'i'}
{'e', 'f', 'g', 'd'}
{'k', 'h', 'l', 'j', 'i'}
{'i', 'h'}
{'k', 'h', 'l', 'j', 'i'}
{'j', 'i', 'h'}
{'k', 'h', 'l', 'j', 'i'}
{'j', 'i', 'h'}
{'l', 'k', 'j', 'i'}
{'k', 'j', 'i', 'h'}
{'l', 'j', 'i'}
{'k', 'h', 'l', 'j', 'i'}
{'j', 'i'}
{'k', 'h', 'l', 'j', 'i'}
{'j'}
{'k', 'h', 'l', 'j', 'i'}
set()






    
Out[484]:





[9, 7, 8]

In [ ]:

    




    

In [22]:

    

def countBattleships(board):
    """
    :type board: List[List[str]]
    :rtype: int
    """
    row, col = len(board), len(board[0])
    count=0
    for i in range(row):
        for j in range(col):
            if board[i][j]=='X' and (i==0 or board[i-1][j]=='.') and (j==0 or board[i][j-1]=='.'):

                count+=1

    return count


    

In [23]:

    

countBattleships([["X",".",".","X"],[".",".",".","X"],[".",".",".","X"]])


    

    
Out[23]:





2

In [44]:

    

def countBits( num):
    """
    :type num: int
    :rtype: List[int]
    """
    ls=[]
    for i in  range(num+1):
        
        ls.append(bin(i)[2:].count('1'))
        
    return ls


    

In [45]:

    

countBits(5)


    

    
Out[45]:





[0, 1, 1, 2, 1, 2]

In [2]:

    

people=[[7,0], [7,1], [6,1], [5,0], [5,2], [4,4]]


    

In [14]:

    

insertion_order = sorted(people, reverse=True)
insertion_order


    

    
Out[14]:





[[7, 1], [7, 0], [6, 1], [5, 2], [5, 0], [4, 4]]

In [18]:

    

insertion_order = sorted(people, key=lambda (h,k): (-h,k))
insertion_order


    

    
Out[18]:





[[7, 0], [7, 1], [6, 1], [5, 0], [5, 2], [4, 4]]

In [15]:

    

ordered_line = []
for person in insertion_order:
    ordered_line.insert(person[1], person)
ordered_line


    

    
Out[15]:





[[5, 0], [7, 0], [6, 1], [5, 2], [4, 4], [7, 1]]

In [17]:

    

ordered_line = []
for person in insertion_order:
    ordered_line.insert(person[1], person)
ordered_line


    

    
Out[17]:





[[5, 0], [7, 0], [5, 2], [6, 1], [4, 4], [7, 1]]

In [8]:

    

def reconstructQueue(self, people):

    if not people:
        return []
    ordered_line = []

    insertion_order = sorted(people, key = lambda (h,k): (-h,k))

    for person in insertion_order:
        ordered_line.insert(person[1], person)

    return ordered_line


    

In [137]:

    

def countSmaller( nums):
    
    dic=dict()
    ls=[]
    
    '''    for i in range(len(nums)):
        dic[nums[i]]=0'''
    
    for i in nums:
        dic[i]=0
        
    for i in range(len(nums)+1):
        for j in range(i+1,(len(nums))):
            
            if nums[i]>nums[j]:
                dic[nums[i]]+=1
                ls.append(dic[nums[i]])
    #for k, v in dic.items():
        
    
    return dic,dic.values(),dic.keys()


    

In [138]:

    

countSmaller([5, 2, 6, 1])


    

    
Out[138]:





({1: 0, 2: 1, 5: 2, 6: 1}, [0, 1, 2, 1], [1, 2, 5, 6])

In [242]:

    

import operator


    

In [251]:

    

def findDuplicates(nums):
    
    if set(nums)==nums:
        return False
    dic=dict()
    for i in nums:
        dic[i]=0
    for i in nums:
        dic[i]+=1
  
    sorted_x = sorted(dic.items(), key=operator.itemgetter(1))
        
    
    return sorted_x[0][0]
#sorted(dic.keys(),reverse=True)[0]


    

In [252]:

    

findDuplicates([1,1,2,3,3,4,4,8,8])


    

    
Out[252]:





2

In [256]:

    

def countSubstrings(s):
    
    ls=[]
    for i in range(len(s)):
        ls= s[:i]
        for j in ls:
            if ls==ls[::-1]:
                print ls


    

In [257]:

    

countSubstrings("abc")


    

    




a

In [267]:

    

def optimalDivision(nums):
    
    a=map(str,nums)
    
    return '({}/({}))'.format(a[0],'/'.join(a[1:]))


    

In [268]:

    

optimalDivision([1000,100,10,2])


    

    
Out[268]:





'(1000/(100/10/2))'

In [352]:

    

import string, collections, re


    

In [366]:

    




    

In [384]:

    

shortestCompletingWord("1s3 456",["looks", "pest", "stew", "show"])


    

    
Out[384]:





''

In [379]:

    

contains("1s3 456","pest")


    

    
Out[379]:





False

In [376]:

    

def shortestCompletingWord( licensePlate, words):
        regex = re.compile('[^a-zA-Z]')
        licensePlate = regex.sub('', licensePlate)
        counter = collections.Counter(licensePlate.lower())
        res = ''
        for word in words:
            if contains(counter, word):
                if res == '' or len(word) < len(res):
                    res = word
        return res


def contains( counter1, w2):
    c2 = collections.Counter(w2)
    c2.subtract(counter1)
    return all(map(lambda x: x >= 0,c2.values()))


    

In [383]:

    

def shortestCompletingWord(licensePlate, words):
    
    import string, collections, re
    regex = re.compile('[^a-zA-Z]')
    licensePlate = regex.sub('',licensePlate)
    counter = collections.Counter(licensePlate.lower())
    res=''
    
    for word in words:
        if contains(counter,word):
            if res=='' or len(word)< len(res):
                re=word
    return res


def contains(counter1,w2):
    
    c2=collections.Counter(w2)
    #print c2
    c2.subtract(counter1)
    #print c2
    
    return all(map(lambda x: x>=0, c2.values()))


    

In [425]:

    

def dailyTemperatures(temperatures):
    
    temp={}
    temp2={}
    for i , t in enumerate(temperatures):
        temp[i]= t
    print temp
    results = [0]*len(temperatures)
    for i in range(len(temperatures)-1,-1,-1):
        temp = temperatures[i]
        day = str('inf')
        
        for j in range(temp+1,101):
            if j in temp2:
                day = min(day, temp2[j]-i)
                print day
        if day!=str('inf'):
            results[i]=day
            
        temp2[temp]=i
    return results


    

In [426]:

    

dailyTemperatures([73, 74, 75, 71, 69, 72, 76, 73])


    

    




{0: 73, 1: 74, 2: 75, 3: 71, 4: 69, 5: 72, 6: 76, 7: 73}
2
1
1
1
1
2
2
2
4
1
1
1
1
1






    
Out[426]:





[1, 1, 4, 2, 1, 1, 0, 0]

In [465]:

    

import collections
def singleNumber(nums):
    
    dic= collections.Counter(nums)
    #print dic
    sorted_dic = sorted(dic.items(),reverse=False, key=operator.itemgetter(1))
    #print list(sorted_dic[:2])
    print [x[0] for x in list(sorted_dic[:2])]


    

In [466]:

    

singleNumber([1, 2, 1, 3, 2, 5])


    

    




Counter({1: 2, 2: 2, 3: 1, 5: 1})
[(3, 1), (5, 1)]
[3, 5]

In [504]:

    

import os, sys, collections, operator


    

In [520]:

    

def findDuplicate(paths):
    
    dic={}
    ls=[]
    for lines in paths:
        data = lines.split()
        root=data[0]
        ls.append(data[-1])
    print ls
    counter=collections.Counter(ls)
    print counter
    return sorted(counter.items(), reverse=True)[0][0]


    

In [521]:

    

findDuplicate(["root/a 1.txt(abcd) 2.txt(efgh)", "root/c 3.txt(abcd)", "root/c/d 4.txt(efgh)", "root 4.txt(efgh)"])


    

    




['2.txt(efgh)', '3.txt(abcd)', '4.txt(efgh)', '4.txt(efgh)']
Counter({'4.txt(efgh)': 2, '2.txt(efgh)': 1, '3.txt(abcd)': 1})






    
Out[521]:





'4.txt(efgh)'

In [482]:

    

os.getcwd()


    

    
Out[482]:





'C:\\Users\\User\\Downloads\\Compressed\\ctci-master\\python'

In [473]:

    

os.listdir('.')


    

    
Out[473]:





['.ipynb_checkpoints',
 'Chapter 1',
 'Chapter 2',
 'Chapter 3',
 'Chapter 4',
 'Chapter 9',
 'CTCI-Python-ch1.ipynb',
 'CTCI-Python-ch2.ipynb',
 'CTCI-Python-ch3.ipynb']

In [ ]:

    

s = [('yellow', 1), ('blue', 2), ('yellow', 3), ('blue', 4), ('red', 1)]
d =collections.defaultdict(list)
for k,v in s:
    d[v]=k
d


    

In [530]:

    

def findDuplicate(paths):
    
    M = collections.defaultdict(list)
    ls=[]
    for lines in paths:
        data = lines.split()
        root=data[0]
        for file in data[1:]:
            name, _, content = file.partition('(')
            print name,_,content
            M[content[:-1]].append(root + '/' + name)
    print M

        #return [x for x in M.values() if len(x) > 1]


    

In [531]:

    

findDuplicate(["root/a 1.txt(abcd) 2.txt(efgh)", "root/c 3.txt(abcd)", "root/c/d 4.txt(efgh)", "root 4.txt(efgh)"])


    

    




1.txt ( abcd)
2.txt ( efgh)
3.txt ( abcd)
4.txt ( efgh)
4.txt ( efgh)
defaultdict(<type 'list'>, {'abcd': ['root/a/1.txt', 'root/c/3.txt'], 'efgh': ['root/a/2.txt', 'root/c/d/4.txt', 'root/4.txt']})

In [548]:

    

def minMoves2( nums):
    median = sorted(nums)[len(nums) / 2]
    print median
    return list(abs(num - median) for num in nums)


    

In [547]:

    

minMoves2([1,2,3])


    

    




---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-547-9f7909964a6d> in <module>()
----> 1 minMoves2([1,2,3])

<ipython-input-546-aba3a94ec0ea> in minMoves2(nums)
      1 def minMoves2( nums):
----> 2     median = sorted((nums)[len(nums) / 2])
      3     print median
      4     return list(abs(num - median) for num in nums)

TypeError: 'int' object is not iterable

In [ ]:

    




    

In [ ]:

    




    

In [ ]:

    




    

In [ ]:

    




    

In [ ]:

    




    

In [ ]:

    




    

In [ ]:

    




    

In [ ]:

    




    

In [ ]:

    




    

In [ ]: