Airbnb | 电面

[tech-cow]

No description provided.

[tech-cow]

755. Pour Water

类型：Brute Force
Time Complexity: O(n^2)
Space Complexity O(1)

Assumptions
水先往左，再往右，最后中间
两边有无限高的墙挡着
水滴是一滴一滴的，不能分为小数，所以一滴水会一直往左走到尽头（其实是不符合物理规则的但理他呢。。）

def pour_water(heights, location, water):
    waters = [0] * len(heights)
    while water > 0:
        left = location - 1
        while left >= 0:
            if heights[left] + waters[left] > heights[left + 1] + waters[left + 1]:
                break
            left -= 1

        if heights[left + 1] + waters[left + 1] < heights[location] + waters[location]:
            location_to_pour = left + 1
        else:
            right = location + 1
            while right < len(heights):
                if heights[right] + waters[right] > heights[right - 1] + waters[right - 1]:
                    break
                right += 1

            if heights[right - 1] + waters[right - 1] < heights[location] + waters[right - 1]:
                location_to_pour = right - 1
            else:
                location_to_pour = location
        waters[location_to_pour] += 1
        water -= 1

        max_height = max(heights)
        res = []
        for h in range(max_height, -1, -1):
            temp = []
            for i in range(len(heights) ):
                if heights[i] + waters[i] < h:
                    temp.append(' '),
                elif heights[i] < h <= heights[i] + waters[i]:
                    temp.append('w'),
                else:
                    temp.append('+'),
            res.append(temp)
    print(res[:-1])

pour_water([3,0,3], 1, 2)

269. Alien Dictionary

类型：Topological Sort + BFS
Time Complexity: 建图 O(n * k) where k is size of word + Topological Sorting O(n)
Space Complexity O(n) 字典

这题的突破口是纵向的字典顺序，是有一个pre-requirement的概念，和Topological是一样的。
找到纵向规律，之后就是两步，建图+Topological Sort

from collections import defaultdict, deque

class Solution(object):
    def alienOrder(self, words):
        graph, indeg = self.make_graph(words)
        return self.topological_sort(graph, indeg)

    def make_graph(self, words):
        graph, indeg = {}, defaultdict(int)
        
        #Creating Graph
        for word in words:
            for ch in word:
                if ch not in graph:
                    graph[ch] = set()
        
        for i in range(len(words) - 1):
            for j in range(min(len(words[i]), len(words[i + 1]))):
                cur_word, next_word = words[i], words[i + 1]
                if cur_word[j] != next_word[j]:
                    graph[cur_word[j]].add(next_word[j])
                    break
        
        #Creating indeg
        for node in graph:
            for neighbor in graph[node]:
                indeg[neighbor] += 1
        
        return graph, indeg
    
    
    def topological_sort(self, graph, indeg):
        q = deque([node for node in graph if indeg[node] == 0])
        res = ""
        while q:
            node = q.popleft()
            res += node
            for neighbor in graph[node]:
                indeg[neighbor] -= 1
                if indeg[neighbor] == 0:
                    q.append(neighbor)
        
        # Edge Check on Cycle
        if len(res) == len(graph):
            return res
        else:
            return ""

787. Cheapest Flights Within K Stops

类型：Djikstras
Time Complexity O()
Space Complexity O()

Djikstras No Pruning

from collections import defaultdict
from heapq import heappush, heappop
class Solution(object):
    def findCheapestPrice(self, n, flights, src, dst, K):
        flight_map = defaultdict(list)
        for start, end, price in flights:
            flight_map[start].append((end, price))
        
        heap = [(0, -1, src)]  # Price | Stops | City
        
        while heap:
            cur_price, stops, city = heappop(heap)
            if stops > K: continue
            if city == dst: #immediately return because dilkstra always finds lowest distance
                return cur_price
            for neighbor, neighbor_price in flight_map[city]:
                heappush(heap, (cur_price + neighbor_price, stops + 1, neighbor))
        return -1

Djikstras Pruning

剪枝部分：

1. 当现有Stops超过Target Stops
2. 当到达邻居最小的Price小于我们现在即将到达他的Price

