DEV Community: Wenqi Jiang

1155. Number of Dice Rolls With Target Sum

Wenqi Jiang — Sun, 02 Oct 2022 09:32:00 +0000

Description

You have n dice and each die has k faces numbered from 1 to k.

Given three integers n, k, and target, return the number of possible ways (out of the kn total ways) to roll the dice so the sum of the face-up numbers equals target. Since the answer may be too large, return it modulo 109 + 7.

Example 1:

Input: n = 1, k = 6, target = 3
Output: 1
Explanation: You throw one die with 6 faces.
There is only one way to get a sum of 3.

Example 2:

Input: n = 2, k = 6, target = 7
Output: 6
Explanation: You throw two dice, each with 6 faces.
There are 6 ways to get a sum of 7: 1+6, 2+5, 3+4, 4+3, 5+2, 6+1.

Example 3:

Input: n = 30, k = 30, target = 500
Output: 222616187
Explanation: The answer must be returned modulo 109 + 7.

Constraints:

1 <= n, k <= 30
1 <= target <= 1000

Solutions

class Solution {
public:
    int numRollsToTarget(int n, int k, int target) {
        const int MOD = 1e9 + 7;
        vector<int> f(target + 1, 0);
        f[0] = 1;
        for (int i = 1; i <= n; i++) {// 枚举所有物品
            for (int j = target; j >= 0; j--) { // 枚举体积, 从大到小 
                f[j] = 0;
                for (int u = 1; u <= k & u <= j; u++) {
                    f[j] = (f[j] + f[j - u]) % MOD;
                }
            }
        }
        return f[target];
    }
};

990. Satisfiability of Equality Equations

Wenqi Jiang — Mon, 26 Sep 2022 08:54:05 +0000

Description

You are given an array of strings equations that represent relationships between variables where each string equations[i] is of length 4 and takes one of two different forms: "xi==yi" or "xi!=yi".Here, xi and yi are lowercase letters (not necessarily different) that represent one-letter variable names.

Return true if it is possible to assign integers to variable names so as to satisfy all the given equations, or false otherwise.

Example 1:

Input: equations = ["a==b","b!=a"]
Output: false
Explanation: If we assign say, a = 1 and b = 1, then the first equation is satisfied, but not the second.
There is no way to assign the variables to satisfy both equations.

Example 2:

Input: equations = ["b==a","a==b"]
Output: true
Explanation: We could assign a = 1 and b = 1 to satisfy both equations.

Constraints:

1 <= equations.length <= 500
equations[i].length == 4
equations[i][0] is a lowercase letter.
equations[i][1] is either '=' or '!'.
equations[i][2] is '='.
equations[i][3] is a lowercase letter.

Solutions

Solution 1

Intuition

Code

class Solution {
private:
    int p[26];

    int find(int x) {
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }
public:
    bool equationsPossible(vector<string>& equations) {
        for (int i = 0; i < 26; i++) {
            p[i] = i;
        }
        for (string& equation : equations) {
            int a = equation[0] - 'a', b = equation[3] - 'a';
            if (equation[1] == '=') {
                p[find(a)] = find(b);
            }
        }

        for (string& equation : equations) {
            int a = equation[0] - 'a', b = equation[3] - 'a';
            if (equation[1] == '!' && find(a) == find(b)) {
                return false;
            }
        }
        return true;

    }
};

Complexity

Time: O(n)
Space: O(1)

1457. Pseudo-Palindromic Paths in a Binary Tree

Wenqi Jiang — Wed, 14 Sep 2022 10:58:27 +0000

Description

Given a binary tree where node values are digits from 1 to 9. A path in the binary tree is said to be pseudo-palindromic if at least one permutation of the node values in the path is a palindrome.

Return the number of pseudo-palindromic paths going from the root node to leaf nodes.

Example 1:

Input: root = [2,3,1,3,1,null,1]
Output: 2 
Explanation: The figure above represents the given binary tree. There are three paths going from the root node to leaf nodes: the red path [2,3,3], the green path [2,1,1], and the path [2,3,1]. Among these paths only red path and green path are pseudo-palindromic paths since the red path [2,3,3] can be rearranged in [3,2,3] (palindrome) and the green path [2,1,1] can be rearranged in [1,2,1] (palindrome).

