Leetcode Problem 1100-1199
- Same Question as fibonacci sequence
Recursive Solution(TLE)
Memoization(Top-Down) (5ms-AC)
Tabulation (Bottom-Up) (0ms-AC)
Optimized Space (0ms-AC)
Recursive Solution (TLE)
- If last character of both strings are same them we can check for LCS with 1 character less in both strings. and return 1+lcs(1 char less in both strings)
- else they are not same we return the maximum of 1 char less in first text and 1 char less in second text.
- We reach to base case when one of i and j are 0, we return 0;
- TC: O(2^n)
Memoization (Top-Down) (AC)
- We can easily memoize the recursive function by using the extra space.
- make sure you pass by value if you are passing anything like string and vector.
- TC: O(nm)
- SC: O(nm)
Tabulation (Bottom-Up) (AC)
- With the help of memoized code we can visualize the code in a tabular form.
- Below is the implementation.
- TC: O(nm)
- SC: O(nm)
Previous Questions
- Binary tree level order traversal
- Binary tree level order traversal - II
- Binary tree zig-zag level order traversal
- Average of levels
- Binary tree right side view
- largest value in each tree row
- Populating next right pointer
- n-ary tree level order traversal
- Just level order traversal and finding the max sum level
Bit masking with hashmap
- We set all the bits of the corresponding indices of each letter, then we easily see if it’s a submask.
- we create a hashmap to keep the frequency of each mask, so that if we have two words with the same letter we will count both.
- we iterate through the puzzles
- We need to find all combinations of submasks to check. This is the faster than iterating through all the words because each puzzle is only 7 letters.
- For that we just do (submask-1) & mask - we are turning off a bit by subtracting one which sets the lowest 1 to 0 and all 0s in the right to 1s, and then we do & with the original mask to get only the desired bits.
Interview Tips
Interview Tip-1
In a real interview, if you are unsure how to solve the problem, a good first step is to remain calm and reread the problem description looking for hidden clues.
Also, remember to ask the interviewer about the problem constraints. The constraints are very important for solving problems as they can help us determine which data structures and algorithms can feasibly be used to solve the problem.
However, if the interviewer chooses to deliberately hide the constraints, then they likely want you to find different methods under different assumed constraints. Although, on rare occasions, a problem may be too simple to provide constraints.
Interview Tip-2
A constraint under `10` usually accepts a method with `N!` time complexity with respect to this constraint. Factorial time complexities can occur for operations like finding all permutations from a set or using brute-force to solve the traveling salesman problem.
A constraint under `30` usually accepts a method with `2^N` time complexity at worst with respect to this constraint. Some examples include iterating over all combinations or subsets from a set or some brute-force solutions that use `DFS`.
However, a solution with better time complexity can still exist even when the constraints are small. One should use the constraints to estimate the complexity of the worst acceptable solution, not the best solution.
Interview Tip-3
When you still do not have any idea after rereading the problem, you can try a brute-force method that works but may have an unacceptable time complexity.
Then you can either try to improve on the brute-force method or gain some insight from the brute-force method.
Interview Tip-4
In an interview, if the first solution that comes to mind involves a complex data structure, you can wait a minute and try thinking of other similar methods. In a real-world setting, we typically prioritize efficiency and readability. We prioritize these characteristics in an interview setting as well, however, we also value solutions that we are less likely to make a mistake while coding and solutions that do not require a long time to code.
In this problem, you should consider your level of familiarity with the trie data structure before choosing between implementing a solution using a trie or a set. If the more comfortable approach is not the most efficient, then you should also weigh the increased chance of making a mistake versus the gain of having a more efficient solution.
Worry not, as we will cover both methods in this article.
Must Read: