Home/Blog/Interview Prep/Ace the Apple Interview: Must-Know Python Coding Problems

Ace the Apple Interview: Must-Know Python Coding Problems

28 min read

May 31, 2024

content

Pattern 1: Custom Data Structures

Implement LRU Cache

Solution

Pattern 2: Knowing What to Track

Two Sum

Solution

Pattern 3: Sliding Window

Longest Substring without Repeating Characters

Solution

Pattern 4: Two Pointers

Sum of Three Values

Solution

Trapping Rain Water

Solution

Pattern 5: Dynamic Programming

Longest Palindromic Substring

Solution

Pattern 6: Stacks

Flatten Nested List Iterator

Solution

Valid Parentheses

Solution

Pattern 7: Top K Elements

Top K Frequent Elements

Solution

Pattern 8: K-Way Merge

Merge Sorted Array

Solution

Apple prides itself on a hierarchy where "experts lead experts." Specialists in areas like Operations, Hardware Engineering, and Machine Learning lead their respective divisions and collaborate to build innovative products using their expertise.

Because of this structure, the interview process can vary significantly across teams. However, you can expect to solve coding problems for any technical position at Apple. Coding problems help interviewers evaluate technical skills, such as proficiency in certain languages, as well as your approach to problem-solving.

It can feel challenging to solve brand-new coding problems under time constraints—especially in front of industry experts. Fortunately, you can prepare to solve various problems by learning patterns.

When you're familiar with the underlying patterns used to solve coding problems, you can quickly identify similarities between the current problem and the ones you’ve encountered before. From there, you can apply relevant strategies and algorithms to find a solution.

So, how do you know which patterns to study?

Based on the most common coding problems in Apple interviews, we've identified 8 coding patterns that can help you ace your technical interview. We'll break down each pattern and then provide sample problems to show you what it looks like in practice. Now, let's get started!

Pattern 1: Custom Data Structures#

Custom data structures are essentially modified versions of existing data structures tailored to address specific needs. We often need to go beyond standard data structures like arrays and hash tables to tackle unique challenges more effectively. For instance, a web crawler that processes numerous pages and URLs might use a specialized "URL queue" to manage these URLs efficiently, ensuring they are unique and prioritized based on relevance. Custom data structures involve creating custom classes that encapsulate the necessary functionality and properties needed to efficiently manage and manipulate the data. By designing data structures optimized for the problem domain, we can improve the performance and readability of our code while simplifying complex operations. To determine if a problem can benefit from the Custom Data Structures pattern, consider scenarios where standard data structures like arrays, lists, or maps are not sufficient or where specialized operations need to be performed frequently. Common problems suitable for this pattern include implementing priority queues, disjoint-set data structures, or specialized graph representations.

Let’s see how the following example illustrates the application of the Custom Data Structures pattern to efficiently solve the given coding problem:

Implement LRU Cache#

Implement an LRU cache class with the following functions:

Init(capacity): Initializes an LRU cache with the capacity size.
Set(key, value): Adds a new key-value pair or updates an existing key with a new value.
Get(key): Returns the value of the key, or −1 if the key does not exist.

If the number of keys has reached the cache capacity, evict the least recently used key and add the new key.

As caches use relatively expensive, faster memory, they are not designed to store large data sets. Whenever the cache becomes full, we must evict some data from it. There are several caching algorithms to implement a cache eviction policy. LRU is a very simple and commonly used algorithm. The core concept of the LRU algorithm is to evict the oldest data from the cache to accommodate more data.

Solution#

This problem can be solved efficiently if we combine two data structures and use their respective functionalities, as well as the way they interact with each other, to our advantage. A doubly linked list allows us to arrange nodes by the time they were last accessed. However, accessing a value in a linked list is $O(n)$ . On the other hand, a hash table has $O(1)$ lookup time but has no concept of recency. We can combine these two data structures to get the best properties.

Here is the algorithm for the LRU cache:

Set:

If the element exists in the hash map, then update its value and move the corresponding linked list node to the head of the linked list.
Otherwise, if the cache is already full, remove the tail element from the doubly linked list. Then delete its hash map entry, add the new element at the head of the linked list, and add the new key-value pair to the hash map.

Get:

If the element exists in the hash map, move the corresponding linked list node to the head of the linked list and return the element value.
Otherwise, return -1.

Note that the doubly linked list keeps track of the most recently accessed elements. The element at the head of the doubly linked list is the most recently accessed element. All newly inserted elements (in Set) go to the head of the list. Similarly, any element accessed (in the Get operation) goes to the head of the list.

Let’s look at the code for this solution below:

main.py

linked_list_node.py

linked_list.py