Example 2:

Input: root = [2,1,1,1,3,null,null,null,null,null,1]
Output: 1 
Explanation: The figure above represents the given binary tree. There are three paths going from the root node to leaf nodes: the green path [2,1,1], the path [2,1,3,1], and the path [2,1]. Among these paths only the green path is pseudo-palindromic since [2,1,1] can be rearranged in [1,2,1] (palindrome).

Example 3:

Input: root = [9]
Output: 1

Constraints:

The number of nodes in the tree is in the range [1, 105].
1 <= Node.val <= 9

Solutions

Solution 1

Intuition

Code

class Solution {
private:
    int res = 0;
    void dfs(int mask, TreeNode* node) {
        if (!node) return;
        mask ^= 1 << node->val;
        dfs(mask, node->left);
        dfs(mask, node->right);
        if (!node->left && !node->right) {
            if (mask == 0 || (mask & (mask - 1)) == 0) res++;
        }
    }
public:
    int pseudoPalindromicPaths(TreeNode* root) {
        dfs(0, root);
        return res;
    }
};

Complexity

Time: O(n)
Space: O(h)

1383. Maximum Performance of a Team

Wenqi Jiang — Sun, 11 Sep 2022 20:47:57 +0000

Description

You are given two integers n and k and two integer arrays speed and efficiency both of length n. There are n engineers numbered from 1 to n. speed[i] and efficiency[i] represent the speed and efficiency of the ith engineer respectively.

Choose at most k different engineers out of the n engineers to form a team with the maximum performance.

The performance of a team is the sum of their engineers' speeds multiplied by the minimum efficiency among their engineers.

Return the maximum performance of this team. Since the answer can be a huge number, return it modulo 109 + 7.

Example 1:

Input: n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 2
Output: 60
Explanation: 
We have the maximum performance of the team by selecting engineer 2 (with speed=10 and efficiency=4) and engineer 5 (with speed=5 and efficiency=7). That is, performance = (10 + 5) * min(4, 7) = 60.

Example 2:

Input: n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 3
Output: 68
Explanation:
This is the same example as the first but k = 3. We can select engineer 1, engineer 2 and engineer 5 to get the maximum performance of the team. That is, performance = (2 + 10 + 5) * min(5, 4, 7) = 68.

Example 3:

Input: n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 4
Output: 72

Constraints:

1 <= k <= n <= 105
speed.length == n
efficiency.length == n
1 <= speed[i] <= 105
1 <= efficiency[i] <= 108

Solutions

Solution 1

Intuition

Code

class Solution {
public:
    int maxPerformance(int n, vector<int>& speed, vector<int>& efficiency, int k) {
        int MOD = 1e9 + 7;
        vector<pair<int, int>> engineers;
        for (int i = 0; i < n; i++)
            engineers.push_back({ speed[i], efficiency[i] });
        // sort engineers by their efficiencies, from big to small
        sort(engineers.begin(), engineers.end(), [&](auto& a, auto& b) {
            return a.second > b.second;
            });
        // store their speed, the slowest is on top, could be pop
        priority_queue<int, vector<int>, greater<int>> pq;
        long speedSum = 0, res = 0;
        for (auto& [s, e] : engineers) {
            pq.push(s);
            speedSum += s;
            if (pq.size() > k) {
                // pop the slowest guy
                speedSum -= pq.top();
                pq.pop();
            }
            // note because we sort engineers by their efficiencies, so the e is the smaller one
            res = max(res, speedSum * e);
        }
        return res % MOD;
    }
};

Some Tips for UCAT

Wenqi Jiang — Sat, 13 Aug 2022 14:51:03 +0000

Evaluating Arguments
- After reading the question, and any text with it, you’ll be provided with a choice of
  
  arguments. You’ll then have to choose which is the best/most relevant/valid
  
  argument.
- Be presented with data, graphs, text which you must interpret and decide which
  
  conclusions follow.
Deductive Reasoning

⚬ You’ll be provided with an opening statement, and you’ll have to decide which of the

conclusion statements you are provided with follows.
Statistical & Figural Reasoning

⚬ Here, you need to be able to make conclusions based on data (numbers and graphs) provided to you.

EVALUATING ARGUMENTS

