PracHub
QuestionsPremiumLearningGuidesCheatsheetNEWCareers

Quick Overview

This collection evaluates algorithmic problem-solving skills, mastery of fundamental data structures (arrays, strings, hash maps, stacks, queues, trees, graphs, linked lists) and the ability to reason about time and space complexity.

  • medium
  • Apple
  • Coding & Algorithms
  • Software Engineer

Solve 15 common interview problems

Company: Apple

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Below are fifteen independent coding problems commonly discussed in software engineering interviews. For each one, write an efficient algorithm and be prepared to explain the time and space complexity, as interviewers may ask for optimizations or follow-up improvements. 1. **Find a target-sum pair.** Given an integer array `nums` and an integer `target`, return the indices of two distinct elements whose values add up to `target`. You may assume exactly one valid answer exists, and you may return the indices in any order. 2. **Count contiguous segments with sum `k`.** Given an integer array `nums` and an integer `k`, return the number of contiguous subarrays whose sum is exactly `k`. 3. **Build a product array without division.** Given an integer array `nums`, return an array `answer` where `answer[i]` is the product of all elements of `nums` except `nums[i]`. Do not use division, and aim for linear time. 4. **Find the longest substring with all unique characters.** Given a string `s`, return the length of the longest contiguous substring that contains no repeated characters. 5. **Find the shortest covering substring.** Given strings `s` and `t`, return the smallest substring of `s` that contains every character of `t`, including duplicates. If no such substring exists, return an empty string. 6. **Expand a nested repetition encoding.** Given a string encoded with rules such as `k[encoded_part]`, where the substring inside brackets should be repeated `k` times, return the fully decoded string. For example, `3[a2[c]]` becomes `accaccacc`. 7. **Count connected land regions in a grid.** Given a 2D grid of characters where `'1'` represents land and `'0'` represents water, return the number of islands. Cells are connected horizontally and vertically. 8. **Find the shortest word transformation length.** Given a `beginWord`, an `endWord`, and a dictionary `wordList`, transform the begin word into the end word by changing exactly one letter at a time. Every intermediate word must exist in `wordList`. Return the length of the shortest valid transformation sequence, or `0` if no such sequence exists. 9. **Determine whether all courses can be completed.** You are given `numCourses` labeled from `0` to `numCourses - 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`. 10. **Traverse a binary tree by levels.** Given the root of a binary tree, return the node values level by level from top to bottom, where each level is returned as a separate list. 11. **Find the nearest shared ancestor in a binary tree.** Given the root of a binary tree and two nodes `p` and `q`, return their lowest common ancestor. The lowest common ancestor is the deepest node that has both `p` and `q` as descendants, where a node may be a descendant of itself. 12. **Merge multiple sorted linked lists.** You are given an array of `k` singly linked lists, each sorted in ascending order. Merge them into one sorted linked list and return its head. 13. **Deep-copy a linked list with arbitrary cross-links.** Each node in a linked list has `val`, `next`, and `random` pointers, where `random` may point to any node in the list or be `null`. Return a deep copy of the entire list. 14. **Rotate a square matrix in place.** Given an `n x n` matrix, rotate it 90 degrees clockwise without using another matrix for the final result. 15. **Compute the longest increasing subsequence length.** Given an integer array `nums`, return the length of the longest strictly increasing subsequence. Aim for an algorithm better than `O(n^2)` if possible.

Quick Answer: This collection evaluates algorithmic problem-solving skills, mastery of fundamental data structures (arrays, strings, hash maps, stacks, queues, trees, graphs, linked lists) and the ability to reason about time and space complexity.

Part 1: Find a target-sum pair

Given an integer array nums and an integer target, return the indices of two distinct elements whose values add up to target. You may assume exactly one valid answer exists, and you may return the indices in any order. For consistent testing here, return the earlier index first when found by a left-to-right scan.

Constraints

  • 2 <= len(nums) <= 100000
  • -1000000000 <= nums[i], target <= 1000000000
  • Exactly one valid answer exists

Examples

Input: ([2, 7, 11, 15], 9)

Expected Output: [0, 1]

Explanation: 2 + 7 = 9.

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

Expected Output: [1, 2]

Explanation: 2 + 4 = 6.

Input: ([3, 3], 6)

Expected Output: [0, 1]

Explanation: The smallest valid input size still works.

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

Expected Output: [2, 4]

Explanation: -3 + -5 = -8.

Hints

  1. As you scan the array, ask what number you would need to complete the target for the current value.
  2. A hash map can store previously seen values and their indices in O(1) average lookup time.

Part 2: Count contiguous segments with sum k

Given an integer array nums and an integer k, return the number of contiguous subarrays whose sum is exactly k.

Constraints

  • 0 <= len(nums) <= 100000
  • -1000 <= nums[i] <= 1000
  • -10000000 <= k <= 10000000

Examples

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

Expected Output: 2

Explanation: The subarrays [1,1] at positions (0,1) and (1,2) both sum to 2.

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

Expected Output: 2

Explanation: The subarrays [1,2] and [3] sum to 3.

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

Expected Output: 3

Explanation: The subarrays [1,-1], [0], and [1,-1,0] all sum to 0.

Input: ([], 0)

Expected Output: 0

Explanation: An empty array has no non-empty contiguous subarrays.

Hints

  1. If prefix_sum[j] - prefix_sum[i] = k, then the subarray between them sums to k.
  2. Track how many times each prefix sum has appeared so far.

Part 3: Build a product array without division

Given an integer array nums, return an array answer where answer[i] is the product of all elements of nums except nums[i]. Do not use division, and aim for linear time.

Constraints

  • 0 <= len(nums) <= 100000
  • -30 <= nums[i] <= 30
  • Use no division

Examples

Input: [1, 2, 3, 4]

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

Explanation: Each entry is the product of all values except the one at that index.

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

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

Explanation: Only the index containing 0 gets the product of all non-zero numbers.

Input: [5]

Expected Output: [1]

Explanation: The product of all numbers except itself is the empty product, treated as 1.

Input: []

Expected Output: []

Explanation: An empty input produces an empty output.

Hints

  1. What is the product of everything to the left of i? What about everything to the right of i?
  2. You can combine prefix products and suffix products in one output array.

Part 4: Find the longest substring with all unique characters

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

Constraints

  • 0 <= len(s) <= 100000
  • s may contain letters, digits, spaces, and symbols

Examples

Input: 'abcabcbb'

Expected Output: 3

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

Input: 'bbbbb'

Expected Output: 1

Explanation: Only one unique character can appear in the best window.

Input: 'pwwkew'

Expected Output: 3

Explanation: One longest valid substring is 'wke'.

Input: ''

Expected Output: 0

Explanation: The empty string has longest length 0.

Input: ' '

Expected Output: 1

Explanation: A single space is still one unique character.

Hints

  1. Use a sliding window and move its left edge forward when you see a repeated character.
  2. Store the last index where each character appeared.

Part 5: Find the shortest covering substring

Given strings s and t, return the smallest substring of s that contains every character of t, including duplicates. If no such substring exists, return an empty string.

Constraints

  • 0 <= len(s) <= 100000
  • 0 <= len(t) <= 100000
  • Characters are case-sensitive

Examples

Input: ('ADOBECODEBANC', 'ABC')

Expected Output: 'BANC'

Explanation: 'BANC' is the smallest substring containing A, B, and C.

Input: ('a', 'a')

Expected Output: 'a'

Explanation: The whole string is the answer.

Input: ('a', 'aa')

Expected Output: ''

Explanation: There are not enough copies of 'a'.

Input: ('ab', 'b')

Expected Output: 'b'

Explanation: A one-character window can be optimal.

Input: ('', 'a')

Expected Output: ''

Explanation: No window exists when s is empty.

Hints

  1. A sliding window can expand until it becomes valid, then shrink to try to improve it.
  2. Track how many required characters are still missing, not just whether each character appears.

Part 6: Expand a nested repetition encoding

Given an encoded string using the rule k[encoded_part], where the substring inside brackets is repeated k times, return the fully decoded string. Encodings may be nested.

Constraints

  • 0 <= len(s) <= 100000
  • Repeat counts are positive integers
  • The input is guaranteed to be a valid encoding

Examples

Input: '3[a2[c]]'

Expected Output: 'accaccacc'

Explanation: The inner part 'a2[c]' becomes 'acc', then repeated 3 times.

Input: '2[abc]3[cd]ef'

Expected Output: 'abcabccdcdcdef'

Explanation: Concatenate each decoded segment in order.

Input: '10[a]'

Expected Output: 'aaaaaaaaaa'

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

Input: ''

Expected Output: ''

Explanation: An empty string decodes to empty.

Hints

  1. When you hit '[', save the current built string and repeat count.
  2. When you hit ']', pop the previous context and append the repeated block.

Part 7: Count connected land regions in a grid

Given a 2D grid where '1' represents land and '0' represents water, return the number of islands. Cells are connected only horizontally and vertically. For simple testing, the grid is provided as a list of strings of equal length.

