【面經(jīng)】美團(tuán)-后端開(kāi)發(fā)工程師實(shí)習(xí)-2021.3.19

筆試是統(tǒng)一的 2021-03-13 16:00-18:00 周六，無(wú)論是否內(nèi)推都需要參加。
筆試分為 4 道算法題和 1 道專項(xiàng)題。不細(xì)講

一面 2021.3.19 周五 15.00~16.00

此次面試是17號(hào)約了周四上午，但是面試官有一些緊急的事情，推遲到周五下午

  1. 首先講了一下字節(jié)跳動(dòng)西瓜視頻實(shí)習(xí)項(xiàng)目，然后問(wèn)了點(diǎn)問(wèn)題，期間遇到的一些問(wèn)題以及怎么解決的，
  2. 然后講了一下字節(jié)跳動(dòng)基礎(chǔ)架構(gòu)實(shí)習(xí)項(xiàng)目，他說(shuō)對(duì)這個(gè)蠻感興趣，我就敞開(kāi)說(shuō)了一下我負(fù)責(zé)的部分，以及期間解決的一些第三方庫(kù)toolkit的不兼容bug。
  3. 沒(méi)問(wèn)啥基礎(chǔ)問(wèn)題，直接開(kāi)始兩道算法，題庫(kù)找了一些題
  • 算法題1，二叉樹(shù)的層次遍歷，然后按照層次輸出
二叉樹(shù)的層次遍歷

Tip：一般層次遍歷可以利用隊(duì)列實(shí)現(xiàn)，這里不太行，因?yàn)樾枰R(shí)別層次的轉(zhuǎn)換
一開(kāi)始寫的急，出了很多的bug，他讓我慢點(diǎn)，我說(shuō)沒(méi)找到調(diào)試的地方，就點(diǎn)運(yùn)行來(lái)著，他說(shuō)好像是沒(méi)調(diào)試的地方，可以讓我多提交幾次。最后寫完運(yùn)行通過(guò)。
思想：利用列表，每次遍歷列表，然后把 不是 空 的 child 加入新的列表中。每層完畢后，存儲(chǔ)該層節(jié)點(diǎn)的值。然后繼續(xù)遍歷下一層。

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

#
# 
# @param root TreeNode類 
# @return int整型二維數(shù)組
class Solution:
    def levelOrder(self , root):
        # write code here
        if root is None:
            return []
        res = []
        next_nodes = [root]
        while len(next_nodes) > 0:
            new_next_nodes = []
            for node in next_nodes:
                if node.left:
                    new_next_nodes.append(node.left)
                if node.right:
                    new_next_nodes.append(node.right)
            res.append([n.val for n in next_nodes])
            next_nodes = new_next_nodes
            # print(res)
        return res
    
if __name__ == "__main__":
    root = TreeNode(3)
    root.left = TreeNode(9)
    root.right = TreeNode(20)
    
    node = root.left
    node.left = TreeNode(15)
    node.right = TreeNode(7)
    
    S = Solution()
    print(S.levelOrder(root))
  • 算法題2，鏈表環(huán)入口查找
鏈表環(huán)入口查找

Tips：定義兩個(gè)指針，快指針每次走兩步，慢指針一次走一步，當(dāng)環(huán)存在時(shí)，則快指針一定會(huì)追上慢指針；
追上時(shí)使其中一個(gè)指針指向鏈頭，然后兩個(gè)指針同時(shí)走，則再次追上時(shí)指針的位置為環(huán)開(kāi)始的位置

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

#
#
# @param head ListNode類
# @return ListNode類
#
class Solution:
    def detectCycle(self, head):
        # write code here
        if head is None:
            return None
        l, f = head, head
        while f is not None and f.next is not None:
            l = l.next
            f = f.next.next
            if l == f:
                l = head
                while f != l:
                    f = f.next
                    l = l.next
                return l
        return None

