Problems
July 22, 2022
Jump game
This problem could definitely be solved by dynamic programming, but if we take greedy approach, we can solve it in linear time. We can iterate through the array from last index to first index. We set...
ReadJuly 21, 2022
Meeting rooms
We will sort the given array based on start time. Then we can compare, if the end of first meeting is before the start of last meeting, if yes return False, else return True. Time Complexity:...
ReadJuly 21, 2022
Merge intervals
First we sort the intervals with the start key. Then we append the first item on the output list. Then we will iterate over all intervals and compare the last end with the current start, if the last...
ReadJuly 21, 2022
Implement stack using queues
It's easy to implement a stack using queue. You can pop, peek and check the empty as you normally do in a queue. You just need to do some extra work during the push method. First you push it to the...
ReadJuly 21, 2022
Implement trie prefix tree
This problem literary ask to implement a prefix tree or Trie. Each node will have children for which we have used a hashmap for constant time insert and lookup abd a boolean value to denote whether...
ReadJuly 21, 2022
Graph valid tree
First we create a adjacency list from the edge list. Then we traverse the whole graph starting from node 0. If we don't have any cycle or any disjoint node, then it's a valid tree, otherwise we...
ReadJuly 21, 2022
Maximum subarray
We will have 2 running count, one is for our result and one is for the total of the array. First we assume first element of the input is out result. Then we iterate through the input and calculate...
ReadJuly 21, 2022
Fibonacci number
This is the classing fibonacci number problem. First we solve this using recursion, then we memoize it to increase efficiency.
Time Complexity: O(n)
Space Complexity:...
July 20, 2022
Kth largest element in a stream
We will create a min heap from the elements of the stream. We will make sure heap size is always k. That means the smallest element will ve at the heap's top and the largest element will be at the...
ReadJuly 20, 2022
Binary tree preorder traversal
We will traverse the tree with recursive DFS, as it is preorder traversal, we first append the root, then the left subtree and then right subtree.
Time Complexity: O(n)
Space...