Apple Hard Interview Questions

Background: Apple heavily relies on highly efficient routing and navigation systems, especially within their Apple Maps product. This question is designed to assess how candidates can apply graph algorithms to solve real-world problems related to navigation.
Problem statement: Given a directed graph represented as an adjacency list where each edge has a weight that represents the distance between nodes, write a function that returns the shortest path from a starting node to a destination node. The function should handle cycles appropriately and return -1 if no path exists.
Function/class signature:

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

Example 1:

• Input: graph = {0: [(1, 2), (2, 4)], 1: [(2, 1)], 2: []}, start = 0, end = 2


• Output: 3


• Explanation: The path 0 -> 1 -> 2 has a total weight of 2 + 1 = 3.

Example 2:

• Input: graph = {0: [(1, 5)], 1: [(2, 1)], 2: [(0, -6)]}, start = 0, end = 2


• Output: -1


• Explanation: There's no valid path due to the negative cycle.

Constraints:

• 1 <= number of nodes <= 10^5


• Weights are integers in the range [-1000, 1000].


• A node is represented by an integer.


• The graph will not contain self-loops.

In order to track the number of borrowed books, Apple Books needs an effective way to manage the list of borrowed books based on different genres and their borrowing time.
Problem statement: You are given an array of integers books representing the borrowing times in days for different genres of books. Return the number of unique genres that have been borrowed for k or more days.Example 1:
Input: books = [3, 1, 4, 1, 5, 9, 2], k = 3
Output: 4
Explanation: The unique genres with a borrowing time of 3 days or more are 3, 4, 5, and 9.Example 2:
Input: books = [1, 2, 3, 4, 5, 6], k = 5
Output: 2
Explanation: The unique genres with a borrowing time of 5 days or more are 5 and 6.
Constraints:

• 1 <= books.length <= 10^4


• 1 <= books[i] <= 10^5


• 1 <= k <= 10^5

Apple is known for its high-quality media streaming services. The goal of this problem is to create a dynamic viewing experience that adapts to varying bandwidth conditions.
Problem statement: Given an array of integers representing the bandwidth availability over time, find the maximum sum of continuous k bandwidth values that can ensure a smooth streaming experience.Example 1:
Input: bandwidth = [10, 1, 2, 3, 4, 5, 6], k = 3
Output: 15
Explanation: The maximum bandwidth from indices 4 to 6 is 5 + 6 + 4 = 15.Example 2:
Input: bandwidth = [12, 5, 4, 1, 3], k = 2
Output: 17
Explanation: The maximum bandwidth from indices 0 to 1 is 12 + 5 = 17.
Constraints:

• 1 <= bandwidth.length <= 10^4


• 1 <= bandwidth[i] <= 100


• 1 <= k <= bandwidth.length