Solve 15 common Apple coding questions

The post summarizes high-frequency coding problems reported for Apple Software Engineer interviews. Practice the following algorithm and data-structure questions:

1. Design a recency-based cache: Implement a fixed-capacity cache with get(key) and put(key, value) operations. Both operations should run in O(1) average time. When the cache is full, evict the least recently used item.

2. Design a set with random retrieval: Build a data structure that supports insert(val), remove(val), and getRandom(), where each operation runs in O(1) average time.

3. Build a prefix word dictionary: Implement a structure with insert(word), search(word), and startsWith(prefix).

4. Return the k most frequent values: Given an integer array such as nums = [1,1,1,2,2,3] and k = 2, return the k values that appear most often, for example [1,2] in any order.

5. Compute product except self: Given an array like [1,2,3,4], return an array where each position contains the product of all other elements, for example [24,12,8,6]. Do not use division, and aim for O(n) time.

6. Measure trapped water between bars: Given a non-negative integer array representing elevation heights, for example [0,1,0,2,1,0,1,3,2,1,2,1], compute how much rainwater can be trapped.

7. Find the largest water container: Given heights of vertical lines, choose two lines that together with the x-axis hold the maximum amount of water, and return that maximum area.

8. Find the longest substring without duplicates: Given a string such as "abcabcbb", return the length of the longest substring that contains no repeated characters. For this example, the answer is 3.

9. Group words by letter composition: Given a list like ["eat","tea","tan","ate","nat","bat"], group together words that are made of the same letters, for example [["eat","tea","ate"],["tan","nat"],["bat"]].

10. Decode nested repetition strings: Given an encoded string such as "3[a2[c]]", return its decoded form. For this example, the result is "accaccacc".

11. Count islands in a grid: Given a 2D grid of land and water cells, count how many disconnected islands exist using BFS or DFS.

12. Check whether all courses can be completed: Given n courses and a list of prerequisite pairs, determine whether it is possible to finish all courses. This is a graph cycle-detection / topological-order problem.

13. Merge multiple sorted linked lists: Given k sorted linked lists such as 1->4->5, 1->3->4, and 2->6, merge them into one sorted linked list: 1->1->2->3->4->4->5->6.

14. Rotate a square matrix clockwise: Given an n x n matrix, rotate it 90 degrees clockwise in place. Example: [[1,2,3],[4,5,6],[7,8,9]] becomes [[7,4,1],[8,5,2],[9,6,3]].

15. Find the longest mountain subarray: Given an array such as [2,1,4,7,3,2,5], return the length of the longest contiguous subarray that strictly increases and then strictly decreases. In this example, the longest mountain is [1,4,7,3,2], so the answer is 5.