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

Ace the Microsoft Interview: Must-Know Python Coding Problems

27 min read

Jun 12, 2024

content

Pattern 1: Custom Data Structures

Implement LRU Cache

Solution

Pattern 2: Cyclic Sort

First Missing Positive

Solution

Pattern 3: Sliding Window

Longest Substring without Repeating Characters

Solution

Pattern 4: Dynamic Programming

Maximum Subarray

Solution

Word Break

Solution

Word Break II

Solution

Pattern 5: Knowing What to Track

Two Sum

Solution

Group Anagrams

Solution

Pattern 6: K-Way Merge

Merge K Sorted Lists

Solution

Pattern 7: Merge Intervals

Meeting Rooms II

Solution

Microsoft’s culture is based on a growth mindset, where employees constantly strive to learn about their customers, colleagues, and field of expertise. As a result, Microsoft takes a holistic approach to assessing candidates’ technical competency during interviews. Interviewers look for core technical skills paired with a strategic approach to problem-solving.

One of the best ways you can showcase your technical and analytical skills is through coding problems. During the Microsoft technical interview, you can expect to solve multiple coding problems in real time and walk interviewers through your solutions.

Breaking down a new coding problem in front of industry experts can be challenging. However, you can set yourself up for success by focusing on the patterns that underlie common coding problems.

When you recognize a coding pattern, you can identify similarities between the problem and the ones you’ve solved. This can help you solve even the toughest problems in a structured, efficient way.

Today, we’ll review 7 patterns you will most likely encounter in your technical interview at Microsoft.

Once familiar with these patterns, you can solve common coding problems confidently. Let's dive in!

Pattern 1: Custom Data Structures#

Custom data structures are essentially modified versions of existing data structures tailored to address specific needs. We often must 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 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 insufficient or where specialized operations must 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.

Caches use relatively expensive, faster memory, so they are not designed to store large datasets. 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 and how they interact 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.

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 of a 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 frequently asked coding pattern in the list.

Pattern 2: Cyclic Sort#

The Cyclic Sort pattern is a strategy for sorting arrays containing a known range of numbers from 1 to n. This method involves iterating through the array and placing each element at its correct position, where each element's value matches its index in the array. Each element is shifted to its rightful position through a series of swaps, guaranteeing a sorted array without needing additional space. This sorts the array differently than comparison-based algorithms like Quicksort or Merge Sort. Examine scenarios where the array consists of distinct numbers within a specific range to determine if a problem can be solved using the Cyclic Sort pattern. Common problems well-suited for this pattern include finding missing or duplicate numbers, sorting arrays of numbers from 1 to n, or identifying the smallest missing positive integer.

Let’s explore the following problem to understand how easy it is to use Cyclic Sort to solve the given coding problem:

First Missing Positive#

Given an unsorted integer array, nums, return the smallest missing positive integer. Create an algorithm that runs with an $O(n)$ time complexity and utilizes a constant amount of space.

Note: The smallest missing positive isn’t the first positive number that’s missing in the range of elements in the input, but the first positive number that’s missing if we start from $1$ .

Solution#

An array of size $n$ containing numbers ranging from $1$ to $n$ can be sorted using the cyclic sort approach in $O(n)$ . Here, we have two challenges. First, the array may have negative numbers as well. Second, the array does not have all consecutive numbers.

The first challenge can be solved by simply ignoring the negative values. The second problem can be solved by linearly scanning the sorted array in $O(n)$ . So, overall, our problem is solved in $O(n)$ time and $O(1)$ space because cyclic sort sorts the elements in place with $O(1)$ extra space. Now, we can proceed further and discuss our algorithm.

The algorithm iterates over each element of the array, and for each element, it determines the correct position where the element should be placed. It subtracts $1$ from the element value because of 0-based indexing. It checks the following conditions for each element after determining its correct position:

If the current element is in the $[1−n]$ range, and if it is not already at its correct position, swap the current element with the element at its correct position.
Otherwise, move on to the next element.

After placing all the elements at the correct positions, traverse the array again and check if the value at each index is equal to its index plus $1$ . If it is not, return the index plus $1$ as the smallest missing positive integer.

