Only Prime - Algo Meta Top 100

Posted on | In

Reference

. . .

找工小队群里公司面经

  • hong:
    • 华人Wevision旗下小创业公司
      • algo: 岛屿大小, LC621，LC127, LC934
      1. 第一轮就一个算法题：岛屿大小，然后聊了点项目和简历
      2. 第二轮两个算法题：LC621，LC127
      3. 第三轮一个算法一个SD：LC934，短链服务
      4. 第四轮两个SD: 设计一个数据平台，设计一个消息通知系统
  • nao:
    • DoorDash:
      • DoorDash问的leetcode 124的变种 是他家高频面经, doordash的sd也是他家高频面经 设计一个评论系统, 其实不难 你提前做一做, 研究透了就行
      • algo: 124,
      • sd: 设计一个评论系统
    • databricks:
      • databricks都是面经 题目比较复杂 这里说不清, databricks就是纯面经题库 很容易押到题, databricks的问题就是你押中原题了 也不一定能做得好 因为太难了
    • Walmart:
      • algo:
        • next permutation(题号lc31, 经典题),
        • lc68,
        • 写一个二叉搜索树, 能实现加节点和删除节点
        • 另一个给出每张图片需要处理的起始天和终点天[start, end],和每张图片处理一天需要的花费，n张图片，每天处理的总花费如果超过x，总花费就视为x，求处理所有图片的最少花费 不是lc原题 是hackerrank上的题目
      • 第一轮: lc68，先是一个简单版的 然后才是68本体，没写完本体 也给过了, 第一轮还问了一些k8s的八股 完全不会 也给过了
      • 第二轮: 问了一些微服务的八股(问的咋实现无状态？以及一些分布式基础理论对吧, 幂等idempotency, redis没问) 然后是写一个二叉搜索树, 能实现加节点和删除节点
      • 第三轮: 是lc31 和另一个给出每张图片需要处理的起始天和终点天[start, end],和每张图片处理一天需要的花费，n张图片，每天处理的总花费如果超过x，总花费就视为x，求处理所有图片的最少花费 不是lc原题 是hackerrank上的题目 第二题没写完 也过了
      • 最后一轮: 就是跟老板聊天 比较随意
    • Amazon:
      • bq: 亚麻bq大全, 答案要自己准备小故事, 16条军规 低职级的一般只考里面的10条, 4轮面试 每轮问两个不同的lp, 10选8, leadership principles, 就是军规, 其他公司的bq一般就是看你是不是个能一起工作的正常人, 亚麻是直接决定有没有offer
      • algo:
        • 都是原题, 亚麻coding很简单 主要是bq重要,
        • 店面问了一个trie
        • 两轮coding
          1. 一个是简单bfs(类似岛的数量number of islands, 经典中的经典了)
          2. 写一个能O1 add remove getrandom的set
    • okx:
      • 我还面了okx coinbase之后的炒币app第二名, payment组
      • algo: 一轮是lc49, 一轮是lc362
      • sd: sd是设计一个notification system
    • Google:
      • algo:
        • 除了google没人考dp, dp会几个经典的就行了(背包，股票，偷房子, 很多变形), dp难的是给竞赛生的,

Meta面经1

补充内容 (2024-09-11 09:55 +08:00):
今天面完了5轮onsite，3 coding + bq+ sd，下面是面试前我自己整理的地理面经（3月到现在），onsite和电面的题目全在里面。如果时间不多，1～2个月内就面试，你看这一个帖子差不多就够了
面senior的别担心算法，出的题目都是看一眼就知道答案。几年前拿过meta offer，当时还被面了2轮hard，现在算法要求降低很多。

algo

