Instacart Medium Interview Questions

Background: At Instacart, understanding customer preferences is crucial for enhancing user experience. Analyzing the most frequently purchased items helps optimize inventory and offers.
Problem statement: Given a list of strings representing item names in a shopping cart (e.g., ['apple', 'banana', 'apple', 'orange', 'banana', 'banana']), write a function most_frequent_item(cart: List[str]) -> Tuple[str, int] that returns the item that appears most frequently in the cart and its count. If multiple items have the same count, return any one of them.
Function/class signature:

• most_frequent_item(cart: List[str]) -> Tuple[str, int]

Example 1:
Input: ['apple', 'banana', 'apple', 'orange', 'banana', 'banana']
Output: ('banana', 3)
Explanation: 'banana' appears 3 times, more than any other item.Example 2:
Input: ['grape', 'apple', 'grape', 'orange', 'apple']
Output: ('grape', 2)
Explanation: Both 'grape' and 'apple' appear 2 times, but 'grape' can be returned.Constraints:

• 1 ≤ |cart| ≤ 10^6


• Each item name is a non-empty string of length at most 100.

Background: Instacart needs efficient algorithms to optimize delivery logistics and maximize the number of deliveries handled within a specific timeframe. This impacts customer satisfaction and operational costs.
Problem statement: You are tasked with implementing a function that determines the maximum number of deliveries a delivery person can make within a time window. Each delivery requires a certain amount of time, and the delivery person cannot exceed their total available time. Given a list of delivery times for n deliveries and a total available time T, return the maximum number of deliveries that can be completed.
Function/class signature:

• def max_deliveries(delivery_times: List[int], total_time: int) -> int:




Example 1:


• Input: delivery_times = [2, 3, 4, 5], total_time = 7


• Output: 2


• Explanation: The delivery person can complete two deliveries taking 2 and 3 units of time, summing up to 5, which is less than 7.


Example 2:


• Input: delivery_times = [1, 2, 3, 4], total_time = 5


• Output: 2


• Explanation: The delivery person can complete two deliveries taking 1 and 2 units, summing to 3, which is less than 5.


Constraints:


• 1 <= len(delivery_times) <= 100


• 1 <= delivery_times[i] <= 100


• 1 <= total_time <= 1000`

1. Background: Instacart is focused on efficient grocery delivery, and determining which items can be combined into a single batch can optimize delivery operations. This problem relates to managing the batch size to minimize delivery costs while maximizing efficiency.
2. Problem statement: You are given an array of integers weights, where each value represents the weight of a grocery item. The total weight of any batch cannot exceed a limit maxWeight. Write a function that finds the maximum number of items you can include in a single batch while respecting the maxWeight. Key constraints are that the items must be taken in order from the weights array.
3. Function/class signature:
- def max_items_in_batch(weights: List[int], maxWeight: int) -> int:
4. Example 1:
- Input: weights = [2, 3, 5, 2, 8], maxWeight = 10
- Output: 4
- Explanation: You can combine items with weights [2, 3, 5], and one additional item with weight 2 which totals 10 (i.e., 2 + 3 + 5 = 10).
5. Example 2:
- Input: weights = [1, 1, 1, 1, 1], maxWeight = 3
- Output: 3
- Explanation: The best option is to take 3 items with weight 1 each totaling 3.
6. Constraints:
- 1 <= len(weights) <= 1000
- 1 <= weights[i] <= 100
- 1 <= maxWeight <= 1000

Background: Instacart needs an efficient method to calculate the shortest delivery path for its shoppers navigating through grocery stores. This problem is crucial for optimizing delivery times, improving customer satisfaction, and enhancing operational efficiency.
Problem statement: Given a grid representing a grocery store layout where obstacles (shelves or areas that cannot be traversed) are denoted by 1 and open paths by 0, write a function to find the shortest path from the starting point to the destination. The function should return the minimum number of steps needed to reach the destination, or -1 if the destination cannot be reached.
Function/class signature:

• def shortest_delivery_path(store: List[List[int]], start: Tuple[int, int], destination: Tuple[int, int]) -> int:

Example 1:

• Input: store = [[0,0,0],[0,1,0],[0,0,0]], start = (0, 0), destination = (2, 2)


• Output: 4


• Explanation: The path is [(0,0) -> (0,1) -> (0,2) -> (1,2) -> (2,2)], with 4 steps.

Example 2:

• Input: store = [[0,1],[0,0]], start = (0, 0), destination = (1, 1)


• Output: 2


• Explanation: The path is [(0,0) -> (1,0) -> (1,1)], with 2 steps.

Constraints:

• 1 <= len(store) <= 100


• 1 <= len(store[i]) <= 100


• Start and destination coordinates are within bounds and valid (0, 0) to (len(store) - 1, len(store[0]) - 1).

Background: In a complex shopping delivery network, Instacart aims to optimize the paths of shoppers to minimize delivery times. Using efficient algorithms helps in dynamically calculating the best delivery routes based on various factors.
Problem statement: Given a list of deliveryPoints representing the sequence of delivery locations and an integer maxStops which represents the maximum number of stops a shopper can make, write a function that returns the shortest route for the shopper that includes all the delivery points up to maxStops. Each delivery point has a distance associated with it. You can assume that the list is already sorted by the distance from the store.
Function/class signature:

• def shortest_delivery_route(deliveryPoints: List[int], maxStops: int) -> List[int]:

Example 1:
Input: deliveryPoints = [2, 3, 5, 8, 10], maxStops = 3
Output: [2, 3, 5]
Explanation: The shortest route with a maximum of 3 stops is to deliver to the points 2, 3, and 5.Example 2:
Input: deliveryPoints = [1, 4, 6, 7], maxStops = 2
Output: [1, 4]
Explanation: The shortest route with a maximum of 2 stops is to deliver to the points 1 and 4.Constraints:

• 1 <= len(deliveryPoints) <= 100


• 1 <= deliveryPoints[i] <= 10^6


• 1 <= maxStops <= len(deliveryPoints)

1. Background: In the context of Instacart, understanding customer purchasing behavior can help optimize inventory management and promotional strategies. Identifying the k most frequently ordered items allows Instacart to focus its marketing efforts.
2. Problem statement: Given a list of items that represent customer orders, each an item in a string format, and an integer k, write a function to return the k most frequently purchased items in order of their frequency. If two items have the same frequency, return them in the order they first appeared in the list.
3. Function/class signature:
- def top_k_frequent(items: List[str], k: int) -> List[str]:
4. Example 1:
- Input: items = ['apple', 'banana', 'apple', 'orange', 'banana', 'banana'], k = 2
- Output: ['banana', 'apple']
- Explanation: 'banana' appears 3 times, and 'apple' appears 2 times.
5. Example 2:
- Input: items = ['carrot', 'carrot', 'potato', 'onion', 'carrot', 'potato'], k = 1
- Output: ['carrot']
6. Constraints:
- 1 <= len(items) <= 10^4
- 1 <= k <= len(items)

Background: Instacart needs to optimize the shopping experience by identifying longer lists of consecutive items in a user's cart, which may indicate a trend or spike in demand for certain food categories. This will aid in inventory management and promotional strategies.
Problem statement: Given an array of integers representing grocery item IDs in a shopping cart, find the maximum length of a subarray where the IDs are consecutive. The IDs can be in any order for the length of the subarray to be considered valid.
Function/class signature:

• def longest_consecutive_items(items: List[int]) -> int:

Example 1:
Input: [1, 3, 2, 4, 5]
Output: 5
Explanation: The IDs 1, 2, 3, 4, 5 form a consecutive subarray.
Example 2:
Input: [10, 2, 3, 11, 4, 5, 1]
Output: 5
Explanation: The IDs 1, 2, 3, 4, 5 form a consecutive subarray.
Constraints:

• 1 <= len(items) <= 1000


• Each item ID is a positive integer up to 10^6.