Problems
November 30, 2022
Bitwise xor of all pairings
From Boolean algebra we know that n^0 = n and n^n = 0, from which we can infer that the xor of an even count of an integer n is 0, and the xor of an odd count of an integer n is n. We also know that...
ReadNovember 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 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
Count nodes equal to average of subtree
We will traverse the tree in post-order fashion. For each node, we will calculate the sum of all nodes in its subtree and the number of nodes in its subtree. Then we will check if the average of the...
ReadNovember 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
Maximum split of positive even integers
We can be greedy and try to split the number into as many parts as possible. We will start from the 2 and try to split it until we reach the end of the number. If we can't split the number, we will...
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 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),...
November 29, 2022
Print immutable linked list in reverse
We can use a stack to store the values of the linked list. We will then pop the values from the stack and print them.
Time complexity: O(n), n is the number of nodes in the linked...