Coding Week 5 - Recursion and Backtracking Flashcards
Problem 1) Restore IP Addresses
A valid IP address consists of exactly four integers separated by single dots. Each integer is between 0 and 255 (inclusive) and cannot have leading zeros.
For example, “0.1.2.201” and “192.168.1.1” are valid IP addresses, but “0.011.255.245”, “192.168.1.312” and “192.168@1.1” are invalid IP addresses.
Given a string s containing only digits, return all possible valid IP addresses that can be formed by inserting dots into s. You are not allowed to reorder or remove any digits in s. You may return the valid IP addresses in any order.
Example 1:
Input: s = “25525511135”
Output: [“255.255.11.135”,”255.255.111.35”]
Question 1)
The naive solution would be to brute-force, i.e. to check all possible positions for the dots and keep only the valid ones. In the worst case that means 11 possible positions and hence
11×10×9=990 validations. Is it possible to reduce these validations?
A) Yes
B) No
A) Yes
We can use the concept of constrained programming and backtracking to reduce the combinations to validate:
1) Constrained programming: That basically means to put restrictions after each dot placement. If one already put a dot that leaves only 3 possibilities for the next dot to be placed : after one digit, after two digits, or after three digits. The first dot has only 3 available slots as well. That propagates constraints and helps to reduce a number of combinations to consider. Instead of 990 combinations it’s enough to check just 3×3×3=27.
2) Backtracking: Let’s imagine that one put one or two dots already and that left no way to place the others to create a valid IP address. What to do? To backtrack. That means to come back, to change the position of the previously placed dot and try to proceed again. If that would not work either, backtrack again.
Problem 1) Restore IP Addresses
A valid IP address consists of exactly four integers separated by single dots. Each integer is between 0 and 255 (inclusive) and cannot have leading zeros.
For example, “0.1.2.201” and “192.168.1.1” are valid IP addresses, but “0.011.255.245”, “192.168.1.312” and “192.168@1.1” are invalid IP addresses.
Given a string s containing only digits, return all possible valid IP addresses that can be formed by inserting dots into s. You are not allowed to reorder or remove any digits in s. You may return the valid IP addresses in any order.
Example 1:
Input: s = “25525511135”
Output: [“255.255.11.135”,”255.255.111.35”]
Question 2)
What is the time and space complexity of the most optimal solution?
A) Time - O(N ^ 2), Space - O(N)
B) Time - O(1), Space - O(1)
C) Time - O(2 ^ N), Space - O(N)
D) Time - O(N), Space - O(1)
B) Time - O(1), Space - O(1)
There are not more than 27 combinations to validate and store, hence the time and auxiliary space is constant.
Problem 2) Generate Parentheses
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
Example 1:
Input: n = 3
Output: [”((()))”,”(()())”,”(())()”,”()(())”,”()()()”]
Question 1) If we try to solve this problem using backtracking, which out of the following should be the backtracking conditions?
A) Number of opening brackets is greater than the number of closing brackets.
B) Number of opening brackets is equal to the number of closing brackets.
C) Number of opening brackets is less than the number of closing brackets.
D) Number of opening brackets is greater than n.
C) Number of opening brackets is less than the number of closing brackets.
D) Number of opening brackets is greater than n.
Any combination where the number of opening brackets is less than the number of closing brackets or where the number of opening brackets is greater than n, can never generate well-formed parentheses. Examples, “())”, “)”, for n = 3, “((((“ is invalid.
Problem 2) Generate Parentheses
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
Example 1:
Input: n = 3
Output: [”((()))”,”(()())”,”(())()”,”()(())”,”()()()”]
Question 2)
What will be the asymptotic time and auxiliary space complexity of the optimal approach?
A) Time - O(N ^ 2), Space - O(N ^ 2)
B) Time - O(1), Space - O(1)
C) Time - O((4 ^ N)/root(N)), Space - O(N)
D) Time - O(N), Space - O(N)
C) Time - O((4 ^ N)/root(N)), Space - O(N)
The time complexity will nth catalan number that is O((4 ^ N)/root(N))
Auxiliary space will be O(N) to store the sequence.
Problem 3) Integer to English Words
Convert a non-negative integer num to its English words representation.
Example 1:
Input: num = 123
Output: “One Hundred Twenty Three”
Question 1) We can divide the initial problem into sub-problems. We can divide the initial integer into groups containing how many digits?
A) 1
B) 2
C) 3
D) 4
C) 3
We can simplify the problem by representing it as a set of simple sub-problems. One could split the initial integer 1234567890 on the groups containing not more than three digits 1.234.567.890. That results in representation 1 Billion 234 Million 567 Thousand 890 and reduces the initial problem to how to convert a 3-digit integer to an English word. One could split further 234 -> 2 Hundred 34 into two sub-problems : convert 1-digit integer and convert 2-digit integer. The first one is trivial. The second one could be reduced to the first one for all 2-digit integers but the ones from 10 to 19 which should be considered separately.
Problem 3) Integer to English Words
Convert a non-negative integer num to its English words representation.
Example 1:
Input: num = 123
Output: “One Hundred Twenty Three”
Question 2)
What will be the time and auxiliary space complexity of the most optimal approach? (N -> Number of digits)
A) Time - O(N ^ 2), Space - O(N)
B) Time - O(1), Space - O(1)
C) Time - O(N), Space - O(N)
D) Time - O(N), Space - O(1)
D) Time - O(N), Space - O(1)
We need to process each once, hence the time complexity will be O(N) and we can solve this problem using only a constant of extra space. Hence the auxiliary space complexity will be O(1).
Problem 4) Decode String
Given an encoded string, return its decoded string.
The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times. Note that k is guaranteed to be a positive integer.
You may assume that the input string is always valid; there are no extra white spaces, square brackets are well-formed, etc. Furthermore, you may assume that the original data does not contain any digits and that digits are only for those repeat numbers, k. For example, there will not be input like 3a or 2[4].
The test cases are generated so that the length of the output will never exceed 105.
Example 1:
Input: s = “3[a]2[bc]”
Output: “aaabcbc”
Question 1) Is it possible to solve this question using a single stack?
A) Yes
B) No
A) Yes
We can also solve this using only a single stack. The idea is to traverse the input from left to right, one character at a time.
- If the current character is a closing bracket (‘]’), we will start decoding our string. We will pop from the stack and append to the front a string ‘temp’ until we find an opening bracket (‘[‘). After we found an opening bracket, we know the next element in the stack will be an integer. So, we pop the integer and create the original number ‘num’. Then we append the ‘temp’, ‘num’ number of times, to a string and push its characters in the stack. .
- If the current character is not a closing bracket (‘]’), we just add the current character to the stack.
Problem 4) Decode String
Given an encoded string, return its decoded string.
The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times. Note that k is guaranteed to be a positive integer.
You may assume that the input string is always valid; there are no extra white spaces, square brackets are well-formed, etc. Furthermore, you may assume that the original data does not contain any digits and that digits are only for those repeat numbers, k. For example, there will not be input like 3a or 2[4].
The test cases are generated so that the length of the output will never exceed 105.
Example 1:
Input: s = “3[a]2[bc]”
Output: “aaabcbc”
Question 1) Is it possible to solve this question using a single stack?
A) Yes
B) No