from collections import defaultdict
from heapq import heappush, heappop
class Solution(object):
    def findCheapestPrice(self, n, flights, src, dst, K):
        flight_map = defaultdict(list)
        for start, end, price in flights:
            flight_map[start].append((end, price))
        
        heap = [(0, -1, src)]  # Price | Stops | City
        
        min_price = defaultdict(lambda: float("inf"))
        max_stops = defaultdict(int)
        
        while heap:
            cur_price, stops, city = heappop(heap)
            min_price[city] = min(min_price[city], cur_price)
            max_stops[city] = max(max_stops[city], stops)
            if stops > K: continue
            if city == dst: 
                return cur_price
            for neighbor, neighbor_price in flight_map[city]:
                if min_price[neighbor] > (cur_price + neighbor_price) or max_stops[neighbor] > (stops + 1):
                    heappush(heap, (cur_price + neighbor_price, stops + 1, neighbor))
        return -1

File System

类型：API + Hash
Time Complexity O(N)
Space Complexity O(N)

API Design
   create(path, value)
   set(path, value)
   get(path)
   watch(path, callback)

 Example
 > create("/a",1)
 > get("/a") //得到1
 > create("/a/b",2)
 > get("/a/b") //得到2
 > create("/c/d",1) //Error，因为它的上一级“/c”并不存在
 > get("/c") //Error,因为“/c”不存在

 * follow up是写一个watch函数，比如watch("/a",new Runnable(){System.out.println("helloword");})后，
 * 每当create("/a/b"，1) 等在/a之下的目录不产生error的话，都会执行绑在“/a”上的callback函数
 *
 * 比如 watch("/a",System.out.println("yes"))
 * watch("/a/b",System.out.println("no"))
 * 当create("/a/b/c",1)时，两个callback函数都会被触发，会output yes 和no
 *
 * NOTE: 这里用的Runnable会一直运行不停，Runnable用得不熟表示不知道怎么停下来，就用System.exit(0)测试了

class FileSystem(object):
    def __init__(self):
        self.path_dic = {}
        self.callback_dic = {}

    def create(self, path, value):
        if path in self.path_dic:
            return False
        path_prefix = '/'.join(path.split('/')[:-1])

        if path_prefix != '' and path_prefix not in self.path_dic:
            return False

        self.path_dic[path] = value
        return True

    def set(self, path, value):
        if path not in self.path_dic:
            return False
        # print(value)
        self.path_dic[path] = value

        # Callback for all previous path entry
        path_str = ''
        for path in path.split('/')[1:]:  #start from index 1, because index 0 will be empty
            path_str = path_str + '/' + path
            if path_str in self.callback_dic:
                self.callback_dic[path_str]()
        return True

    def get(self, path):
        if path not in self.path_dic:
            return None
        return self.path_dic[path]


    def watch(self, path, has_path):
        '''
        @param has_path: callback function
        '''
        if path not in self.path_dic:
            return False
        self.callback_dic[path] = has_path
        return True


def foo():
    print("yes")

fs = FileSystem()
print(fs.create("/a/b", 1)) #False
print(fs.create("/a", 2))   #True
print(fs.create("/a/b", 3)) #True
print(fs.get("/a/b")) #3
print(fs.set("/a/b",9))#True	
print(fs.get("/a/b")) #9
print(fs.get("/a/b/c")) #None
print(fs.create("/a/b/c",34)) #True
fs.watch("/a/b", foo) #True + callback
print(fs.set("/a/b",1))
print(fs.get("/a/b"))
fs.watch("/a", foo)
print(fs.set("/a/b",6))
print(fs.get("/a/b"))

Collatz Conjecture

类型：Recursion + Hash
Time Complexity O(?)
Space Complexity O(?)

1. 對於1到n的每一個數，都計算一遍（一個for迴圈）。
2. 對於每一個數，用以上公式計算step數。
3. 在每一個for迴圈結束前，用max來拿到/記錄當前最大的步數，以及這個步數所對應的數。
4. 最後，return那個最大步數所對應的數字。

