indeed

indeed1.py

'''
moving avg，就是一个stream输入，
给一个int getNow()API获取当前timestamp，
完成两个函数void record(int value)和double getAvg()，
有输入时会自动call record，然后call getAvg()时返回5分钟内的平均值。 
getMedium -> quick select
'''

from collections import deque

class test(object):

    def __init__(self, arg):
        self.q = deque()
        self.sum = 0

    def record(self, input):
        dt = self.getNow
        if isinstance(input, int):
            self.q.append((input, dt))
            self.sum += input
        self.remove_outdate()

    def getAvg(self):
        self.remove_outdate()
        return self.sum / len(self.q)

    def remove_outdate(self):
        for pair in q:
            if pair[1] - dt > 300:
                self.sum -= pair[0]
                self.q.popleft()
'''
写一个函数float sumPossibility(int dice, int target)，
就是投dice个骰子，求最后和为target的概率。
'''
class test2(object):
    def sumPossiblility(self, dice, target):
        self.count = 0
        total = 6 ** dice
        self.dfs(dice, 0, target, 0)

    def dfs(self, dice, trial, target, sum):
        if tiral == dice:
            if sum == target::
                self.count += 1
            return
        for i in range(1, 7):
            self.dfs(dice, tiral + 1, target, sum + i)


'''
git commit的题，也是面经题
第一问给一个commit（node），BFS输出所有commits (nodes)。
第二问，两个commits （nodes），找到他们的最近的公共parent，
就是先BFS一个，然后用map记录下其各个parent到这个commit(node)的距离，
然后BFS第二个commit(node)，碰到在map里的node，就算一个总距离，然后更新最短距离和的点，最后最短距离和的点就是结果了，写完面试官也表示很满意。这个注意解释下BFS的复杂度为什么是O（V+E），他会问为什么不是O(V)之类的。
'''


'''
一道题，大概意思是给一些python代码的rule，
全部符合就是valid的，否则就是invalid的，
给你一段代码（String[]的形式），判断是不是valid。
不难。也问了下怎么优化，细节不太记得了
大家都知道python是没有括号的，让写一个验证python语句是否合法。就是看缩进是不是正确
parse 一段Python代码，根据缩进规则，比如第一行不能有空格，前一行以冒号结尾的话，下一行空格数要比上一行多。。。
'''

'''
dijkstra
'''


'''
存树。用什么办法可以节省空间，如果比较full的tree，
用heap的实现方式。比较sparse的tree就用tree本身。
介于中间的可以用两个数组，一个表示value，一个表示这个节点在第一种表示方式下的index。
http://www.1point3acres.com/bbs/thread-171444-1-1.html
'''

'''
Indeed use python and java to deal with the python python and is for java
然后找到java 和python距离最小的一个，然后输出。在上面就是python and java, 在输出的时候还要输出其前三个和后三个： Indeed use python and java to deal with.
https://tonycao.gitbooks.io/leetcode-locked/content/LeetCode%20Locked/c1.4.html
'''


'''
类似Hash Table with linked list的结构，然后让你写一个function插入一个数，然后继续问删除一个数
'''

'''
给了一个自定义的数据结构，是一个链表，链表的每个节点是一个array，要求实现插入删除操作
linked list，但是每个节点是一个class，class里有linked list node还有size等attribute。让实现插入删除操作
'''

'''
找一个数根到叶子的min cost path
然后变成图再求一次(有向无环图)
'''

'''
求n个有序数组里面出现频率k（这里的定义是在多少个数组出现过）以上的数
heap
http://www.1point3acres.com/bbs/thread-148694-1-1.html
'''

'''
linkedelist中的每个节点里存了个固定长度的数组，
但是数组未必满。进行插入操作的时候，如果要插入的节点的数组满了，
可以考虑新建个节点插当前节点的数组的溢出的元素。
'''

'''
ode就是summary range,给你[1,2,3,5,6,8,10] return "1-3,5-6,8,10"
follow up 有duplicate number怎么办, 问了各种complexity, runtime和space.signature是public string tostring(int[] numbers){....} 
http://www.1point3acres.com/bbs/thread-173601-1-1.html
https://leetcode.com/problems/summary-ranges/
'''

