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 .