Recognizing assumptions & strong arguments
Based on facts and evidence
- Not based on emotion, opinion, subjective views or ASSUMPTIONS!
  - I think
  - In my experience
Directly connected to subject matter
Mentions all parts of the subject matter
Pay attention to the wording of the argument:
- must = will happen
- might/could = can happen but you don't know if it is likely or unlikely
Interpreting information and drawing conclusions
- Written passages, graphs, data, charts
- Some charts & graphs might include a lot of information, focus on what the question refers to
- Drag and drop your answer
- Can be multiple correct answer options

DEDUCTIVE REASONING

Deductive reasoning is a logical process in which a conclusion is drawn based on multiple premises that are generally assumed to be true.

Example:

Premise → In a classroom there are 2 students sitting on chairs. There are two students sitting on the floor.

Conclusion→There are 4 students in the classroom.

Logic puzzles and syllogisms are based on multiply steps/layers of deductive reasoning.

Syllogisms contain at least two statements and a list of conclusions. You have to work out if the conclusions logically follow.
Use your whiteboard/scratch pad, Venn diagrams and abbreviations to help you.
Pay attention to the language used e.g. all, some, this, many

STATISTICAL & FIGURAL REASONING

Venn Diagram

Choose the correct Venn diagram based on the text given
Implicit Venn diagrams
Choose the correct answer using the Venn diagram provided

Probability

Revise basic probability
Note whether you are using independent or non-independent probability
Use probability trees to help you
Be able to convert quickly between rations, % and fractions

VERBAL REASONING

Forget all prior knowledge! Just concentrate on what logically follows from the passage. Act
like you are an alien who knows nothing about earth.

Strategy

Read first couple of sentences of passage & the first question - note the key words
Skim read the passage looking for key words
Read the sentence before and after each keyword
Scan the remainder of the passage for more instances of the key words
If you find more instances of the key words, repeat step 3
Choose your answer

DEFINITION OF TERMS

Target reading – only read what is necessary to answer the question, scanning the text looking for the key words

Key words – words in a given item that stand out and are as specific as possible to that item e.g. date or place.

Watch out for synonyms! Just because the key word/phrase isn’t there it doesn’t mean the answer is can’t tell.

over estimated = less than expected

Language

EXTREME

the best
no longer used
biggest
tallest
full
most
never
certainly
must
will/must happen
always

MILD

one of the best
rarely used
could
might
occasionally
can
sometimes
maybe
frequently

Look out for reverse questions: Which of the following is incorrect/not true? What statement cannot be inferred from the passage?
Be careful of discrepancies in text and question e.g UK & England
Key word synonyms e.g quarterly, 3 months, Jan-March, 1/4
Don't be a perfectionist - once you have the answer, move on.

210. Course Schedule II

Wenqi Jiang — Wed, 03 Aug 2022 21:03:43 +0000

Description

There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take course ai.

For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1.

Return the ordering of courses you should take to finish all courses. If there are many valid answers, return any of them. If it is impossible to finish all courses, return an empty array.

Example 1:

Input: numCourses = 2, prerequisites = [[1,0]]
Output: [0,1]
Explanation: There are a total of 2 courses to take. To take course 1 you should have finished course 0. So the correct course order is [0,1].

Example 2:

Input: numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
Output: [0,2,1,3]
Explanation: There are a total of 4 courses to take. To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0.
So one correct course order is [0,1,2,3]. Another correct ordering is [0,2,1,3].

Example 3:

Input: numCourses = 1, prerequisites = []
Output: [0]

Constraints:

1 <= numCourses <= 2000
0 <= prerequisites.length <= numCourses * (numCourses - 1)
prerequisites[i].length == 2
0 <= ai, bi < numCourses
ai != bi
All the pairs [ai, bi] are distinct.

Solutions

Solution 1

Intuition

DFS

Code

class Solution {
    private static final int WHITE = 1;
    private static final int GRAY = 2;
    private static final int BLACK = 3;

    boolean isPossible;
    Map<Integer, Integer> color;
    Map<Integer, List<Integer>> adjList;
    List<Integer> topologicalOrder;

    private void init(int numCourses) {
        isPossible = true;
        color = new HashMap<>(numCourses);
        adjList = new HashMap<>(numCourses);
        topologicalOrder = new ArrayList<>();
        // By default, all vertices are WHITE
        for (int i = 0; i < numCourses; i++) {
            color.put(i, WHITE);
        }
    }