If all the values are in order, return the length of the array plus $1$ as the smallest missing positive integer.

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

def smallest_missing_positive_integer(nums):
	i = 0
	while i < len(nums):
		correct_spot = nums[i] - 1  # Determine the correct position of the current element
		
		# Check if the current element is in the range [1, n] and is not already at its correct position
		if 0 <= correct_spot < len(nums) and nums[i] != nums[correct_spot]:
			
			# Swap the current element with the element at its correct position
			nums[i], nums[correct_spot] = nums[correct_spot], nums[i]
		else:
			i += 1  # Move on to the next element if the current element is already at its correct position or out of range
	# Iterate through the array again and check if each element is equal to its index plus 1
	for i in range(len(nums)):
		if i + 1 != nums[i]:
			return i + 1  # Return the smallest missing positive integer
	return len(nums) + 1  # If all the elements are in order, return the next positive integer
# Driver code
def main():
	input_array = [[1, 2, 3, 4], [-1, 3, 5, 7, 1], [1, 5, 4, 3, 2], [-1 , 0, 2, 1, 4], [1,4,3]]
	x = 1
	for i in range(len(input_array)):
		print(x, ".\tThe first missing positive integer in the list ", input_array[i], " is: ", sep = "")
		print("\t" + str(smallest_missing_positive_integer(input_array[i])))
		print("-" * 100)
		x = x + 1
if __name__ == '__main__':
  	main()

First Missing Positive

After understanding how to use the Cyclic Sort effectively, it's time to explore the next 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 it. Sequential information processing 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. The current character is checked during each iteration to see if it exists in the hash map. It is added to the hash map along with its index if it does not exist. However, a repeating character has been discovered if the current character already exists in the hash map and its index falls within the current window. 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, with the key being the current element and the value being 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 current element from repeating in the current window, the next candidate substring will start 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 current element's index.
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: 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 examples illustrate the application of the Dynamic Programming pattern to efficiently solve these problems:

Maximum Subarray#

Given an integer array, nums, find the contiguous subarray with the largest sum and return its sum.

Note: A subarray is a contiguous part of an array that contains at least one number.

Solution#

We’ll solve this problem using Kadane’s Algorithm. It’s a Dynamic Programming approach. The key idea is that we can efficiently find the maximum subarray ending at any position based on the maximum subarray ending at the previous position.

The subproblem here is finding the maximum subarray sum that ends at a specific index i. We need to calculate this for every index i in the array. The base case is the first element of the array, where both the current subarray sum and maximum subarray sum are initialized with the first element’s value. This is the starting point for solving the subproblems. We reuse the previously computed maximum subarray sum at each step to find the solution for the current subproblem.

The steps of the algorithm are given below:

Initialize two variables, current_sum and max_sum, with the value of the first element in the input list. These variables are used to keep track of the current sum of the subarray being considered and the maximum sum found so far.
Iterate through the input list, starting from the second element to the end of the list. Within the loop, perform the following steps:
1. If current_sum + nums[i] is smaller than nums[i], this indicates that starting a new subarray with nums[i] would yield a larger sum than extending the previous subarray. In such cases, reset current_sum to nums[i].
2. Compare the current max_sum with the updated current_sum. This step ensures that the max_sum always stores the maximum sum encountered so far.
After the loop completes, the function returns the max_sum, which represents the maximum sum of any contiguous subarray within the input list.

Let’s look at the code for this solution:

def max_sub_array(nums):
    # Initialize variables to keep track of the current subarray sum and the maximum subarray sum.
    current_sum = nums[0]
    max_sum = nums[0]
    # Iterate through the array starting from the second element.
    for i in range(1, len(nums)):
        # Calculate the current subarray sum by considering two possibilities:
        # 1. The current element creates a new subarray with a higher sum (nums[i] itself).
        # 2. The current element extends the subarray ending at i-1 with the current element.
        current_sum = max(nums[i], current_sum + nums[i])
        # Update the maximum subarray sum seen so far.
        max_sum = max(max_sum, current_sum)
    # Return the maximum subarray sum.
    return max_sum