from linked_list import LinkedList
# We will use a linked list having pair of integers
# where the first integer will be the key
# and the second integer will be the value
class LRUCache:
    # Initializes an LRU cache with the capacity size
    def __init__(self, capacity):
        self.cache_capacity = capacity
        self.cache_map = {}
        self.cache_list = LinkedList()
    # Returns the value of the key, or -1 if the key does not exist.
    def get(self, key):
        # If the key doesn't exist, we return -1
        found_itr = None
        if key in self.cache_map:
            found_itr = self.cache_map[key]
        else:
            return -1
        list_iterator = found_itr
        # If the key exists, we must move it to the front of the list
        self.cache_list.move_to_head(found_itr)
        return list_iterator.pair[1]
    # Adds a new key-value pair or updates an existing key with a new value
    def set(self, key, value):
        # Check if the key exists in the cache hashmap
        # If the key exists
        if key in self.cache_map:
            found_iter = self.cache_map[key]
            list_iterator = found_iter
            # Move the node corresponding to key to front of the list
            self.cache_list.move_to_head(found_iter)
            # We then update the value of the node
            list_iterator.pair[1] = value
            return
        # If key does not exist and the cache is full
        if len(self.cache_map) == self.cache_capacity:
            # We will need to evict the LRU entry
            # Get the key of the LRU node
            # The first element of each cache entry is the key
            key_tmp = self.cache_list.get_tail().pair[0]
            # This is why we needed to store a <key, value> pair
            # in the cacheList. We would not have been able to get
            # the key if we had just stored the values
            # Remove the last node in list
            self.cache_list.remove_tail()
            # Remove the entry from the cache
            del self.cache_map[key_tmp]
        # The insert_at_head function inserts a new element at the front
        # of the list in constant time
        self.cache_list.insert_at_head([key, value])
        # We set the value of the key as the list begining
        # since we added the new element at head of the list
        self.cache_map[key] = self.cache_list.get_head()
    def print(self):
        print("Cache current size: ", self.cache_list.size,
              ", ", end="")
        print("Cache contents: {", end="")
        node = self.cache_list.get_head()
        while node:
            print("{", str(node.pair[0]), ",", str(node.pair[1]),
                  "}", end="")
            node = node.next
            if node:
                print(", ", end="")
        print("}")
        print("-"*100, "\n")
def main():
    # Creating a cache of size 2
    cache_capacity = 2
    cache = LRUCache(cache_capacity)
    print("Initial state of cache")
    print("Cache capacity: " + str(cache_capacity))
    cache.print()
    keys = [10, 10, 15, 20, 15, 25, 5]
    values = ["20", "get", "25", "40", "get", "85", "5"]
    for i in range(len(keys)):
        if values[i] == "get":
            print("Getting by Key: ", keys[i])
            print("Cached value returned: ", cache.get(keys[i]))
        else:
            print("Setting cache: Key: ", keys[i], ", Value: ", values[i])
            cache.set(keys[i], int(values[i]))
        cache.print()
if __name__ == '__main__':
    main()

Implement LRU Cache

Now that we've explored the design and implementation of Custom Data Structures, let's explore the next coding pattern.

Pattern 2: Knowing What to Track#

The Knowing What to Track pattern is a strategy for efficiently solving problems by tracking certain properties of the input elements. An example of such a property is the frequency of the occurrence of elements in an array or a string. Tracking such a property can often help derive efficient solutions. This pattern operates in two main phases: the tracking phase and the utilization phase. During the tracking phase, we iterate through the dataset and tally the frequency of each element using appropriate data structures like hash maps or arrays. Once frequencies are calculated, we transition to the utilization phase, where we apply this frequency information to solve specific problems. These problems often involve finding the most frequent element, identifying unique occurrences, or detecting patterns within the dataset. To determine if a problem can be solved using this pattern, look for scenarios where frequency tracking or pattern recognition is essential. The famous interview problems that can be solved with this pattern include Palindrome Permutation, Valid Anagram, Design Tic-Tac-Toe, and Group Anagrams.

Let’s take a closer look at how the following coding problem can be efficiently solved with the Knowing What to Track pattern:

Two Sum#

Given an array of integers, arr, and a target, t, identify and return the two indices of the elements that add up to the target t. Moreover, the same index can’t be used twice, and there will be only one solution.

Note: We will assume that the array is zero-indexed and the output order doesn’t matter.

Solution#

We will use a hash map to solve the two-sum problem because it allows us to perform lookups in a constant time, enabling us to quickly check if the difference between the target value and each value of the array already exists in the hash map. If the difference exists in the hash map, we have found the two numbers that add up to the target value, and we can return their indexes. If not, we add the current number and index to the hash map and continue iterating through the input array.

To implement this algorithm, we will first create an empty hash map to store the numbers and their indexes. Then, we will iterate over the input array, and for each number in the array, we will calculate its difference (the difference between the target value and the number). Next, we will check if the difference exists in the hash map as a key. If it does, we will retrieve the value of the difference from the hash map, which is the index of the difference value in the array and return it with the current index as the solution to the problem. If the difference is not in the hash map, we will add the current number as a key and its index i as a value to the hash map. We will continue iterating through the input array until we find a pair of numbers adding to the target value. Once we find such a pair, we will return their indexes.

Let’s look at the code for this solution below:

def two_sum(arr, t):
    # Create an empty hash map to store numbers and their indices
    hashmap = {}
    
    # Iterating over the array of numbers
    for i in range(len(arr)):
        
		# Calculating the difference between the current and target number
        difference = t - arr[i]
        
		# Checking if the difference already exists in the hash map
        if difference in hashmap:
            
			# Returning the indices of the two numbers that add up to the target
            return [i, hashmap[difference]]
        
		# Adding the current number and its index to the hash map
        hashmap[arr[i]] = i
# Driver code
def main():
    inputs = [
                [1, 10, 8, 4, 9],
                [5, 12, 15, 21, 6, 17],
                [2, 4, 6, 8, 10, 19],
                [-4, -8, 0, -7, -3, -10],
                [49, 17, 15, 22, -45, 29, 18, -15, 11, 37, 12, -52]
             ]
    
    targets = [17, 33, 21, -15, 0]
    for i in range(len(targets)):
        print(i + 1, ". Input array = ", inputs[i], sep="")
        print("   Target = ", targets[i], sep="")
        print("   Indices of two numbers = ", two_sum(inputs[i], targets[i]), sep="")
        print("-" * 100)
