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

Ace the Oracle Interview: Must-Know Python Coding Problems

27 min read

Jun 13, 2024

content

Pattern 1: Custom Data Structures

Implement LRU Cache

Solution

Insert Delete GetRandom O(1)

Solution

Time-Based Key-Value Store

Solution

Pattern 2: Merge Intervals

Meeting Rooms II

Solution

Pattern 3: K-Way Merge

Merge K Sorted Lists

Solution

Pattern 4: Knowing What to Track

Two Sum

Solution

Pattern 5: Dynamic Programming

Longest Palindromic Substring

Solution

Maximum Subarray

Solution

Pattern 6: Stacks

Valid Parentheses

Solution

Pattern 7: Cyclic Sort

First Missing Positive

Solution

Oracle believes in empowering employees through a healthy, transparent work environment. This begins with the hiring process.

At Oracle, interviewers set candidates up for success by defining a clear agenda. For example, you'll receive several problems to solve by writing code and creating a test case. You can code in your language of choice unless asked otherwise. You'll present an overview of your plan and then jump into coding. You are also encouraged to ask questions as needed.

So, how can you prepare to analyze complex problems and build solutions under time constraints?

Get familiar with the patterns that underlie common coding problems. Coding patterns give you the tools to deconstruct problems and work through them step by step. Once you spot a pattern, you can take a completely unfamiliar problem and apply strategies you've used before.

Today, we'll review 7 patterns often appearing in Oracle's coding problems, with a detailed explanation and sample problems for each.

A strong grasp of these coding patterns will help you interview with confidence. Let's begin!

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 examples illustrate the application of the Custom Data Structures pattern to efficiently solve these problems:

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

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")
# Driver code
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, let's move to the next example of Custom Data Structures.

Insert Delete GetRandom O(1)#

Implement a Random Set data structure that can perform the following operations:

Init(): This initializes the Random Set object.
Insert(): This function takes an integer, data, as its parameter and, if it does not already exist, adds it to the set, returning TRUE. If the integer already exists in the set, the function returns FALSE.
Delete(): This function takes an integer, data, as its parameter and, if it exists in the set, removes it, returning TRUE. If the integer does not exist in the set, the function returns FALSE.
GetRandom(): This function takes no parameters. It returns an integer chosen at random from the set.

Note: Your implementation should aim to have a running time of $O(1)$ (on average) for each operation.

Solution#

Arrays support constant time lookups, but deletion operations in arrays typically take $O(n)$ time complexity due to the need to shift elements. To overcome this limitation, we can use a data structure with constant time deletion—a hash map. We can design our custom data structure by combining arrays for efficient lookups with hash maps for rapid deletions. The implementation of our custom data structure's methods is as follows:

Insert(): We will store the new element in our array when inserting data. Then, insert a key-value pair in our hash map, where the key will be the new element, and the value will be its index in the array. Both of these operations have a time complexity of $O(1)$ .
Delete(): Using the hash map, we find the index in the array at which the element is located. Swap the last element in the array with the one to be removed. Then, in the hash map, update the location of the element we just swapped with the target element and remove the entry for the target element from the hash map. Lastly, pop out the target element from the array. Each of these five operations has a time complexity of $O(1)$ .
GetRandom(): For this operation, we can choose a number at random between $0$ and $n−1$ , where $n$ is the size of the array. We return the integer located at this random index.

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

from random import choice
class RandomSet():
    def __init__(self):
        self.indexor = {}  # Maps the actual value to its index
        self.store = []   # Stores actual values in an array
    # Function to insert a value
    def insert(self, val):
        """
        Inserts a value in the data structure.
        Returns True if it does not already contain the specified element.
        """
        if val in self.indexor:
            return False
        
        # Insert the actual value as a key and its index as a value
        self.indexor[val] = len(self.store)
        
        # Append a new value to the array
        self.store.append(val)
        return True
    # Function to remove a value
    def delete(self, val):
        """
        Removes a value from the data structure.
        Returns True if it contains the specified element.
        """
        if val in self.indexor:
            
            # swap the last element in the array with the element
            # to delete, update the location of the moved element
            # in its entry in the hash map
            last, i = self.store[-1], self.indexor[val]
            self.store[i], self.indexor[last] = last, i
            
            # delete the last element
            del self.indexor[val]
            self.store.pop()
            return True
        return False
    # Function to generate a random value
    def get_random(self):
        """
        Choose an element at random from the data structure.
        """
        return choice(self.store)
