Problems
August 6, 2022
Binary tree maximum path sum
We will calculate the sum of left subtree and right subtree and return the value of maximum of them added with the current node value from our recursive DFS method. In the process we will keep track...
ReadAugust 6, 2022
Reverse nodes in k group
We will create a helper funtion to get the kths item of the list. Then as we go through the whole list, we will take kth item, reverse it in place and move forward till the end of the ;list. Time...
ReadAugust 6, 2022
Kth smallest element in a bst
If we traverse the binary search tree in inorder, then we will actually get the sorted array. Then we can easily pick the kth element by picking k-1 indexed value from the array, as it's mentioned, k...
ReadAugust 6, 2022
Validate binary search tree
We will run a DFS, and each iteration we will compare the value of the node with a left and right value, which we will pass along each iteration. For root, this values will be negative and positive...
ReadAugust 6, 2022
Merge k sorted lists
We can merge 2 sorted list with O(n) time complexity. Now we can go through the lists, and merge it one by one, this will be a O(n^2) operation. But if we merge every 2 list...
August 6, 2022
Design twitter
This is a classic object oriented design problem. We will use a hashmap for the tweet map and another hashmap for the follow map. Each element of the tweet map with be a list, and each element of the...
ReadAugust 5, 2022
Coin change 2
We will first solve the problem with brute force using recursion. Then we use memoization to reduce it's complexity.
Time Complexity: O(n*a), n is the number of coins, a is the amount...
August 5, 2022
Combination sum
Basically, we have 2 ways to built the decision tree, either take the number or skip it. We are going to use backtracking to calculate the problem.
Time Complexity: O(2^n)
Space...
August 5, 2022
Combination sum II
We will run a DFS for the decision tree and use backtracking if we failed to find a result. As we are bit allowed to use the same items twice, we will keep track of the previous item, and if it is...
ReadAugust 5, 2022
Combination sum IV
This is very similar to coin change 2. But when you take one item from the allowed list, rather start it from the same index like coin change, you should start it from the beginning of the list....
Read