How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Apple.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Apple during technical interviews.

Solve 15 common Apple coding questions

Company: Apple

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

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`.

Quick Answer: This set evaluates algorithmic problem-solving and data-structure competence, including mastery of hash tables, linked lists, stacks, queues, heaps, graphs, sliding-window and two-pointer techniques, complexity analysis, and in-place transformations.

Part 1: Design a Recency-Based Cache

Implement an LRU cache simulator. The function receives a cache `capacity` and a list of operations. Each operation is either `('put', key, value)` or `('get', key)`. Return a result list aligned with the operations: append `None` for every `put`, and append the stored value or `-1` for every `get`. When the cache is full, evict the least recently used key.

Constraints

0 <= capacity <= 10^5
0 <= len(operations) <= 2 * 10^5
Keys and values are integers
Target complexity: O(1) average time per operation

Examples

Input: (2, [('put', 1, 1), ('put', 2, 2), ('get', 1), ('put', 3, 3), ('get', 2), ('put', 4, 4), ('get', 1), ('get', 3), ('get', 4)])

Expected Output: [None, None, 1, None, -1, None, -1, 3, 4]

Explanation: Standard LRU behavior with evictions of keys 2 and 1.

Input: (1, [('put', 2, 1), ('put', 2, 2), ('get', 2), ('put', 1, 1), ('get', 2)])

Expected Output: [None, None, 2, None, -1]

Explanation: Updating an existing key should refresh its recency.

Input: (0, [('put', 1, 1), ('get', 1)])

Expected Output: [None, -1]

Explanation: A zero-capacity cache never stores anything.

Input: (2, [('get', 5)])

Expected Output: [-1]

Explanation: Getting a missing key returns -1.

Hints

A hash map gives O(1) access by key.
Use a doubly linked list to maintain recency order and move touched nodes to the front.

Part 2: Design a Set with Random Retrieval

Implement a set-like structure supporting `insert(val)`, `remove(val)`, and `getRandom()` in O(1) average time. For deterministic testing, the function receives `operations` and an initial integer `seed`. Maintain elements in a dynamic array, and when removing a value use the standard swap-with-last trick before popping. On each `getRandom`, if the set is non-empty, update `seed` by `seed = (seed * 1103515245 + 12345) % (2**31)` and return the element at index `seed % current_size` from the internal array. Return a result list aligned with operations: booleans for `insert` and `remove`, the selected value for `getRandom`, or `None` if `getRandom` is called on an empty set.

Constraints

0 <= len(operations) <= 2 * 10^5
Values are integers
Target complexity: O(1) average per operation

Examples

Input: ([('insert', 1), ('remove', 2), ('insert', 2), ('getRandom',), ('remove', 1), ('insert', 2), ('getRandom',)], 0)

Expected Output: [True, False, True, 2, True, False, 2]

Explanation: This follows the standard insert/remove behavior, with deterministic random picks.

Input: ([('getRandom',), ('insert', 5), ('getRandom',), ('remove', 5), ('getRandom',)], 7)

Expected Output: [None, True, 5, True, None]

Explanation: Calling `getRandom` on an empty set returns None.

Input: ([('insert', 10), ('insert', 20), ('insert', 30), ('getRandom',), ('remove', 20), ('getRandom',), ('getRandom',)], 1)

Expected Output: [True, True, True, 10, True, 30, 10]

Explanation: After removing 20, the last value is swapped into its place.

Input: ([('insert', 1), ('insert', 1), ('remove', 2), ('remove', 1)], 5)

Expected Output: [True, False, False, True]

Explanation: Duplicate inserts and removing missing values should return False.

Hints

Use a list for random access and a hash map from value to index.
Deletion becomes O(1) if you swap the target with the last list element.

Part 3: Build a Prefix Word Dictionary

Implement a prefix dictionary with three operations: `insert(word)`, `search(word)`, and `startsWith(prefix)`. The function receives a list of operations and returns a result list aligned with them. Use `None` for `insert`, `True` or `False` for `search`, and `True` or `False` for `startsWith`.

Constraints

0 <= len(operations) <= 2 * 10^5
Each word or prefix length is between 0 and 200
All characters are lowercase English letters or the empty string

Examples

Input: ([('insert', 'apple'), ('search', 'apple'), ('search', 'app'), ('startsWith', 'app'), ('insert', 'app'), ('search', 'app')],)

Expected Output: [None, True, False, True, None, True]

Explanation: A prefix is not automatically a complete word until inserted.

Input: ([('search', ''), ('startsWith', ''), ('insert', ''), ('search', ''), ('startsWith', '')],)

Expected Output: [False, True, None, True, True]

Explanation: The empty prefix matches trivially, but the empty word must be inserted before search succeeds.

Input: ([('insert', 'cat'), ('insert', 'car'), ('startsWith', 'ca'), ('search', 'cap'), ('startsWith', 'dog')],)

Expected Output: [None, None, True, False, False]

Explanation: The trie can share the `ca` prefix.

Hints

A trie stores shared prefixes efficiently.
Mark complete words separately from prefix nodes.

Part 4: Return the k Most Frequent Values

Given an integer array `nums` and an integer `k`, return the `k` values that appear most often. To make the answer deterministic, if multiple values have the same frequency, return smaller values first.

Constraints

0 <= len(nums) <= 10^5
0 <= k <= number of distinct values in nums
Values fit in standard 32-bit integers

Examples

Input: ([1, 1, 1, 2, 2, 3], 2)

Expected Output: [1, 2]

Explanation: 1 appears three times and 2 appears twice.

Input: ([4, 4, 1, 1, 2, 2], 2)

Expected Output: [1, 2]

Explanation: All three values tie, so smaller values come first.

Input: ([], 0)

Expected Output: []

Explanation: Empty input with k = 0 returns an empty list.

Input: ([5], 1)

Expected Output: [5]

Explanation: A single element is trivially the most frequent.

Hints

Count frequencies first.
You can bucket numbers by frequency instead of sorting every element globally.

Part 5: Compute Product Except Self

Given an integer array `nums`, return an array `answer` where `answer[i]` is the product of every element in `nums` except `nums[i]`. Do not use division, and aim for O(n) time.

Constraints

0 <= len(nums) <= 10^5
Each value fits in 32-bit signed integer range
Do not use division

Examples

Input: ([1, 2, 3, 4],)

Expected Output: [24, 12, 8, 6]

Explanation: Each position gets the product of all other values.

Input: ([-1, 1, 0, -3, 3],)

Expected Output: [0, 0, 9, 0, 0]

Explanation: The single zero makes only one position non-zero.

Input: ([5],)

Expected Output: [1]

Explanation: The product of all elements except itself is the empty product, defined here as 1.

Input: ([0, 0],)

Expected Output: [0, 0]

Explanation: With two zeros, every position becomes zero.

Hints

Build left products and right products.
You can reuse the output array to keep extra space low.

Part 6: Measure Trapped Water Between Bars

Given a non-negative integer array `height` representing elevation bars, compute how much rainwater can be trapped after raining.

Constraints

0 <= len(height) <= 2 * 10^5
0 <= height[i] <= 10^5

Examples

Input: ([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1],)

Expected Output: 6

Explanation: This is the classic example with multiple pockets.

Input: ([4, 2, 0, 3, 2, 5],)

Expected Output: 9

Explanation: Water is trapped between several higher bars.

Input: ([],)

Expected Output: 0

Explanation: No bars means no trapped water.

Input: ([1, 2, 3],)

Expected Output: 0

Explanation: Strictly increasing heights cannot trap water.

Hints

Water above a bar depends on the highest wall to its left and right.
A two-pointer approach can avoid building full prefix and suffix arrays.

Part 7: Find the Largest Water Container

Given an array `height` where each value is the height of a vertical line, choose two lines that together with the x-axis form a container holding the maximum amount of water. Return that maximum area.

Constraints

0 <= len(height) <= 2 * 10^5
0 <= height[i] <= 10^5

Examples

Input: ([1, 8, 6, 2, 5, 4, 8, 3, 7],)

Expected Output: 49

Explanation: The best pair is height 8 at index 1 and height 7 at index 8.

Input: ([1, 1],)

Expected Output: 1

Explanation: Only one container is possible.

Input: ([4, 3, 2, 1, 4],)

Expected Output: 16

Explanation: The widest good pair uses both 4s.

Input: ([5],)

Expected Output: 0

Explanation: At least two lines are required.

Hints

The width shrinks when pointers move, so only move the shorter side.
A brute-force O(n^2) scan is too slow for large inputs.

Part 8: Find the Longest Substring Without Duplicates

Given a string `s`, return the length of the longest substring that contains no repeated characters.

Constraints

0 <= len(s) <= 2 * 10^5
The string may contain any visible ASCII characters

Examples

Input: ('abcabcbb',)

Expected Output: 3

Explanation: The longest substring without repeats is `abc`.

Input: ('bbbbb',)

Expected Output: 1

Explanation: Any valid substring can only contain one `b`.

Input: ('',)

Expected Output: 0

Explanation: An empty string has length 0.

Input: ('abba',)

Expected Output: 2

Explanation: The best substring is `ab` or `ba`.

Hints

Use a sliding window.
Track the most recent index of each character so the left boundary only moves forward.

Part 9: Group Words by Letter Composition

Given a list of strings, group together words that are made of the same letters. For deterministic output, sort each group lexicographically, then sort the list of groups by each group's first word.

Constraints

0 <= len(words) <= 10^4
0 <= len(words[i]) <= 100
All strings use lowercase English letters

Examples

Input: (['eat', 'tea', 'tan', 'ate', 'nat', 'bat'],)

Expected Output: [['ate', 'eat', 'tea'], ['bat'], ['nat', 'tan']]

Explanation: The output is normalized by sorting within and across groups.

Input: ([],)

Expected Output: []

Explanation: No words means no groups.

Input: ([''],)

Expected Output: [['']]

Explanation: A single empty string forms one group.

Input: (['abc', 'bca', 'cab', 'foo', 'ofo', 'bar'],)

Expected Output: [['abc', 'bca', 'cab'], ['bar'], ['foo', 'ofo']]

Explanation: Each anagram class becomes one group.

Hints

Words that are anagrams share the same canonical signature.
A sorted-character key is simple and reliable.

Part 10: Decode Nested Repetition Strings

Given an encoded string with the pattern `k[encoded_string]`, return its decoded form. Nested encodings are allowed, and repetition counts may have multiple digits.

Constraints

0 <= len(s) <= 10^5
The input contains digits, lowercase letters, and brackets
The fully decoded output length is at most 10^5

Examples

Input: ('3[a2[c]]',)

Expected Output: 'accaccacc'

Explanation: `a2[c]` becomes `acc`, repeated 3 times.

Input: ('2[abc]3[cd]ef',)

Expected Output: 'abcabccdcdcdef'

Explanation: Decode each bracketed segment and concatenate.

Input: ('10[a]',)

Expected Output: 'aaaaaaaaaa'

Explanation: Multi-digit repeat counts must be handled correctly.

Input: ('',)

Expected Output: ''

Explanation: Empty input decodes to an empty string.

Hints

When you see `[`, save the current number and current built string.
When you see `]`, combine the saved prefix with the repeated segment.

Part 11: Count Islands in a Grid

Given a 2D grid of land and water, count how many disconnected islands exist. An island is formed by horizontally or vertically adjacent `'1'` cells. In this version, each grid row is provided as a string such as `'11001'`.

Constraints

0 <= number of rows, columns <= 300
Grid is rectangular
Use BFS or DFS

Examples

Input: (['11000', '11000', '00100', '00011'],)

Expected Output: 3

Explanation: There are three disconnected land masses.

Input: (['11110', '11010', '11000', '00000'],)

Expected Output: 1

Explanation: All land cells belong to one island.

Input: ([],)

Expected Output: 0

Explanation: An empty grid contains no islands.

Input: (['1'],)

Expected Output: 1

Explanation: A single land cell is one island.

Hints

Whenever you find an unvisited land cell, start a flood-fill.
Mark cells as visited so each land cell is processed only once.

Part 12: Check Whether All Courses Can Be Completed

There are `num_courses` labeled from `0` to `num_courses - 1` and a list of prerequisite pairs `[a, b]` meaning course `b` must be taken before course `a`. Return `True` if it is possible to finish all courses, otherwise return `False`.

Constraints

0 <= num_courses <= 10^5
0 <= len(prerequisites) <= 2 * 10^5
Each prerequisite pair contains valid course indices

Examples

Input: (2, [[1, 0]])

Expected Output: True

Explanation: Take course 0, then course 1.

Input: (2, [[1, 0], [0, 1]])

Expected Output: False

Explanation: The prerequisites form a cycle.

Input: (4, [[1, 0], [2, 0], [3, 1], [3, 2]])

Expected Output: True

Explanation: A valid topological ordering exists.

Input: (0, [])

Expected Output: True

Explanation: With no courses, finishing all courses is trivially possible.

Hints

This is equivalent to checking whether a directed graph has a cycle.
Kahn's algorithm processes courses with indegree 0.

Part 13: Merge Multiple Sorted Linked Lists

Merge `k` sorted linked lists into one sorted linked list. For easy testing, each linked list is represented as a Python list of sorted integers, and you should return the merged linked list as a single Python list.

Constraints

0 <= k <= 10^4
The total number of elements across all lists is at most 10^5
Each inner list is already sorted in non-decreasing order

Examples

Input: ([[1, 4, 5], [1, 3, 4], [2, 6]],)

Expected Output: [1, 1, 2, 3, 4, 4, 5, 6]

Explanation: This is the classic merge-k-lists example.

Input: ([],)

Expected Output: []

Explanation: No lists means no output values.

Input: ([[], [1], [], [0, 2]],)

Expected Output: [0, 1, 2]

Explanation: Empty lists should be ignored.

Input: ([[5]],)

Expected Output: [5]

Explanation: A single one-node list stays unchanged.

Hints

Always take the smallest current head among the `k` lists.
A min-heap gives that choice in O(log k) time.

Part 14: Rotate a Square Matrix Clockwise

Given an `n x n` matrix, rotate it 90 degrees clockwise in place. For testing, return the matrix after rotation.

Constraints

0 <= n <= 200
The matrix is square
Aim for O(1) extra space

Examples

Input: ([[1, 2, 3], [4, 5, 6], [7, 8, 9]],)

Expected Output: [[7, 4, 1], [8, 5, 2], [9, 6, 3]]

Explanation: This is the standard 3x3 example.

Input: ([[1]],)

Expected Output: [[1]]

Explanation: A 1x1 matrix is unchanged.

Input: ([],)

Expected Output: []

Explanation: An empty matrix remains empty.

Input: ([[1, 2], [3, 4]],)

Expected Output: [[3, 1], [4, 2]]

Explanation: The 2x2 rotation is straightforward to verify.

Hints

A clockwise rotation can be done by transposing and then reversing each row.
Because the matrix is square, swaps across the diagonal are enough for the transpose.

Part 15: Find the Longest Mountain Subarray

Given an integer array, return the length of the longest contiguous subarray that strictly increases and then strictly decreases. If no mountain exists, return 0.

Constraints

0 <= len(arr) <= 10^5
Values fit in 32-bit signed integer range

Examples

Input: ([2, 1, 4, 7, 3, 2, 5],)

Expected Output: 5

Explanation: The longest mountain is `[1, 4, 7, 3, 2]`.

Input: ([2, 2, 2],)

Expected Output: 0

Explanation: Flat segments cannot form a mountain.

Input: ([1, 3, 2],)

Expected Output: 3

Explanation: This whole array is a mountain.

Input: ([],)

Expected Output: 0

Explanation: No elements means no mountain.

Input: ([1, 2, 3, 4, 5],)

Expected Output: 0

Explanation: A purely increasing array is not a mountain.

Hints

A valid mountain needs both an uphill part and a downhill part.
Precomputing increasing lengths from the left and decreasing lengths from the right makes peak checks easy.