    private void dfs(int node) {
        // Don't recurse further if we found a cycle already
        if (!isPossible) {
            return;
        }
        // Start the recursion
        color.put(node, GRAY);
        // Traverse on neighboring vertices
        for (Integer neighbor : adjList.getOrDefault(node, new ArrayList<>())) {
            if (color.get(neighbor) == WHITE) {
                dfs(neighbor);
            } else if (color.get(neighbor) == GRAY) {
                // An edge to a GRAY vertex represents a cycle
                isPossible = false;
            }
        }
        // Recursion ends. We mark it as black
        color.put(node, BLACK);
        topologicalOrder.add(node);
    }

    public int[] findOrder(int numCourses, int[][] prerequisites) {
        init(numCourses);
        // Create the adjacency list representation of the graph
        for (int[] prerequisite : prerequisites) {
            int dest = prerequisite[0];
            int src = prerequisite[1];
            List<Integer> lst = adjList.getOrDefault(src, new ArrayList<>());
            lst.add(dest);
            adjList.put(src, lst);
        }
        // If the node is unprocessed, then call dfs on it.
        for (int i = 0; i < numCourses; i++) {
            if (color.get(i) == WHITE) {
                dfs(i);
            }
        }
        int[] order;
        if (isPossible) {
            order = new int[numCourses];
            for (int i = 0; i < numCourses; i++) {
                order[i] = topologicalOrder.get(numCourses - i - 1);
            }
        } else {
            order = new int[0];
        }
        return order;
    }
}

Complexity

Time: O(V+E)
Space: O(V+E)

Solution 2

Intuition

BFS

Code

class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {

        Map<Integer, List<Integer>> adjList = new HashMap<>();
        int[] indegree = new int[numCourses];
        int[] topologicalOrder = new int[numCourses];

        // Create the adjacency list representation of the graph
        for (int[] prerequisite : prerequisites) {
            int dest = prerequisite[0];
            int src = prerequisite[1];
            List<Integer> lst = adjList.getOrDefault(src, new ArrayList<Integer>());
            lst.add(dest);
            adjList.put(src, lst);
            // Record in-degree of each vertex
            indegree[dest] += 1;
        }

        // Add all vertices with 0 in-degree to the queue
        Queue<Integer> q = new LinkedList<Integer>();
        for (int i = 0; i < numCourses; i++) {
            if (indegree[i] == 0) {
                q.add(i);
            }
        }

        int index = 0;
        // Process until the Q becomes empty
        while (!q.isEmpty()) {
            int node = q.remove();
            topologicalOrder[index++] = node;
            // Reduce the in-degree of each neighbor by 1
            if (adjList.containsKey(node)) {
                for (Integer neighbor : adjList.get(node)) {
                    indegree[neighbor]--;
                    // If in-degree of a neighbor becomes 0, add it to the Q
                    if (indegree[neighbor] == 0) {
                        q.add(neighbor);
                    }
                }
            }
        }

        // Check to see if topological sort is possible or not.
        if (index == numCourses) {
            return topologicalOrder;
        }

        return new int[0];
    }
}

class Solution {
public:
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
        vector<vector<int>> g(numCourses);
        vector<int> in(numCourses, 0);
        for (auto& p : prerequisites) {
            int a = p[0], b = p[1];
            // b -> a
            g[b].push_back(a);
            // how many prerequisites need to learn a course?
            in[a] ++;
        }

        queue<int> q;
        // in = 0, means you've already finished the prerequisites, and you can learn this course
        for (int i = 0; i < numCourses; i++)
            if (in[i] == 0) q.push(i);

        vector<int> res;
        while (!q.empty()) {
            int p = q.front();
            q.pop();
            res.push_back(p);
            for (auto& c : g[p]) {
                if (--in[c] == 0) q.push(c);
            }
        }
        if (res.size() == numCourses) return res;
        else return {};
    }
};

Complexity

Time: O(V+E)
Space: O(V+E)

417. Pacific Atlantic Water Flow

Wenqi Jiang — Wed, 03 Aug 2022 13:01:31 +0000

417. Pacific Atlantic Water Flow

Description

