Databricks 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

1. Background: In the Databricks ecosystem for financial services, managing stock orders efficiently and accurately is crucial. This problem relates to the order handling system for a stock broker, which must process orders in a transactional, reliable manner.
2. Problem Statement: You are tasked with developing a system that handles stock orders for a broker. The order system should process BUY and SELL orders and ensure no expired orders are processed. Each order has a unique ID, a stock symbol, a quantity, and a timestamp indicating when it was placed. Expired orders should be automatically removed from processing. Implement the method void processOrder(Order order) and return a list of confirmed orders.
3. Function/class signature:
- class Order:
- def __init__(self, order_id: int, stock_symbol: str, quantity: int, timestamp: int):
- def processOrder(self, order: Order) -> List[Order]:
4. Example 1:
- Input: Order(1, "AAPL", 10, 100)
- Output: Confirmed Order: Order(1, "AAPL", 10, 100)
- Explanation: A valid buy order is placed and confirmed.
5. Example 2:
- Input: Order(2, "GOOG", 5, 50) (expired order is not processed)
- Output: []
- Explanation: The order has expired and is not confirmed.
6. Constraints:
- 0 < order_id <= 10^6
- 0 < quantity <= 1000
- timestamp is a positive integer designating the order time.

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: In Databricks, efficient data processing often involves navigating complex dependency graphs for job scheduling. Understanding how to find the shortest path in a directed graph can optimize such workflows.
Problem statement: Given a directed graph represented as an adjacency list, implement a function to find the shortest path from a starting node to a destination node. Each edge has a weight that represents the time taken to travel along that edge. If there is no path, return -1.
Function/class signature:

• def shortest_path(graph: Dict[int, List[Tuple[int, int]]], start: int, destination: int) -> Union[int, List[int]]:

Example 1:
Input: graph = {0: [(1, 4), (2, 2)], 1: [(3, 1)], 2: [(1, 1), (3, 5)], 3: []}, start = 0, destination = 3
Output: 5
Explanation: The shortest path is 0 -> 2 -> 1 -> 3, which has a total weight of 5.Example 2:
Input: graph = {0: [(1, 4), (2, 1)], 1: [(3, 1)], 2: [(1, 2), (3, 5)], 3: []}, start = 0, destination = 1
Output: 4 Constraints:

• The number of nodes in the graph will be 1 <= len(graph) <= 100.


• Each edge's weight is a positive integer not exceeding 10^3.


• No cycles will be present in the graph.

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