Constraints

  • 0 <= number of rows, number of columns <= 300
  • All rows have the same length
  • Connectivity is 4-directional

Examples

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

Expected Output: 1

Explanation: All land cells are connected into one island.

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

Expected Output: 3

Explanation: There are three separate land regions.

Input: []

Expected Output: 0

Explanation: An empty grid has no islands.

Input: ['0']

Expected Output: 0

Explanation: A single water cell contains no island.

Input: ['1']

Expected Output: 1

Explanation: A single land cell is one island.

Hints

  1. Whenever you find unvisited land, start a flood fill from it and count one new island.
  2. Depth-first search or breadth-first search both work here.

Part 8: Find the shortest word transformation length

Given a beginWord, an endWord, and a dictionary wordList, transform the begin word into the end word by changing exactly one letter at a time. Every intermediate word must exist in wordList. Return the length of the shortest valid transformation sequence, or 0 if no such sequence exists.

Constraints

  • 1 <= len(beginWord) == len(endWord) <= 20
  • 1 <= len(wordList) <= 5000
  • All words contain lowercase English letters

Examples

Input: ('hit', 'cog', ['hot', 'dot', 'dog', 'lot', 'log', 'cog'])

Expected Output: 5

Explanation: One shortest sequence is hit -> hot -> dot -> dog -> cog.

Input: ('hit', 'cog', ['hot', 'dot', 'dog', 'lot', 'log'])

Expected Output: 0

Explanation: The end word is unreachable.

Input: ('a', 'c', ['a', 'b', 'c'])

Expected Output: 2

Explanation: A direct one-letter change from 'a' to 'c' is allowed because 'c' is in the list.

Input: ('red', 'tax', ['ted', 'tex', 'red', 'tax', 'tad', 'den', 'rex', 'pee'])

Expected Output: 4

Explanation: One shortest path is red -> ted -> tad -> tax.

Hints

  1. This is a shortest-path problem on an implicit graph, so breadth-first search is a natural fit.
  2. Instead of comparing every pair of words, group words by wildcard patterns like h*t.

Part 9: Determine whether all courses can be completed

You are given numCourses labeled from 0 to numCourses - 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

  • 1 <= numCourses <= 100000
  • 0 <= len(prerequisites) <= 200000
  • 0 <= a, b < numCourses

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: (1, [])

Expected Output: True

Explanation: A single course with no prerequisites is always possible.

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

Expected Output: True

Explanation: This dependency chain has no cycle.

Hints

  1. Think of courses and prerequisites as a directed graph.
  2. If you can repeatedly take courses with in-degree 0 and finish them all, there is no cycle.

Part 10: Traverse a binary tree by levels

Given the root of a binary tree, return the node values level by level from top to bottom, where each level is returned as a separate list. For testing, the tree is given as a level-order Python list using None for missing children.

Constraints

  • 0 <= number of nodes <= 2000
  • Node values are integers
  • None represents a missing child in the level-order encoding

Examples

Input: [3, 9, 20, None, None, 15, 7]

Expected Output: [[3], [9, 20], [15, 7]]

Explanation: This is the standard level-order traversal.

Input: []

Expected Output: []

Explanation: An empty tree has no levels.

Input: [1]

Expected Output: [[1]]

Explanation: A single-node tree has one level.

Input: [1, 2, 3, 4, None, None, 5]

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

Explanation: Missing children should be skipped correctly.

Hints

  1. A queue naturally processes tree nodes in breadth-first order.
  2. For each loop iteration, process exactly the number of nodes currently in the queue to form one level.

Part 11: Find the nearest shared ancestor in a binary tree

Given a binary tree and two node values p and q, return the value of their lowest common ancestor. The lowest common ancestor is the deepest node that has both nodes as descendants, where a node may be a descendant of itself. For testing, the tree is given as a level-order list with unique values and None for missing children.

Constraints

  • 1 <= number of nodes <= 2000
  • All node values are unique
  • Both p and q are guaranteed to exist in the tree

Examples

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

Expected Output: 3

Explanation: The root is the first node that has both targets below it.

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

Expected Output: 5

Explanation: A node can be an ancestor of itself.

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

Expected Output: 1

Explanation: The root is the common ancestor.

Input: ([1], 1, 1)

Expected Output: 1

Explanation: With one node, it is its own ancestor.

Hints

  1. A recursive function can tell you whether p or q appears in the left subtree, right subtree, or at the current node.
  2. If one target is found on each side of a node, that node is the answer.

Part 12: Merge multiple sorted linked lists