There is an m x n rectangular island that borders both the Pacific Ocean and Atlantic Ocean. The Pacific Ocean touches the island's left and top edges, and the Atlantic Ocean touches the island's right and bottom edges.

The island is partitioned into a grid of square cells. You are given an m x n integer matrix heights where heights[r][c] represents the height above sea level of the cell at coordinate (r, c).

The island receives a lot of rain, and the rain water can flow to neighboring cells directly north, south, east, and west if the neighboring cell's height is less than or equal to the current cell's height. Water can flow from any cell adjacent to an ocean into the ocean.

Return a 2D list of grid coordinates result where result[i] = [ri, ci] denotes that rain water can flow from cell (ri, ci) to both the Pacific and Atlantic oceans.

Example 1:

Input: heights = [[1,2,2,3,5],[3,2,3,4,4],[2,4,5,3,1],[6,7,1,4,5],[5,1,1,2,4]]
Output: [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]

Example 2:

Input: heights = [[2,1],[1,2]]
Output: [[0,0],[0,1],[1,0],[1,1]]

Constraints:

m == heights.length
n == heights[r].length
1 <= m, n <= 200
0 <= heights[r][c] <= $10^5$

Solutions

Solution 1

Intuition

from Ocean to land heights[x][y] <= heights[dx][dy]

two types flag, 1 and 2, if two ocean can reach land simultaneous, the flag will be 3

Code

class Solution {
private:
    int m, n;
    int dirs[5] = { 0, 1, 0, -1, 0 };
    vector<vector<int>> state;
    void dfs(int x, int y, int val, vector<vector<int>>& heights) {
        if (state[x][y] & val) return;
        state[x][y] |= val;
        for (int i = 0; i < 4; i++) {
            int dx = x + dirs[i], dy = y + dirs[i + 1];

            if (dx >= 0 && dx < m && dy >= 0 && dy < n && heights[x][y] <= heights[dx][dy]) {
                dfs(dx, dy, val, heights);
            }
        }
    }

public:
    vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
        m = heights.size(), n = heights[0].size();
        state.resize(m, vector<int>(n, 0));
        // top
        for (int i = 0; i < n; i++) dfs(0, i, 1, heights);
        // left
        for (int i = 0; i < m; i++) dfs(i, 0, 1, heights);
        // bottom
        for (int i = 0; i < n; i++) dfs(m - 1, i, 2, heights);
        // right
        for (int i = 0; i < m; i++) dfs(i, n - 1, 2, heights);

        vector<vector<int>> res;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (state[i][j] == 3) res.push_back({ i,j });
            }
        }
        return res;
    }
};

Complexity

Time: O(n)
Space: O(n)

721. Accounts Merge

Wenqi Jiang — Mon, 01 Aug 2022 22:40:27 +0000

Description

Given a list of accounts where each element accounts[i] is a list of strings, where the first element accounts[i][0] is a name, and the rest of the elements are emails representing emails of the account.

Now, we would like to merge these accounts. Two accounts definitely belong to the same person if there is some common email to both accounts. Note that even if two accounts have the same name, they may belong to different people as people could have the same name. A person can have any number of accounts initially, but all of their accounts definitely have the same name.

After merging the accounts, return the accounts in the following format: the first element of each account is the name, and the rest of the elements are emails in sorted order. The accounts themselves can be returned in any order.

Example 1:

Input: accounts = [["John","johnsmith@mail.com","john_newyork@mail.com"],["John","johnsmith@mail.com","john00@mail.com"],["Mary","mary@mail.com"],["John","johnnybravo@mail.com"]]
Output: [["John","john00@mail.com","john_newyork@mail.com","johnsmith@mail.com"],["Mary","mary@mail.com"],["John","johnnybravo@mail.com"]]
Explanation:
The first and second John's are the same person as they have the common email "johnsmith@mail.com".
The third John and Mary are different people as none of their email addresses are used by other accounts.
We could return these lists in any order, for example the answer [['Mary', 'mary@mail.com'], ['John', 'johnnybravo@mail.com'], 
['John', 'john00@mail.com', 'john_newyork@mail.com', 'johnsmith@mail.com']] would still be accepted.

Example 2:

Input: accounts = [["Gabe","Gabe0@m.co","Gabe3@m.co","Gabe1@m.co"],["Kevin","Kevin3@m.co","Kevin5@m.co","Kevin0@m.co"],["Ethan","Ethan5@m.co","Ethan4@m.co","Ethan0@m.co"],["Hanzo","Hanzo3@m.co","Hanzo1@m.co","Hanzo0@m.co"],["Fern","Fern5@m.co","Fern1@m.co","Fern0@m.co"]]
Output: [["Ethan","Ethan0@m.co","Ethan4@m.co","Ethan5@m.co"],["Gabe","Gabe0@m.co","Gabe1@m.co","Gabe3@m.co"],["Hanzo","Hanzo0@m.co","Hanzo1@m.co","Hanzo3@m.co"],["Kevin","Kevin0@m.co","Kevin3@m.co","Kevin5@m.co"],["Fern","Fern0@m.co","Fern1@m.co","Fern5@m.co"]]

Constraints:

1 <= accounts.length <= 1000
2 <= accounts[i].length <= 10
1 <= accounts[i][j] <= 30
accounts[i][0] consists of English letters.
accounts[i][j] (for j > 0) is a valid email.

Solutions

Solution 1

Intuition

Union find

Code

class Solution {

    private class UnionFind {
        int[] p;

        public UnionFind(int n) {
            p = new int[n];
            for (int i = 0; i < n; i++) {
                p[i] = i;
            }
        }

        public int find(int x) {
            if (p[x] != x) {
                p[x] = find(p[x]);
            }
            return p[x];
        }

        public void union(int a, int b) {
            p[find(a)] = find(b);
        }
    }

    public List<List<String>> accountsMerge(List<List<String>> accounts) {
        int n = accounts.size();
        UnionFind uf = new UnionFind(n);

        Map<String, Integer> emailWithOwnerIndex = new HashMap<>();

        for (int index = 0; index < n; index++) {
            List<String> account = accounts.get(index);
            String name = account.get(0);
            for (int i = 1; i < account.size(); i++) {
                String email = account.get(i);
                if (emailWithOwnerIndex.containsKey(email)) {
                    uf.union(index, emailWithOwnerIndex.get(email));
                } else {
                    emailWithOwnerIndex.put(email, index);
                }
            }
        }

        Map<Integer, List<String>> ownerIndexWithEmails = new HashMap<>();
        for (String email : emailWithOwnerIndex.keySet()) {
            int ownerIndex = uf.find(emailWithOwnerIndex.get(email));
            List<String> emails = ownerIndexWithEmails.getOrDefault(uf.find(ownerIndex), new ArrayList<String>());
            emails.add(email);
            ownerIndexWithEmails.put(ownerIndex, emails);
        }

        List<List<String>> ans = new ArrayList<>();
        for (int index : ownerIndexWithEmails.keySet()) {
            List<String> emails = ownerIndexWithEmails.get(index);
            Collections.sort(emails);
            emails.add(0, accounts.get(index).get(0));
            ans.add(emails);
        }
        return ans;
    }
}

const int N = 1001;
class Solution {
private:
    int p[N];

    int find(int x) {
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }

public:
    vector<vector<string>> accountsMerge(vector<vector<string>>& accounts) {
        int n = accounts.size();
        for (int i = 0; i < n; i++) p[i] = i;

        // email -> user indexes
        unordered_map<string, vector<int>> hash;
        for (int i = 0; i < n; i++) {
            for (int j = 1; j < accounts[i].size(); j++) {
                hash[accounts[i][j]].push_back(i);
            }
        }
        // union account indexes
        for (auto& [email, accountIndexes] : hash) {
            for (int i = 1; i < accountIndexes.size(); i++) {
                p[find(accountIndexes[i])] = p[find(accountIndexes[0])];
            }
        }
        // sorting the emails for each account
        vector<set<string>> emails(n);
        for (int i = 0; i < n; i++) {
            for (int j = 1; j < accounts[i].size(); j++) {
                emails[find(i)].insert(accounts[i][j]);
            }
        }

        vector<vector<string>> res;
        for (int i = 0; i < n; i++) {
            if (!emails[i].empty()) {
                vector<string> account;
                account.push_back(accounts[i][0]);
                for (auto& email : emails[i]) account.push_back(email);
                res.push_back(account);
            }
        }
        return res;

    }
};

Complexity

Time: O(nlogn)
Space: O(n)