# Driver code
def main():
    inputs = [[1, 2, 2, 3, 3, 1, 4], [2, 2, 1], [4, 1, 2, 1, 2], [-4, -1, -2, -1, -2], [25]]
    for i in range(len(inputs)):
        print(i + 1, ".\tArray: ", inputs[i], sep="")
        print("\tResult: ", max_sub_array(inputs[i]), sep="")
        print("-" * 100)
if __name__ == "__main__":
    main()

Maximum Subarray

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

Word Break#

Given a string, s, and a dictionary of strings, word_dict, check if s can be segmented into a space-separated sequence of one or more dictionary words. If yes, return TRUE; else, return FALSE.

Note: The same word in the dictionary may be used multiple times.

Solution#

If we solve this using a recursive approach, we'll notice that many prefixes are computed again even though they were checked in the earlier computations. For example, a prefix of two characters contains a prefix of one character that has already been checked. These redundant computations consume a lot of time that can be avoided using dynamic programming. The idea is to use a lookup table, dp, of size $n+1$ , where $n$ is the length of the input string and $1$ is added to cater the empty string. This table will store the results of the shorter prefixes that can be used, in $O(1)$ lookup time, for solving the longer prefixes.

The dp is initialized with FALSE except for dp[0], which is set to TRUE because an empty string is assumed to be a valid word in the dictionary. Then, using two pointers, i and j, we check every possible prefix s[j..i] and whether they’re contained in the dictionary. If the substring s[j..i] is found in the dictionary, we don’t check further smaller substrings. We also check whether dp[j] is TRUE, which tells us that the prefix s[0..j] was found in the dictionary. If both conditions are fulfilled, the corresponding dp index, i.e., dp[i], is set to TRUE. We continue this process until the whole string has been processed. Finally, we return the value of dp[n], which tells us that the input string could be segmented into a space-separated sequence of dictionary words.

def word_break(s, word_dict):
    n = len(s)
    # Create a set of words from the list so that the lookup cost in the dictionary becomes O(1)
    word_set = set(word_dict)
    # Initialize the lookup table
    dp = [False]*(n+1)
    # Setting the first element to True as it represents the empty string
    dp[0] = True
    for i in range(1, n+1):
        for j in range(i):
            # Checking if the substring from j to i is present in the wordDict and dp[j] is true
            if dp[j] and s[j:i] in word_set:
                dp[i] = True
                # If a substring is found, no need to check further smaller substrings
                break
    
    # Return the last element of dp list
    return dp[n]
# Driver Code
def main():
    s = ["vegancookbook", "catsanddog", "highwaycrash",
         "pineapplepenapple", "screamicecream", "educativecourse"]
    word_dict = ["ncoo", "kboo", "inea", "icec", "ghway", "and", "anco", "hi", "way", "wa",
                 "amic", "ed", "cecre", "ena", "tsa", "ami", "lepen", "highway", "ples",
                 "ookb", "epe", "nea", "cra", "lepe", "ycras", "dog", "nddo", "hway",
                 "ecrea", "apple", "shp", "kbo", "yc", "cat", "tsan", "ganco", "lescr",
                 "ep", "penapple", "pine", "book", "cats", "andd", "vegan", "cookbook"]
    print("The list of words we can use to break down the strings are:\n\n", word_dict, "\n")
    print("-" * 100)
    for i in range(len(s)):
        print("Test Case #", i+1, "\n\nInput: '" + str(s[i])+"'\n")
        print_possible_combinations(s[i], word_dict)
        print("\nOutput: " + str(word_break(str(s[i]), word_dict)))
        print("-" * 100)
if __name__ == '__main__':
    main()

Word Break

Now, let's move to the next example of Dynamic Programming.

Word Break II#

Given a string, s, and an array of strings, word_dict, representing a dictionary, add spaces to s to break it up into a sequence of valid words from word_dict. The output is an array of all possible sequences of words (sentences). The order in which the sentences are listed is not significant.

Note: The same dictionary word may be reused multiple times in the segmentation.

Solution#

