Databricks Medium Interview Questions

Background: In the context of Databricks, auctioning houses represents a series of investments where each house can be sold for a specified profit. This problem relates to optimizing revenue from investment in a big data analytics pipeline.
Problem statement: Given an array profits where profits[i] represents the profit of selling the ith house, you want to maximize your total profit. However, you cannot sell two consecutive houses. Implement a function that determines the maximum profit possible from the auctioning of these houses.Function/class signature:

• def max_profit(profits: List[int]) -> int:

Example 1:

• Input: [2, 7, 9, 3, 1]


• Output: 12


• Explanation: You can sell house 1 (profit of 7) and house 3 (profit of 9) for a total of 12 profit.

Example 2:

• Input: [1, 2, 3, 1]


• Output: 4


• Explanation: Sell house 1 (profit of 2) and house 3 (profit of 3) for a total of 4 profit.

Constraints:

• 0 <= profits.length <= 100


• The values in profits must be non-negative integers and less than 1000.

Background: In large-scale data processing systems like those at Databricks, effectively managing data with key-value pairs is crucial, especially when optimizing computations and reducing runtime.
Problem statement: You are given an array of integers nums and an integer target. Write a function to find two numbers in nums such that they add up to target. Return their indices as an array. Each input would be such that exactly one solution exists, and you may not use the same element twice.
Function signature:

• def two_sum(nums: List[int], target: int) -> List[int]:

Example 1:
Input: nums = [2, 7, 11, 15], target = 9
Output: [0, 1]
Explanation: nums[0] + nums[1] = 2 + 7 = 9.
Example 2:
Input: nums = [3, 2, 4], target = 6
Output: [1, 2]
Explanation: nums[1] + nums[2] = 2 + 4 = 6.
Constraints:

• 2 <= nums.length <= 10^4


• -10^9 <= nums[i] <= 10^9


• -10^9 <= target <= 10^9


• Only one solution exists, and you cannot use the same element twice.

Background: In data analytics, processing real-time streams of data is vital. Databricks aims to provide efficient data processing and analytics capabilities, making it essential to quickly retrieve the maximum values in a sliding window from incoming data streams.
Problem statement: Given an array of integers nums and an integer k, return the maximum sliding window for each window of size k. The output should be an array of the maximum values from each sliding window.
Function/class signature:

• def max_sliding_window(nums: List[int], k: int) -> List[int]:

Example 1:

• Input: nums = [1,3,-1,-3,5,3,6,7], k = 3


• Output: [3, 3, 5, 5, 6, 7]


• Explanation: The maximums of each sliding window are [3], [3], [5], [5], [6], and [7].

Example 2:

• Input: nums = [1], k = 1


• Output: [1]

Constraints:

• 1 <= nums.length <= 10^5


• -10^4 <= nums[i] <= 10^4


• 1 <= k <= nums.length

Background: In the data analytics and processing domain, Databricks often deals with time series data that includes stock prices. Building systems to optimize stock trading can significantly enhance trading strategies.
Problem statement: You are tasked with finding the maximum earnings that can be achieved from a list of stock prices where you can buy and sell. You can complete as many transactions as you want, but you must sell the stock before you buy again. Given an array prices representing the prices of a stock on different days, return the maximum profit you can achieve.
Function/class signature:

• def max_profit(prices: List[int]) -> int:

Example 1:

• Input: prices = [7, 1, 5, 3, 6, 4]


• Output: 7


• Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4. Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3. Total profit is 4 + 3 = 7.

Example 2:

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


• Output: 4


• Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5). Total profit is 5-1 = 4.

Constraints:

• 0 <= prices.length <= 3 * 10^4


• 0 <= prices[i] <= 10^4

Background: Databricks needs a robust system to manage stock trades efficiently as their software may provide analytics for stock markets. Utilizing dynamic programming can help in optimizing transaction strategies for maximum profits.
Problem statement: You are tasked to implement a function that determines the maximum profit that can be made from a series of stock transactions over a given number of days. Given an array prices where prices[i] is the price of a stock on the i-th day, you can complete as many transactions as you like (i.e., buy and sell multiple times) but you must sell the stock before you buy it again. Your goal is to calculate the maximum profit you can achieve.
Function/class signature:

• def maxProfit(prices: List[int]) -> int:

Example 1:
Input: prices = [7, 1, 5, 3, 6, 4]
Output: 7
Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4. Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3. Total profit = 4 + 3 = 7.
Example 2:
Input: prices = [1, 2, 3, 4, 5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
Constraints:

• 0 <= prices.length <= 30000


• 0 <= prices[i] <= 10^4