roblox面经汇总

倒序浏览 · 2023-11-11 16:36:13

之前准备roblox的面试，把能搜到的面经都过了一遍，coding都写了出来
附件一个是所有coding，一个是system design和behavior的大杂烩

电面和onsite面到的题都在我自己总结的面经里了，也拿到了offer，可惜最后没有去

希望对之后准备他家的朋友们有用，顺便求点大米，最近又有面试要准备，十分感谢!

update:
复制粘贴，以下！

##################################################################
### 528. Random Pick with Weight
##################################################################
import random
class Solution(object):
def __init__(self, w):
self.cumm_w = [w[0] for _ in range(len(w))]
self.total_w = sum(w)
for i in range(1, len(w)):
self.cumm_w[i] = self.cumm_w[i - 1] + w[i]
# linear search
def pickIndex(self):
num = random.random() * self.total_w
for i, weight in enumerate(self.cumm_w):
if num < weight:
return i
# binary search
def pickIndex(self):
num = random.random() * self.total_w
l, r = 0, len(self.cumm_w) - 1
while l < r:
mid = (l + r) // 2
if num > self.cumm_w[mid]:
l = mid + 1
else:
r = mid
return l
# Your Solution object will be instantiated and called as such:
# obj = Solution(w)
# param_1 = obj.pickIndex()
##################################################################
### 1197. Minimum Knight Moves
##################################################################
from collections import deque
class Solution(object):
# Bidirectional BFS: (max(∣x∣,∣y∣)) ** 2
def minKnightMoves(self, x, y):
offsets = [(1, 2), (2, 1), (-1, 2), (-2, 1),
(1, -2), (2, -1), (-1, -2), (-2, -1)]
origin_queue = deque([(0, 0, 0)])
origin_dis = {(0, 0): 0}
target_queue = deque([(x, y, 0)])
target_dis = {(x, y): 0}
while origin_queue or target_queue:
origin_x, origin_y, origin_step = origin_queue.popleft()
if (origin_x, origin_y) in target_dis:
return origin_step + target_dis[(origin_x, origin_y)]
target_x, target_y, target_step = target_queue.popleft()
if (target_x, target_y) in origin_dis:
return target_step + origin_dis[(target_x, target_y)]
for offset_x, offset_y in offsets:
next_origin_x, next_origin_y = origin_x + offset_x, origin_y + offset_y
next_target_x, next_target_y = target_x + offset_x, target_y + offset_y
if (next_origin_x, next_origin_y) not in origin_dis:
origin_queue.append((next_origin_x, next_origin_y, origin_step + 1))
origin_dis[(next_origin_x, next_origin_y)] = origin_step + 1
if (next_target_x, next_target_y) not in target_dis:
target_queue.append((next_target_x, next_target_y, target_step + 1))
target_dis[(next_target_x, next_target_y)] = target_step + 1
return -1
# BFS
def minKnightMoves(self, x, y):
offsets = [(1, 2), (2, 1), (-1, 2), (-2, 1),
(1, -2), (2, -1), (-1, -2), (-2, -1)]
queue = deque([(0, 0, 0)])
visited = set()
while queue:
pos_x, pos_y, step = queue.popleft()
if pos_x == x and pos_y == y:
return step
visited.add((pos_x, pos_y))
for i, j in offsets:
if (pos_x + i, pos_y + j) in visited:
continue
queue.append((pos_x + i, pos_y + j, step + 1))
return -1
##################################################################
### 207. Course Schedule
##################################################################
from collections import deque
from collections import defaultdict
class Solution(object):
def canFinish(self, numCourses, prerequisites):
"""
:type numCourses: int
:type prerequisites: List[List[int]]
:rtype: bool
"""
inDegree = defaultdict(int)
dependencyMap = defaultdict(list)
for x, y in prerequisites:
inDegree[y] += 1
dependencyMap[x].append(y)
queue = deque()
for i in range(numCourses):
if i not in inDegree:
queue.append(i)
result = 0
while queue:
curr_course = queue.popleft()
result += 1
for neighbor in dependencyMap[curr_course]:
inDegree[neighbor] -= 1
if inDegree[neighbor] == 0:
queue.append(neighbor)
return True if result == numCourses else False
##################################################################
### 210. Course Schedule II
##################################################################
from collections import deque
from collections import defaultdict
class Solution(object):
def findOrder(self, numCourses, prerequisites):
"""
:type numCourses: int
:type prerequisites: List[List[int]]
:rtype: List[int]
"""
in_degree_count = defaultdict(int)
dependency_graph = defaultdict(set)
for prereq in prerequisites:
a, b = prereq[0], prereq[1]
in_degree_count[a] += 1
dependency_graph[b].add(a)
queue = deque()
for i in range(numCourses):
if in_degree_count[i] == 0:
queue.append(i)
order = []
while queue:
course = queue.popleft()
order.append(course)
course_dependency = dependency_graph[course]
for d in course_dependency:
in_degree_count[d] -= 1
if in_degree_count[d] == 0:
queue.append(d)
return order if len(order) == numCourses else []
##################################################################
### 723. Candy Crush
##################################################################
class Solution(object):
def candyCrush(self, board):
"""
:type board: List[List[int]]
:rtype: List[List[int]]
"""
m, n = len(board), len(board[0])
crush_h = self.check_horizontal(board, m, n)
crush_v = self.check_vertical(board, m, n)
while crush_h or crush_v:
self.drop(board, m, n)
crush_h = self.check_horizontal(board, m, n)
crush_v = self.check_vertical(board, m, n)
return board
def drop(self, board, m, n):
for i in range(n):
curr = m - 1
for j in range(m - 1, -1, -1):
if board[j][i] > 0:
board[curr][i] = board[j][i]
curr -= 1
for k in range(curr + 1):
board[k][i] = 0
def check_horizontal(self, board, m, n):
to_crush = False
for i in range(m):
for j in range(n - 2):
if abs(board[i][j]) == abs(board[i][j + 1]) == abs(board[i][j + 2]) != 0:
board[i][j] = board[i][j + 1] = board[i][j + 2] = -abs(board[i][j])
to_crush = True
return to_crush
def check_vertical(self, board, m, n):
to_crush = False
for i in range(n):
for j in range(m - 2):
if abs(board[j][i]) == abs(board[j + 1][i]) == abs(board[j + 2][i]) != 0:
board[j][i] = board[j + 1][i] = board[j + 2][i] = -abs(board[j][i])
to_crush = True
return to_crush
##################################################################
### 348. Design Tic Tac Toe
##################################################################
# Connect 4
class TicTacToe(object):
def __init__(self, n):
self.n = n
self.rows = [0] * n
self.cols = [0] * n
self.diagonal = self.antiDiagonal = 0
def move(self, row, col, player):
curr_player = 1 if player == 1 else -1
self.rows[row] += curr_player
self.cols[col] += curr_player
if row == col:
self.diagonal += curr_player
if row == self.n - col - 1:
self.antiDiagonal += curr_player
if abs(self.rows[row]) == self.n or \
abs(self.cols[col]) == self.n or \
abs(self.diagonal) == self.n or \
abs(self.antiDiagonal) == self.n:
return player
return 0
# def __init__(self, n):
# self.n = n
# self.board = [[0 for _ in range(n)] for _ in range(n)]
# def move(self, row, col, player):
# self.board[row][col] = player
# if self.horizontal_win(row, player) or \
# self.vertical_win(col, player) or \
# self.diagonal_inc_win(col, row, player) or \
# self.diagonal_dec_win(col, row, player):
# return player
# return 0
# def horizontal_win(self, row, player):
# for i in range(self.n):
# if self.board[row][i] != player:
# return False
# return True
# def vertical_win(self, col, player):
# for i in range(self.n):
# if self.board[i][col] != player:
# return False
# return True
# def diagonal_inc_win(self, col, row, player):
# for i in range(self.n):
# if self.board[i][i] != player:
# return False
# return True
# def diagonal_dec_win(self, col, row, player):
# for i in range(self.n):
# if self.board[i][self.n - i - 1] != player:
# return False
# return True
# Your TicTacToe object will be instantiated and called as such:
# obj = TicTacToe(n)
# param_1 = obj.move(row,col,player)
##################################################################
### 212. Word Search II
##################################################################
class Solution(object):
def findWords(self, board, words):
"""
:type board: List[List[str]]
:type words: List[str]
:rtype: List[str]
"""
def backtracking(i, j, parentNode):
letter = board[i][j]
currNode = parentNode[letter]
if "match" in currNode:
matched_words.append(currNode["match"])
currNode.pop("match")
board[i][j] = "#"
for x, y in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
new_i, new_j = i + x, j + y
if new_i < 0 or new_j < 0 or new_i >= m or new_j >= n:
continue
if board[new_i][new_j] not in currNode:
continue
backtracking(new_i, new_j, currNode)
board[i][j] = letter
# optimization: remove leaf node recursively
if not currNode:
parentNode.pop(letter)
return
trie = {}
for word in words:
curr = trie
for w in word:
curr[w] = curr.get(w, {})
curr = curr[w]
curr["match"] = word
m, n = len(board), len(board[0])
matched_words = []
for i in range(m):
for j in range(n):
if board[i][j] in trie:
backtracking(i, j, trie)
return matched_words
##################################################################
### 79. Word Search
##################################################################
class Solution(object):
def exist(self, board, word):
"""
:type board: List[List[str]]
:type word: str
:rtype: bool
"""
def backtracking(x, y, index):
if index == len(word) - 1:
return True
board[x][y] = "#"
for x_offset, y_offset in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
new_x, new_y = x + x_offset, y + y_offset
if new_x < 0 or new_y < 0 or new_x >= m or new_y >= n \
or board[new_x][new_y] != word[index + 1]:
continue
if backtracking(new_x, new_y, index + 1):
return True
board[x][y] = word[index]
return False
m, n = len(board), len(board[0])
for i in range(m):
for j in range(n):
if board[i][j] == word[0] and backtracking(i, j, 0):
return True
return False
##################################################################
### 981. Time Based Key-Value Store
##################################################################
from sortedcontainers import SortedDict
class TimeMap(object):
def __init__(self):
self.kv_map = {}
def set(self, key, value, timestamp):
"""
:type key: str
:type value: str
:type timestamp: int
:rtype: None
"""
if key not in self.kv_map:
self.kv_map[key] = SortedDict()
self.kv_map[key][timestamp] = value
def get(self, key, timestamp):
"""
:type key: str
:type timestamp: int
:rtype: str
"""
if key not in self.kv_map:
return ""
idx = self.kv_map[key].bisect_right(timestamp)
return "" if idx == 0 else self.kv_map[key].peekitem(idx - 1)[1]
# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)
##################################################################
### Key-Value Store w/ Transactions
##################################################################
# GlobalStore is a map which is shared by all the transactions in the stack.
# This is how we achieve a parent-child relationship
from collections import deque
class KVStore(object):
def __init__(self):
self.stack = deque([{}])
def set(self, key, val):
if len(self.stack) == 0:
self.stack.append({})
self.stack[-1][key] = val
def get(self, key):
for i in range(len(self.stack) - 1, -1, -1):
if key in self.stack[i]:
return self.stack[i][key]
return ""
def delete(self, key):
# ?
if len(self.stack) > 0:
self.stack[-1][key] = None
def begin(self):
curr_snapshot = {}
self.stack.append(curr_snapshot)
def commit(self):
#?
last_dic = self.stack.pop()
for k, v in last_dic.items():
self.stack[-1][k] = v
# ??
# curr_snapshot = {}
# self.stack.append(curr_snapshot)
def rollback(self):
if len(self.stack) > 0:
self.stack.pop()
##################################################################
### 162. Find Peak Element (One)
##################################################################
class Solution(object):
def findPeakElement(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
l, r = 0, len(nums) - 1
while l < r:
mid = (l + r) / 2
if nums[mid] > nums[mid + 1]:
r = mid
else:
l = mid + 1
return l
##################################################################
### 162. Find Peak Element (All)
##################################################################
class Solution(object):
# front, end?
# duplicate?
def findAllPeakElement(self, nums):
if len(nums) <= 1:
return nums
result = []
for i in range(len(nums)):
if i == 0:
if nums[i + 1] < nums[i]:
result.append(num[i])
elif i == len(nums) - 1:
if nums[i - 1] < nums[i]:
result.append(nums[i])
else:
if nums[i - 1] < nums[i] > nums[i + 1]:
result.append(nums[i])
return result
# with duplicate
def findAllPeakElementWithDuplicate(nums):
if len(nums) <= 1:
return nums
unique_nums = []
curr, count = nums[0], 1
for i in range(1, len(nums)):
if nums[i] == curr:
count += 1
else:
unique_nums.append((curr, count))
curr, count = nums[i], 1
unique_nums.append((curr, count))
if len(unique_nums) == 1:
return [unique_nums[0][0]] * unique_nums[0][1]
result = []
for j in range(len(unique_nums)):
if j == 0:
if unique_nums[j + 1][0] < unique_nums[j][0]:
result += [unique_nums[j][0]] * unique_nums[j][1]
elif j == len(unique_nums) - 1:
if unique_nums[j - 1][0] < unique_nums[j][0]:
result += [unique_nums[j][0]] * unique_nums[j][1]
else:
if unique_nums[j - 1][0] < unique_nums[j][0] > unique_nums[j + 1][0]:
result += [unique_nums[j][0]] * unique_nums[j][1]
return result
##################################################################
### Top Game
##################################################################
# dict = {"user1": [(1001, xxxxx, join), (1001, xxxxxxxx, quit)],
# "user2": []}
def topGame(logs):
user_game_map = defaultdict(list)
for l in logs:
time, user, game, action = l.split(",")
user_game_map.append((game, time))
game_map = defaultdict(int)
for user, game_events in user_game_map.items():
curr_time = curr_count = 0
games_to_estimate = []
l = 0
while l < len(game_events):
if game_events[l][2] == "join":
if l == len(game_events) - 1 or game_events[l + 1][2] == "join":
games_to_estimate.append(l)
l += 1
else:
if game_events[l][0] == game_events[l + 1][0]:
curr_count += 1
curr_time += game_events[l + 1][1] - game_events[l][1]
game_map[game_events[l][0]] += game_events[l + 1][1] - game_events[l][1]
l += 2
avg = float(curr_time) / float(curr_count)
for index in games_to_estimate:
# grab next event from game_events
# find min of avg and next event time
# add it to game_map
return max in game_map
# dict = {"1001": {"user1": (0, 10), "user2": (0, 5)},
# "1002": {"user1": (0, 15), "user3": (0, 5)},""}
def topGame(logs):
game_user_map = {}
for l in logs:
time, user, game, action = l.split(",")
if game not in game_user_map:
game_user_map[game] = {}
if user not in game_user_map[game]:
game_user_map[game][user] = (-1, 0)
last_timestamp, total_time = game_user_map[game][user]
if action == "join":
last_timestamp = time
else:
last_timestamp = -1
total_time += time - last_timestamp
game_user_map[game][user] = (last_timestamp, total_time)
top_game, max_time = None, -float("inf")
for game, user_map in game_user_map.items():
curr_time = 0
for user_time in user_map.values():
curr_time += user_time[1]
if curr_time > max_time:
top_game = game
max_time = curr_time
return top_game
##################################################################
### 1472. Design Browser History
##################################################################
from collections import deque
class BrowserHistory(object):
def __init__(self, homepage):
self.history = deque()
self.history.append(homepage)
self.curr_index = 0
def visit(self, url):
while len(self.history) > self.curr_index + 1:
self.history.pop()
self.history.append(url)
self.curr_index = len(self.history) - 1
def back(self, steps):
while steps > 0 and self.curr_index > 0:
self.curr_index -= 1
steps -= 1
return self.history[self.curr_index]
def forward(self, steps):
while self.curr_index < (len(self.history) - 1) and steps > 0:
self.curr_index += 1
steps -= 1
return self.history[self.curr_index]
# multi-tab: 写一个新的class去实现openTab，和closeTab
# Your BrowserHistory object will be instantiated and called as such:
# obj = BrowserHistory(homepage)
# obj.visit(url)
# param_2 = obj.back(steps)
# param_3 = obj.forward(steps)
##################################################################
### 33. Search in Rotated Sorted Array
##################################################################
class Solution(object):
def search(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
l, r = 0, len(nums) - 1
while l <= r:
mid = l + (r - l) // 2
if nums[mid] == target:
return mid
elif nums[mid] >= nums[l]:
if nums[l] <= target < nums[mid]:
r = mid - 1
else:
l = mid + 1
else:
if nums[mid] < target <= nums[r]:
l = mid + 1
else:
r = mid - 1
return -1

复制代码

SD
- Design一个fraud侦测service
- 通过run model来说一个user是不是fraud
- Collaborative TODO list
- 要求能handle concurrent editing
- 允许users相互share，共同编辑
- The application should allow a single user or team of users to keep track of a list of tasks to do in the
future. Example:
- 1. John creates a list named "Grocery shopping list”
- 2. John adds task Buy Tomatoes to Grocery Shopping List
- 3. John adds task Buy Onions to Grocery Shopping List
- 4. John completes task Buy Onions from Grocery Shopping List
- 5. John has 1 TODO list with 2 tasks B
- 设计一个checklist application，可以允许多人share并协同工作，需要支持：添加list，添加
item，删除item，标记完成，分享list。考察的比较细致，data model, api design, protocol，
scalability都有考察到，甚至还写了点sql —
thread-899276-1-1.html
- On top of managing todo lists the application should allow collaboration of multiple users on
individual todo lists. Example
- 1. John has 1 TODO list with 2 tasks
- 2. John shares Grocery shopping list with Maria
- 3. Maria adds task Buy Oranges to Grocery shopping list
- 4. Maria completes task Buy Tomatoes from Grocery shopping list
- Design a collaborative to-do list application. 大体要求是多人可以在同一个to-do list里面add
task，或者complete task。其次是不同人有不同的role，从基础的viewer（可以增加或者完成
task），到editor（可以改task名字什么的），到admin（可以创建删除todo list之类的）。讨论
内容有API， data model， database选择，如何把某个client的改动及时同步到别的clients里
面，
一个todo list里面collaborator太多读写流量太大怎么办之类的。
- shared links per 5 min, 1 hour, 24 hours，qps很高。刚开始用heap，后来改用ring buffer做的，但
是俄罗斯面试官几乎在我每说一句话都会问‍ ‌‌‍‌‌‌‍‌‍‌‌‍‍‍‍‍‍ 各种问题，比方da

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限或查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

的作者。所以会产生一些输入[{user1, pay amount:$100, time: 15:00}, {user2, pay amount:$50,
time: 16:00}...]。按照面试官的意思，要求是payment在指定时间的几分钟之内发生吧，如果
出错了要像个办法处理
- Design payment system
- 设计一个payment hold的系统。这个其他面筋也提到过，讲一下其他面筋都没有提到的问
题。第一：QPS 5K，第二：这个系统需要直接cancel payment。这个就需要确定payment
hold API的返回值是什么，如果用了卡夫卡做缓冲会怎么样，NO SQL怎么做sharding等等，
这个地方我答的不太好，很可能就是挂在这里，希望可以帮到后来人。另外也问了一下
payment system怎么跟payment hold配合工作的，需要讲一下payment system的workflow和
DB。
- 设计一个delay transcation system，背景是他们自己的game platform里面的虚拟货币，要求用
户可以设定一个未来的时间来给另一个用户转特定数额的钱，并可以支持cancel还未发生的
transactions，可以assume有一个banking API可以call去真正执行transaction。
- Design a payment scheduling system. 主要要求是可以允许Roblox玩家说给另一个玩家转一定数
量的游戏币，不过要在指定是时间点转（比如3天后，2小时后之类的），然后不用考虑
payment system本身的设计，就假设有个现成的payment API。大方向上像个delayed job
scheduling system，不过有一些特别的细节：（1）发起转账的用户里面的钱得立马扣下；
（2）指定的未来时间可以是10几秒之后，所以定时polling的系统是不行的；（3）发给接收
方的钱的操作可能会有不可重试的错误，比如接收方账户因为用外挂被注销了什么的，所以
其实整个系统其实是个transaction系统，要考虑rollback，以及常见的WAL之类的手段来达到
durability要求。面试官还粗略问了一些API design（REST vs RPC），API security，
notification，idempotency（payment）相关的内容。

WaynePai

好人一生平安

匿名用户-X2UOH *2023-12-8 13:02:25* · 2023-12-8 13:02:25

匿名用户发表于 2023-12-7 20:24
包含了onsite

哦哦感觉他家coding题目看来没有特别多的样子，多谢楼主！

spongeFox · 2023-11-16 05:52:01

感謝樓主!

pumazda · 2023-11-17 02:39:49

好人一生平安

吃瓜群众攒人品

好人一生平安！！

turbo0428

好人一生平安！！

匿名用户-X2UOH *2023-12-8 04:23:24* · 2023-12-8 04:23:24

已加米！请问楼主coding是只是店面吗还是包含了onsite的？谢谢呀

匿名用户-FZMAO *2023-12-8 04:41:50* · 2023-12-8 04:41:50

好人一生平安！！

来自APP · 2023-12-8 12:24:16

匿名用户发表于 2023-12-07 12:23:24
已加米！请问楼主coding是只是店面吗还是包含了onsite的？谢谢呀

包含了onsite

匿名用户-X2UOH *2023-12-10 02:50:52* · 2023-12-10 02:50:52

还想请问一下楼主老看到的karat 面试是什么呀，是针对某些特定职位么，现在是否取消了呢？谢谢！

roblox面经汇总

本帖子中包含更多资源

评分

浏览过的版块