算法题目，下面是leetcode题号:

  • 1 - 100: 7, 19, 21, 23, 26, 31, 34, 39, 43, 50, 56, 60, 62, 65, 71, 76, 79, 88
  • 101 - 200: 116, 121, 125, 127, 129, 133, 138, 140, 146, 162, 190, 199, 200
  • 201 - 400: 207, 210, 215, 219, 224, 227, 236, 249, 266, 283, 295, 301, 314, 317, 332, 339(不是给List，而是给字符串，可以用stack解题), 346, 347, 380
  • 401 - 1000: 408, 426, 435, 437, 438, 443, 447, 494, 499, 523, 528, 543, 560, 658, 680, 721, 739(单调栈的典型应用 www.geeksforgeeks.org), 791, 827, 934, 938, 973, 986, 987
  • Above 1000: 1004, 1047, 1060, 1091, 1123, 1161, 1209, 1216, 1249, 1382, 1539, 1570, 1644, 1650, 1762, 1778

sd

  1. Design a chess game, 要求可以撤回上一步
  2. 游戏leaderboard，需要有global&friends排名。这题准备过 但是面试官侧重点是怎么去sort我是没想到的
    1. 需要返回当前整个游戏的top N player、当前用户的前后N个player
    2. 返回当前用户朋友的top N player、当前用户朋友的前后N个player
  3. Hacker version Web crawler
  4. 有一些限定条件，比如说一万台机器，尽可能让每台机器的load evenly distributed。
  5. Design an Ads Aggregation System (广告点击)
  6. facebook 評論系統: user1 看到某個post1, user1 write comment, user2 看到post2, write comment, 同時要通知user1
  7. design zoom
  8. Design instagram
  9. Design ig auction: 设计一个auction system。 用户可以view current bid price 然就可以bid with higher price。 主要问了如果bid at same‍‍‌‍‍‍‍‌‌‌‍‌‍‌‍‍‍‌‍‌ price 怎么解决conflict。以及怎么scale一个很hot的auction。
  10. ig newsfeed, 怎么处理new post来通知用户的情况
  11. design dropbox. 全程drive对话，自己说哪里是bottleneck，如何解决，面试官的问题都回答上了，后期dive in主要着重于how to chunk large file in detail, get updated file list 的时候如何提高performance，get updated file list的时候有什么edge case吗，如何解决。面试官最后looking very good。
  12. 设计一个抢票系统
  13. trending hashtags: Top K 问题
  14. 设计post的隐私设置
  15. proximity service
  16. price tracker
  17. design camel camel camel
  18. Ticketmaster
  19. deep dive facebook news feed API 包括pagination.. 如何实现at一个人等
  20. design Spotify
  21. Design hotel booking system.
  22. 设计一个streaming service: 需要支持video play、recommendation、subscription
  23. Presence indicator
  24. 设计google map中，选择一个地点，可以拖拽看到周围街景的那个功能。主要问了问怎么hash longtitude/latitude，看看alex xu绿皮书Google map那一章会有帮助。‍‍‌‍‍‍‍‌‌‌‍‌‍‌‍‍‍‌‍‌以及如何降低latency，如何存储image等等。
  25. metrics monitoring
  26. youtube
  27. LeetCode contest platform

bq

  1. conflict with others, xfn conflict
  2. biggest mistake
  3. have you ever broke prod code
  4. most proud project
  5. difficult working re‍‍‌‍‍‍‍‌‌‌‍‌‍‌‍‍‍‌‍‌lationship
  6. conflict when you are right, conflict when you are wrong
  7. feedback from mana‍‍‌‍‍‍‍‌‌‌‍‌‍‌‍‍‍‌‍‌ger: negative feedback, critical feedback you received
  8. What did you learn from your tech lead, what do you want to improve?
  9. 多个task同时进行的时候怎么协调

Binary Tree

lc1650 - Lowest Common Ancestor of a Binary Tree III

Description:

Given two nodes of a binary tree p and q, return their lowest common ancestor (LCA).

Each node will have a reference to its parent node. The definition for Node is below:

1
2
3
4
5
6
class Node {
    public int val;
    public Node left;
    public Node right;
    public Node parent;
}

