Google 2015-10-2 MTV 另求教

huanghe0828 发表于 2015-10-13 07:27
请问楼主过了吗？

挂了，今天刚收到的通知。祝大家好运吧~~

bitware 发表于 2015-10-3 16:06
第六道能不能这么做：取1/4，2/4，3/4，4/4这四个数，对每个数，分别找到第一个大于它的数的位置和最后一个 ...

//{1, 2, 3, 4, 5, 6, 6} 这个case可以过吗？

mark.  Thanks a lot !

# 1
# assume it is valid
def get_itinerary(tickets):
    ins = {}
    outs = {}
    cnt = {}
    for s, e in tickets:
        ins[e] = ins.get(e, []) + [s]
        outs[s] = outs.get(s, []) + [e]
        cnt[(s, e)] = cnt.get((s, e), 0) + 1

    start = filter(lambda k : len(outs[k]) - len(ins.get(k, 0)) == 1, outs.keys())[0]
    itinerary = []

    def dfs(k, path):
        path.append(k)
        if len(cnt) == 0:
            itinerary.append(path[:])
        else:
            for n in outs.get(k, []):
                if (k, n) in cnt:
                    dec(k, n)
                    dfs(n, path)
                    inc(k, n)
        path.pop()

    def dec(s, e):
        cnt[(s, e)] -= 1
        if cnt[(s, e)] == 0:
            del cnt[(s, e)]

    def inc(s, e):
        cnt[(s, e)] = cnt.get((s, e), 0) + 1

    dfs(start, [])
    return itinerary

tickets = (('A', 'B'), ('B', 'C'), ('C', 'A'), ('A', 'D'), ('D', 'C'))
print get_itinerary(tickets)

# question 6
import bisect
def find_element_more_than_one_forth(nums):
    return find_element_more_than_half(nums, 0, len(nums) / 2 - 1) or \
            find_element_more_than_half(nums, len(nums) / 2 + 1, len(nums) - 1) or \
             cnt(nums, 0, len(nums) - 1, nums[len(nums) / 2]) > len(nums) / 4

def find_element_more_than_half(nums, low, high):
    return cnt(nums, low, high, nums[(high + low) / 2]) > (high - low + 1) / 2

def cnt(nums, low, high, target):
    return bisect.bisect_right(nums, target, low, high + 1) - bisect.bisect_left(nums, target, low, high + 1)

newlxnewlx 发表于 2015-10-24 18:42
# question 6
import bisect
def find_element_more_than_one_forth(nums):

LZ用的是Java没这福利 谢谢你的代码，学习了~