You are given an array of k singly linked lists, each sorted in ascending order. Merge them into one sorted linked list. For easier testing, each linked list is provided as a Python list of its values, and you should return the merged linked list as a Python list.

Constraints

  • 0 <= k <= 10000
  • The total number of nodes across all lists is at most 100000
  • 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: Merging all three sorted lists produces one sorted output.

Input: []

Expected Output: []

Explanation: No lists means no nodes.

Input: [[], []]

Expected Output: []

Explanation: Empty linked lists contribute nothing.

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

Expected Output: [0, 1, 2]

Explanation: The heap should skip empty lists.

Hints

  1. At any moment, you only need the smallest current head among the k lists.
  2. A min-heap lets you repeatedly extract the next smallest value in O(log k) time.

Part 13: Deep-copy a linked list with arbitrary cross-links

Each node in a linked list has val, next, and random pointers, where random may point to any node in the list or be null. For testing, the list is represented as an array of [value, random_index] pairs in next order, where random_index is the index of the random target or None. Return the deep-copied list in the same representation.

Constraints

  • 0 <= number of nodes <= 1000
  • Each random_index is either None or an integer in [0, n - 1]
  • The output must represent a deep copy, not reused original nodes

Examples

Input: [[7, None], [13, 0], [11, 4], [10, 2], [1, 0]]

Expected Output: [[7, None], [13, 0], [11, 4], [10, 2], [1, 0]]

Explanation: The copied list should preserve values and random pointer structure.

Input: []

Expected Output: []

Explanation: An empty list copies to an empty list.

Input: [[1, None]]

Expected Output: [[1, None]]

Explanation: A single node with no random link stays simple.

Input: [[1, 0]]

Expected Output: [[1, 0]]

Explanation: A node may point its random pointer to itself.

Hints

  1. A hash map from old nodes to new nodes makes it easy to wire next and random pointers.
  2. You can build all copied nodes first, then connect their pointers in a second pass.

Part 14: Rotate a square matrix in place

Given an n x n matrix, rotate it 90 degrees clockwise without using another matrix for the final result. For testing convenience, return the matrix after performing the in-place rotation.

Constraints

  • 0 <= n <= 200
  • matrix is square
  • Modify in place conceptually, but returning the matrix is allowed for testing

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

Input: [[1]]

Expected Output: [[1]]

Explanation: A 1x1 matrix remains unchanged.

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

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

Explanation: The 2x2 case is the smallest non-trivial rotation.

Input: []

Expected Output: []

Explanation: An empty matrix stays empty.

Hints

  1. A clockwise rotation can be decomposed into a transpose followed by reversing each row.
  2. Think about how cell (r, c) moves after a transpose.

Part 15: Compute the longest increasing subsequence length

Given an integer array nums, return the length of the longest strictly increasing subsequence. Aim for an algorithm better than O(n^2).

Constraints

  • 0 <= len(nums) <= 100000
  • -1000000000 <= nums[i] <= 1000000000
  • The subsequence does not need to be contiguous

Examples

Input: [10, 9, 2, 5, 3, 7, 101, 18]

Expected Output: 4

Explanation: One LIS is [2, 3, 7, 101].

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

Expected Output: 4

Explanation: One LIS is [0, 1, 2, 3].

Input: [7, 7, 7, 7, 7, 7, 7]

Expected Output: 1

Explanation: Equal values cannot extend a strictly increasing subsequence.

Input: []

Expected Output: 0

Explanation: An empty array has LIS length 0.

Input: [4]

Expected Output: 1

Explanation: A single element is an increasing subsequence of length 1.

Hints

  1. Maintain a list where tails[i] is the smallest possible tail of an increasing subsequence of length i + 1.
  2. Binary search tells you where each number should update tails.
Last updated: May 7, 2026

Loading coding console...

PracHub

Master your tech interviews with 7,500+ real questions from top companies.

Product

  • Questions
  • Learning Tracks
  • Interview Guides
  • Resources
  • Premium
  • Careers
  • For Universities
  • Student Access

Browse

  • By Company
  • By Role
  • By Category
  • Topic Hubs
  • SQL Questions
  • Compare Platforms
  • Discord Community

Support

  • support@prachub.com
  • (916) 541-4762

Legal

  • Privacy Policy
  • Terms of Service
  • About Us

© 2026 PracHub. All rights reserved.

Related Coding Questions

  • Compute Earliest Bus Arrival - Apple (medium)
  • Find the Extra Edge - Apple (hard)
  • Rotate a Matrix In Place - Apple (medium)
  • Encode and Rebuild a Binary Tree - Apple (hard)
  • Wrap Matching Substrings in Bold Tags - Apple (medium)