Interview Cheat Sheet

Wenqi Jiang — Wed, 29 Jun 2022 14:01:14 +0000

The 3 pillars of good code :

Readable
Time Complexity
Space Complexity

What skills interviewer is looking for :

Analytic Skills - How can you think through problems and analyze things ?
Coding Skills - Do you code well, by writing clean, simple, organized, readable code ?
Technical knowledge - Do you know the fundamentals of the job you're applying for ?
Communication skills : Does your personality match the companies' culture ?

Step By Step through a problem:

When the interviewer says the question, write down the key points at the top (i.e. sorted array). Make sure you have all the details. Show how organized you are.
Make sure you double check: What are the inputs? What are the outputs?
What is the most important value of the problem? Do you have time, and space and memory, etc.. What is the main goal?
Don't be annoying and ask too many questions.
Start with the naive/brute force approach. First thing that comes into mind. It shows that you’re able to think well and critically (you don't need to write this code, just speak about it).
Tell them why this approach is not the best (i.e. O(n^2) or higher, not readable, etc...)
Walk through your approach, comment things and see where you may be able to break things. Any repetition, bottlenecks like O(N^2), or unnecessary work? Did you use all the information the interviewer gave you? Bottleneck is the part of the code with the biggest Big O. Focus on that. Sometimes this occurs with repeated work as well.
Before you start coding, walk through your code and write down the steps you are going to follow.
Modularize your code from the very beginning. Break up your code into beautiful small pieces and add just comments if you need to.
Start actually writing your code now. Keep in mind that the more you prepare and understand what you need to code, the better the whiteboard will go. So never start a whiteboard interview not being sure of how things are going to work out. That is a recipe for disaster. Keep in mind: A lot of interviews ask questions that you won’t be able to fully answer on time. So think: What can I show in order to show that I can do this and I am better than other coders. Break things up in Functions (if you can’t remember a method, just make up a function and you will at least have it there. Write something, and start with the easy part.
Think about error checks and how you can break this code. Never make assumptions about the input. Assume people are trying to break your code and that Darth Vader is using your function. How will you safeguard it? Always check for false inputs that you don’t want. Here is a trick: Comment in the code, the checks that you want to do... write the function, then tell the interviewer that you would write tests now to make your function fail (but you won't need to actually write the tests).
Don’t use bad/confusing names like i and j. Write code that reads well.
Test your code: Check for no params, 0, undefined, null, massive arrays, async code, etc... Ask the interviewer if we can make assumption about the code. Can you make the answer return an error? Poke holes into your solution. Are you repeating yourself?
Finally talk to the interviewer where you would improve the code. Does it work? Are there different approaches? Is it readable? What would you google to improve? How can performance be improved? Possibly: Ask the interviewer what was the most interesting solution you have seen to this problem
If your interviewer is happy with the solution, the interview usually ends here. It is also common that the interviewer asks you extension questions, such as how you would handle the problem if the whole input is too large to fit into memory, or if the input arrives as a stream. This is a common follow-up question at Google, where they care a lot about scale. The answer is usually a divide-and-conquer approach — perform distributed processing of the data and only read certain chunks of the input from disk into memory, write the output back to disk and combine them later.

Good code checklist:

[ ] It works
[ ] Good use of data structures
[ ] Code Re-use/ Do Not Repeat Yourself
[ ] Modular - makes code more readable, maintainable and testable
[ ] Less than O(N^2). We want to avoid nested loops if we can since they are expensive. Two separate loops are better than 2 nested loops
[ ] Low Space Complexity --> Recursion can cause stack overflow, copying of large arrays may exceed memory of machine

Heurestics to ace the question:

[ ] Hash Maps are usually the answer to improve Time Complexity
[ ] If it's a sorted array, use Binary tree to achieve O(log N). Divide and Conquer - Divide a data set into smaller chunks and then repeating a process with a subset of data. Binary search is a great example of this
[ ] Try Sorting your input
[ ] Hash tables and precomputed information (i.e. sorted) are some of the best ways to optimize your code
[ ] Look at the Time vs Space tradeoff. Sometimes storing extra state in memory can help the time. (Runtime)
[ ] If the interviewer is giving you advice/tips/hints. Follow them
[ ] Space time tradeoffs: Hastables usually solve this a lot of the times. You use more space, but you can get a time optimization to the process. In programming, you often times can use up a little bit more space to get faster time

And always remember: Communicate your thought process as much as possible. Don’t worry about finishing it fast. Every part of the interview matters.

Longest Common Substring

Wenqi Jiang — Wed, 22 Jun 2022 18:35:48 +0000

https://binarysearch.com/problems/Longest-Common-Substring

int solve(string s0, string s1) {
    int m = s0.size(), n = s1.size(), res = 0;
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (s0[i] == s1[j]) dp[i + 1][j + 1] = dp[i][j] + 1;
            res = max(res, dp[i + 1][j + 1]);
        }
    }
    return res;
}

Multi Search LCCI

Wenqi Jiang — Mon, 13 Jun 2022 21:37:48 +0000

Given a string band an array of smaller strings T, design a method to search b for each small string in T. Output positions of all strings in smalls that appear in big, where positions[i] is all positions of smalls[i].

Input: 
big = "mississippi"
smalls = ["is","ppi","hi","sis","i","ssippi"]
Output:  [[1,4],[8],[],[3],[1,4,7,10],[5]]

0 <= len(big) <= 1000
0 <= len(smalls[i]) <= 1000
The total number of characters in smalls will not exceed 100000.
No duplicated strings in smalls.
All characters are lowercase letters.

https://leetcode.cn/problems/multi-search-lcci/

const int N = 100000 + 10;

class Solution {
private:
  int son[N][26], values[N], idx;
  vector<vector<int>> res;
  void insert(string &word, int val) {
    int p = 0;
    for (char &c : word) {
      int i = c - 'a';
      if (!son[p][i])
        son[p][i] = ++idx;
      p = son[p][i];
    }
    values[p] = val;
  }

  void search(int start, string &big) {
    int p = 0;
    for (int i = start; i < big.size(); i++) {
      int k = big[i] - 'a';
      if (!son[p][k])
        return;
      p = son[p][k];
      if (values[p] >= 0)
        res[values[p]].push_back(start);
    }
  }

public:
  vector<vector<int>> multiSearch(string big, vector<string> &smalls) {
    memset(son, 0, sizeof son);
    memset(values, -1, sizeof values);
    idx = 0;
    res.resize(smalls.size());

    for (int i = 0; i < smalls.size(); ++i)
      insert(smalls[i], i);

    for (int i = 0; i < big.size(); ++i)
      search(i, big);

    return res;
  }
};

[Grind 75] 57. Insert Interval

Wenqi Jiang — Wed, 11 May 2022 09:54:05 +0000

Description

You are given an array of non-overlapping intervals intervals where intervals[i] = [starti, endi] represent the start and the end of the ith interval and intervals is sorted in ascending order by starti. You are also given an interval newInterval = [start, end] that represents the start and end of another interval.

Insert newInterval into intervals such that intervals is still sorted in ascending order by starti and intervals still does not have any overlapping intervals (merge overlapping intervals if necessary).

Return intervals after the insertion.

Example 1:

Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]

Example 2:

Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
Output: [[1,2],[3,10],[12,16]]
Explanation: Because the new interval [4,8] overlaps with [3,5],[6,7],[8,10].

Constraints:

0 <= intervals.length <= 104
intervals[i].length == 2
0 <= starti <= endi <= 105
intervals is sorted by starti in ascending order.
newInterval.length == 2
0 <= start <= end <= 105

Solutions

Solution 1

Intuition

left: end < newStart
covered: newStart = min(start, newStart); find the last start which is smaller than newEnd, and update newEnd = max(end, newEnd);
right: the rest part of intervals

Code

class Solution {
    public:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        int n = intervals.size();
        vector<vector<int>> res;
        int idx = 0;
        while (idx < n && intervals[idx][1] < newInterval[0]) res.push_back(intervals[idx++]);

        if (idx < n) {
            newInterval[0] = min(intervals[idx][0], newInterval[0]);
            while (idx < n && intervals[idx][0] <= newInterval[1])
                newInterval[1] = max(intervals[idx++][1], newInterval[1]);
        }
        res.push_back(newInterval);
        while (idx < n) res.push_back(intervals[idx++]);

        return res;
    }
};

Complexity

Time: O(n)
Space: O(n)