In this solution, we will use a bottom-up Dynamic Programming (also known as the tabulation) approach. This is an iterative method of solving dynamic programming problems. The idea is that if a prefix of the input string matches any word www in the dictionary, we can split the string into two parts: the matching word and the suffix of the input string. We start from an empty prefix, which is the base case. The prefix would eventually develop into the complete input string.

Here’s how the algorithm works:

We initialize an empty lookup table, dp, of length, $n+1$ , where dp[i] will correspond to the prefix of length i. This table will be used to store the solutions to previously solved subproblems. It will have the following properties:
- The first entry of the table will represent a prefix of length 0, i.e., an empty string "".
- The rest of the entries will represent the other prefixes of the string s. For example, the input string "vegan" will have the prefixes "v", "ve", "veg", "vega", and "vegan".
- Each table entry will contain an array containing the sentences that can be formed from the respective prefix. At this point, all the arrays are empty.
For the base case, we add an empty string to the array corresponding to the first entry of the dp table. This is because the only sentence that can be formed from an empty string is an empty string.
Next, we traverse the input string by breaking it into its prefixes by including a single character, one at a time, in each iteration.
- For the current prefix, we initialize an array, temp, to store the valid sentences formed from that prefix. Let’s suppose that the input string is “vegan” and that the current prefix is "vega".
- For all possible suffixes of the current prefix, we check if the suffix exists in the given dictionary. In our example, this would mean checking the dictionary for the suffixes "vega", "ega", "ga", and "a". For each suffix, it will either match a dictionary word or not:
  - If it does, we know that the suffix is a valid word from the dictionary and can be used as part of the solution. Therefore, in the dp table, we retrieve all the possible sentences for the prefix to the left of this suffix. Supposing that the current suffix of "vega" is "a" and that "a" is present in the dictionary, we would retrieve all the sentences already found for "veg". This means that we reuse the solutions of the subproblem smaller than the current subproblem. Now, we form new sentences for the current prefix by appending a space character and the current suffix (valid dictionary word) to each retrieved sentence. Supposing that the valid sentences for the subproblem "veg" are "v eg", and "ve g", we will add these new sentences for the current subproblem, "vega": "veg a", "v eg a", and "ve g a". We add the new sentences to the temp array of this prefix.
  - If the suffix is not present in the dictionary, no sentences can be made from the current prefix, so the temp array of that prefix remains empty.
- We repeat the above steps for all suffixes of the current prefix.
- We set the entry corresponding to the current prefix in the dp table equal to the temp array.
We repeat the steps above for all prefixes of the input string.
After all the prefixes have been evaluated, the last entry of the dp table will be an array containing all the sentences formed from the largest prefix, i.e., the complete string. Therefore, we return this array.

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

def word_break(s, word_dict):
    # Initialize the dp table of size s.length + 1
    dp = [[]] * (len(s) + 1)
    # Set the base case
    dp[0] = [""]
    # For each substring in the input string, repeat the process.
    for i in range(1, len(s) + 1):
        prefix = s[:i]
        # An array to store the valid sentences formed from the current prefix being checked.
        temp = []
        # Iterate over the current prefix and break it down into all possible suffixes.
        for j in range(0, i):
            suffix = prefix[j:]
            
            # Check if the current suffix exists in word_dict. If it does, we know that it is a valid word
            # and can be used as part of the solution.
            if suffix in word_dict:
                
                # Retrieve the valid sentences from the previously computed subproblem
                for substring in dp[j]:
                    # Merge the suffix with the already calculated results
                    temp.append((substring + " " + suffix).strip())
        dp[i] = temp
    # Returning all the sentences formed from the complete string s.
    return dp[len(s)]
