回复: 3
收起左侧

Snap - L4 VO (January 2022)

|只看干货
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   73% (19)
 
 
26% (7)    👎

2022(1-3月) 工程类 本科 全职@snapchat - 猎头 - Onsite  | 😃 Positive 😐 AverageWaitList | 在职跳槽

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
本帖最后由 tomzhawang 于 2023-2-2 11:13 编辑

Please give me rice :)
"""
You are using a browser to visit web pages.
e.g. page1 -> page2 -> page3 -> page4 -> page5 (single thread page view)

This gives a list like so:
[
    [page1, page2],
    [page2, page3],
    [page3, page4],
    [page4, page5],
]

Now we shuffle the list:
[
    [page2, page3],
    [page1, page2],
    [page4, page5],
    [page3, page4],
]

Return a pair of strings indicating the first and last page you visited:
["page1", "page2"]


FOLLOW UP:
There are some cases where you cannot determine what page you started with:
page1 -> page2 -> page3 -> page4 -> page5 -> page1
You could start at any of the pages

But there are also cases where you can determine where you started

page1 -> page2 -> page3 -> page4 -> page5 -> page1 -> page5 (single thread page view)
Input:
[
    [page3, page4],
    [page4, page5],
    [page1, page2],
    [page2, page3],
    [page5, page1],
    [page1, page5],

]
The only possible answer is ["page1", "page5"] (because the indegree of page 1 < outdegree of page1)
(and the indegree of page 2 >= outdegree of page 2)
Handle this case as well
"""

def firstAndLastPages(pageSequence):
    if not pageSequence or not pageSequence[0]:
        return ["", ""]
    pageToNumInpages = {}
    pageToNumOutpages = {}
    for inpage, outpage in pageSequence:
        pageToNumInpages[outpage] = pageToNumInpages.get(outpage, 0) + 1
        pageToNumOutpages[inpage]  = pageToNumOutpages.get(inpage, 0) + 1
    firstPage = None
    for page in pageToNumOutpages:
        indegree = pageToNumInpages.get(page, 0)
        outdegree = pageToNumOutpages.get(page, 0)
        if (indegree == 0) or (outdegree > indegree):
            firstPage = page
            break
    lastPage = None
    for page in pageToNumInpages:
        indegree = pageToNumInpages.get(page, 0)
        outdegree = pageToNumOutpages.get(page, 0)
        if (outdegree == 0) or (indegree > outdegree):
            lastPage = page
            break
    return [firstPage, lastPage]



------------------

# You are given a n x n array of integers where each position contains a 1 or 0.
# 1 represents land and 0 represents water.
# You walk from the top of the input to the bottom using the shortest land path.
# You can move up, down, left or right (no diagonal movements).
#
# Modify the array so that every cell not on the shortest land path is water.
"""
input = [
    [1,0,0,1,0],
    [1,1,1,1,0],
    [1,0,1,0,0],
    [0,1,1,0,1],
    [0,1,0,0,0]
]

output = [
    [0,0,0,1,0],
    [0,0,1,1,0],
    [0,0,1,0,0],
    [0,1,1,0,0],
    [0,1,0,0,0]
]
"""


#  Part 2: Now you are given a 2D array of integer where each position contains 0-9.
#
#  The number 0 still represents water and values 1-9 represent the cost of
#  traversing that piece of land. Return an array containing the land used in the
#  lowest cost path.
#  E.g.
#  int[][] input = {
#    {2,0,0,1,0},
#    {2,0,1,1,0},
#    {2,0,1,0,0},
#    {2,0,1,1,1},
#    {2,0,0,2,0}
#  };

#  int[][] output = {
#    {0,0,0,1,0},
#    {0,0,1,1,0},
#    {0,0,1,0,0},
#    {0,0,1,1,0},
#    {0,0,0,2,0}
#  };
#
#  This is the lowest cost path (cost = 8).


def shortestPath(grid):
    if not grid or not grid[0]:
        return grid
    level = [] #List<Tuples<row, col, pathSoFar: List[(row, col)]>>
    R = len(grid)
    C = len(grid[0])
    directions = ((0, 1), (0, -1), (1, 0), (-1, 0))
    cellToParentInTheClosestPath = {} # Map<(row, col) of current, (row, col) of parent>
    for col in range(C):
        if grid[0][col] == 1:
            level. append((0, col))
            cellToParentInTheClosestPath[(0, col)] = None
    rowOfBottom = -1
    colOfBottom = -1
    while level:
        #BFS to the bottom
        nextLevel = []
        for row, col in level:
            if row == R - 1: # You
您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限查看其他获取积分的方式
      nextCol = col + dc
                if 0 <= nextRow < R and 0 <= nextCol < C and grid[nextRow][nextCol] != 0 and (nextRow, nextCol) not in cellToParentInTheClosestPath:
                    # cellToParentInTheClosestPath[(nextRow, nextCol)] = (row, col)
                    minCostToNextCell = grid[nextRow][nextCol] + smallestDist
                    heappush(heap, (minCostToNextCell, nextRow, nextCol, row, col))

    cellsInTheShortestPath = set()
    if rowOfBottom != -1:
        current = (rowOfBottom, colOfBottom)
        while current != (None, None):
            cellsInTheShortestPath.add(current)
            current = cellToParentInTheClosestPath[current]
    for row in range(R):
        for col in range(C):
            if (row, col) not in cellsInTheShortestPath:
                grid[row][col] = 0
    return grid



----

The System Design was to design a password login app. It should support lockout, changing passwords, logging in, and login history lookup.

----

The last coding question was a topological sort.

评分

参与人数 10大米 +34 收起 理由
liu8626921 + 1 赞一个
coasting + 1 给你点个赞!
fay1224 + 1 很有用的信息!
a111d + 1 给你点个赞!
ff12 + 1 给你点个赞!

查看全部评分


上一篇:Tiktok面经
下一篇:催来了两个月前面完的字节的拒信
fay1224 2023-2-8 08:13:43 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   94% (328)
 
 
5% (20)    👎
楼主过了吗
回复

使用道具 举报

coasting 2023-2-19 22:32:30 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (2)
 
 
0% (0)    👎
OP, the answer for the first question first part should be ["page1", "page5"] if it's the first and last pages right?
回复

使用道具 举报

 楼主| tomzhawang 2023-2-21 04:45:14 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   73% (19)
 
 
26% (7)    👎
coasting 发表于 2023-2-19 06:32
OP, the answer for the first question first part should be ["page1", "page5"] if it's the first and  ...

Yeah. That's right.
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表