Questions ================================== .. _uf_longest_consecutive_sequence: Longest Consecutive Sequence ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ Given an unsorted array of integers, find **the length of the longest consecutive elements sequence**. For example, given [100, 4, 200, 1, 3, 2], the longest consecutive elements sequence is [1, 2, 3, 4], it will return its length: 4. The algorithm should run in O(N) complexity. - Algo 1: union find .. literalinclude:: longest_consecutive_seq.cpp :language: c++ :linenos: :lines: 12-45 - Algo 2: hashtable Since the O(n) algorithm is required, sorting is obviously not possible, so it is natural to use a hash table. Store all the numbers in the sequence in an unordered_set. For any number A[i] in the sequence, we can immediately know A through the set Whether [i] 1 and A[i]-1 are also in the sequence. If so, continue to find A[i] 2 and A[i]-2, and so on, until the entire continuous sequence is found. In order to avoid scanning When A[i]-1 is reached, the sequence is searched again, and the searched number is removed from the set at the same time as each search. Until the set is empty, all consecutive sequence searches end. Complexity: Since each Numbers are inserted into the set only once, and removed once, so the algorithm is O(n). .. literalinclude:: longest_consecutive_seq.cpp :language: c++ :linenos: :lines: 48-69 Number of Connected Components in an Undirected Graph ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ .. code-block:: none Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each edge is a pair of nodes), write a function to find the number of connected components in an undirected graph. Example 1: 0 3 | | 1 --- 2 4 Given n = 5 and edges = [[0, 1], [1, 2], [3, 4]], return 2. Example 2: 0 4 | | 1 --- 2 --- 3 Given n = 5 and edges = [[0, 1], [1, 2], [2, 3], [3, 4]], return 1. .. _uf_group_strings: Groups of Strings ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ .. code-block:: none You are given a 0-indexed array of strings words. Each string consists of lowercase English letters only. No letter occurs more than once in any string of words. Two strings s1 and s2 are said to be connected if the set of letters of s2 can be obtained from the set of letters of s1 by any one of the following operations: - Adding exactly one letter to the set of the letters of s1. - Deleting exactly one letter from the set of the letters of s1. - Replacing exactly one letter from the set of the letters of s1 with any letter, including itself. The array words can be divided into one or more non-intersecting groups. A string belongs to a group if any one of the following is true: - It is connected to at least one other string of the group. - It is the only string present in the group. Note that the strings in words should be grouped in such a manner that a string belonging to a group cannot be connected to a string present in any other group. It can be proved that such an arrangement is always unique. Return an array ans of size 2 where: - ans[0] is the maximum number of groups words can be divided into, and - ans[1] is the size of the largest group. Example 1: Input: words = ["a","b","ab","cde"]; Output: [2,3] Explanation: - words[0] can be used to obtain words[1] (by replacing 'a' with 'b'), and words[2] (by adding 'b'). So words[0] is connected to words[1] and words[2]. - words[1] can be used to obtain words[0] (by replacing 'b' with 'a'), and words[2] (by adding 'a'). So words[1] is connected to words[0] and words[2]. - words[2] can be used to obtain words[0] (by deleting 'b'), and words[1] (by deleting 'a'). So words[2] is connected to words[0] and words[1]. - words[3] is not connected to any string in words. Thus, words can be divided into 2 groups ["a","b","ab"] and ["cde"]. The size of the largest group is 3. Example 2: Input: words = ["a","ab","abc"]; Output: [1,3] Explanation: - words[0] is connected to words[1]. - words[1] is connected to words[0] and words[2]. - words[2] is connected to words[1]. Since all strings are connected to each other, they should be grouped together. Thus, the size of the largest group is 3. ---- This question is to cluster all 1-edit-distance words in an array, and return the cluster number and the size of the largest cluster. .. literalinclude:: code/group_of_strings_test.cpp :language: c++ :linenos: :name: group_of_strings :caption: Group of Strings :emphasize-lines: 5-40 .. only:: html - https://leetcode.com/problems/groups-of-strings/ .. _ost_percentile_query_tree: Percentile Query Tree ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ .. code-block:: none [Google L5]Coding round interviewer showed up and asked me to do the question without saying any extra word: Given a stream of prices from transactions: 79.20, 20.05, 96.82, ... Implement 2 methods: 1) insert(price) 2) query(percentile) - e.g.: query(0.2) should give a price that 20% of prices is lower than it, 80% of prices should be higher. ---- .. literalinclude:: percentile_tree_test.cpp :language: c++ :lines: 6-41 :linenos: :name: order_statistics_tree_q1 :caption: An order statistic tree :emphasize-lines: 3 .. only:: html - https://www.1point3acres.com/bbs/thread-862172-1-1.html Refer to :numref:`ost`, :numref:`median_tree` .. _uf_maze_gen: Maze Generation ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ Generate a maze in a matrix. .. code-block:: none The number in the cell is encoded by the edge in a binary number format: 0b[left][bottom][right][up] 0 +---+ 3 | 1 | 1 +---+ 2 So the number has a range of [0-15], from 0b0000 to 0b1111. 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1111 +---+ + + +---+ + + +---+ + + +---+ + + +---+ + + +---+ 1 2 | 3 | 4 5 6 | 7 | | 8 | 9 | 10| ... | 15| + + + + + + +---+ +---+ +---+ +---+ + + + + + + +---+ The following are two example of maze generation: .. code-block:: none +---+---+---+---+---+---+ +---+---+---+---+---+---+ +---+---+---+---+---+---+ 7 | 15| 15| 15| 15| 15| start --> 5 1 5 5 5 3 | start --> 1 5 3 | 11| 9 3 | +---+---+---+---+---+---+ +---+ +---+---+---+ + + +---+ + + + + | 15| 15| 15| 15| 15| 15| | 11| 12 5 5 3 | 10| | 8 3 | 12 4 2 | 10| +---+---+---+---+---+---+ => + +---+---+---+ + + or + + +---+---+ + + | 15| 15| 15| 15| 15| 15| | 8 5 1 5 6 | 14| | 10| 14| 11| 13 2 | 14| +---+---+---+---+---+---+ + +---+ +---+---+---+ + +---+ +---+ +---+ | 15| 15| 15| 15| 15| 13 | 12 7 | 12 5 5 5 -->end | 12 7 | 12 5 4 5 -->end +---+---+---+---+---+---+ +---+---+---+---+---+---+ +---+---+---+---+---+---+ Desired Properties • None of the boundary is deleted (except at 'start' and 'end'). • Every cell is reachable from every other cell. • There are no cycles – no cell can reach itself by a path unless it retraces some part of the path. A sample API is: .. code-block:: c++ vector> maze_generation(int row, int column) {...} ---- There are many ways to generate a maze. Something in common is we need randomized function since it is a maze generation. .. literalinclude:: code/maze_generation_test.cpp :language: c++ :linenos: :name: maze_generation :caption: Maze Generation by Union Find :emphasize-lines: 17, 33, 36 .. _uf_translator: Multi-language Translator ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ Design a multi-language translator where there are two APIs: .. code-block:: none add(String inputLanguage, String inputWord, String outputLanguage, String outputWord) get(String inputLanguage, String inputWord, String outputLanguage) For example: add("English", "hello", "Spanish", "hola") add("Spanish", "hola", "French", "Bon jour") add("French", "Bon jour", "Chinese", "nihao") Then: get("English", "hello", "French") => "Bon jour" get("Spanish", "hola", "Chinese") => "nihao" ---- An intuitive way to solve this problem is graph traversal like BFS, DFS, but **union find** can be used to solve it in a more efficient way. .. literalinclude:: code/multilang_translator_test.cpp :language: c++ :linenos: :name: multilang_translator :caption: Multilang Translator using Union Find :emphasize-lines: 17, 33, 36 .. only:: html - https://www.1point3acres.com/bbs/thread-907525-1-1.html