# Driver code
def main():
    commands = [["I", "G", "I", "I", "R", "G"],
                ["I", "I", "R", "G", "R", "I"]]
    values = [[10, -1, 100, 1000, 200, -1], [30, 60, 10, -1, 30, 90]]
    for i in range(len(commands)):
        dataset = RandomSet()
        print(i + 1, ". Starting operations:", "\n", sep="")
        for j in range(len(commands[i])):
            if commands[i][j] == "I":
                print("\tInsert (", values[i][j], ") returns ",
                      dataset.insert(values[i][j]), sep="")
            elif commands[i][j] == "R":
                print("\tDelete (", values[i][j], ") returns ",
                      dataset.delete(values[i][j]), sep="")
            elif commands[i][j] == "G":
                print("\tGenerate Random() returns ",
                      dataset.get_random(), sep="")
        print("-" * 100)
if __name__ == '__main__':
    main()

Insert Delete GetRandom O(1)

Now, let's look at another problem that can be solved using the Custom Data Structures pattern.

Time-Based Key-Value Store#

Implement a data structure that can store multiple values of the same key at different timestamps and retrieve the key’s value at a certain timestamp.

We’ll need to implement the TimeStamp class. This class has the following functions:

Init(): This function initializes the values dictionary and timestamp dictionary.
Set Value(key, value, timestamp): This function stores the key and value at any given timestamp.
Get Value(key, timestamp): This function returns the value set for this key at the specified timestamp.

Note: When a query requests the value of a key at a timestamp that is more recent than the most recent entry for that key, our data structure should return the value corresponding to the most recent timestamp.

Solution#

In this solution, we will use two dictionaries to effectively implement the required class. The first dictionary, values_dict, stores the values against a specific key. The second dictionary, timestamps_dict, stores the timestamps corresponding to the same key to keep track of the values stored at a specific timestamp.

Additionally, we aim to reduce the overall time complexity using the binary search instead of the linear one.

Now, let’s discuss the implementation of two of our fundamental functions:

Set Value(key, value, timestamp): This function adds the key with the value for the given timestamp. For this, we check if the key already exists in the values_dict dictionary.

If the key exists and the provided value does not equal the last value stored in the values_dict for this key, we append the value and timestamp to the lists associated with that key in the values_dict and timestamps_dict, respectively.
If the key does not exist in the values_dict dictionary, it creates a new entry in both the values_dict and timestamps_dict dictionaries.

Get Value(key, timestamp): This function returns the value set previously, with the highest timestamp for the respective key. This function uses the search_index function, which uses the binary search in its implementation. To implement this function, we initialize the left and right variables as starting and ending positions of the timestamps_dict dictionary. We then find the middle position and move these pointers to get the required value. If the required value is less than the middle value, we increment the right pointer. Otherwise, we increment the left pointer.

We check the following conditions to get the required value:

We first verify whether or not the required key exists. If it does not exist, then return the empty string.
If the key exists, we check the following conditions:
- If the given timestamp does not exist but is greater than the timestamp that was set previously, it returns the value associated with the nearest smaller timestamp.
- If the given timestamp exists, it returns the value associated with the given key and timestamp.

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