'''
电面：找2个ARRAY的INTERSECTION

ONSITE：

1. WORD DISTANCE I, II, II注意BUG. 鍥磋鎴戜滑@1point 3 acres

2. 如何用ARRAY表示BST，参考HEAP

3. 一个LINKEDLIST OF LINKEDLIST结构，如何插入删除. from: 1point3acres.com/bbs 

'''

def summaryRanges(nums):
    res = []
    if not nums:
        return res
    nums = [nums[0] - 2] + nums + [nums[-1] + 2]
    l = 1
    while l < len(nums) - 1:
        if nums[l] - nums[l - 1] > 1 and nums[l + 1] - nums[l] > 1:
            res.append(str(nums[l]))
            l += 1
        else:
            r = l + 1
            while r < len(nums) and nums[r] - nums[r - 1] == 1:
                r += 1
            res.append('{0}->{1}'.format(nums[l], nums[r - 1]))
            l = r
    return res

def summaryRanges2(nums):
    ranges = []
    for num in nums:
        if not ranges or num - ranges[-1][-1] > 1:
            ranges.append([])
        if not ranges[-1]:
            ranges[-1].append(num)
        elif ranges[-1][0] != num:
            ranges[-1][1:] = [num]
    return ['->'.join(map(str, r)) for r in ranges]


'''
reverse string
'''
def reverse(l, r, charlist):

    while l < r:
        charlist[l], charlist[r] = charlist[r], charlist[l]
        l += 1
        r -= 1

def reverseWords(string):
    reverse(0, len(string) - 1, string)
    left = 0
    for right in range(1, len(string) + 1):
        if right == len(string) or string[right] == '':
            reverse(left, right - 1)
            left = right + 1


'''
http://www.1point3acres.com/bbs/thread-158403-1-1.html
2. reverse string except HTML entity.1point3acres缃�
    eg.  // "1234&euro;" => &euro;4321"
          // "1234&euro" => "orue&4321"
         // "1234&euro;567" => "765&euro;4321". 1poi
'''
def reverseHTML(self, HTML):
    rh = list(HTML[::-1])
    left = 0
    while left < len(rh) - 1:
        if rh[left] == ';':
            while left < len(rh) and rh[left] == rh[left - 1]:
                left += 1
            right = left + 1
            while rh[right] != '&':
                right += 1
            reverse(left, right, rh)
            left = right + 1
        left += 1


'''
问题是输入一组word，找出duplicate. 1point3acres.com/bbs
例如输入 "abc def ghi abc"，输出abc即可
follow up输出最早出现的duplicate，.
输入 "abc def ghi jkl ghi abc"，这里应该输出abc.
http://www.1point3acres.com/bbs/thread-173293-1-1.html
'''

def findduplicate(self, text):
    d = {}
    for word in text.split():
        d[word] = d.get(word, 0) + 1
    return [item[0] for item in filter(lambda x:x[1] > 0, d.items())]

def findfirstduplicate(self, text):
    d = {}
    words = text.split()
    minidx = len(words)
    for idx, word in enumerate(words):
        if word not in d:
            d[word] = idx
        else:
            minidx = min(minidx, d[word])
    if minidx != n:
        return words[minidx]
    else:
        return None

'''
http://www.1point3acres.com/bbs/thread-191589-1-1.html
Given the list [1,[4,[6]]],
return [1,4,6]
给一个list of Iterator 输出 list of int
'''
def bianli(self, l, targetnum, res):
    for iter in l:
        while iter.hasNext():
            id = iter.next()
            d[id] = d.get(id, 0) + 1
            if d[id] >= targetnum:
                res.append(id)

l = [[1, 2, 3], [3, 4, 5], [5, 6, 7]]
list_of_int = [i for i in bianli(l)]