According to the definition of LCA on Wikipedia: “The lowest common ancestor of two nodes p and q in a tree T is the lowest node that has both p and q as descendants (where we allow a node to be a descendant of itself).”

Example 1:
alt text

1
2
3
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3
Explanation: The LCA of nodes 5 and 1 is 3.

Example 2:
alt text

1
2
3
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output: 5
Explanation: The LCA of nodes 5 and 4 is 5 since a node can be a descendant of itself according to the LCA definition.

Example 3:

1
2
Input: root = [1,2], p = 1, q = 2
Output: 1

Constraints:

  • The number of nodes in the tree is in the range [2, 105].
  • 109 <= Node.val <= 109
  • All Node.val are unique.
  • p != q
  • p and q exist in the tree.

Solution: 

1
2
3
4
5
6
7
8
9
10
// - 其实就变成求两条链表的相交点了, refer to : https://programmercarl.com/面试题02.07.链表相交.html#其他语言版本
// - Two runners and circle track,  same as leetcode-160: https://leetcode.com/problems/intersection-of-two-linked-lists/description/
public Node lowestCommonAncestor(Node p, Node q) {
	Node a = p, b = q;
	while (a != b) {
		a = a == null? q : a.parent;
		b = b == null? p : b.parent;    
	}
	return a;
}

DFS

lc263 - Lowest Common Ancestor of a Binary Tree

lc129 - Sum Root to Leaf Numbers

BFS

lc314 - Binary Tree vertical order traversal

Given the root of a binary tree, return the vertical order traversal of its nodes’ values. (i.e., from top to bottom, column by column).

If two nodes are in the same row and column, the order should be from left to right.

Example 1:

Input: root = [3,9,20,null,null,15,7]
Output: [[9],[3,15],[20],[7]]
Example 2:

Input: root = [3,9,8,4,0,1,7]
Output: [[4],[9],[3,0,1],[8],[7]]
Example 3:

Input: root = [3,9,8,4,0,1,7,null,null,null,2,5]
Output: [[4],[9,5],[3,0,1],[8,2],[7]]

alt text

Constraints:

The number of nodes in the tree is in the range [0, 100].
-100 <= Node.val <= 100

Solution1: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
// - BFS level order traversal, time O(N), space O(N)
    
//     Observation:
    
//     - The column range is continuous, from min to max
    
//     Steps
    
//     - BFS, put `node`, `col` into queue at the same time
//     - Every left child access `col - 1` while right child `col + 1`
//     - This maps `node` into different `col` buckets
//     - Get `col` boundary `min` and `max` on the fly
//     - Retrieve `result` from `cols`

import java.util.Map;
import java.util.Queue;
import java.util.Collections;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Arrays;
import java.util.ArrayList;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class Solution {

    public static List<List<Integer>> verticalOrder(TreeNode root) {
        List<List<Integer>> resultList = new ArrayList<>();
        if (root == null) {
            return resultList;
        }

        Map<Integer, List<Integer>> colToVals = new HashMap<>();
        Queue<TreeNode> nodeQueue = new ArrayDeque<>();
        Queue<Integer> colQueue = new ArrayDeque<>();
        nodeQueue.offer(root);
        colQueue.offer(0);

        int minColIndex = 0;
        int maxColIndex = 0;
        while (!nodeQueue.isEmpty()) {
            TreeNode tempNode = nodeQueue.poll();
            int curCol = colQueue.poll();

            if (colToVals.containsKey(curCol)) {
                List<Integer> curVals = colToVals.get(curCol);
                curVals.add(tempNode.val);
            } else {
                List<Integer> newVals = new ArrayList<>();
                newVals.add(tempNode.val);
                colToVals.put(curCol, newVals);
            }

            // update min, max cols and add current value to corresponding column's list
            minColIndex = Math.min(curCol, minColIndex);
            maxColIndex = Math.max(curCol, maxColIndex);

            // add children for level order traversal
            if (tempNode.left != null) {
                nodeQueue.offer(tempNode.left);
                colQueue.offer(curCol - 1);
            }
            if (tempNode.right != null) {
                nodeQueue.offer(tempNode.right);
                colQueue.offer(curCol + 1);
            }
        }

        // build result
        for (int i = minColIndex; i <= maxColIndex; i++) {
            resultList.add(colToVals.get(i));
        }

        return resultList;
    }

    public static void main(String[] args) {
        TreeNode testTree = new TreeNode(3);
        testTree.left = new TreeNode(9);
        testTree.right = new TreeNode(20);
        testTree.right.left = new TreeNode(15);
        testTree.right.right = new TreeNode(7);
        List<List<Integer>> result = verticalOrder(testTree);
        System.out.println(result);

    }
}