# Driver Code
def main():
    s = ["vegancookbook", "catsanddog", "highwaycrash",
         "pineapplepenapple", "screamicecream", "educativecourse"]
    word_dict = ["oghi", "ncoo", "kboo", "inea",
        "icec", "ghway", "tsand", "anco", "eame", "ghigh", "hi", "way", "wa",
        "amic", "mi", "ed", "cecre", "pple", "reamicecreamed", "ena", "tsa", "ami", "hwaycrashpineapplepenapplescreamicecreamed", "lepen", "okca", "highway", "ples", "atsa", "oghig", "ookb", "epe", "ookca", "nea", "cra", "lepe", "vegancookbookcatsandd",
        "kc", "ra", "le", "ay", "crashpineapple", "ycras", "vegancookbookcatsanddoghighwaycrashpineapplepenapplescre", "doghi", "nddo", "hway", "vegancookbookcatsanddoghi", "vegancookbookcatsanddoghighwaycr", "at", "mice", "nc", "d", "enapplescreamicecreamed", "h",
        "ecrea", "nappl", "shp", "kbo", "yc", "vegancookbookcatsanddoghighwaycrashpineapplepenapplescream", "cat", "waycrashpineapplepenapplescreamicecreamed", "tsan", "vegancookbookcatsanddoghighwaycrashpineap", "ganco", "lescr", "sand", "applescreamicecreamed", "vegancookbookcatsanddoghig", "pi", "vegancookbookcatsanddoghighwaycrashpineapp", "cookb", "okcat", "neap", "nap", "oghighwaycrashpineapplepenapplescreamicecreamed", "crashpineapplepenapplescreamicecreamed",
        "ashpi", "ega", "escreamicecreamed", "hwa", "rash", "cre", "micecreamed", "plepe", "coo", "epen", "napp", "wayc", "vegancookbookcatsanddoghighwaycrashpinea", "vegancookbookcatsanddogh", "plep", "ice", "ple", "gh", "ghw", "cook", "pl", "app", "ic", "pinea", "hello", "dog", "vegancookbookcat", "eamed", "ook", "lesc", "ddog", "ca", "vegancookbookcatsanddoghighwaycrashpineapplepenapplescreamice", "c", "escr", "penap", "boo", "eami", "ecreamed", "vegancookbookcatsanddoghighwaycrashpi", "igh", "mic", "ganc", "vegancookbookcatsanddoghighwaycrashpineapplepenap",
        "eappl", "vegancookbookcatsanddoghighway", "ep", "penapple", "b", "ycrashpineapplepenapplescreamicecreamed", "pin", "book", "p", "sa", "okb", "andd", "ayc", "sh", "vegan", "cookbook"]
    print("The list of words we can use to break down the strings are:\n\n", word_dict, "\n")
    print("-" * 100)
    for i in range(len(s)):
        print("Test Case #", i+1, "\n\nThe possible strings from the string '" +
              str(s[i]) + "' are the following combinations:", sep="")
        print("\n" + str(word_break(str(s[i]), word_dict)))
        print("-" * 100)
if __name__ == '__main__':
    main()

Word Break II

After understanding how to use Dynamic Programming effectively, it's time to explore the next coding pattern.

Pattern 5: 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 problems 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 indexes of the two 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, let's move to another example that can be solved using the Knowing What to Track pattern.

Group Anagrams#

Given a list of words or phrases, group the words that are anagrams of each other. An anagram is a word or phrase formed from another word by rearranging its letters.

Solution#

This solution involves computing the frequency of each letter in every string. This will help reduce the time complexity of the given problem. We’ll just compute the frequency of every string and store the strings in their respective list in a hash map.

We see that all members of each set are characterized by the same frequency of each letter. This means that the frequency of each letter in the words belonging to the same group is equal. In the set [["speed", "spede"]], the frequency of the characters s, p, e, and d are the same in each word.

Let’s see how we can implement the above algorithm:

For each string, compute a $26$ -element list. Each element in this list represents the frequency of an English letter in the corresponding string. This frequency count will be represented as a tuple. For example, "abbccc" will be represented as (1, 2, 3, 0, 0, ..., 0). This mapping will generate identical lists for strings that are anagrams.
Use this list as a key to insert the strings into a hash map. All anagrams will be mapped to the same key in this hash map.
While traversing each string, we generate its $26$ -element list and check if this list is present as a key in the hash map. If it does, we'll append the string to the array corresponding to that key. Otherwise, we'll add the new key-value pair to the hash map.
Return the values of the hash map in a two-dimensional array since each value will be an individual set of anagrams.

Let's look at the coded solution below:

