Snap - L4 VO (January 2022)

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 = pageToN

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

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

      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.

楼主过了吗

OP, the answer for the first question first part should be ["page1", "page5"] if it's the first and last pages right?

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

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

Thanks for sharing. Hope you get admitted by your ideal company.

hey :) I hope everyone is happy!

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

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