Problems
November 30, 2022
Nim game
Let us think of the small cases. It is clear that if there are only one, two, or three stones in the pile, and it is your turn, you can win the game by taking all of them. Like the problem...
ReadNovember 30, 2022
Partitioning into minimum number of deci binary numbers
Assume max digit in n is x, because deci-binary only contains 0 and 1, we need at least x numbers to sum up a digit x. So we can just find the max digit in n and return it. Time complexity:...
ReadNovember 30, 2022
Recover a tree from preorder traversal
We save the construction path in a stack. In each loop, we get the number level of '-'. We get the value val of node to add. If the size of stack is bigger than the level of node, we pop the stack...
ReadNovember 30, 2022
Remove duplicates from an unsorted linked list
We will use a hashmap to count the frequency of each node in the linked list. Then we will traverse the linked list again and remove the nodes that have frequency greater than 1. Time complexity:...
ReadNovember 30, 2022
Sparse matrix multiplication
We will iterate over the non-zero elements of the first matrix and multiply them with the corresponding elements of the second matrix. We will store the result in a dictionary and return the result....
ReadNovember 30, 2022
Unique number of occurrences
We will count the number of occurrences of each number in the array. We will then check if the number of occurrences is unique using a hash set.
Time complexity: O(n), n is the length...
November 30, 2022
Unique word abbreviation
We will use a dictionary to store the count of each abbreviation, and a set to store the words that have been added to the dictionary. If the word is already present in the set, we will return false....
ReadNovember 30, 2022
Verify preorder sequence in binary search tree
Using stack for storing the current node as a check point for the next element. Once the current is larger than the last element in the stack, we know we should take it as the right node. The last...
ReadNovember 29, 2022
Count of smaller numbers after self
We will make a sorted copy of the nums. Then we iterate over each number, find the index of the number in the sorted copy, and add the number of numbers smaller than the number to the result. Time...
ReadNovember 29, 2022
Count univalue subtrees
We will use postorder traversal to count the number of univalue subtrees. We will also use a helper function to check if the current node is a univalue subtree.
Time complexity: O(n),...