-> 邊界條件，如果給的數小於1，return 0. 如果給的數等於1，return 1.
-> 這道題有兩種寫法，一種是iteration，一種是recursion。
我自己寫是用iteration寫的，然後給的參考程式碼是用recursion寫的，儘量保證兩種都會。
-> 在參考程式碼裡有一種優化寫法。參考程式碼定義了一個hashmap作為全域性變數，然後，
對於每一個[1, n]中的數，都把它和它最後的step數記錄到這個hashmap裡。
然後在recursion的計算過程中，在計算每個數之前，先check這個數是否在hashmap裡有過歷史記錄，
如果有這個歷史記錄，就可以直接用hashmap裡的結果，而不是去再算一遍。
這樣以增加空間complexity為代價，略微提高了時間complexity。

def get_longest_step(n):
    if n < 1: return 0
    res = float('-inf')
    dic = {}
    #Ask interviewer, range from 0 - 6? or 1 - 7
    for i in range(1, n + 1):
        step = get_step(i, dic)
        dic[i] = step
        res = max(res, step)
    print(dic)
    return res


def get_step(n, dic):
    if n <= 1: return 1
    if n in dic: return dic[n]
    if n % 2 == 0: return 1 + get_step(n // 2, dic)
    return 1 +  get_step(n * 3 + 1, dic)

print(get_longest_step(7))

336. Palindrome Pairs

类型：Hash
Time Complexity O(?)
Space Complexity O(?)

def palindromePairs(words):
    # word to index pair
    dic = {word: i for i, word in enumerate(words)}
    res = []
    for word, k in dic.items():
        n = len(word)
        for j in range(n+1):
            prefix = word[:j]
            suffix = word[j:]
            if is_pali(prefix):
                reversed_half = suffix[::-1]
                if reversed_half != word and reversed_half in dic:
                    res.append([dic[reversed_half],  k])
            # j != n handle edge cases
            if j != n and is_pali(suffix):
                reversed_half = prefix[::-1]
                if reversed_half != word and reversed_half in dic:
                    res.append([k, dic[reversed_half]])
    return res

def is_pali(word):
  return word == word[::-1]

print(palindromePairs(["abcd","dcba","lls","s","sssll"]))   #[[0,1],[1,0],[3,2],[2,4]]

Sliding Puzzle

Manhattan Distance

from heapq import heappop, heappush
def auto_play(board):
    m, n = len(board), len(board[0])
    x, y = 0, 0
    for i in range(m):
        for j in range(n):
            if board[j] == '0':
                x, y = i, j

    init_board = ''.join(''.join(row) for row in board)
    heap = [(get_distance(x, y), x, y, init_board)]
    visited = set()
    count = 0

    while heap:
        _, x, y, cur = heappop(heap)
        if cur in visited:
            continue
        visited.add(cur)
        count += 1
        print(count, ' ' , cur)
        if cur == '123456780':
            return True

        # Direction Check
        for dx, dy in zip((1, -1, 0, 0), (0, 0, 1, -1)):
            # Edge/Boundry
            if x + dx < 0 or x + dx > m - 1 or y + dy < 0 or y + dy > n - 1: continue

            # DFS
            new_board = move_dir(cur, x, y, x + dx, y + dy)
            heappush(heap, (get_distance(x + dx, y + dy), x + dx, y + dy, new_board))

    return False


def get_distance(x, y):
    return (x - 2) ** 2 + (y - 2) ** 2


def move_dir(cur, x, y, new_x, new_y):
    board = list(cur)
    pos = x * 3 + y
    new_pos = new_x * 3 + new_y
    board[pos], board[new_pos] = board[new_pos], board[pos]
    return ''.join(board)


print(auto_play([['1', '3', '0'], ['4', '2', '5'], ['7','8','6']]))

Preference List

from collections import defaultdict, deque
def preference_list(total_lists):
    graph = defaultdict(set)
    indeg = defaultdict(int)

    #Make Graph
    for one_list in total_lists:
        for i in range(1, len(one_list)):
            graph[one_list[i - 1]].add(one_list[i])

    #Make indegree
    for node in graph:
        for neighbor in graph[node]:
            indeg[neighbor] += 1

    # BFS + Topological Sort
    q = deque([node for node in graph if indeg[node] == 0])
    res = []
    while q:

        node = q.popleft()
        res.append(node)
        for neighbor in graph[node]:
            indeg[neighbor] -= 1
            if indeg[neighbor] == 0:
                q.append(neighbor)
    return res

print(preference_list([[3, 5, 7, 9], [2, 3, 8], [5, 8]])) #[2,3,5,8,7,9]