What are the most frequently asked coding interview questions at Apple?

Apple's coding interviews are known for their emphasis on problem-solving, data structures, and algorithms. Here are some of the most frequently asked coding interview questions at Apple, along with a brief explanation and approach for each:

1. Two Sum

Problem: Given an array of integers, return indices of the two numbers such that they add up to a specific target.

Approach: Use a hash map to store the difference between the target and each element.

def two_sum(nums, target):
    num_map = {}
    for i, num in enumerate(nums):
        complement = target - num
        if complement in num_map:
            return [num_map[complement], i]
        num_map[num] = i
    return []

2. Reverse a Linked List

Problem: Reverse a singly linked list.

Approach: Use iterative pointer manipulation.

def reverse_list(head):
    prev = None
    current = head
    while current:
        next_node = current.next
        current.next = prev
        prev = current
        current = next_node
    return prev

3. Merge Intervals

Problem: Merge all overlapping intervals in an array of intervals.

Approach: Sort the intervals by the start time and merge overlapping intervals.

def merge(intervals):
    intervals.sort(key=lambda x: x[0])
    merged = []
    for interval in intervals:
        if not merged or merged[-1][1] < interval[0]:
            merged.append(interval)
        else:
            merged[-1][1] = max(merged[-1][1], interval[1])
    return merged

4. Longest Substring Without Repeating Characters

Problem: Find the length of the longest substring without repeating characters.

Approach: Use a sliding window approach with a set to track characters.

def length_of_longest_substring(s):
    char_set = set()
    left = 0
    max_length = 0
    for right in range(len(s)):
        while s[right] in char_set:
            char_set.remove(s[left])
            left += 1
        char_set.add(s[right])
        max_length = max(max_length, right - left + 1)
    return max_length

5. Median of Two Sorted Arrays

Problem: Find the median of two sorted arrays.

Approach: Use a binary search approach to partition the arrays and find the median.

def findMedianSortedArrays(nums1, nums2):
    A, B = nums1, nums2
    total = len(A) + len(B)
    half = total // 2
    if len(A) > len(B):
        A, B = B, A
    
    l, r = 0, len(A) - 1
    while True:
        i = (l + r) // 2
        j = half - i - 2
        
        Aleft = A[i] if i >= 0 else float('-infinity')
        Aright = A[i + 1] if (i + 1) < len(A) else float('infinity')
        Bleft = B[j] if j >= 0 else float('-infinity')
        Bright = B[j + 1] if (j + 1) < len(B) else float('infinity')
        
        if Aleft <= Bright and Bleft <= Aright:
            if total % 2:
                return min(Aright, Bright)
            return (max(Aleft, Bleft) + min(Aright, Bright)) / 2
        elif Aleft > Bright:
            r = i - 1
        else:
            l = i + 1

6. Clone Graph

Problem: Given a reference of a node in a connected undirected graph, return a deep copy (clone) of the graph.

Approach: Use BFS or DFS with a hash map to keep track of visited nodes and their corresponding clones.

def cloneGraph(node):
    if not node:
        return None
    node_map = {}
    def dfs(node):
        if node in node_map:
            return node_map[node]
        clone = Node(node.val, [])
        node_map[node] = clone
        for neighbor in node.neighbors:
            clone.neighbors.append(dfs(neighbor))
        return clone
    return dfs(node)

7. Word Ladder

Problem: Given two words (beginWord and endWord), and a dictionary's word list, find the length of the shortest transformation sequence from beginWord to endWord.

Approach: Use BFS to explore all possible transformations level by level.

from collections import deque

def ladderLength(beginWord, endWord, wordList):
    if endWord not in wordList:
        return 0
    wordList = set(wordList)
    queue = deque([(beginWord, 1)])
    while queue:
        current_word, level = queue.popleft()
        for i in range(len(current_word)):
            for char in 'abcdefghijklmnopqrstuvwxyz':
                next_word = current_word[:i] + char + current_word[i+1:]
                if next_word == endWord:
                    return level + 1
                if next_word in wordList:
                    wordList.remove(next_word)
                    queue.append((next_word, level + 1))
    return 0

8. Trapping Rain Water

Problem: Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

Approach: Use two pointers to calculate the trapped water.

def trap(height):
    if not height:
        return 0
    left, right = 0, len(height) - 1
    left_max, right_max = height[left], height[right]
    water = 0
    while left < right:
        if height[left] < height[right]:
            left += 1
            left_max = max(left_max, height[left])
            water += max(0, left_max - height[left])
        else:
            right -= 1
            right_max = max(right_max, height[right])
            water += max(0, right_max - height[right])
    return water

9. Remove Nth Node From End of List

Problem: Remove the nth node from the end of a linked list and return its head.

Approach: Use two pointers to find the node to remove.

def remove_nth_from_end(head, n):
    dummy = ListNode(0)
    dummy.next = head
    first, second = dummy, dummy
    for _ in range(n + 1):
        first = first.next
    while first:
        first = first.next
        second = second.next
    second.next = second.next.next
    return dummy.next

10. Longest Palindromic Substring

Problem: Find the longest palindromic substring in a given string.

Approach: Use expand around center technique.

def longest_palindromic_substring(s):
    if not s or len(s) < 1:
        return ""
    
    def expand_around_center(left, right):
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1
        return right - left - 1
    
    start, end = 0, 0
    for i in range(len(s)):
        len1 = expand_around_center(i, i)
        len2 = expand_around_center(i, i + 1)
        max_len = max(len1, len2)
        if max_len > end - start:
            start = i - (max_len - 1) // 2
            end = i + max_len // 2
    
    return s[start:end + 1]

These questions reflect the types of problems that require a deep understanding of algorithms, data structures, and efficient problem-solving techniques. Practice solving these and similar problems to prepare effectively for your coding interview at Apple.