def group_anagrams(strs):
    
	# Hash map for counting the characters
    res = {}
    for s in strs:
        
		# A place for every single letter in our string
        count = [0] * 26
        
		# Compute the frequency for every string
        for i in s:
            
			# Calculating the value from 1 to 26 for the letter
            index = ord(i) - ord('a')
            
			# Increasing its frequency in the hash map
            count[index] += 1
        
		# Each element in this tuple represents the frequency of an
        # English letter in the corresponding title
        key = tuple(count)
        if key in res:
            res[key].append(s)
        else:
            
			# We add the string as an anagram if it 
            # matched the content of our 'res' hash map
            res[key] = [s]
    return res.values()
# Driver code
def main():
    titles = [
        ["eat", "beat", "neat", "tea"],
        ["duel", "dule", "speed", "spede", "deul", "cars"],
        ["eat", "tea", "tan", "ate", "nat", "bat"],
        [""],
        ["sword", "swords"], ["pot", "top", "opt"]]
    for i in range(len(titles)):
        print((i+1), ".\tThe Grouped Anagrams for the list ",
              titles[i], " are:", sep="")
        
        result = list(group_anagrams(titles[i]))
        print("\t", result, sep="")
        print("-" * 100)
if __name__ == '__main__':
    main()

Group Anagrams

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

Pattern 6: 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 in 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 K Sorted Lists#

Given an array of $k$ sorted linked lists, merge them into a single sorted linked list and return the head of this linked list.

Solution#

In this solution, we iterate through the given list of sorted lists, progressively merging pairs of lists until only one merged list remains. We achieve this by using a divide-and-conquer strategy, where it iteratively merges adjacent pairs of lists. This way, after the first pairing, we're left with $\frac{k}{2}$ lists, then $\frac{k}{4}$ , then $\frac{k}{8}$ , and so on.

To merge the adjacent pairs of lists at a time, we use a helper function, merge_2_lists(head1, head2). It uses a dummy node to initialize the merged list and a prev pointer to track the last node added. Iterating through both lists simultaneously, it compares nodes from each list and attaches the smaller one to the merged list. It continues until one list is exhausted. Then, it appends the remaining nodes from the non-empty list. Finally, it returns the head of the merged list. This approach ensures the merged list remains sorted throughout the merging process.

We keep merging the adjacent pairs of lists until all lists are merged into one. Finally, we return the head of the final merged list.

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

main.py

print_list.py

linked_list_node.py

linked_list.py

from __future__ import print_function
from linked_list import LinkedList
from linked_list_node import LinkedListNode
from print_list import print_list_with_forward_arrow
# Helper function
def merge_2_lists(head1, head2): 
    dummy = LinkedListNode(-1)
    prev = dummy  # Set the prev pointer to the dummy node
    # Traverse over the lists until both or one of them becomes null
    while head1 and head2:
        if head1.data <= head2.data:
            
            # If l1 value is <=  l2 value, add l1 node to the list
            prev.next = head1
            head1 = head1.next
        else:
            
            # If l1 value is greater than l2 value, add l2 node to the list
            prev.next = head2
            head2 = head2.next
        prev = prev.next
    if head1 is not None:
        prev.next = head1
    else:
        prev.next = head2
    return dummy.next
# Main function
def merge_k_lists(lists):  
    if len(lists) > 0:
        step = 1
        while step < len(lists):
            
            # Traverse over the lists in pairs to merge with result
            for i in range(0, len(lists) - step, step * 2):
                lists[i].head = merge_2_lists(lists[i].head, lists[i + step].head)
            step *= 2
        return lists[0].head
    return
# Driver code
def main():
    inputlists = [[[21, 23, 42], [1, 2, 4]],
        [[11, 41, 51], [21, 23, 42]],
        [[2], [1, 2, 4], [25, 56, 66, 72]],
        [[11, 41, 51], [2], [2], [2], [1, 2, 4]],
        [[10, 30], [15, 25], [1, 7], [3, 9], [100, 300], [115, 125], [10, 70], [30, 90]]
    ]
    inp_num = 1
    for i in inputlists:
        print(inp_num, ".\tInput lists:", sep = "")
        ll_lists = []
        for x in i:
            a = LinkedList()
            a.create_linked_list(x)
            ll_lists.append(a)
            print("\t", end = "")
            print_list_with_forward_arrow(a.head)
            print()
        inp_num += 1
        print("\n\tMerged list: \n\t", end = "")
        print_list_with_forward_arrow(merge_k_lists(ll_lists))
        print("\n", "-"*100, sep = "")
