Coding Week 1 - Sorting and Binary Search Flashcards
3Sum Closet
Given an integer array nums of length n and an integer target, find three integers in nums such that the sum is closest to target.
Return the sum of the three integers.
You may assume that each input would have exactly one solution.
Example 1:
Input: nums = [-1,2,1,-4], target = 1
Output: 2
Explanation: The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).
Question: Why is it better to solve the above problem using (presorting + two pointers) approach than the HashTable approach?
a. The time complexity of (presorting + two pointers) approach is less than Hashtable approach.
b. The space complexity of (presorting + two pointers) approach is less than Hashtable approach..
c. The coding for (presorting + two pointers) approach is easier than the Hashtable approach.
d. The Hashtable approach does not guarantee a right answer.
Answer:
b. The space complexity of (presorting + two pointers) approach is less than Hashtable approach.
Explanation: In hash table approach, the space complexity will be O(n) whereas, the space complexity of (presorting + two pointers) will be O(1).
3Sum Closet
Given an integer array nums of length n and an integer target, find three integers in nums such that the sum is closest to target.
Return the sum of the three integers.
You may assume that each input would have exactly one solution.
Example 1:
Input: nums = [-1,2,1,-4], target = 1
Output: 2
Explanation: The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).
Question: What will be the asymptotic time and space complexity of the (presorting + two pointers) approach to solve the above problem?
a. Time - O(n), Space - O(n)
b. Time - O(n * (log n)), Space - O(n)
c. Time - O(n ^ 2), Space - O(1)
d. Time - O((n ^ 2) * (log n)), Space - O(n ^ 2)
Answer:
c. Time - O(n ^ 2), Space - O(1)
Explanation: We have outer and inner loops, each going through n elements. Sorting takes O(n * log(n)) time. so overall complexity is O(n * log (n) + n ^ 2). This is asymptotically equivalent to O(n ^ 2).
Reorder Data in Log Files
You are given an array of logs. Each log is a space-delimited string of words, where the first word is the identifier.
There are two types of logs:
- Letter-logs: All words (except the identifier) consist of lowercase English letters.
- Digit-logs: All words (except the identifier) consist of digits.
Reorder these logs so that:
- The letter-logs come before all digit-logs.
- The letter-logs are sorted lexicographically by their contents. If their contents are the same, then sort them lexicographically by their identifiers.
- The digit-logs maintain their relative ordering.
Return the final order of the logs.
Example 1:
Input: logs = [“dig1 8 1 5 1”,”let1 art can”,”dig2 3 6”,”let2 own kit dig”,”let3 art zero”]
Output: [“let1 art can”,”let3 art zero”,”let2 own kit dig”,”dig1 8 1 5 1”,”dig2 3 6”]
Explanation:
The letter-log contents are all different, so their ordering is “art can”, “art zero”, “own kit dig”.
The digit-logs have a relative order of “dig1 8 1 5 1”, “dig2 3 6”.
Question: The efficient approach of solving this problem has the time complexity of:
(N -> Length of ‘logs’ array, M -> Length of longest log)
a. O(M * N)
b. O(M)
c. O(M * N * log (N))
d. O(M * N * log (M))
Answer:
c. O(M * N * log (N))
Explanation: Sorting the ‘logs’ will take O(N * log (N)) time and each comparison in sorting will take O(M) time.
Search a 2D Matrix II
Write an efficient algorithm that searches for a value target in an m x n integer matrix matrix. This matrix has the following properties:
- Integers in each row are sorted in ascending from left to right.
- Integers in each column are sorted in ascending from top to bottom.
Example 1 (in the photo below)
Input: matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
Output: true
Question: In the binary search approach, we will begin our search from:
a. Top right
b. Top left
c. Bottom right
d. Middle of the matrix
Answer:
a. Top Right
Explanation: If we begin from top right, then if the current element is lesser than target we will discard this row and move downwards, as this row contains elements lesser than the target and if the current element is greater than the target than we will discard this column and move inward as this column will contain elements greater than the target. We can also start our search from the bottom left.
Search a 2D Matrix II
Write an efficient algorithm that searches for a value target in an m x n integer matrix matrix. This matrix has the following properties:
- Integers in each row are sorted in ascending from left to right.
- Integers in each column are sorted in ascending from top to bottom.
Example 1 (in the photo below)
Input: matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
Output: true
Question: The time and space complexity of binary search approach will:
(n -> no. of rows, m -> number of columns)
a. Time - O(n + m), Space - O(n + m)
b. Time - O(n * m), Space - O(n + m)
c. Time - O(n + m), Space - O(1)
d. Time - O(n + m), Space - O(n * m)
Answer:
c. Time - O(n + m), Space - O(1)
Explanation: Time complexity will be O(n + m) because at each check we will either discard a complete row or a complete column, hence we will check only (n + m) number of elements in the worst case.
Space complexity will be O(1), because we do not need any auxiliary space.
Capacity To Ship Packages Within D Days
A conveyor belt has packages that must be shipped from one port to another within days days.
The ith package on the conveyor belt has a weight of weights[i]. Each day, we load the ship with packages on the conveyor belt (in the order given by weights). We may not load more weight than the maximum weight capacity of the ship.
Return the least weight capacity of the ship that will result in all the packages on the conveyor belt being shipped within days days.
Example 1:
Input: weights = [1,2,3,4,5,6,7,8,9,10], days = 5
Output: 15
Explanation: A ship capacity of 15 is the minimum to ship all the packages in 5 days like this:
1st day: 1, 2, 3, 4, 5
2nd day: 6, 7
3rd day: 8
4th day: 9
5th day: 10
Note that the cargo must be shipped in the order given, so using a ship of capacity 14 and splitting the packages into parts like (2, 3, 4, 5), (1, 6, 7), (8), (9), (10) is not allowed.
Question: What is the minimum and maximum possible answer, irrespective of the given ‘days’?
a. Minimum - min(weights) and Maximum - max(weights)
b. Minimum - min(weights) and Maximum - sum(weights)
c. Minimum - max(weights) and Maximum - sum(weights)
d. Minimum - max(weights) and Maximum - length(weights)
Answer:
c. Minimum - max(weights) and Maximum - sum(weights)
Explanation: If the number of days is the length of the ‘weights’ array, we still need capacity equal to ‘maximum weight’ as we cannot divide any weight. If the number of days is 1, we need capacity equal to ‘Sum of all the weights’ to carry all weight in one day.
Capacity To Ship Packages Within D Days
A conveyor belt has packages that must be shipped from one port to another within days days.
The ith package on the conveyor belt has a weight of weights[i]. Each day, we load the ship with packages on the conveyor belt (in the order given by weights). We may not load more weight than the maximum weight capacity of the ship.
Return the least weight capacity of the ship that will result in all the packages on the conveyor belt being shipped within days days.
Example 1:
Input: weights = [1,2,3,4,5,6,7,8,9,10], days = 5
Output: 15
Explanation: A ship capacity of 15 is the minimum to ship all the packages in 5 days like this:
1st day: 1, 2, 3, 4, 5
2nd day: 6, 7
3rd day: 8
4th day: 9
5th day: 10
Note that the cargo must be shipped in the order given, so using a ship of capacity 14 and splitting the packages into parts like (2, 3, 4, 5), (1, 6, 7), (8), (9), (10) is not allowed.
Question: The time and space complexity of binary search approach will:
a. Time - O(length (weights) * log (sum (weights)), Space - O(1)
b. Time - O(length (weights) * log (max (weights)), Space - O(1)
c. Time - O(min (weights) * log (sum (weights))), Space - O(1)
d. Time - O(max(weights) * log (sum (weights))), Space - O(1)
Answer:
a. Time - O(length (weights) * log (sum (weights)), Space - O(1)
Explanation: We run a binary search in the sum space which is bounded by [max(weights), sum(weights)]. For each mid value, we will check if capacity equal to mid is possible or not. For checking it, we will iterate through the ‘weights’ array. Hence, the time complexity will be O(length (weights) * log (sum (weights)).