if __name__ == "__main__":
    main()

Two Sum

Now that we've discussed Knowing What to Track, let's focus on another important coding pattern.

Pattern 3: Sliding Window#

The Sliding Window pattern is a useful tool for efficiently solving problems involving sequential data, such as arrays or strings, where computations on subsets of data must be repeated. In this technique, a window is defined as a contiguous subset of elements within the data that adjusts its boundaries as it moves through the data. The processing of sequential information is efficient because the window only focuses on relevant subsets of the data at any given time, avoiding unnecessary computations on the entire dataset. Computations are typically updated in constant time by considering elements entering or exiting the window. By subtracting leaving elements and adding new ones, the computational time remains constant with each movement of the window. Problems like Find Maximum in Sliding Window, Repeated DNA Sequences, and Best Time to Buy and Sell Stock are commonly solved using the Sliding Window pattern.

Let’s see how the following example illustrates the application of the Sliding Window pattern to efficiently solve the given coding problem:

Longest Substring without Repeating Characters#

Given a string, input_str, return the length of the longest substring without repeating characters.

Solution#

In this solution, we use a modified version of the classic sliding window method. Instead of a fixed-size window, we allow our window to grow, looking for the window that corresponds to the longest substring without repeating characters.

We initialize an empty hash map along with a variable to track character indices and the starting point of the window. Next, we traverse the string character by character. During each iteration, the current character is checked to see if it exists in the hash map. If it does not exist, it is added to the hash map along with its index. However, if the current character already exists in the hash map and its index falls within the current window, a repeating character has been discovered. In this case, the start of the window is updated to the previous location of the current element and incremented, and the length of the current window is calculated. The longest substring seen so far is updated if the length of the current window is greater than its current value. Finally, the length of the longest substring is returned as the result.

Here’s how we implement this technique.

We initialize the following set of variables to $0$ to keep track of the visited elements.
1. window_start: The starting index of the current substring.
2. window_length: The length of the current substring.
3. longest: The length of the longest substring.
For every element in the string, we check whether or not it’s present in the hash map.
1. If it isn’t present, we store it in the hash map such that the key is the current element and the value is its index in the string.
2. If it’s already present in the hash map, the element may have already appeared in the current substring. For this, we check if the previous occurrence of the element is before or after the starting index, window_start, of the current substring.
  1. If it’s after window_start, we calculate the current substring's length, window_length, as the difference between the current index and window_start. If longest is less than the new window_length, we set longest as window_length.
  2. To prevent the repetition of the current element in the current window, the next candidate substring will be set to start from just after the last occurrence of the current element.
3. We then update the value of the corresponding key in the hash map, setting it to the index of the current element.
After traversing the entire sequence of elements, longest holds the length of the longest substring without repeating characters.

Let’s look at the code for this solution:

def find_longest_substring(input_str):
    
	# Check the length of input_str
    if len(input_str) == 0:
        return 0
    window_start, longest, window_length = 0, 0, 0
    last_seen_at = {}
    # Traverse str to find the longest substring 
    # without repeating characters.
    for index, val in enumerate(input_str):
        
		# If the current element is not present in the hash map,
        # then store it in the hash map with the current index as the value.
        if val not in last_seen_at:
            last_seen_at[val] = index
        else:
            
			# If the current element is present in the hash map,
            # it means that this element may have appeared before.
            # Check if the current element occurs before or after `window_start`.
            if last_seen_at[val] >= window_start:
                window_length = index - window_start
                if longest < window_length:
                    longest = window_length
                window_start = last_seen_at[val] + 1
            # Update the last occurrence of
            # the element in the hash map
            last_seen_at[val] = index
    index += 1
    
	# Update the longest substring's
    # length and starting index.
    if longest < index - window_start:
        longest = index - window_start
    return longest
# Driver code
def main():
    string = [
        "abcabcbb",
        "pwwkew",
        "bbbbb",
        "ababababa",
        "",
        "ABCDEFGHI",
        "ABCDEDCBA",
        "AAAABBBBCCCCDDDD",
    ]
    for i in range(len(string)):
        print(i + 1, ". \t Input String: ", string[i], sep="")
        print("\t Length of longest substring: ",
                (find_longest_substring(string[i])))
        print("-" * 100)
if __name__ == "__main__":
    main()

Longest Substring without Repeating Characters

With our understanding of Sliding Window established, let's discuss the next coding pattern.

Pattern 4: Two Pointers#

The Two Pointers technique is one of the must-know coding techniques for effective problem-solving. It involves traversing linear data structures like arrays or linked lists using two pointers moving in a coordinated way. These pointers move in either one direction or opposite directions based on the given problem’s requirements until a condition is met or the input is exhausted. This technique is the go-to solution for problems with sequentially arranged data like arrays, strings, or linked lists or if we need to find some paired elements to satisfy certain constraints or conditions. From verifying a palindrome to detecting cycles in the given data, the Two Pointers technique showcases its efficiency by providing solutions with linear time complexity.

The dynamic movement of these pointers makes the technique both efficient and versatile. Pointers can move independently of each other based on specific criteria, advancing through the same or different data structures. Whether they move in tandem or diverge, their synchronized traversal enables swift problem resolution.

Let’s see how the following examples illustrate the application of the Two Pointers pattern to efficiently solve these problems:

Sum of Three Values#

