Coding Week 4 - Stacks and Linked Lists Flashcards
Problem 1) Asteroid Collision (Stacks)
We are given an array asteroids of integers representing asteroids in a row.
For each asteroid, the absolute value represents its size, and the sign represents its direction (positive meaning right, negative meaning left). Each asteroid moves at the same speed.
Find out the state of the asteroids after all collisions. If two asteroids meet, the smaller one will explode. If both are the same size, both will explode. Two asteroids moving in the same direction will never meet.
Example 1:
Input: asteroids = [5,10,-5]
Output: [5,10]
Explanation: The 10 and -5 collide resulting in 10. The 5 and 10 never collide.
Example 2:
Input: asteroids = [8,-8]
Output: []
Explanation: The 8 and -8 collide exploding each other.
Example 3:
Input: asteroids = [10,2,-5]
Output: [10]
Explanation: The 2 and -5 collide resulting in -5. The 10 and -5 collide resulting in 10.
Constraints:
2 <= asteroids.length <= 104
-1000 <= asteroids[i] <= 1000
asteroids[i] != 0
Question 1) What will be the correct output for the input [-2, -1, 1, 2]:
A) []
B) [-2, -1, 1, 2]
C) [-2, 2]
D) [2]
B) [-2, -1, 1, 2]
1st and 2nd asteroids are moving to the left and, 3rd and 4th asteroids are moving to the right. So, there will be no collision at all.
Problem 1) Asteroid Collision (Stacks)
We are given an array asteroids of integers representing asteroids in a row.
For each asteroid, the absolute value represents its size, and the sign represents its direction (positive meaning right, negative meaning left). Each asteroid moves at the same speed.
Find out the state of the asteroids after all collisions. If two asteroids meet, the smaller one will explode. If both are the same size, both will explode. Two asteroids moving in the same direction will never meet.
Example 1:
Input: asteroids = [5,10,-5]
Output: [5,10]
Explanation: The 10 and -5 collide resulting in 10. The 5 and 10 never collide.
Example 2:
Input: asteroids = [8,-8]
Output: []
Explanation: The 8 and -8 collide exploding each other.
Example 3:
Input: asteroids = [10,2,-5]
Output: [10]
Explanation: The 2 and -5 collide resulting in -5. The 10 and -5 collide resulting in 10.
Constraints:
2 <= asteroids.length <= 104
-1000 <= asteroids[i] <= 1000
asteroids[i] != 0
Question 2) We will maintain a stack to solve this problem. For any asteroid ‘A’ we will push ‘A’ into the stack if:
(Multiple options are correct)
A) Stack is empty.
B) Top of the stack is negative.
C) ‘A’ is negative.
D) ‘A’ is positive.
A) Stack is empty.
B) Top of the stack is negative.
D) ‘A’ is positive.
If the stack is empty, we simply push ‘A’ in the stack.
If the top of the stack is negative, we push ‘A’ in the stack because:
- If ‘A’ is positive, it is moving in the right direction, so it will not collide with the top of the stack, which is negative(moving in the left direction).
- If ‘A’ is negative, it is moving in the left direction, and two asteroids moving in the same direction will never collide.
- If ‘A’ is positive, we push ‘A’ in the stack because:
If the top of the stack is negative, it is moving in the left direction, and ‘A’ is moving in the right direction, so they will not collide.
If the top of the stack is positive, and ‘A’ is also positive, they will not collide as two asteroids moving in the same direction will never collide.
Problem 2) Maximum Subarray Min-Product (Prefix Sum, Stacks)
The min-product of an array is equal to the minimum value in the array multiplied by the array’s sum.
For example, the array [3,2,5] (minimum value is 2) has a min-product of 2 * (3+2+5) = 2 * 10 = 20.
Given an array of integers nums, return the maximum min-product of any non-empty subarray of nums. Since the answer may be large, return it modulo 109 + 7.
Note that the min-product should be maximized before performing the modulo operation. Testcases are generated such that the maximum min-product without modulo will fit in a 64-bit signed integer.
A subarray is a contiguous part of an array.
Example 1:
Input: nums = [1,2,3,2]
Output: 14
Explanation: The maximum min-product is achieved with the subarray [2,3,2] (minimum value is 2).
2 * (2+3+2) = 2 * 7 = 14.
Example 2:
Input: nums = [2,3,3,1,2]
Output: 18
Explanation: The maximum min-product is achieved with the subarray [3,3] (minimum value is 3).
3 * (3+3) = 3 * 6 = 18.
Example 3:
Input: nums = [3,1,5,6,4,2]
Output: 60
Explanation: The maximum min-product is achieved with the subarray [5,6,4] (minimum value is 4).
4 * (5+6+4) = 4 * 15 = 60.
Constraints:
1 <= nums.length <= 105
1 <= nums[i] <= 107
Question 1) Is the following approach correct?
(Ignore the modulo part for now)
Approach:
For each element nums[i] in array nums:
We treat nums[i] as minimum number in subarray which includes nums[i]
ans = max(ans, nums[i] * getSum(left_bound, right_bound))
left_bound: index of the farthest element greater or equal to nums[i] in the left side
right_bound: index of the farthest element greater or equal to nums[i] in the right side
A) Yes
B) No
A) Yes
Problem 2) Maximum Subarray Min-Product (Prefix Sum, Stacks)
The min-product of an array is equal to the minimum value in the array multiplied by the array’s sum.
For example, the array [3,2,5] (minimum value is 2) has a min-product of 2 * (3+2+5) = 2 * 10 = 20.
Given an array of integers nums, return the maximum min-product of any non-empty subarray of nums. Since the answer may be large, return it modulo 109 + 7.
Note that the min-product should be maximized before performing the modulo operation. Testcases are generated such that the maximum min-product without modulo will fit in a 64-bit signed integer.
A subarray is a contiguous part of an array.
Example 1:
Input: nums = [1,2,3,2]
Output: 14
Explanation: The maximum min-product is achieved with the subarray [2,3,2] (minimum value is 2).
2 * (2+3+2) = 2 * 7 = 14.
Example 2:
Input: nums = [2,3,3,1,2]
Output: 18
Explanation: The maximum min-product is achieved with the subarray [3,3] (minimum value is 3).
3 * (3+3) = 3 * 6 = 18.
Example 3:
Input: nums = [3,1,5,6,4,2]
Output: 60
Explanation: The maximum min-product is achieved with the subarray [5,6,4] (minimum value is 4).
4 * (5+6+4) = 4 * 15 = 60.
Constraints:
1 <= nums.length <= 105
1 <= nums[i] <= 107
Question 1) Is the following approach correct?
(Ignore the modulo part for now)
Approach:
For each element nums[i] in array nums:
We treat nums[i] as minimum number in subarray which includes nums[i]
ans = max(ans, nums[i] * getSum(left_bound, right_bound))
left_bound: index of the farthest element greater or equal to nums[i] in the left side
right_bound: index of the farthest element greater or equal to nums[i] in the right side
A) Yes
B) No
B) No
We need to create three arrays
To store the prefix sum.
To store the next smaller element.
Too store the previous smaller element.
Each will take O(N) time and O(N) space.
After creating the above arrays, we just need to iterate through nums once, to find the answer.
Problem 3) Valid Parentheses (Stacks)
Given a string s containing just the characters ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[’ and ‘]’, determine if the input string is valid.
An input string is valid if:
Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.
Every close bracket has a corresponding open bracket of the same type.
Example 1:
Input: s = “()”
Output: true
Example 2:
Input: s = “()[]{}”
Output: true
Example 3:
Input: s = “(]”
Output: false
Constraints:
1 <= s.length <= 104
s consists of parentheses only ‘()[]{}’.
Question 1) For each bracket in ‘s’, if the current bracket is a closing bracket and the top of the stack is the opening bracket of the same type, I pop from the stack. Otherwise I push the current bracket in the stack. What will the empty stack, after traversing ‘s’ indicate?
A) Input string is valid.
B) Input string is invalid.
A) Input string is valid.
If the stack is empty at last, it means there was an opening bracket for each closing bracket of the same type and in the correct order(The output of the above approach for input “([)]” is false, which is correct).
Problem 3) Valid Parentheses (Stacks)
Given a string s containing just the characters ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[’ and ‘]’, determine if the input string is valid.
An input string is valid if:
Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.
Every close bracket has a corresponding open bracket of the same type.
Example 1:
Input: s = “()”
Output: true
Example 2:
Input: s = “()[]{}”
Output: true
Example 3:
Input: s = “(]”
Output: false
Constraints:
1 <= s.length <= 104
s consists of parentheses only ‘()[]{}’.
Question 2) What will be the time and auxiliary space complexity of the stacks approach?
(N -> length of the input string)
A) Time - O(N), Space - O(1)
B) Time - O(N), Space - O(N)
C) Time - O(N ^ 2), Space - O(1)
D) Time - O(N ^ 2), Space - O(N)
B) Time - O(N), Space - O(N)
Time complexity : O(N), because we simply traverse the given string one character at a time and push and pop operations on a stack take O(1) time.
Space complexity : O(N), as we push all opening brackets onto the stack and in the worst case, we will end up pushing all the brackets onto the stack. e.g. ((((((((((.
Problem 4) Remove Zero Sum Consecutive Nodes from Linked List (Prefix sum, Hash Table, Linked List)
Given the head of a linked list, we repeatedly delete consecutive sequences of nodes that sum to 0 until there are no such sequences.
After doing so, return the head of the final linked list. You may return any such answer.
(Note that in the examples below, all sequences are serializations of ListNode objects.)
Example 1:
Input: head = [1,2,-3,3,1]
Output: [3,1]
Note: The answer [1,2,1] would also be accepted.
Example 2:
Input: head = [1,2,3,-3,4]
Output: [1,2,4]
Example 3:
Input: head = [1,2,3,-3,-2]
Output: [1]
Constraints:
The given linked list will contain between 1 and 1000 nodes.
Each node in the linked list has -1000 <= node.val <= 1000.
Question 1) Given a linked list head = [a, b, c, d, e], where a, b, c, d, e stores some integer values. The cumulative sum of head = [1, 5, 7, 1, 8]. Without finding the actual values of a, b, c, d, e, tell which of the following options is correct.
A) a + b + c + d = 0
B) b + c + d = 0
C) c + d = 0
D) a + b - c = 0
B) b + c + d = 0
Cumulative sum of a and d is same.
a = 1 and a + b + c + d = 1, then b + c + d = 0.
To solve this question we can simply remove b, c, d by performing the following operation:
a.next = d.next.
Problem 4) Remove Zero Sum Consecutive Nodes from Linked List (Prefix sum, Hash Table, Linked List)
Given the head of a linked list, we repeatedly delete consecutive sequences of nodes that sum to 0 until there are no such sequences.
After doing so, return the head of the final linked list. You may return any such answer.
(Note that in the examples below, all sequences are serializations of ListNode objects.)
Example 1:
Input: head = [1,2,-3,3,1]
Output: [3,1]
Note: The answer [1,2,1] would also be accepted.
Example 2:
Input: head = [1,2,3,-3,4]
Output: [1,2,4]
Example 3:
Input: head = [1,2,3,-3,-2]
Output: [1]
Constraints:
The given linked list will contain between 1 and 1000 nodes.
Each node in the linked list has -1000 <= node.val <= 1000.
Question 1) What is the time and auxiliary space complexity of the (Prefix sum + Hash Table) approach?
(N -> Length of the linked list)
A) Time - O(N ^ 2), Space - O(N)
B) Time - O(N ^ 2), Space - O(1)
C) Time - O(N), Space - O(N)
D) Time - O(N ^ 2), Space - O(N ^ 2)
C) Time - O(N), Space - O(N)
Finding and storing the prefix sum of each node will take O(N) time and O(N) space.
Then we can traverse the Hash Table to find nodes having the same prefix sum in O(N) time and let’s say nodes a and b have prefix sum, so we can perform a.next = b.next which will take O(1) time.
Hence, the time complexity and space complexity will be O(N).
Problem 5) Evaluate Reverse Polish Notation
Evaluate the value of an arithmetic expression in Reverse Polish Notation.
Valid operators are +, -, *, and /. Each operand may be an integer or another expression.
Note that division between two integers should truncate toward zero.
It is guaranteed that the given RPN expression is always valid. That means the expression would always evaluate to a result, and there will not be any division by zero operation.
Example 1:
Input: tokens = [“2”,”1”,”+”,”3”,”*”]
Output: 9
Explanation: ((2 + 1) * 3) = 9
Example 2:
Input: tokens = [“4”,”13”,”5”,”/”,”+”]
Output: 6
Explanation: (4 + (13 / 5)) = 6
Example 3:
Input: tokens = [“10”,”6”,”9”,”3”,”+”,”-11”,””,”/”,””,”17”,”+”,”5”,”+”]
Output: 22
Explanation: ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22
Constraints:
1 <= tokens.length <= 104
tokens[i] is either an operator: “+”, “-“, “*”, or “/”, or an integer in the range [-200, 200].
Question 1) In the stack approach, while traversing the ‘tokens’ if we encounter an operator, what is the correct operation to be performed?
A) push it directly on to the stack
B) pop 2 operands, evaluate them and push the result on to the stack
C) pop the entire stack
D) ignore the operator
B) pop 2 operands, evaluate them and push the result on to the stack
When an operator is encountered, the first two operands are popped from the stack, they are evaluated and the result is pushed into the stack.
