Questions ======================================== Step-By-Step Directions From a Binary Tree Node to Another ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ .. code-block:: none You are given the root of a binary tree with n nodes. Each node is uniquely assigned a value from 1 to n. You are also given an integer startValue representing the value of the start node s, and a different integer destValue representing the value of the destination node t. Find the shortest path starting from node s and ending at node t. Generate step-by-step directions of such path as a string consisting of only the uppercase letters 'L', 'R', and 'U'. Each letter indicates a specific direction: 'L' means to go from a node to its left child node. 'R' means to go from a node to its right child node. 'U' means to go from a node to its parent node. Return the step-by-step directions of the shortest path from node s to node t. Example: +---+ | 0 | +---+ / \ +---+ +---+ | 1 | | 2 | +---+ +---+ / \ \ +---+ +---+ +---+ | 3 | | 4 | | 5 | +---+ +---+ +---+ From 3 to 2, the shortest path is 3->1->0->2, so the direction string is UUR. From 4 to 5, the shortest path is 4->1->0->2->5, so the direction string is UURR. ---- It’s no hard to see that the shortest path is from the start node to the lowest common ancestor (LCA) of (start, end), then to the end node. The key is to find the LCA while finding paths from root to two nodes. We can use recursion to find/build a path from root to a target node. The common prefix of these two paths is the path from root to the LCA that we need to remove from the shortest path: e.g. root to start “LLRLR”, root to dest “LLLR”. common prefix is “LL”, after removing, it becomes: LCA to start “RLR”,LCA to dest “LR”. Final path becomes “UUU” + “LR” = “UUULR” The final step is to replace the L/R with U for the start path since we are moving up and then concatenate with the target path. Time complexity: O(n) Space complexity: O(n) .. literalinclude:: step_by_step_directions_from_a_binary_tree_node_to_another_test.cpp :linenos: :lines: 5-26 :language: c++ .. only:: html - https://leetcode.com/problems/step-by-step-directions-from-a-binary-tree-node-to-another/ .. _Second_Smallest_Number: Second Smallest Number |:ninja:| ---------------------------------- Given an array of integers, find the minimum element and the element just greater than that in less than **2N** comparisons. The given array is not necessarily sorted. Extra space is allowed. Examples: Input: {3, 6, 100, 9, 10, 12, 7, -1, 10} Output: Minimum: -1, Second minimum: 3 .. _Buddy_Bitmap: Buddy Bitmap |:ninja:| ---------------------------------- .. literalinclude:: buddy.txt :language: c++ :lines: 1-24 :emphasize-lines: 6-14 The tricky part is the indexing scheme. From this question, we can see parent_index is equal to child_index/2. Also the buddy bitmap uses `bit-wise and` as the merging scheme, so the parent is 0 if any of its children is 0. .. literalinclude:: buddy.txt :language: c++ :lines: 27-36 ---- **Follow-up Questions:** .. literalinclude:: buddy.txt :language: c++ :lines: 40-46 Setting bit is trickier than clearing bit. To set the parent, we need to make sure the both children are set too. .. literalinclude:: buddy.txt :language: c++ :lines: 48-74 We can consolidate all the conditions into one clause and get the simpler form: .. literalinclude:: buddy.txt :language: c++ :lines: 77-91 This question is related to Segment Tree(:numref:`Segment_Tree`). Design Segment Tree ----------------------------- Design a data structure to represent a specialized segment tree where each node can either be a leaf node or an internal node. An internal node possesses two children—specifically, a left child and a right child—and stores the total length of all descendant nodes. A leaf node, in contrast, holds a specific value alongside its length. Consider the structure illustrated below as an example: .. code-block:: none InternalNode, 26 / \ / \ / \ Leaf(5, "ABCDE") InternalNode, 21 / \ / \ / \ / \ Leaf(10, "FGHIJKLMNO") Leaf(11, "PQRSTUVWXYZ") - Question 1 - Data Structure Design: Propose a data structure that effectively models the described segment tree. Ensure your design can accommodate both leaf nodes, which contain a string value and a length, and internal nodes, which maintain the combined length of their child nodes. - Question 2 - Character Retrieval Function: Develop a function that, given a tree (as per the data structure you've designed) and an index, returns the character located at that specific index within the tree. The index refers to the position in the concatenated string formed by traversing all leaf nodes in order. ---- This can be done by segment tree or cord tree. .. _Manipulate_Long_String: Manipulate Long String ----------------------------------------- Design a tree-based data structure to efficiently manipulate a very long string. .. code-block:: c++ class LongString { public: LongString(string s) {...} // Returns the character at index 'i', if not available, return null or '' char index(int i) {...} // string length char size() {...} /* Remove the specified character substring. The substring begins at the specified 'start' and extends to the character at index 'end - 1' or to the end of the sequence, if no such character exists. If 'start' is equal to 'end', no changes are made. @param start The beginning index, inclusive. @param end The ending index, exclusive. @return false if 'start' is negative, greater than length, or greater than 'end'. */ bool remove(int start, int end) {...} } Hint: - Segment tree - Cord tree In computer programming, a rope, or cord, is a data structure composed of smaller strings that is used to efficiently store and manipulate a very long string. For example, a text editing program may use a rope to represent the text being edited, so that operations such as insertion, deletion, and random access can be done efficiently. A rope is a left-ish binary tree (that is, each node can have maximum of 2 children) where each leaf (end node) holds a string and a length (also known as a “weight”), and each node further up the tree holds the sum of the lengths of all the leaves in its left subtree. For string "ABCDEFGHIJKLMNOPQRSTUVWXYZ", you can use the following cord tree to store it: .. code-block:: none InternalNode, 5 / \ / \ / \ Leaf(5, ABCDE) InternalNode, 10 / \ / \ / \ / \ Leaf(10, FGHIJKLMNO) Leaf(11, PQRSTUVWXYZ) ---- **Solution**: Please refer to Cord Tree(:numref:`cord_tree`) for the details. .. literalinclude:: code/long_string_cord_test.cpp :language: c++ :linenos: .. only:: html - https://medium.com/underrated-data-structures-and-algorithms/rope-data-structure-e623d7862137 - https://leetcode.com/discuss/interview-question/413991/ - https://leetcode.com/discuss/interview-question/1593355/Google-or-Phone-Interview-or-Rejected/1162223 - https://leetcode.com/playground/TGQ4PSZN - https://stackoverflow.com/questions/71315383/how-to-implement-rope-data-structure-split-operation - https://www.geeksforgeeks.org/ropes-data-structure-fast-string-concatenation/