Given an array of integers, nums, and an integer value, target, determine if there are any three integers in nums whose sum is equal to the target, that is, nums[i] + nums[j] + nums[k] == target. Return TRUE if three such integers exist in the array. Otherwise, return FALSE.

Note: A valid triplet consists of elements with distinct indexes. This means, for the triplet nums[i], nums[j], and nums[k], i $\not =$ j, i $\not =$ k and j $\not =$ k.

Solution#

The Two Pointers pattern is used to solve a similar problem where we find two integers instead of three that sum up to the target value. We place one pointer at each end of a sorted array, the low pointer and the high pointer, and then traverse the array conditionally to find the two integers that sum up to the target value.

Now, in this problem, since we need to find the three integers that sum up to the target value, we slightly enhance the Two Pointers pattern. We use this pattern inside an additional loop. In the loop, we keep one value of the array with us and then look for the other two integers against this selected value that completes the triplet whose sum equals the target value.

First, we sort the input array, nums, in ascending order. This is because traversing an unsorted array would lead to a bad time complexity. If the input array is sorted, we can easily decide, depending on the sum of the current triplet, whether to move the low pointer toward the end, or, the high pointer toward the start. Next, we iterate over the elements in nums using the index i, where i $<$ nums.length - 2. Against each nums[i], we find the other two integers that complete the triplet whose sum equals the target value, that is, nums[i] + nums[low] + nums[high] == target. We do this by traversing nums with the low and high pointers. In each iteration, the traversal starts with the low pointer being at nums[i+1] and the high pointer at the last element of nums. Then, depending on the current sum value, we move these pointers as follows:

If the sum of the triplet is equal to the target, we return TRUE. Otherwise, we continue.
If the sum of the triplet is less than the target, we move the low pointer forward, that is, toward the end. The aim is to increase the sum to be closer or equal to the target value.
If the sum of the triplet is greater than the target, we move the high pointer toward the start. The aim is to reduce the sum to be closer or equal to the target value.

We repeat this for each iteration until we get the required triplet.

Note: As per the problem statement, each number in a triplet, nums[i], nums[low], and nums[high], should be a different element of nums, so i can’t be equal to low or high, and low can’t be equal to high. Therefore, we keep the loop restricted to nums.length - 2.

Let’s look at the code for this solution below:

def find_sum_of_three(nums, target):
    # Sort the input list
    nums.sort()
    # Fix one integer at a time and find the other two
    for i in range(0, len(nums)-2):
        # Initialize the two pointers
        low = i + 1
        high = len(nums) - 1
        # Traverse the list to find the triplet whose sum equals the target
        while low < high:
            triplet = nums[i] + nums[low] + nums[high]
            # The sum of the triplet equals the target
            if triplet == target:
                return True
                
            # The sum of the triplet is less than the target, so move the low pointer forward
            elif triplet < target:
                low += 1
            
            # The sum of the triplet is greater than the target, so move the high pointer backward
            else:
                high -= 1
    
    # No such triplet found whose sum equals the given target
    return False
# Driver code
def main():
    nums_lists = [[3, 7, 1, 2, 8, 4, 5],
                  [-1, 2, 1, -4, 5, -3],
                  [2, 3, 4, 1, 7, 9],
                  [1, -1, 0],
                  [2, 4, 2, 7, 6, 3, 1]]
    targets = [10, 7, 20, -1, 8]
    for i in range(len(nums_lists)):
        print(i + 1, ".\tInput array: ", nums_lists[i], sep="")
        if find_sum_of_three(nums_lists[i], targets[i]):
            print("\tSum for", targets[i], "exists")
        else:
            print("\tSum for", targets[i], "does not exist")
        print("-"*100)
if __name__ == '__main__':
    main()

Sum of Three Values

Now, let's look at another problem that can be solved using the Two Pointers pattern.

Trapping Rain Water#

Given a sequence of non-negative integers representing the heights of bars in an elevation map, the goal is to determine the amount of rainwater that can be trapped between the bars after rain.

Solution#

An optimized approach to solving this problem utilizes the Two Pointers technique. Instead of separately processing the left and right sides for each element, we simplify it into a single iteration using two pointers, left and right, initially positioned at the elevation map's extremes. The key idea is to maintain two variables, left_max and right_max, which track the maximum heights encountered on the left and right. As the pointers move inwards, they calculate the trapped water for each bar based on the lower of the two maximum heights.

Here's the step-by-step algorithm to find the solution:

Start iterating the heights array using two pointers left and right. To keep track of maximum heights on the leftmost side and the rightmost side use two variables left_max and right_max.
If left_max is greater than right_max then it means the maximum height on the left side is greater than the maximum height on the right side.
Hence, we proceed to the right side and calculate the trapped water at the current right position based on right_max. Otherwise, we move on to the left side.
Store the amount of water that can be accumulated by taking a difference between the maximum of the respective sides (left_max or right_max) and the current bar’s height.
Keep iterating and updating the pointers at each step until left becomes greater than right.

Let’s look at the code for this solution below:

def rain_water(heights):
	
    # Initialize two pointers at the leftmost and rightmost positions of the elevation map
	left = 0
	right = len(heights) - 1
    # Variables to store the accumulated rainwater and maximum heights
	stored_water = 0
	left_max, right_max = 0, 0
	
	while left <= right:
		# If the maximum height on the right is less than or equal to the maximum height on the left
		if  left_max > right_max:
			stored_water +=  max(0, right_max - heights[right])
			# Update the right maximum height if necessary
			right_max = max(right_max, heights[right])
			right -= 1
        
		# If the maximum height on the left is less than the maximum height on the right
		else:
			stored_water += max(0, left_max - heights[left])
			# Update the left maximum height if necessary
			left_max = max(left_max, heights[left])
			left +=1
	return stored_water