if __name__ == "__main__":
    main()

Merge K Sorted Lists

With our understanding of K-Way Merge established, let’s explore the last, but certainly not least, coding pattern from Microsoft's list of frequently asked patterns.

Pattern 7: Merge Intervals#

The Merge Intervals pattern is a powerful coding technique for problems involving meeting times or intervals. This technique is particularly useful when dealing with a set of intervals and performing operations such as merging overlapping intervals or determining their intersections.

In this technique, we typically start by sorting the given intervals based on their start or end times, which helps identify the overlapping intervals efficiently. Once we have this interval information, we can swiftly perform the tasks based on the problem’s requirements. The Merge Intervals pattern has many applications in multiple scenarios, including scheduling algorithms, resource allocation problems, and calendar management systems. From analyzing time-based data to consolidating meeting schedules, this coding technique offers an elegant solution for handling interval-related operations effectively.

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

Meeting Rooms II#

Given an input array of meeting time intervals, intervals, where each interval has a start time and an end time, find the minimum number of meeting rooms required to hold these meetings.

An important thing to note here is that the specified end time for each meeting is exclusive.

Solution#

The optimized approach to solve this problem is to use the Merge Intervals technique. In this approach, we sort the given meetings by their start time and keep track of the end times of each meeting. We do this by initializing a min-heap and adding the end time of the first meeting to the heap. The heap data structure enables us to efficiently keep track of the meeting with the earliest end time, thereby providing insight into the availability of meeting rooms.

Then, for each subsequent meeting, we check if the room occupied by the earliest ending meeting, the minimum element of the heap, is free at the time of the current meeting. If the meeting with the earliest end time has already ended before the start of the current meeting, then we can use the same meeting room again for the current meeting. We remove the meeting with the earliest end time from the heap and add the end time of the current meeting to the heap. If the earliest ending meeting has not ended by the start of the current meeting, then we know that we have to allocate a new room for the current meeting, therefore, we add its end time to the heap.

After processing all the meeting intervals, the size of the heap will be equal to the number of meeting rooms allocated. This will be the minimum number of rooms needed to accommodate all the meetings.

Let’s look at the code for this solution:

import heapq
def find_sets(intervals):
    if not intervals:
        return 0
    # Meetings are sorted according to their start time
    intervals.sort(key=lambda x: x[0])
    # Initialize a new heap and add the ending time of the first meeting to the heap
    end_times_heap = []
    heapq.heappush(end_times_heap, intervals[0][1])
    
    for i in range(1, len(intervals)):
        # Check if the minimum element of the heap (i.e., the earliest ending meeting) is free
        if intervals[i][0] >= end_times_heap[0]:
            # If the room is free, extract the earliest ending meeting and add the ending time of the current meeting
            heapq.heappop(end_times_heap)
        # Add the ending time of the current meeting to the heap
        heapq.heappush(end_times_heap, intervals[i][1])
    
    # The size of the heap tells us the number of rooms allocated
    return len(end_times_heap)
# Driver code
def main():
    schedule_meetings = [[[0,10], [2,10], [11,30]], 
                        [[3,7], [2,12], [10,20], [8,24]],
                        [[1,9], [5,8], [4,14], [3,10], [11,25]],
                        [[1,4], [3,8], [8,11], [3,17], [9,15], [16,18]],
                        [[4,12], [5,11], [4,9], [2,12], [9,22]],]
    
    for i in range(len(schedule_meetings)):
        print(str(i+1),".\tScheduled meetings:", schedule_meetings[i])
        print("\tRooms required:", find_sets(schedule_meetings[i]))
        print("-"*100)
if __name__ == '__main__':
    main()

Meeting Rooms II

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

To ace your Microsoft interview, mastering the patterns above is important. Understanding the underlying patterns behind the solutions you devise will help you tackle similar problems in the future and 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 Microsoft, 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