if __name__ == "__main__":
    s = Solution()

    nodes = [1, 2, 3, 4, 5]
    A = ListNode(1)
    cur = A
    for n in nodes[1:]:
        cur.next = ListNode(n)
        cur = cur.next

    res = s.detectCycle(A)
    if res:
        print("True! {}".format(res.val))
    else:
        print("False!")

    nodes = [1, 2, 3, 4, 5]
    A = ListNode(1)
    cur = A
    for n in nodes[1:]:
        cur.next = ListNode(n)
        cur = cur.next
    cur.next = A.next
    s = Solution()
    res = s.detectCycle(A)
    if res:
        print("True! {}".format(res.val))
    else:
        print("False!")

    nodes = [3, 2, 0, -4]
    A = ListNode(1)
    cur = A
    for n in nodes[1:]:
        cur.next = ListNode(n)
        cur = cur.next
    cur.next = A.next
    s = Solution()
    res = s.detectCycle(A)
    if res:
        print("True! {}".format(res.val))
    else:
        print("False!")

    nodes = [0, 1]
    A = ListNode(0)
    cur = A
    for n in nodes[1:]:
        cur.next = ListNode(n)
        cur = cur.next
    cur.next = A
    s = Solution()
    res = s.detectCycle(A)
    if res:
        print("True! {}".format(res.val))
    else:
        print("False!")

輸出
False!
True! 2
True! 2
True! 0

  1. 讓我問(wèn)他一些問(wèn)題
    一面面試官：美團(tuán)大數(shù)據(jù)平臺(tái)，分為實(shí)時(shí)部分和離線部分，這邊的組是實(shí)時(shí)部分

    • 主要工作包含：日志收集，業(yè)務(wù)方的日志上報(bào)到kafka收集，根據(jù)業(yè)務(wù)需求同步到hive等地方；業(yè)務(wù)方利用這邊開(kāi)發(fā)的組件，比如flink之類的實(shí)時(shí)數(shù)據(jù)聚合組件。是面向公司內(nèi)部 ToB 的。
    • 旁邊的組是負(fù)責(zé)實(shí)時(shí)引擎的，實(shí)時(shí)計(jì)算
    • 美團(tuán)后端技術(shù)棧：C++，python，java

  2. 補(bǔ)一個(gè)舍友面試問(wèn)到的題
    10億數(shù)據(jù)找到一個(gè)數(shù)

二面 2021.3.22 周一 16.00~17.00

此次面試是22號(hào)上午 hr 聯(lián)系，直接定了下午4點(diǎn)

  1. 面試官首先自己介紹了一下，是個(gè)小姐姐，在美團(tuán)大數(shù)據(jù)平臺(tái)工作
  2. 自我介紹
  3. 問(wèn)了一下實(shí)習(xí)的兩個(gè)項(xiàng)目，講了很多細(xì)節(jié)，大概花了半小時(shí)。著重問(wèn)了緩存機(jī)制，以及為什么這么做，有沒(méi)有驗(yàn)證，自己的優(yōu)化達(dá)到了什么效果？
  4. 兩段實(shí)習(xí)自己的感受怎么樣，覺(jué)得哪段更體驗(yàn)更好或者收獲更大？
    我覺(jué)得都好，簡(jiǎn)單闡述了一下為什么：第一次擴(kuò)大自己的眼界，第二次是了解一些底層實(shí)現(xiàn)方式，并在生活中有所理解。
  5. 面試官問(wèn)了一個(gè)開(kāi)放性問(wèn)題：如果讓你實(shí)現(xiàn)一個(gè)定時(shí)器，你怎么實(shí)現(xiàn)（就是業(yè)務(wù)方有很多定時(shí)需求，你怎么去實(shí)現(xiàn)調(diào)度，比如 Linux 的 crontab 怎么實(shí)現(xiàn)的）
    我大概說(shuō)了一下 crontab 的實(shí)現(xiàn)方式，其實(shí)是按照分的粒度去輪訓(xùn)。
    面試官問(wèn)：那如果輪訓(xùn)達(dá)不到需求呢？比如你的定時(shí)任務(wù)很多（我也說(shuō)了一下，如果一分鐘都輪訓(xùn)不完本次要執(zhí)行的，那么之后的定時(shí)就得延時(shí)了）
    然后我提出生產(chǎn)者跟消費(fèi)者，生產(chǎn)者負(fù)責(zé)發(fā)送要執(zhí)行的任務(wù)到消息隊(duì)列，消費(fèi)者拿到就去執(zhí)行，并監(jiān)聽(tīng)消息隊(duì)列。
    面試官著重問(wèn)生產(chǎn)者的實(shí)現(xiàn)細(xì)節(jié)？過(guò)程中繼續(xù)復(fù)雜化：如果有一些任務(wù)是每隔5分鐘執(zhí)行呢？如果有一些任務(wù)是每隔倆小時(shí)執(zhí)行呢？如果有一些任務(wù)是最近五天執(zhí)行，之后就不執(zhí)行了呢？
    我最終的思想是：分層級(jí)存一個(gè)列表，每個(gè)元素是一個(gè)隊(duì)列，每個(gè)隊(duì)列分為“分鐘”“小時(shí)”“天”等，比如分的隊(duì)列里面，存3600個(gè)列表，表示每個(gè)分鐘要執(zhí)行的任務(wù)，小時(shí)的隊(duì)列里面存24個(gè)列表，表示每個(gè)小時(shí)要執(zhí)行的任務(wù)。每次遍歷分級(jí)隊(duì)列列表，然后去彈出頂部的任務(wù)列表，發(fā)到消息隊(duì)列之后再添加到隊(duì)尾。