# Driver code
def main():
    input_list = [
                [1, 0, 1, 2, 1, 4, 0, 3, 5], 
                [2, 0, 9, 6],
                [3, 1, 2, 0, 2],
                [4, 2, 5, 3], [3, 0]
				
                ]
    index = 1
    for i in input_list:
        print(str(index)+".\tHeights: "+str(i))
        print("\tMaximum rainwater: " + str(rain_water(i)))
        index += 1
        print("-" * 100)
if __name__ == "__main__":
    main()

Trapping Rain Water

Now that we've covered the Two Pointers, let's move on to another frequently asked coding pattern.

Pattern 5: Dynamic Programming #

The Dynamic Programming pattern is a technique that helps solve complex problems by breaking them down into simpler subproblems and storing their solutions to avoid redundant computations. This technique is useful when the problem can be divided into overlapping subproblems and optimal substructures. By storing and reusing intermediate results, dynamic programming enables us to solve problems with improved time and space complexity. For instance, a naive recursive approach to check if a string like "rotator" is a palindrome or to calculate Fibonacci numbers can be inefficient due to the repeated calculations of the same subproblems. Dynamic programming addresses these inefficiencies through two main strategies:

Memoization (top-down approach): This technique optimizes recursion by storing the results of subproblems the first time they are computed, preventing redundant calculations.
Tabulation (bottom-up approach): Tabulation constructs a table to store the results of smaller subproblems, gradually building up to solve the larger problem.

Let’s see how the following example illustrates the application of the Dynamic Programming pattern to efficiently solve the given coding problem:

Longest Palindromic Substring#

Given a string s, return the longest palindromic substring in s.

Solution#

If we look at the example above, we notice that any substring of length $3$ contains a substring of length $1$ at the center. Although we had already checked all substrings of length $1$ , our algorithm rechecked them for substrings of longer lengths. This rechecking consumes a lot of time, which can be avoided by storing and reusing the results of the earlier computations. To do this, we can create a lookup table, dp, of size $n \times n$ , where $n$ is the length of the input string. Each cell dp[i][j] will store whether the string s[i..j] is a palindromic substring. If the cell dp[i][j] holds the result of the earlier computation, we will utilize it in the $O(1)$ lookup time instead of making a recursive call again.

Create a resultant array, res, to store the starting and ending indexes of the longest palindromic substring. Initialize it with $[0, 0]$ , depicting that the longest palindromic substring seen so far is the first character of the input string. By definition, any string of length $1$ is always a palindrome.
Initialize a lookup table, dp, with FALSE.
Base case 1: The diagonal in the lookup table is populated with TRUE, because any cell in the diagonal corresponds to a substring of length $1$ , and any string of length $1$ is always a palindrome.
Base case 2: We check whether all two-letter substrings are palindromes and update the res and dp accordingly. We do this by iterating over the string, comparing s[i] and s[i+1], and storing the result at dp[i][i+1]. After that, we also update res if the value of dp[i][i+1] is TRUE, which tells us that the two-letter substring was a palindrome.
After these base cases, we check all substrings of lengths greater than $2$ . However, we only compare the first and the last characters. The rest of the string is checked using the lookup table. For example, for a given string “zing”, we want to check whether “zin” is a palindrome. We’ll only compare ‘z’ and ‘n’ and check the value of dp[1][1], which will tell whether the remaining string “i”, represented by s[1..1], is a palindrome. We’ll take the logical AND of these two results and store it at dp[0][2] because “zin” is represented by the substring s[0..2]. This way, we’ll avoid redundant computations and check all possible substrings using the lookup table.

Let's implement the algorithm as discussed above:

def longest_palindromic_substring(s):
	
    # To store the starting and ending indexes of LPS
    res = [0, 0]
    n = len(s)
    # Initialize a lookup table of dimensions len(s) * len(s)
    dp = [[False for i in range(len(s))] for i in range(len(s))]
    # Base case: A string with one letter is always a palindrome
    for i in range(len(s)):
        dp[i][i] = True
    # Base case: Substrings of length 2
    for i in range(len(s)-1):
        dp[i][i + 1] = (s[i] == s[i + 1]) # Check if two characters are equal
        if dp[i][i + 1]:
            res = [i, i + 1] # Update the resultant array
    # Substrings of lengths greater than 2
    for length in range(3, len(s)+1):
        i = 0
        # Checking every possible substring of any specific length
        for j in range(length - 1, len(s)): # Iterate over possible ending indexes
            dp[i][j] = dp[i + 1][j - 1] and (s[i] == s[j])
            if dp[i][j]:
                res = [i, j]
            i += 1
    
    return s[res[0]:res[1] + 1] # Return the longest palindromic substring
# Driver code
def main():
    strings = ['cat', 'lever', 'xyxxyz', 'wwwwwwwwww', 'tattarrattat']
    
    for i in range(len(strings)):
        print(i + 1, ".\t Input string: '", strings[i], "'", sep="")
        result = longest_palindromic_substring(strings[i])
        print("\t Number of palindromic substrings: ", result, sep="")
        print("-" * 100)
    
if __name__ == '__main__':
    main()

Longest Palindromic Substring