Solution2:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

class Solution {

    private int minVerticalColIndex = 0;
    private int maxVerticalColIndex = 0;

    public List<List<Integer>> verticalTraversal(TreeNode root) {
        // use dfs to solve this problem
        List<List<Integer>> resultList = new ArrayList<>();
        if (root == null) {
            return resultList;
        }

        Map<Integer, List<Integer>> colToVals = new HashMap<>();
        
        dfs(root, 0, colToVals);
        
        // System.out.println("colToVals = ");
        // System.out.println(colToVals);

        for (int i = this.minVerticalColIndex; i <= this.maxVerticalColIndex; i++) {
            resultList.add(colToVals.get(i));
        }
        // System.out.println("resultList = ");
        // System.out.println(resultList);
        return resultList;
    }

    private void dfs(TreeNode node, int curCol, Map<Integer, List<Integer>> colToVals) {
        if (node == null) {
            return;
        }

        if (curCol < this.minVerticalColIndex) {
            this.minVerticalColIndex = curCol;
        }
        if (curCol > this.maxVerticalColIndex) {
            this.maxVerticalColIndex = curCol;
        }

        if (colToVals.containsKey(curCol)) {
            List<Integer> curVals = colToVals.get(curCol);
            curVals.add(node.val);
        } else {
            List<Integer> newVals = new ArrayList<>();
            newVals.add(node.val);
            colToVals.put(curCol, newVals);
        }

        dfs(node.left, curCol - 1, colToVals);
        dfs(node.right, curCol + 1, colToVals);
    }
}

lc199 - Binary Tree Right Side View

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> resultList = new ArrayList<Integer>();
        if (root == null ) {
            return resultList;
        }
        Queue<TreeNode> que = new LinkedList<TreeNode>();
        que.offer(root);

        while (!que.isEmpty()) {
            int len = que.size();
            while (len > 0) {  // 注意这个len, 这里一定要使用固定大小 len，不要使用que.size()，因为que.size是不断变化的
                TreeNode tmpNode = que.poll();
                if (len == 1) {
                    // 层序遍历的时候，判断是否遍历到单层的最后面的元素，如果是，就放进result数组中，随后返回result就可以了。
                    resultList.add(tmpNode.val);
                }

                if (tmpNode.left != null) { que.offer(tmpNode.left); }
                if (tmpNode.right != null) { que.offer(tmpNode.right); }
                len--;
            }
        }

        return resultList;
    }
}

lc543 - diameter-of-binary-tree

BST

lc938 - range-sum-of-bst

lc426 - Convert Binary Search Tree to Sorted Doubly Linked List

  • comments: true
  • difficulty: Medium
  • tags:
    • Stack
    • Tree
    • Depth-First Search
    • Binary Search Tree
    • Linked List
    • Binary Tree
    • Doubly-Linked List

Convert a Binary Search Tree to a sorted Circular Doubly-Linked List in place.

You can think of the left and right pointers as synonymous to the predecessor and successor pointers in a doubly-linked list. For a circular doubly linked list, the predecessor of the first element is the last element, and the successor of the last element is the first element.