參考：
定時(shí)器有幾種實(shí)現(xiàn)方式？

  • 算法三 最大路徑是多少
最大路徑

首先問(wèn)了怎么存這個(gè)數(shù)據(jù)結(jié)構(gòu)，每個(gè)節(jié)點(diǎn)的實(shí)際物理節(jié)點(diǎn)是幾個(gè)之類的。然后需要自己寫數(shù)據(jù)定義，并傳入函數(shù)
同時(shí)問(wèn)了一下怎么實(shí)現(xiàn)，考慮后先說(shuō)一下自己的思路再實(shí)現(xiàn)。

class TNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


# coding=utf-8

class Solution:
    def __init__(self):
        self.cache = {}

    def A(self, head):
        return self.get_max_path(head, 0, 0)

    def get_max_path(self, node, i, j):
        lm, rm = 0, 0
        cache = self.cache
        name = str(i) + "-" + str(j)
        if name in cache:
            return cache[name]

        if node.left is not None:
            lm = self.get_max_path(node.left, i + 1, j)
        if node.right is not None:
            rm = self.get_max_path(node.right, i + 1, j + 1)
        cache[name] = max(lm, rm) + node.val
        # print(i, j, cache[name])
        return cache[name]


if __name__ == "__main__":
    nodes = [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]]
    cache_node = {}
    for i, nv in enumerate(nodes):
        for j, v in enumerate(nv):
            cache_node[str(i) + "-" + str(j)] = TNode(v)
    for i, nv in enumerate(nodes):
        for j, v in enumerate(nv):
            n, ln, rn = str(i) + "-" + str(j), str(i + 1) + "-" + str(j), str(i + 1) + "-" + str(j + 1)
            node = cache_node[n]
            if ln in cache_node:
                node.left = cache_node[ln]
            if rn in cache_node:
                node.right = cache_node[rn]
    head = cache_node["0-0"]
    s = Solution()
    print(s.A(head))

HR面 2021.3.24 周五 10.00

HR簡(jiǎn)單電話聊了一下，5分鐘左右，問(wèn)了一下大概的情況，問(wèn)我的入職時(shí)間，我有啥別的問(wèn)題。
我問(wèn)了一下，我是不是進(jìn)入的就是大數(shù)據(jù)部門（是的，面試官可能一個(gè)就是我的leader，一個(gè)就是我的總管）
然后問(wèn)了一下基礎(chǔ)情況：
美團(tuán)在望京，實(shí)習(xí)工資每天300，晚上9.30之后打車報(bào)銷，晚上8點(diǎn)之后有餐補(bǔ)30，別的沒(méi)了，對(duì)于北京的同學(xué)沒(méi)有房補(bǔ)
Offer去申請(qǐng)了，大概需要2~3天

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書(shū)系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容