Apple Interview Questions

1. Background: At Apple, improving performance in data manipulation is crucial, especially in applications like Maps where navigation data can be represented using linked lists. Efficiently reversing a linked list is a fundamental operation that can optimize various algorithmic processes within the application.
2. Problem statement: Given the head of a singly linked list, reverse the list and return the new head. For example, the list 1 -> 2 -> 3 -> 4 -> 5 would become 5 -> 4 -> 3 -> 2 -> 1 after reversal.
3. Function/class signature:
- def reverse_list(head: Optional[ListNode]) -> Optional[ListNode]:
4. Example 1:
- Input: head = [1, 2, 3, 4, 5]
- Output: [5, 4, 3, 2, 1]
- Explanation: The linked list is reversed to give the output list.
5. Example 2:
- Input: head = []
- Output: []
- Explanation: An empty list should return an empty list.
6. Constraints:
- The number of nodes in the list is in the range [0, 5000].
- Node values are within the range [-5000, 5000].
- Must solve with O(n) time complexity and O(1) space complexity.

Background: In many Apple products, efficient manipulation of bits is crucial for feature enhancements, such as optimizing memory usage or processing data more efficiently in complex algorithms.
Problem statement: Write a C function isolate_bits(int number, int k, int n) that isolates n bits from an integer number starting from a given bit offset k. You should return the isolated bits as an integer. The isolated bits should be obtained by shifting the original number to the right by k bits and masking the first n bits from the result.
Function/class signature:

• int isolate_bits(int number, int k, int n)

Example 1:
Input: isolate_bits(29, 1, 3)
Output: 7
Explanation: The binary representation of 29 is 11101. Isolating 3 bits from position 1 results in 111 which is 7 in decimal.Example 2:
Input: isolate_bits(15, 0, 2)
Output: 3
Explanation: The binary representation of 15 is 01111. Isolating 2 bits from position 0 results in 11 which is 3 in decimal.Constraints:

• 0 <= number <= 2^31 - 1


• 0 <= k <= 31


• 1 <= n <= 31 - k

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.

1. Background: Apple Music needs an efficient caching mechanism to store recently accessed song data. An LRU (Least Recently Used) cache can improve the performance of music playback by storing the most frequently accessed songs while efficiently managing memory.
2. Problem statement: You need to implement an LRU cache to manage song data. The cache should support two operations: get(songId: int) which retrieves the song data if it exists in the cache, and put(songId: int, songData: str) which adds a new song data to the cache. If the cache exceeds its capacity, the least recently used song should be removed. Ensure that both operations are performed in O(1) time complexity.
3. Function/class signature:
- def get(self, songId: int) -> str:
- def put(self, songId: int, songData: str) -> None:
4. Example 1:
- Input: put(1, "Song A"), put(2, "Song B"), get(1)
- Output: "Song A"
- Explanation: Song A is retrieved from the cache.
5. Example 2:
- Input: put(3, "Song C"), get(2)
- Output: -1
- Explanation: After adding Song C, the cache evicts Song B (least recently used), hence get(2) returns -1.
6. Constraints:
- 1 <= capacity <= 1000
- 0 <= songId < 10^6
- The put method will not be called if the songId already exists in the cache.
- The songData for each songId is guaranteed to be unique and non-empty.

Background: In building applications that handle real-time streaming data, like the Apple Music app, it is crucial to efficiently process and store user input to provide seamless playback experiences.
Problem statement: Given a string s, find the length of the longest substring without repeating characters. Ensure that your solution uses an efficient approach, as Apple's performance standards require handling data optimally.
Function/class signature:

• def length_of_longest_substring(s: str) -> int:

Example 1:

• Input: "abcabcbb"


• Output: 3


• Explanation: The answer is the substring "abc", with the length of 3.

Example 2:

• Input: "bbbbb"


• Output: 1


• Explanation: The answer is "b", with the length of 1.

Constraints:

• 0 <= s.length <= 10^5


• s consists of English letters, digits, symbols, and spaces.

Background: Apple’s services, such as Apple Music or Apple Podcasts, often manage user playlists as linked lists. Efficient manipulation of these lists is essential for performance.
Problem statement: Given the head of a singly linked list, reverse the list and return the new head. A linked list is a sequence of nodes where each node contains a value and a pointer to the next node. You need to reverse the linkage of the nodes.
Function/class signature:

• def reverse_linked_list(head: Optional[ListNode]) -> Optional[ListNode]:

Example 1:

• Input: head = 1 -> 2 -> 3 -> 4 -> 5


• Output: 5 -> 4 -> 3 -> 2 -> 1


• Explanation: The list is reversed, changing the pointers accordingly.

Example 2:

• Input: head = 1 -> 2


• Output: 2 -> 1

Constraints:

• The number of nodes in the list is between 0 and 5000.


• The value of each node is between -1000 and 1000.

Background: Apple's products often involve managing user data efficiently. A balanced binary search tree can optimize search times for user preferences in applications like the App Store.
Problem statement: You are tasked with writing a function that balances a binary search tree. Given the root of a binary search tree, rearrange the nodes so that they form a balanced binary search tree. The height of the new tree should be minimized. Return the root of the balanced binary search tree.
Function/class signature:

• def balance_bst(root: TreeNode) -> TreeNode:

Example 1:

• Input: root = [1, null, 2, null, 3, null, 4]


• Output: [2, 1, 3, null, null, null, 4]


• Explanation: The original tree is skewed to the right, so the balanced version restructures it.

Example 2:

• Input: root = [3, 1, 4, null, 2]


• Output: [2, 1, 3, null, null, null, 4]


• Explanation: The balanced tree now has an equal height on both sides.

Constraints:

• The number of nodes in the tree is in the range [1, 1000].


• -10^4 <= Node.val <= 10^4


• All the values in the tree are unique.

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

Apple Music needs a fast caching layer to store recently played songs and their metadata, enhancing user experience by minimizing load times while playing music.
Class LRUCache:

• LRUCache(int capacity): Initializes the LRU cache with a positive size cap.


• int get(int key): Returns the value of the key if the key exists, otherwise returns -1.


• void put(int key, int value): Updates the value of the key if it exists, or adds the key-value pair if it doesn't. When the cache reached its capacity, it should invalidate the least recently used item before inserting the new item.

Example 1:
Input: cache = LRUCache(2), cache.put(1, 1), cache.put(2, 2), cache.get(1)
Output: 1
Explanation: Returns 1 and makes key 1 the most-recently used.Example 2:
Input: cache.put(3, 3), cache.get(2)
Output: -1
Explanation: Key 2 was already evicted due to reaching the capacity limit.
Constraints:

• 1 <= capacity <= 3000


• 0 <= key, value <= 10^4