Postmates | 电面 about leetcode

[tech-cow]

API Design

Walmart Timer

Hashmap

商场开门日期的input，实现一个函数看看在某一天（星期一到星期日）某一个时刻商场是否开门。
难点就在于比如周五，早上九点开到凌晨四点。那么过了凌晨就要算第二天了，这里需要稍微绕一下。

'''
input: '10:00'
output: boolean
'''

class WalmartTimer(object):
    def __init__(self, date, time_string):
        self.date = date
        self.hour = int(time_string.split(':')[0])
        self.min = int(time_string.split(':')[1])
        self.dic = {
            # 0 - 4am | 4 - 12 pm
            1:[(0,240), (960,1440)],
            2:[(0,240), (960,1440)],
            3:[(0,240), (960,1440)],
            4:[(0,240), (960,1440)],
            5:[(0,240), (960,1440)],
            6:[(0,240), (960,1440)],
            7:[(0,240), (960,1440)],
            }


    def time_is_valid(self):
        '''check the input string is a valid time'''
        if self.date not in self.dic: return False
        if self.hour < 0 or self.hour > 24: return False
        if self.min < 0 or self.min > 60: return False
        return True


    def time_conversion(self):
        '''converting the time from "xx:xx" to unique measureable time'''
        return self.hour * 60 + self.min


    def is_open(self):
        '''return if walmart is open at a given time'''
        if not self.time_is_valid(): return False
        time = self.time_conversion()
        open_range = self.dic[self.date]
        for range in open_range:
            if time >= range[0] and time <= range[1]:
                return True
        return False


def main():
    time = ['10:00', '22:10', '13:99', '99:00']
    t1 = WalmartTimer(1, time[0]).is_open() # False
    t2 = WalmartTimer(2, time[1]).is_open() # True
    t3 = WalmartTimer(3, time[2]).is_open() # False
    t4 = WalmartTimer(4, time[3]).is_open()   # False
    t5 = WalmartTimer(100, time[0]).is_open()  # False
    print(t1,t2,t3,t4,t5)



if __name__ ==  '__main__':
    main()

EventHandler

makeRequest 是一个request的API
eventHandler Handles进来的request call

写一个event_handler 的方程，使得makeRequest5秒内只能被访问一次。

// 以下是初始代码 in Javascript.
function makeRequest(payload) {
    console.log({
      data: payload,
      time: new Date().getTime()
    });
}

const eventHandler = function(payload) {
    makeRequest(payload);
}

思路就是用全球变量记录这个request的访问时间。

# 源代码 自己肉的Python版本
from datetime import datetime
import time

class EventHandler(object):
    def __init__(self, time):
        self.time = time
        self.has_called = False

    def make_request(self, payload):
        dic = {
            'data': payload,
            'time': datetime.now().second
        }
        print(dic)

    def event_handler(self, payload):
        if not self.has_called:
            self.make_request(payload)
            self.time = datetime.now().second
            self.has_called = True
        else:
            cur = datetime.now().second
            # print(cur, self.time)
            if cur - self.time > 5:
                self.make_request(payload)
                self.time = cur
            else:
                print('Not so frequent please')

def main():
    event1 = EventHandler(datetime.now().second)
    event1.event_handler('hello')
    event1.event_handler('1')
    time.sleep(1)
    event1.event_handler('2')
    event1.event_handler('3')
    time.sleep(7)
    event1.event_handler('world')
    event1.event_handler('3')
    event1.event_handler('3')
    time.sleep(7)
    event1.event_handler('!')


if __name__ == '__main__':
    main()

[tech-cow]

Algorithm

Median of Two Sorted Arrays

2分

def findMedianSortedArrays(self, nums1, nums2):
    l = len(nums1) + len(nums2)
    if l % 2:  # the length is odd
        return self.findKthSmallest(nums1, nums2, l//2+1)
    else:
        return (self.findKthSmallest(nums1, nums2, l//2) +
        self.findKthSmallest(nums1, nums2, l//2+1))*0.5
    
def findKthSmallest(self, nums1, nums2, k):
    # force nums1 is not longer than nums2
    if len(nums1) > len(nums2):
        return self.findKthSmallest(nums2, nums1, k)
    if not nums1:
        return nums2[k-1]
    if k == 1:
        return min(nums1[0], nums2[0])
    pa = min(k/2, len(nums1)); pb = k-pa  # take care here
    if nums1[pa-1] <= nums2[pb-1]:
        return self.findKthSmallest(nums1[pa:], nums2, k-pa)
    else:
        return self.findKthSmallest(nums1, nums2[pb:], k-pb)

Sort Tuples

Given: 一个List of Tuples
用Tuples里面的第二个元素排序

可以通过sorted里面的key attribute将一个callable变成一个parameter。

版本1

def first_element(tuple):
    return tuple[1]

def sort_by_second(arr):
    return sorted(arr, key=first_element)

t1 = [("Person 1",10), ("Person 2",8), ("Person 3",12), ("Person 4",20)]
print(sort_by_second(t1))

版本2

def sort_by_second(arr):
    return sorted(arr, key=lambda tup: tup[1])

t1 = [("Person 1",10), ("Person 2",8), ("Person 3",12), ("Person 4",20)]
print(sort_by_second(t1))

Dog in Dic

DFS

在一个字典里。给一个value，找寻所有包含此value的key
中间可能有Nested情况

t1 = {
    'a' : 'apple',
    'b' : 'bobb',
    'c' : {'d' : 'dog'},
    'e' : 'dog'
    }

I/P: 'dog'
O/P: ['e', 'c.d']

'''
t1 = {
    'a' : 'apple',
    'b' : 'bobb',
    'c' : {'d' : 'dog'},
    'e' : 'dog'
    }


I/P: 'dog'
O/P: ['e', 'c.d']
'''
class Solution(object):
    def __init__(self):
        self.res = []
        self.stored_dic = {}

    def find_key(self, tar_val, dic, parent_path):
        if not tar_val or not dic: return
        if isinstance(dic, str): return

        for key, val in dic.items():
            cur_path = parent_path + key if not parent_path else parent_path + '.' + key
            if val == tar_val:
                self.res.append(cur_path)
            self.find_key(tar_val, val, cur_path)
        return self.res


def main():
    t1 = {
        'a' : 'apple',
        'b' : 'bobb',
        'c' : {'d' : 'dog'},
        'f' : {'x' : {'z' : {'z' : {'z' : {'z' : {'z' : {'z' : {'z' : {'z' : 'dog', 'e' : 'dog'}}}}}}}}},
        'e' : 'dog'
        }
    a = Solution()
    print(a.find_key('dog', t1, ''))  # ['c,d', 'f,x,z,z,z,z,z,z,z,z', 'e']
    # print(a.stored_dic)

    t2 = {'a' : 'cat'}
    b = Solution()
    print(b.find_key('dog', t2, ''))  # []
    # print(b.stored_dic)


if __name__ == '__main__':
    main()