# """
# This is the interface that allows for creating nested lists.
# You should not implement it, or speculate about its implementation
# """
#class NestedInteger(object):
#    def isInteger(self):
#        """
#        @return True if this NestedInteger holds a single integer, rather than a nested list.
#        :rtype bool
#        """
#
#    def getInteger(self):
#        """
#        @return the single integer that this NestedInteger holds, if it holds a single integer
#        Return None if this NestedInteger holds a nested list
#        :rtype int
#        """
#
#    def getList(self):
#        """
#        @return the nested list that this NestedInteger holds, if it holds a nested list
#        Return None if this NestedInteger holds a single integer
#        :rtype List[NestedInteger]
#        """

class NestedIterator(object):

    def __init__(self, nestedList):
        self.stack = nestedList[::-1]
        """
        Initialize your data structure here.
        :type nestedList: List[NestedInteger]
        """


    def next(self):
        """
        :rtype: int
        """
        return self.stack.pop().getInteger()


    def hasNext(self):
        """
        :rtype: bool
        """
        while self.stack:
            top = self.stack[-1]
            if top.isInteger():
                return True
            self.stack = self.stack[:-1] + top.getList()[::-1]
        return False



# Your NestedIterator object will be instantiated and called as such:
# i, v = NestedIterator(nestedList), []
# while i.hasNext(): v.append(i.next())


'''
jobid storage, 就是给你jobid type是long，
然后在64 bit的操作系统里，16gb内存 如何能存下4 Billion个jobid。然后实现expire 和isExpire的操作，这个其实比较次要的 ，更多的是比较open的讨论。
input是一个parent pointer的node，def __init__(self,id): self.parent = [] self.id = id. 第二问 让实现方法 isExpire ,
和expire 但是其实这不是重点，hashmap，大家都能实现，关键是如何用最节省内存的方法存下来，第三题stream 的type是iterator，input是（streams，k）
'''


'''
https://leetcode.com/problems/excel-sheet-column-title/
'''

def int2alpha(self, n):
    res = ''
    while n > 0:
        res += chr((n - 1) % 26 + ord('A'))
        n = (n - 1) // 26
    return res[::-1]

def alpha2int(self, s):
    # 28 AB
    res = 0
    for idx, c in enumerate(s[::-1]):
        res += (ord(c) - ord('A') + 1) * 26 ** idx
    return res

'''
电面
第一题return the intersection of two sorted array, 第二题return the intersection of k sorted array
'''
def intersection(self, a, b):
    if a[0] > b[-1] or a[-1] < b[0]:
        return []
    p1, p2 = 0, 0
    res = []
    while p1 < len(a) and p2 < len(b):
        if a[p1] == b[p2]:
            res += [a[p1]]
            p1 += 1
            p2 += 1
        elif a[p1] < b[p2]:
            p1 += 1
        else:
            p2 += 1
    return res

def k_intersection(self, l):
    # type l: List[List[int]]
    # rtype: List[int]
    n = len(l)
    if n == 1:
        return l[0]
    temp = l[0]
    for i in range(1, n - 1):
        if not temp:
            return []
        temp = self.intersection(temp, l[i])


'''
下午1点45接到电话，在hackerrank上面的。对方两个人，一个人面，一个人听。
问题：
1.问简历，问的很细，问了5分钟。
2.好像没在地里的电面里面看到这个问题。
实现一个ExpiringMap的两个操作，put操作和get操作，超时了取出来为null，没超时就能取出正确的value。. from: 1point3acres.com/bbs 
public void put(K key, V value, long durationMs) {}.鏈枃鍘熷垱鑷�1point3acres璁哄潧
public V get(K key) {}
. 1point 3acres
ex:
// put(k, v, 1000)
// get(k) -> v (less than 1000 ms has passed since put)
// get(k) -> null (more than 1000 ms has passed since put)
'''
from datetime import datetime, timedelta
def put(self, key, value, durationMs):
    self.d[key] = (value, datetime.now(), durationMs)

def get(self, key):
    if datetime.now() - self.d[key][1] > timedelta(milliseconds=d[key][2]):
        return None
    else:
        return self.d[key][0]

'''
number of islands

'''