We want to do the transformation in place. After the transformation, the left pointer of the tree node should point to its predecessor, and the right pointer should point to its successor. You should return the pointer to the smallest element of the linked list.

 


Example 1:

alt text

alt text

Input: root = [4,2,5,1,3]


Output: [1,2,3,4,5]

Explanation: The figure below shows the transformed BST. The solid line indicates the successor relationship, while the dashed line means the predecessor relationship.

alt text

Example 2:

Input: root = [2,1,3]
Output: [1,2,3]

 


Constraints:


  • The number of nodes in the tree is in the range [0, 2000].

  • -1000 <= Node.val <= 1000

  • All the values of the tree are unique.

Solution: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
/*
// Definition for a Node.
class Node {
    public int val;
    public Node left;
    public Node right;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val,Node _left,Node _right) {
        val = _val;
        left = _left;
        right = _right;
    }
};
*/

class Solution {
    private Node prev;
    private Node head;

    public Node treeToDoublyList(Node root) {
        if (root == null) {
            return null;
        }
        prev = null;
        head = null;
        dfs(root);
        prev.right = head;
        head.left = prev;
        return head;
    }

    private void dfs(Node root) {
        // Since an in-order traversal of a binary search tree gives us a sorted array,
        if (root == null) {
            return;
        }
        dfs(root.left);
        if (prev != null) {
            prev.right = root;
            root.left = prev;
        } else {
            head = root;
        }
        prev = root;
        dfs(root.right);
    }
}

lc270 - Closest Binary Search Tree Value

Given the root of a binary search tree and a target value, return the value in the BST that is closest to the target. If there are multiple answers, print the smallest.

 


Example 1:

alt text

Input: root = [4,2,5,1,3], target = 3.714286
Output: 4

Example 2:

Input: root = [1], target = 4.428571
Output: 1

 


Constraints:


  • The number of nodes in the tree is in the range [1, 104].

  • 0 <= Node.val <= 109

  • -109 <= target <= 109

Solution 1: Recursion

We define a recursive function dfs(node), which starts from the current node node and finds the node closest to the target value target. We can update the answer by comparing the absolute difference between the current node’s value and the target value. If the target value is less than the current node’s value, we recursively search the left subtree; otherwise, we recursively search the right subtree.

The time complexity is $O(n)$, and the space complexity is $O(n)$. Where $n$ is the number of nodes in the binary search tree.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    private int ans;
    private double target;
    private double diff = Double.MAX_VALUE;

    public int closestValue(TreeNode root, double target) {
        this.target = target;
        dfs(root);
        return ans;
    }

    private void dfs(TreeNode node) {
        if (node == null) {
            return;
        }
        double nxt = Math.abs(node.val - target);
        if (nxt < diff || (nxt == diff && node.val < ans)) {
            diff = nxt;
            ans = node.val;
        }
        node = target < node.val ? node.left : node.right;
        dfs(node);
    }
}

Solution 2: Iteration

We can rewrite the recursive function in an iterative form, using a loop to simulate the recursive process. We start from the root node and check whether the absolute difference between the current node’s value and the target value is less than the current minimum difference. If it is, we update the answer. Then, based on the size relationship between the target value and the current node’s value, we decide to move to the left subtree or the right subtree. The loop ends when we traverse to a null node.

The time complexity is $O(n)$, where $n$ is the number of nodes in the binary search tree. The space complexity is $O(1)$.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int closestValue(TreeNode root, double target) {
        int ans = root.val;
        double diff = Double.MAX_VALUE;
        while (root != null) {
            double nxt = Math.abs(root.val - target);
            if (nxt < diff || (nxt == diff && root.val < ans)) {
                diff = nxt;
                ans = root.val;
            }
            root = target < root.val ? root.left : root.right;
        }
        return ans;
    }
}