1. Leetcode 367

Given a

**positive**integer num, write a function which returns True if num is a perfect square else False.**Follow up:**

**Do not**use any built-in library function such as sqrt.

**Example 1:**

Input:num = 16Output:true

**Example 2:**

Input:num = 14Output:false

**Constraints:**

- 1 <= num <= 2^31 - 1

2. Leetcode 678

Given a string s containing only three types of characters: '(', ')' and '*', return true

*if*s*is***.***valid*The following rules define a

**valid**string:- Any left parenthesis '(' must have a corresponding right parenthesis ')'.
- Any right parenthesis ')' must have a corresponding left parenthesis '('.
- Left parenthesis '(' must go before the corresponding right parenthesis ')'.
- '*' could be treated as a single right parenthesis ')' or a single left parenthesis '(' or an empty string "".

**Example 1:**

Input:s = "()"Output:true

**Example 2:**

Input:s = "(*)"Output:true

**Example 3:**

Input:s = "(*))"Output:true

**Constraints:**

- 1 <= s.length <= 100
- s[i] is '(', ')' or '*'.

3. Leetcode 1650

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:

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:**

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

**Example 2:**

Input:root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4Output:5Explanation: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:**

Input:root = [1,2], p = 1, q = 2Output: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.

4. Leetcode 297

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.

**Clarification:**The input/output format is the same as how LeetCode serializes a binary tree. You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.

**Example 1:**

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

**Example 2:**

Input:root = []Output:[]

**Constraints:**

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

5. Leetcode 449

Serialization is converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a

**binary search tree**. There is no restriction on how your serialization/deserialization algorithm should work. You need to ensure that a binary search tree can be serialized to a string, and this string can be deserialized to the original tree structure.**The encoded string should be as compact as possible.**

**Example 1:**

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

**Example 2:**

Input:root = []Output:[]

**Constraints:**

- The number of nodes in the tree is in the range [0, 104].
- 0 <= Node.val <= 104
- The input tree is
**guaranteed**to be a binary search tree.

6. Leetcode 127

A

**transformation sequence**from word beginWord to word endWord using a dictionary wordList is a sequence of words beginWord -> s1 -> s2 -> ... -> sk such that:- Every adjacent pair of words differs by a single letter.
- Every si for 1 <= i <= k is in wordList. Note that beginWord does not need to be in wordList.
- sk == endWord

Given two words, beginWord and endWord, and a dictionary wordList, return

*the**number of words**in the**shortest transformation sequence**from*beginWord*to*endWord*, or*0*if no such sequence exists.*

**Example 1:**

Input:beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]Output:5Explanation:One shortest transformation sequence is "hit" -> "hot" -> "dot" -> "dog" -> cog", which is 5 words long.

**Example 2:**

Input:beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]Output:0Explanation:The endWord "cog" is not in wordList, therefore there is no valid transformation sequence.

**Constraints:**

- 1 <= beginWord.length <= 10
- endWord.length == beginWord.length
- 1 <= wordList.length <= 5000
- wordList[i].length == beginWord.length
- beginWord, endWord, and wordList[i] consist of lowercase English letters.
- beginWord != endWord
- All the words in wordList are
**unique**.

7. Leetcode 449

Serialization is converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a

**binary search tree**. There is no restriction on how your serialization/deserialization algorithm should work. You need to ensure that a binary search tree can be serialized to a string, and this string can be deserialized to the original tree structure.**The encoded string should be as compact as possible.**

**Example 1:**

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

**Example 2:**

Input:root = []Output:[]

**Constraints:**

- The number of nodes in the tree is in the range [0, 104].
- 0 <= Node.val <= 104
- The input tree is
**guaranteed**to be a binary search tree.

8. Leetcode 236

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow

**a node to be a descendant of itself**).”**Example 1:**

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

**Example 2:**

Input:root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4Output:5Explanation: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:**

Input:root = [1,2], p = 1, q = 2Output: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 will exist in the tree.

9. Leetcode 432

Design a data structure to store the strings' count with the ability to return the strings with minimum and maximum counts.

Implement the AllOne class:

- AllOne() Initializes the object of the data structure.
- inc(String key) Increments the count of the string key by 1. If key does not exist in the data structure, insert it with count 1.
- dec(String key) Decrements the count of the string key by 1. If the count of key is 0 after the decrement, remove it from the data structure. It is guaranteed that key exists in the data structure before the decrement.
- getMaxKey() Returns one of the keys with the maximal count. If no element exists, return an empty string "".
- getMinKey() Returns one of the keys with the minimum count. If no element exists, return an empty string "".

**Note**that each function must run in O(1) average time complexity.

**Example 1:**

Input["AllOne", "inc", "inc", "getMaxKey", "getMinKey", "inc", "getMaxKey", "getMinKey"] [[], ["hello"], ["hello"], [], [], ["leet"], [], []]Output[null, null, null, "hello", "hello", null, "hello", "leet"]ExplanationAllOne allOne = new AllOne(); allOne.inc("hello"); allOne.inc("hello"); allOne.getMaxKey(); // return "hello" allOne.getMinKey(); // return "hello" allOne.inc("leet"); allOne.getMaxKey(); // return "hello" allOne.getMinKey(); // return "leet"

**Constraints:**

- 1 <= key.length <= 10
- key consists of lowercase English letters.
- It is guaranteed that for each call to dec, key is existing in the data structure.
- At most 5 * 104 calls will be made to inc, dec, getMaxKey, and getMinKey.

10. Lowest Common Ancestor of Deepest Leaves

| Given a rooted binary tree, return the lowest common anCEstor of its deepest leaves

Recall that:

The node of a binary tree is a leaf if and only if it has no children

The depth of the root of the tree is O, and if the depth of a node is d, the depth of each of its children is d+1.

The lowest common ancestor of a set Sof nodes is the node A with the largest depth such that every node in S is in the subtree with root A.

Recall that:

The node of a binary tree is a leaf if and only if it has no children

The depth of the root of the tree is O, and if the depth of a node is d, the depth of each of its children is d+1.

The lowest common ancestor of a set Sof nodes is the node A with the largest depth such that every node in S is in the subtree with root A.

11. Measure changing search results from list to box

| 如果把linkedin给recuriter的搜索结果从list变box，你怎么看？

12. Tradeoff

| 一个metric下降，一个metric上升如何做选择。