import random
class TimeStamp:
    def __init__(self):
        self.values_dict = {}
        self.timestamps_dict = {}
    #  Set data variables in the TimeStamp class
    def set_value(self, key, value, timestamp):
        # Check if the given key already exists in the values dictionary
        if key in self.values_dict:            
            
			# Check if the given value of the key already exists in the values dictionary
            if value != self.values_dict[key][len(self.values_dict[key])-1]:
                
				# Store values for the given key in the values dictionary
                self.values_dict[key].append(value)
                
				# Store the timestamp for the given key in the timestamp dictionary
                self.timestamps_dict[key].append(timestamp)
        else:
            
			# Store the value and key for the given key in the values dictionary
            self.values_dict[key] = [value]
            
			# Store the timestamp for the given key in the timestamp dictionary
            self.timestamps_dict[key] = [timestamp]
    # Find the index of right most occurrence of the given timestamp
    # using binary search
    def search_index(self, n, key, timestamp):
        left = 0
        j=right = n
        mid = 0
        while left < right:
            
			# It will return the mid of the current dictionary
            mid = (left+right) >> 1
            # Increase index value if required index is less than the
            # current index otherwise decrease it
            if self.timestamps_dict[key][mid] <= timestamp:
                left = mid + 1
            else:
                right = mid
        return left-1
    # Get time_stamp data variables
    def get_value(self, key, timestamp):
        
		# Check if the given key is present in the values dictionary
        if key not in self.values_dict:
            
			# Return empty string if item does not exist
            return ""
        else:
            
			# Find the right most occurrence of the given timestamp
            index = self.search_index(len(self.timestamps_dict[key]),
                                      key, timestamp)
            
			# If the timestamp exist in the timestamp dictionary, return the
            # value with that timestamp
            if index > -1:
                return self.values_dict[key][index]
            # return empty string if the timestamp does not exist
            return ""
# Driver code
def main():
    ts = TimeStamp()
    num = 1
    random_value = 0
    input = (
            ("course", "OOP", 3),
            ("course", "PF", 5),
            ("course", "OS", 7),
            ("course", "ALGO", 9),
            ("course", "DB", 10)
        )
    for i in input:
        print(num, ".\tAdd value: (", '"', i[0], '"',
                   ", ", '"', i[1], '"', ", ", i[2], ")", sep="")
        ts.set_value(i[0], i[1], i[2])
        random_value = random.randint(0, 10)
        print("\n\tGet value for:")
        print("\t\tKey = course  \n\t\tTimestamp = ", random_value, sep="")
        print("\n\tReturned value = ", '"',
              ts.get_value("course", random_value), '"', sep="")
        num += 1
        print("-" * 100, sep="")
if __name__ == "__main__":
    main()

Time-Based Key-Value Store

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

Pattern 2: Merge Intervals#

For problems involving meeting times or intervals of some nature, the Merge Intervals pattern is a powerful coding technique. 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

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

Pattern 3: 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

linked_list_node.py

linked_list.py

print_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):
            
            # Traversing 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 next coding pattern in the list.

Pattern 4: 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 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 = {}
    
    # Iterate over the array of numbers
    for i in range(len(arr)):
        
		# Calculate the difference between the current and target number
        difference = t - arr[i]
        
		# Check if the difference already exists in the hash map
        if difference in hashmap:
            
			# Return the indexes 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 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 examples illustrate the application of the Dynamic Programming pattern to efficiently solve these problems:

Longest Palindromic Substring#

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

Solution#

Looking 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

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

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. At each step, we reuse the previously computed maximum subarray sum 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

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 example illustrates the application of the Stacks pattern to efficiently solve the given coding problem:

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 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 explore the last, but certainly not the least, coding pattern from Oracle's list of frequently asked patterns.

Pattern 7: 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 the value of each element matches with its index in the array. Through a series of swaps, each element is shifted to its rightful position, guaranteeing a sorted array without needing additional space. This sorts the array differently than comparison-based algorithms like Quicksort or Merge Sort. To determine if a problem can be solved using the Cyclic Sort pattern, examine scenarios where the array consists of distinct numbers within a specific range. 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

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

To ace your Oracle 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 Oracle, 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 Oracle Interview: Must-Know Python Coding Problems

Pattern 1: Custom Data Structures#

Implement LRU Cache#

Solution#

Insert Delete GetRandom O(1)#

Solution#

Time-Based Key-Value Store#

Solution#

Pattern 2: Merge Intervals#

Meeting Rooms II#

Solution#

Pattern 3: K-Way Merge#

Merge K Sorted Lists#

Solution#

Pattern 4: Knowing What to Track#

Two Sum#

Solution#

Pattern 5: Dynamic Programming #

Longest Palindromic Substring#

Solution#

Maximum Subarray#

Solution#

Pattern 6: Stacks#

Valid Parentheses#

Solution#

Pattern 7: Cyclic Sort#

First Missing Positive#

Solution#