Stacks are commonly used for tasks like expression evaluation, syntax parsing, or tracking state changes in algorithms. To identify if a problem can be solved using the Stacks pattern, look for scenarios where the last in, first out property is advantageous or where tracking state changes in a last in, first out manner is necessary. Examples of common interview problems that can be tackled using the Stacks pattern include evaluating arithmetic expressions, checking balanced parentheses, or implementing a browser’s back functionality.

Let’s see how the following examples illustrate the application of the Stacks pattern to efficiently solve these problems:

Flatten Nested List Iterator#

Given a nested list of integers where each element is either an integer or a list whose elements may also be integers or other integer lists, implement an iterator to flatten the nested list.

Implement the Nested Iterator class that has the following functions:

Init: This initializes the iterator with the nested list.
Next (): This returns the next integer in the nested list.
Has Next (): This returns TRUE if there are still some integers in the nested list. Otherwise, it returns FALSE.

Solution#

In this solution, we use a stack to store individual integers and nested lists of integers. We push all the elements of the nested list onto the stack in the reverse order during initialization. We do this to ensure the correct processing of the nested list when using a stack-based iterator. This ensures that when we pop elements off the stack, they are in the correct order as they appeared in the original nested list.

The Has Next function performs a set of push and pop operations on the stack as a loop. It checks if the top element of the stack is an integer. If so, it returns TRUE. Otherwise, if the top element is a list of integers, then it pops from the stack and pushes each element of the list onto the stack in reverse order. This way, the lists at the top of the stack are converted into individual integers whenever the Has Next function is called. If the stack is empty, the function returns FALSE.

The Next function first calls the Has Next function to check if there is an integer in the stack. If the Has Next function returns TRUE, it pops from the stack and returns this popped value.

Let’s look at the code for this solution:

main.py

nested_integers.py

from nested_integers import NestedIntegers
class NestedIterator:
    # NestedIterator constructor initializes the stack using the 
    # given nested_list list
    def __init__(self, nested_list):
        self.nested_list_stack = list(reversed([NestedIntegers(val) for val in nested_list]))
    # has_next() will return True if there are still some integers in the 
    # stack (that has nested_list elements) and, otherwise, will return False.
    def has_next(self):
        # Iterate in the stack while the stack is not empty
        while len(self.nested_list_stack) > 0: 
            # Save the top value of the stack
            top = self.nested_list_stack[-1]
            # Check if the top value is integer, if true return True, 
            # if not continue
            if top.is_integer():
                return True
            # If the top is not an integer, it must be the list of integers
            # Pop the list from the stack and save it in the top_list
            top_list = self.nested_list_stack.pop().get_list()
            # Save the length of the top_list in i and iterate in the list
            i = len(top_list) - 1
            while i >= 0:
                # Append the values of the nested list into the stack
                self.nested_list_stack.append(top_list[i])
                i -= 1
        return False
    # next will return the integer from the nested_list 
    def next(self): 
        # Check if there is still an integer in the stack
        if self.has_next():
            # If true pop and return the top of the stack
            return self.nested_list_stack.pop().get_integer()
        return None
# Driver code
def create_nested_iterator_structure(input_list):
    def parse_input(nested, input_list):
        if isinstance(input_list, int):
            nested.set_integer(input_list)
        else:
            for item in input_list:
                child = NestedIntegers()
                nested.add(child)
                parse_input(child, item)
    nested_structure = NestedIntegers()
    parse_input(nested_structure, input_list)
    return nested_structure
def create_nested_iterator_from_structure(nested_structure):
    def flatten(nested, result):
        if nested.is_integer():
            result.append(nested.get_integer())
        else:
            for child in nested.get_list():
                flatten(child, result)
    flattened_list = []
    flatten(nested_structure, flattened_list)
    return NestedIterator(flattened_list)
# Driver code
def main():
    inputs = [
        [1, [2, 3], 4],
        [3, [2, 3, 4], 4, [2, 3]],
        [[2, 3], 3, [2, 3], 4, [2, 3, 4, 5]],
        [1, [3, [4, [5, 6], 7], 8], 9],
        [[2, 3, [2, 3]]]
    ]
    for i, test_case_input in enumerate(inputs, start=1):
        print(i, ".\tOriginal structure: ", inputs[i-1], sep="")
        print("\n\tOutput:\n")
        nested_structure = create_nested_iterator_structure(test_case_input)
        test_case = create_nested_iterator_from_structure(nested_structure)
        #result = []
        while test_case.has_next():
            print("\titr.next(): ", test_case.next())
        print("-"*100)
if __name__ == '__main__':
    main()

Flatten Nested List Iterator

Now, let's move to the next example for Stacks.

Valid Parentheses#

Given an input string, string, which may consist of opening and closing parentheses, check whether or not the string contains valid parenthesization.

The conditions to validate are as follows:

Every opening parenthesis should be closed by the same kind of parenthesis. Therefore, {)and [(]) strings are invalid.
Every opening parenthesis must be closed in the correct order. Therefore, )( and ()(() are invalid.

Solution#

To determine whether or not a string of brackets is valid, we can use a stack to keep track of the opening brackets in the string. We will also use a hashmap to map closing brackets to their corresponding opening brackets. The process involves iterating through each character in the input string and checking if it is an opening or closing bracket.

If the character we encounter is an opening bracket, we will push it onto the stack. If it is a closing bracket, we retrieve the corresponding opening bracket from the hashmap using the closing bracket as the key. If the retrieved opening bracket does not match the top element of the stack, we will return FALSE.

After iterating through the entire input string, we check if the stack is empty to ensure all opening brackets have matched their corresponding closing brackets. If it is, we return TRUE, indicating that the string of brackets is valid. Otherwise, it means that some opening brackets have not been closed properly, and we return FALSE to indicate that the string is invalid.

In summary, using a stack and a hashmap, we can easily keep track of the opening and closing brackets in a string to determine whether it is valid. By comparing each closing bracket to the top element of the stack, we can ensure that each opening bracket has a corresponding closing bracket.

Let’s take a look at the code for this solution below:

def is_valid(string):
	stack = []  # The stack to keep track of brackets
	hashmap = {")": "(", "}": "{", "]": "["}
	for char in string:
		
		# If the character is an opening bracket
		if char not in hashmap:
			
			# Simply push it onto the stack
			stack.append(char)
		else:
			
			# Pop the element from the stack, if it is not empty
			if stack:
				popped_element = stack.pop()
			
			# Otherwise assign a dummy value of '*' to the popped_element variable
			else:
				popped_element = "*"
			# If the mapping for the opening bracket in our hashmap and the popped
			# element of the stack don't match, return False
			if hashmap[char] != popped_element:
				return False
	# If the stack is empty, we will return True otherwise False
	return not stack
# Driver code
def main():
    inputs = ["(){}[]", "{}[]{}[{}])", "(){[{()}]}", "))){{}}}]]", "{[()}"]
    for i in range(len(inputs)):
        print(i + 1, ". Input string = ", inputs[i], sep="")
        print("   Valid parentheses = ", is_valid(inputs[i]), sep="")
        print("-" * 100)
if __name__ == "__main__":
    main()

Valid Parentheses

We've looked at how stacks can be used as a coding pattern to solve problems that require data to be processed in LIFO order, now let's move on to the next pattern.

Pattern 7: Top K Elements#

Unlike other techniques that require sorting the entire data to find the top or bottom $k$ elements, this technique uses a heap to access the required elements from unsorted data. It begins by processing the elements of the dataset and inserting them into the heap. As new elements are encountered, they are compared with those in the collection. If the new element is larger (or smaller, depending on whether we are finding the top $k$ largest or smallest elements), it replaces one of the elements in the collection. This ensures that the collection always contains the top $k$ elements seen so far. This makes it useful for handling large datasets or real-time data where performance matters. Using this pattern saves time and computational resources while solving problems similar to finding the K Largest Elements in a Stream, Top K Frequent Words, and K Smallest Elements in an Array, etc.

Let’s see how the following example illustrates the application of the Top K Elements pattern to efficiently solve the given coding problem:

Top K Frequent Elements#

Given an array of integers, arr, and an integer, k, return the $k$ most frequent elements.

Note: You can return the answer in any order.

Solution#

Finding the top $k$ frequent elements typically involves iterating through all elements. We can optimize this process using the Top K Elements pattern. We begin by determining the frequency of each element using a hash map. Once we have the frequency map, the min-heap is the best data structure to keep track of the top $k$ frequencies. After storing the frequencies of the elements, we’ll iterate through the hash map, insert each element into our heap, and find the top $k$ frequent elements.

The hash map will store the element as the key, and its corresponding frequency in the array as the value. When inserting elements from the hash map into the min-heap, the following steps are taken:

We’ll store a pair $(a,b)$ as a tuple (this can be in the form of any data structure like an array or a tuple) in the heap where $a$ will be the frequency of the element, and $b$ will be the element itself. This ensures that the elements in the min-heap are always sorted by frequency.
We’ll make sure that if the size of the min-heap becomes greater than $k$ , that is, there are more than $k$ elements in the min-heap, we pop the pair with the lowest frequency element from the min-heap. This ensures that we always have the $k$ maximum frequent elements in the min-heap.

Once we have added the pairs from the hash map to the min-heap, the min-heap will have the pairs with the top $k$ frequencies. We will traverse the min-heap and add the second element of each pair from the min-heap to this new array. This is done since we only need the top $k$ frequent elements, not their respective frequencies. Finally, we will return this new array.

Let’s look at the code for this solution below:

from heapq import heappush, heappop
def top_k_frequent(arr, k):
    # find the frequency of each number
    num_frequency_map = {}
    for num in arr:
        num_frequency_map[num] = num_frequency_map.get(num, 0) + 1
    top_k_elements = []
    # go through all numbers of the num_frequency_map
    # and push them in the top_k_elements, which will have
    # top k frequent numbers. If the heap size is more than k,
    # we remove the smallest(top) number
    for num, frequency in num_frequency_map.items():
        heappush(top_k_elements, (frequency, num))
        if len(top_k_elements) > k:
            heappop(top_k_elements)
    # create a list of top k numbers
    top_numbers = []
    while top_k_elements:
        top_numbers.append(heappop(top_k_elements)[1])
    return top_numbers
# Driver code
def main():
    arr = [[1, 3, 5, 12, 11, 12, 11, 12, 5], [1, 3, 5, 14, 18, 14, 5],
           [2, 3, 4, 5, 6, 7, 7], [9, 8, 7, 6, 6, 5, 4, 3, 2, 1], 
           [2, 4, 3, 2, 3, 4, 5, 4, 4, 4], [1, 1, 1, 1, 1, 1], [2, 3]]
    k = [3, 2, 1, 1, 3, 1, 2]
    for i in range(len(k)):
        print(i+1, ". \t Input: (", arr[i], ", ", k[i], ")", sep="")
        print("\t Top", k[i], "frequent Elements: ",
              top_k_frequent(arr[i], k[i]))
        print("-"*100)
if __name__ == '__main__':
    main()

Top K Frequent Elements

With our understanding of Top K Elements established, let's explore the last, but certainly not the least, coding pattern from the list of frequently asked patterns by Apple.

Pattern 8: K-Way Merge#

The K-Way Merge pattern is a technique for merging multiple sorted data structures, like arrays and linked lists, into one. This technique extends the classic merge sort by not just merging two lists but several at once. We repeatedly pick the smallest (or largest for descending order) elements from each list and keep adding them to a new list until all are merged. We can do this efficiently using a min-heap, where we add the first element of each list to the heap. We keep replacing the top of the heap with the next element from the same list until all elements are merged into the new list. Another approach is grouping lists into pairs and merging them through two-way merges. We do this by merging each pair of lists and repeating until we end up with a single fully sorted merged list. Both methods help us merge multiple lists, ensuring our data stays sorted.

Let’s see how the following example illustrates the application of the K-Way Merge pattern to efficiently solve the given problem:

Merge Sorted Array#

Given two sorted integer arrays, nums1 and nums2, and the number of data elements in each array, m and n, implement a function that merges the second array into the first. You have to modify nums1 in place.

Note: Assume that nums1 has a size equal to m + n, meaning it has enough space to hold additional elements from nums2.

Solution#

Since we have two sorted arrays to merge, this problem is the simplest example of the K-Way Merge pattern.

With the K-Way Merge approach, we iterate over the given arrays using two pointers and merge them in place. We start iterating from the end and compare both arrays while populating the result in the nums1 array.

The algorithm works as follows:

Initialize two pointers that point to the last data elements in both arrays.
Initialize a third pointer that points to the last index of nums1.
Traverse nums1 from the end using the third pointer and compare the values corresponding to the first two pointers.
Place the larger of the two values at the third pointer's index.
Repeat the process until the two arrays are merged.

Let’s look at the code for this solution:

def merge_sorted(nums1, m, nums2, n):
    p1 = m - 1  
    p2 = n - 1 
    for p in range(n + m - 1, -1, -1):
        if p2 < 0:
            break
        if p1 >= 0 and nums1[p1] > nums2[p2]:
            nums1[p] = nums1[p1]
            p1 -= 1
        else:
            nums1[p] = nums2[p2]
            p2 -= 1
    return nums1
# Driver code
def main():
    m = [9, 2, 3, 1, 8]
    n = [6, 1, 4, 2, 1]
    nums1 = [[23, 33, 35, 41, 44, 47, 56, 91, 105, 0, 0, 0, 0, 0, 0], [1, 2, 0], [1, 1, 1, 0, 0, 0, 0], [6, 0, 0], [12, 34, 45, 56, 67, 78, 89, 99, 0]]
    nums2 = [[32, 49, 50, 51, 61, 99], [7], [1, 2, 3, 4], [-99, -45], [100]]
    k = 1
    for i in range(len(m)):
        print(k, ".\tnums1: ", nums1[i], ", m: ", m[i], sep = "")
        print("\tnums2: ", nums2[i], ", n: ", n[i], sep = "")
        print("\n\tMerged list: ", merge_sorted(nums1[i], m[i], nums2[i], n[i]), sep = "")
        print("-"*100, "\n")
        k += 1
if __name__ == "__main__":
    main()

Merge Sorted Array

That's about exploring the coding patterns based on the frequently asked coding questions by Apple.

To ace your Apple interview, mastering the patterns we have just discovered is important. Understanding the underlying patterns behind the solutions you devise will not only help you tackle similar problems in the future but also demonstrate your depth of understanding to interviewers. We have explored some of the most common coding patterns with the help of interview questions frequently asked by Apple, but it’s just a start. Remember, practice makes perfect, so dedicate time to solving problems regularly and seek feedback to improve further. You may explore the following courses by Educative for even better preparation because they cover a wide range of coding patterns as well as Dynamic Programming patterns, and that too in various programming languages:

Written By:

Minahil Yaser

Join 2.5 million developers at

Explore the catalog

Free Resources

Learn in-demand tech skills in half the time

PRODUCTS

Mock Interview

New

Courses

Skill Paths

Projects

Assessments

Operation	Time Complexity	Description
Push	O(1)	Adds the element at the top of the stack.
Pop	O(1)	Removes and returns the element from the top of the stack.
Peek	O(1)	Returns the element at the top of the stack without removing it.
IsEmpty	O(1)	Checks whether the stack is empty or not. Returns TRUE if the stack is empty, FALSE otherwise.
Size	O(1)	Returns the total number of elements in the stack.

Ace the Apple Interview: Must-Know Python Coding Problems

Pattern 1: Custom Data Structures#

Implement LRU Cache#

Solution#

Pattern 2: Knowing What to Track#

Two Sum#

Solution#

Pattern 3: Sliding Window#

Longest Substring without Repeating Characters#

Solution#

Pattern 4: Two Pointers#

Sum of Three Values#

Solution#

Trapping Rain Water#

Solution#

Pattern 5: Dynamic Programming #

Longest Palindromic Substring#

Solution#

Pattern 6: Stacks#

Flatten Nested List Iterator#

Solution#

Valid Parentheses#

Solution#

Pattern 7: Top K Elements#

Top K Frequent Elements#

Solution#

Pattern 8: K-Way Merge#

Merge Sorted Array#

Solution#