Grab Interview
1. Questions
- String Without AAA or BBB — Medium — 37.7% 🔗 https://leetcode.com/problems/string-without-aaa-or-bbb
-
Edge case: (a = 7, b = 1) => Try: “aabaaaba” → still has “aaa”.
-
Time Complexity = O(a + b)
-
Space Complexity = O(a + b) (for the output string).
class Solution:
def strWithout3a3b(self, a: int, b: int) -> str:
# 🔹 Edge case: impossible scenario
if a > 2 * (b + 1) or b > 2 * (a + 1):
return "" # or raise Exception("No valid string can be formed")
res = []
while a > 0 or b > 0:
if a > b:
# Prefer 'a', but avoid "aaa"
if len(res) >= 2 and res[-1] == res[-2] == 'a':
res.append('b')
b -= 1
else:
res.append('a')
a -= 1
else:
# Prefer 'b', but avoid "bbb"
if len(res) >= 2 and res[-1] == res[-2] == 'b':
res.append('a')
a -= 1
else:
res.append('b')
b -= 1
return "".join(res)
- Partition Array into Disjoint Intervals — Medium — 45.4% 🔗 https://leetcode.com/problems/partition-array-into-disjoint-intervals
Idea:
-
max_left[i] <= min_right[i+1] => then we can partition at position i.
-
left_max = the maximum value that must be included in the left partition (so far).
If we see a new value nums[i] that is smaller than this left_max, it means:
If we cut the partition before i, that small number would end up in the right part, but then right would contain an element < left_max, which breaks the rule.
def partitionDisjoint(nums):
left_max = nums[0]
max_so_far = nums[0]
partition_idx = 0
for i in range(1, len(nums)):
max_so_far = max(max_so_far, nums[i])
if nums[i] < left_max: # must extend left partition
partition_idx = i
left_max = max_so_far
return partition_idx + 1
-
Minimum Cost For Tickets — Medium — 60.5% 🔗 https://leetcode.com/problems/minimum-cost-for-tickets
-
Word Abbreviation — Hard — 54.3% 🔗 https://leetcode.com/problems/word-abbreviation
-
Convert to Base -2 — Medium — 59.0% 🔗 https://leetcode.com/problems/convert-to-base-2
-
Reconstruct a 2-Row Binary Matrix — Medium — 40.4% 🔗 https://leetcode.com/problems/reconstruct-a-2-row-binary-matrix
-
Trapping Rain Water — Hard — 48.9% 🔗 https://leetcode.com/problems/trapping-rain-water
-
Add Two Numbers — Medium — 33.9% 🔗 https://leetcode.com/problems/add-two-numbers
-
First Missing Positive — Hard — 32.0% 🔗 https://leetcode.com/problems/first-missing-positive
-
Best Time to Buy and Sell Stock — Easy — 50.5% 🔗 https://leetcode.com/problems/best-time-to-buy-and-sell-stock
-
Palindrome Linked List — Easy — 39.3% 🔗 https://leetcode.com/problems/palindrome-linked-list
-
Product of Array Except Self — Medium — 60.1% 🔗 https://leetcode.com/problems/product-of-array-except-self
-
Kth Largest Element in an Array — Medium — 55.4% 🔗 https://leetcode.com/problems/kth-largest-element-in-an-array
-
Adding Two Negabinary Numbers — Medium — 34.2% 🔗 https://leetcode.com/problems/adding-two-negabinary-numbers
-
Merge Intervals — Medium — 35.4% 🔗 https://leetcode.com/problems/merge-intervals
-
Longest Substring Without Repeating Characters — Medium — 28.2% 🔗 https://leetcode.com/problems/longest-substring-without-repeating-characters
-
Two Sum — Easy — 55.7% 🔗 https://leetcode.com/problems/two-sum
-
Minimum Number of Food Buckets to Feed the Hamsters — Medium — 47.0% 🔗 https://leetcode.com/problems/minimum-number-of-food-buckets-to-feed-the-hamsters
-
Longest Palindromic Substring — Medium — 35.8% 🔗 https://leetcode.com/problems/longest-palindromic-substring
-
LRU Cache — Medium — 45.2% 🔗 https://leetcode.com/problems/lru-cache
-
Search a 2D Matrix — Medium — 52.2% 🔗 https://leetcode.com/problems/search-a-2d-matrix
-
Valid Parentheses — Easy — 42.3% 🔗 https://leetcode.com/problems/valid-parentheses
-
Simplify Path — Medium — 47.8% 🔗 https://leetcode.com/problems/simplify-path
-
Daily Temperatures — Medium — 67.3% 🔗 https://leetcode.com/problems/daily-temperatures
-
Number of Steps to Reduce a Number in Binary Representation to One — Medium — 61.6% 🔗 https://leetcode.com/problems/number-of-steps-to-reduce-a-number-in-binary-representation-to-one