def islands(grid):
    def sink(i, j):
        if 0 <= i < len(grid) and 0 <= j < len(grid[0]) and grid[i][j] == '1':
            grid[i][j] = '0'
            map(sink, (i, i, i - 1, i + 1), (j - 1, j + 1, j, j))
            return 0
        return 1
    return sum(sink(i, j) for i in range(len(grid)) for j in range(len(grid[0])))


'''
给一段话，里面大概是一些单词还有空格，然后给一个target length，
让在这段话里面有空格的地方添加空格，来让这段话达到target length。
要求是让空格的分布尽量平均。
还是一段话，让找到里面重复的单词。看起来很简单吧，但edge case很多
text = 'word is free'

'''
def targetlength(self, text, targetlength):
    n = len(text)
    if n >= targetlength:
        return text
    words = text.split()
    n_words = len(words)
    n_spaces = n - len(text.strip())
    count, i, p = 0, 0, 0
    d = {}
    while p < n:
        if text[p] != ' ':
            while p < n and text[p] != ' ':
                p += 1
        else:
            while p < n and text[p] == ' ':
                p += 1
                count += 1
            d[i] = count
            i += 1
            count = 0
    myd = [[key, val] for key, val in sorted(d.items(), key=lambda x:x[1])]
    # myd = [(0, 1), (3, 1), (4, 1), (2, 3), (5, 4), (1, 7)]
    # n_spaces = 6
    curmin = myd[0][1]
    p = 1
    while p < len(myd):
        while p < len(myd) and myd[p][1] <= curmin:
            p += 1
        diff = myd[p][1] - curmin
        if diff * p > n_spaces:
            break
        for i in range(p):
            myd[i][1] += diff
        n_spaces -= diff * p
        curmin = myd[p][1]
        p += 1
    diff = n_spaces // (p - 1)
    left = n_spaces % (p - 1)
    while p >= 0:
        p -= 1
        myd[p][1] += diff
        if left > 0:
            myd[p][1] += 1
            left -= 1

def findduplicatewords(self, text):
    d = {}
    for word in text.split():
        d[word] = d.get(word, 0) + 1
    return [item[0] for item in filter(lambda x:x[1] > 1, d.items())]



'''
是n叉树然后求出每一个edge上有weight，求最小路径和，并返回最小路径上的node

'''

def next = []



'''

#quantile
strStr和find top k frequent number,
'''
def findK(self, nums):
    d = {}
    for num in nums:
        d[num] = d.get(num, 0) + 1
    return [item[0] for item in sorted(d.items(), key=lambda x:x[1], reverse=True)][:k]

def findKbucket(self, nums):
    res = []
    d = {}
    for num in nums:
        d[num] = d.get(num, 0) + 1
    freqlist = [[] for _ in range(len(nums) + 1)]
    for key in d:
        freqlist[d[key]] += [key]
    for item in freqlist[::-1]:
        res += item
    return res[:k]

'''

1. Two sum 但只问是否存在. 鐗涗汉浜戦泦,涓€浜╀笁鍒嗗湴
2. Two sum in sorted array, 也只问存在与否
'''
def twosum(nums, target):
    d = {}
    for num in nums:
        if num in d:
            return True
        else:
            d[target - num] = 1
    return False

def twosuminsortedarray(nums, target):
    n = len(nums)
    l, r = 0, n - 1
    while l < r:
        s = nums[l] + nums[r]
        if s == target:
            return True
        elif s > target:
            r -= 1
        else:
            l += 1
    return False


'''
https://leetcode.com/problems/minimum-window-substring/
'''


'''
given a String and a length return the string
回傳長度以內的完整word. 涓€浜�-涓夊垎-鍦帮紝鐙鍙戝竷
如果遇到space 去掉
ex:
' f search   for jobs h'
 01234567890123
n=3 return null;
n=6 or 7 return search
n=13, return search for
'''
def completeword(string, length):
    if length >= len(string):
        return string.split()
    candidates = string[:length].split()
    if string[length] == ' ' or string[length - 1] == ' ':
        return candidates
    else:
        return candidates[:-1]