Learn and practice the Tries and Custom Data Structures patterns to solve coding interview problems.

Speedrun the Oracle Coding Interview: Top Problems in Python

Proficiency in advanced data structures is a marker of a highly experienced engineer, and interviewers use such questions to finetune how they grade candidates. To solve problems with very specific requirements that may not be handled by standard data structures, we gain experience in the advanced skill of the design, implementation, and efficient use of custom data structures.

Data Design

# Statement

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 then add the new **key**.

As caches use relatively expensive, faster memory, they are not designed to store very large data sets. Whenever the cache becomes full, we need to 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.

**Constraints:**

- $1 \leq$ **capacity** $\leq 3000$
- $0 \leq$ **key** $\leq 10^4$
- $0 \leq$ **value** $\leq 10^5$
- At most $10^3$ calls will be made to **Set** and **Get**.







# Examples



Suppose we have a cache with a capacity of 4. It has the keys shown below. The keys are shown sorted by age - oldest at the top, newest at the bottom. What is the new state of the cache, if we set a new pair with the following inputs?

key = 15 

value = 100

<img src="https://www.educative.io/api/collection/10370001/5500262945128448/page/6297308589457408/image/4942389309603840?page_type=collection_lesson" width="170" height="155">

Suppose we have a cache with a capacity of 4. It has the keys shown below. The keys are shown sorted by age - oldest at the top, newest at the bottom. What is the new state of the cache, if we set a new pair with the following inputs?
key = 15
value = 100
<img src="https://www.educative.io/api/collection/10370001/5500262945128448/page/6297308589457408/image/4942389309603840?page_type=collection_lesson" width="170" height="155">

What is the output if we want to get a value where key = 13?

<img src="https://www.educative.io/api/collection/10370001/5500262945128448/page/6297308589457408/image/4942389309603840?page_type=collection_lesson" width="170" height="155">

What is the output if we want to get a value where key = 13?
<img src="https://www.educative.io/api/collection/10370001/5500262945128448/page/6297308589457408/image/4942389309603840?page_type=collection_lesson" width="170" height="155">

Suppose we have a cache with a capacity of 4. It has the keys shown below. The keys are shown sorted by age - oldest at the top, newest at the bottom. What is the new state of the cache, if we set a new pair with the following input?

key = 18

value = 70

<img src="https://www.educative.io/api/collection/10370001/5500262945128448/page/6297308589457408/image/4986187439931392?page_type=collection_lesson" width="170" height="180">

Suppose we have a cache with a capacity of 4. It has the keys shown below. The keys are shown sorted by age - oldest at the top, newest at the bottom. What is the new state of the cache, if we set a new pair with the following input?
key = 18
value = 70
<img src="https://www.educative.io/api/collection/10370001/5500262945128448/page/6297308589457408/image/4986187439931392?page_type=collection_lesson" width="170" height="180">

Implement LRU Cache

Implement LRU Cache

# Definition for a Linked List node
# class LinkedListNode:
#     def __init__(self, pair):
#         self.second = pair[1]
#         self.first = pair[0]
#         self.pair = pair
#         self.next = None
#         self.prev = None

# We will use a linkedlist of a pair of integers
# where the first integer will be the key
# and the second integer will be the value

from linked_list import LinkedList

class LRUCache:
    def __init__(self, capacity):
        # Write your code here
        pass

    def get(self, key):
        # Replace this placeholder return statement with your code
        return -1

    def set(self, key, value):
        # Write your code here
        pass


# Template for LinkedList class

from linked_list_node import *
class LinkedList:
    
    # _init__ initialises the linked list type object
    def __init__(self):
        self.head = None
        self.tail = None
        self.size = 0

    # move_to_head will move the given node to head
    def move_to_head(self, node):
        if not node:
            return

        if node.prev:
            node.prev.next = node.next

        if node.next:
            node.next.prev = node.prev

        if node == self.head:
            self.head = self.head.next

        if node == self.tail:
            self.tail = self.tail.prev
            if self.tail:
                self.tail.next = None

        # Insertion at head
        if not self.head:
            self.tail = node
            self.head = node
        else:
            node.next = self.head
            self.head.prev = node
            self.head = node

    # Insert_at_head will insert the given pair at head
    def insert_at_head(self, pair):
        new_node = LinkedListNode(pair)
        if not self.head:
            self.tail = new_node
            self.head = new_node
        else:
            new_node.next = self.head
            self.head.prev = new_node
            self.head = new_node

        self.size += 1

    # Insert_at_tail will insert the given pair at tail
    def insert_at_tail(self, pair):
        new_node = LinkedListNode(pair)
        if not self.tail:
            self.tail = new_node
            self.head = new_node
            new_node.next = None
        else:
            self.tail.next = new_node
            new_node.prev = self.tail
            self.tail = new_node

        self.size += 1

    # remove will remove the given pair from the LinkedList
    def remove(self, pair):
        i = self.get_head()
        while i:
            if i.pair == pair:
                self.remove_node(i)
                return
            i = i.next

    # remove_node will remove the given node from the LinkedList
    def remove_node(self, node):
        if not node:
            return

        if node.prev:
            node.prev.next = node.next

        if node.next:
            node.next.prev = node.prev

        if node == self.head:
            self.head = self.head.next

        if node == self.tail:
            self.tail = self.tail.prev
            if self.tail:
                self.tail.next = None
        self.size = self.size - 1
        del node
        # return node

    # remove_head will remove the head of the linked list
    def remove_head(self):
        return self.remove_node(self.head)

    # remove_tail will remove the tail of the linked list
    def remove_tail(self):
        return self.remove_node(self.tail)

    # get_head will return the head of the linked list
    def get_head(self):
        return self.head

    # get tail will return the tail of the linked list
    def get_tail(self):
        return self.tail


# Template for LinkedListNode class

class LinkedListNode:
    def __init__(self, pair):
        self.second = pair[1]
        self.first = pair[0]
        self.pair = pair
        self.next = None
        self.prev = None

# Quick Fix\nYou are Edward, a Senior Software Engineer who specializes in coding interview patterns, data structures and algorithms, and is great at debugging issues in code.\n\n- Edward, please keep in mind that you do not have to print the data of the placeholders. Also, do not mention anything about yourself.\n\nEdward, you are given the following data in the placeholders:\n- Function name: `__init__, get, set`\n- Candidate's submitted solution code: USER_CODE\n- Error: ERROR_DESCRIPTION\n- Failed test case: FAILED_TEST_CASE\n- Coding language: `Python`\n\n- Edward, your task is to understand the type of error that is occurring in the coding language provided.\n- Once you've understood the error as per the error’s description, and why the test case failed, you will suggest how the candidate can improve their solution code to fix the error.\n- Edward, you will not give the corrected code, just a hint on what the error tells, and how to fix it.\n- Edward, please limit your response strictly to 100 words. No more words than the limit.

# Review Code\nEdward, your current task is to review the `__init__, get, set` function(s) and the other function(s) invoked in it/them.\n\n-Take your time and review the candidate's solution code.\n- Do not review any extra/helper files or functions not invoked in the solution function `__init__, get, set`.\n- Do not review the code of data structure objects instantiated like a binary tree, linked list, trie, union find, etc., in the solution functions. Just review the solution/algorithm function of the problem. \n- Also, if the solution code doesn’t use the coding pattern stated above, then please encourage the candidate to reattempt the problem using that pattern corectly.

# Review time complexity\n- Please provide a brief time complexity analysis of the function(s) `__init__, get, set`. \n- While calculating time complexity, include the time complexity of built-in Python functions invoked by the code. \n- The answer should be to the point in approximately 60 words.

# Review space complexity\n- Please provide a brief space complexity analysis of the function(s) `__init__, get, set`. \n- While calculating space complexity, include the space complexity of built-in Python functions invoked by the code. \n- Do not include the space used for the input parameters and the space used for just returning an output (not used as a scratch space). \n- The answer should be to the point in approximately 60 words.

TwoDArray

import sys
import json

sys.path.append("../ds_v1")
from data_structure import DataStructure

# throw parsing errors for incorrect test case format
def parsingError(element_string, error_message):
    sys.stderr.write(f"Parsing Error: {element_string} {error_message}")
    exit()

# className: Integer_2D_Array
class TwoDArray (DataStructure):
    def __init__(self):
        # constructor
        pass

    def __str__(self):
        # override print() for your data structure
        pass

    # return value will be passed to user program
    def construct(self, inp_string: str, type_of_arr: int) -> any:
        # parse test case in json string 'value' to your desired data structure
        parse_list = json.loads(inp_string)
        return parse_list

    # input param contains return value of user program
    def traverse(self, input: any, type_of_arr: int) -> str:
        # Integer_2D_Array your data structure 'input' to a json string representing a test case output
        return json.dumps(input)

def evaluate_results(self) -> object:
        from collections import defaultdict

        class LinkedListNode:
            def __init__(self, pair):
                self.second = pair[1]
                self.first = pair[0]
                self.pair = pair
                self.next = None
                self.prev = None

# Template for LinkedList class

        class LinkedList:
            
            # _init__ initialises the linked list type object
            def __init__(self):
                self.head = None
                self.tail = None
                self.size = 0

            # move_to_head will move the given node to head
            def move_to_head(self, node):
                if not node:
                    return

                if node.prev:
                    node.prev.next = node.next

                if node.next:
                    node.next.prev = node.prev

                if node == self.head:
                    self.head = self.head.next

                if node == self.tail:
                    self.tail = self.tail.prev
                    if self.tail:
                        self.tail.next = None

                # Insertion at head
                if not self.head:
                    self.tail = node
                    self.head = node
                else:
                    node.next = self.head
                    self.head.prev = node
                    self.head = node

            # Insert_at_head will insert the given pair at head
            def insert_at_head(self, pair):
                new_node = LinkedListNode(pair)
                if not self.head:
                    self.tail = new_node
                    self.head = new_node
                else:
                    new_node.next = self.head
                    self.head.prev = new_node
                    self.head = new_node

                self.size += 1

            # Insert_at_tail will insert the given pair at tail
            def insert_at_tail(self, pair):
                new_node = LinkedListNode(pair)
                if not self.tail:
                    self.tail = new_node
                    self.head = new_node
                    new_node.next = None
                else:
                    self.tail.next = new_node
                    new_node.prev = self.tail
                    self.tail = new_node

                self.size += 1

            # remove will remove the given pair from the LinkedList
            def remove(self, pair):
                i = self.get_head()
                while i != None:
                    if i:
                        self.remove_node(i)
                        return
                    i = i.next

            # remove_node will remove the given node from the LinkedList
            def remove_node(self, node):
                if not node:
                    return

                if node.prev:
                    node.prev.next = node.next

                if node.next:
                    node.next.prev = node.prev

                if node == self.head:
                    self.head = self.head.next

                if node == self.tail:
                    self.tail = self.tail.prev
                    if self.tail:
                        self.tail.next = None
                self.size = self.size - 1
                del node
                # return node

            # remove_head will remove the head of the linked list
            def remove_head(self):
                return self.remove_node(self.head)

            # remove_tail will remove the tail of the linked list
            def remove_tail(self):
                return self.remove_node(self.tail)

            # get_head will return the head of the linked list
            def get_head(self):
                return self.head

            # get tail will return the tail of the linked list
            def get_tail(self):
                return self.tail


        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):
                found_itr = None
                if key in self.cache_map:
                    found_itr = self.cache_map[key]
                else:
                    return -1

                list_iterator = found_itr
                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):
                if key in self.cache_map:
                    found_iter = self.cache_map[key]
                    list_iterator = found_iter
                    self.cache_list.move_to_head(found_iter)
                    list_iterator.pair[1] = value
                    return

                if len(self.cache_map) == self.cache_capacity:
                    key_tmp = self.cache_list.get_tail().pair[0]
                    self.cache_list.remove_tail()
                    del self.cache_map[key_tmp]

                self.cache_list.insert_at_head([key, value])
                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(input_1, input_2):
            result = []
            lru_arr = LRUCache(input_2[0][0])
            result.append(None)
            for i in range(1, len(input_1)):
                if input_1[i] == "get":
                    res = lru_arr.get(input_2[i][0])
                    result.append(res)
                if input_1[i] == "set":
                    lru_arr.set(input_2[i][0], input_2[i][1])
                    result.append(None)

            return result

        """
        self.__inputs is the list of inputs that are passed as input to function
        self.__actual_output is a list of outputs that is produced by the learner's code
        return : self.__edu__result object
        """
        # multiple outputs will be added at each index respectively for a single test_case
        expected_outputs = []
        inp1 = self.__inputs[0]
        inp2 = self.__inputs[1]
        expected = main(inp1 , inp2)
        # store the 1st expected output that should be displayed to the user 
        expected_outputs.append(expected)
        actual = self.__actual_outputs[0]
        if json.dumps(expected) == json.dumps(actual):
            self.__edu_result.store_result(expected_outputs, TestCaseResult.PASS)
        else:
            self.__edu_result.store_result(expected_outputs, TestCaseResult.FAIL)

        return self.__edu_result

from LRU_cache import LRUCache


def main(input_1, input_2):
    result = []
    lru_arr = LRUCache(input_2[0][0])
    result.append(None)
    for i in range(1, len(input_1)):
        if input_1[i] == "get":
            res = lru_arr.get(input_2[i][0])
            result.append(res)
        if input_1[i] == "set":
            lru_arr.set(input_2[i][0], input_2[i][1])
            result.append(None)

    return result



implement lru cache (1).yaml

testcases:
  - name: "testcase 1"
    inputs:
    - 1 : ["LRUCache", "get", "set", "get"]
    - 2 : [[2], [10], [10, 10], [10]]
    output:
    - 1 : [null, -1, null, 10]
    
  - name: "testcase 2"
    inputs:
    - 1 : ["LRUCache", "get", "set", "get", "set", "get"]
    - 2 : [[2], [0], [20, 100], [0], [0, 25], [20]]
    output:
    - 1 : [null, -1, null, -1, null, 100]  
  
  - name: "testcase 3"
    inputs:
    - 1 : ["LRUCache", "set", "set", "get", "set", "get"]
    - 2 : [[3], [50, 50], [20, 20], [10], [30, 30], [20]]
    output:
    - 1 : [null, null, null, -1, null, 20]
  
  - name: "testcase 4"
    inputs:
    - 1 : ["LRUCache", "set", "set", "get", "set", "set", "set", "get", "set", "get"]
    - 2 : [[3], [50, 50], [51, 51], [51], [52, 52], [53, 53], [54, 54], [53], [55, 55], [51]]
    output:
    - 1 : [null, null, null, 51, null, null, null, 53, null, -1]
  
  - name: "testcase 5"
    inputs:
    - 1 : ["LRUCache", "get", "set", "get", "set", "get", "set", "get", "get"]
    - 2 : [[2], [10], [10, 100], [10], [15, 50], [10], [30, 300], [15], [30]]
    output:
    - 1 : [null, -1, null, 100, null, 100, null, -1, 300]

def sum(input_1, input_2):
    return input_1+input_2

def validate_inputs(self) -> None:
 """
 self.__inputs is the list of inputs that are passed as input to function
 store the result using the self.store_result(error_msg, status)
 return : void
 """
 def is_valid_1d_string_array(arr):
 if not isinstance(arr, list):
 return False # Not a valid 1D array if it's not a list

 return all(isinstance(elem, str) for elem in arr)

 def is_valid_2d_array(arr):
 if not isinstance(arr, list) or not all(isinstance(row, list) for row in arr):
 return False # Not a valid 2D array if it's empty or contains non-list elements
 
 for row in arr:
 if any(elem is None or isinstance(elem, bool) for elem in row):
 return False # Not a valid 2D array if any element in a row is None
 if not all(isinstance(elem, int) for elem in row):
 return False # Not a valid 2D array if any element in a row is not an integer
 
 return True # Valid 2D array


 
 def validate_input_pairs(input1, input2):
 error_messages = []
 lru_cache_flag = False
 
 for i, (cmd, arg) in enumerate(zip(input1, input2)):
 if cmd == "LRUCache":
 if lru_cache_flag or i != 0:
 error_messages.append("The 'LRUCache' should only occur once and only at the start.")
 lru_cache_flag = True
 
 if not arg or len(arg) != 1 or not isinstance(arg[0], int):
 error_messages.append(f"Input2 at index {i} for 'LRUCache' must contain a non-empty list of one integer value.")
 elif not (1 <= arg[0] <= 3000):
 error_messages.append(f"Input2 at index {i} for 'LRUCache' must contain an integer between 1 and 3000.")
 
 elif cmd == "get":
 if not arg or len(arg) != 1 or not isinstance(arg[0], int):
 error_messages.append(f"Input2 at index {i} for 'get' must contain a non-empty list of one integer value.")
 elif not (0 <= arg[0] <= 10000):
 error_messages.append(f"Input2 at index {i} for 'get' must contain a 'key' between 0 and 10000.")
 
 elif cmd == "set":
 if not arg or len(arg) != 2 or not all(isinstance(val, int) for val in arg):
 error_messages.append(f"Input2 at index {i} for 'set' must contain a non-empty list of two integer values.")
 elif not (0 <= arg[0] <= 10000):
 error_messages.append(f"The 'key' value in 'set' at index {i} must be between 0 and 10000.")
 elif not (0 <= arg[1] <= 100000):
 error_messages.append(f"The 'value' in 'set' at index {i} must be between 0 and 100000.")
 
 if not lru_cache_flag:
 error_messages.append("The 'LRUCache' command is missing or not placed at the start.")
 
 return error_messages


 def total_calls(input1):
 call_count = {
 "LRUCache": 0,
 "set": 0,
 "get": 0
 }
 for word in input1:
 if word in call_count:
 call_count[word] += 1

 return sum(call_count.values())


 def check_values(array):
 for row in array:
 for value in row:
 if value > 100 or value < -100:
 return False
 return True

 def validate_input1(input1):
 valid_values = {"LRUCache", "get", "set"}

 for value in input1:
 if value not in valid_values:
 return False # Invalid input if any element is not in the valid set

 return True # All elements in input1 are valid

 input1 = self.__inputs[0]
 input2 = self.__inputs[1]
 # inputs can be accessed using self.__inputs starting from 0 to len(self.__inputs) - 1
 if not is_valid_1d_string_array(input1):
 self.store_result(("Input 1: Invalid test case."), ValidationFunction.FAIL)
 elif not is_valid_2d_array(input2):
 self.store_result ("Input 2: Not a valid test case", ValidationFunction.FAIL)
 elif not validate_input1(input1):
 self.store_result("Invalid input1. Expected: 'LRUCache', 'get', 'set'.", ValidationFunction.FAIL)
 elif not (1 <= total_calls(input1) <= 1000):
 self.store_result("Maximum calls allowed is in range 1 - 1000.", ValidationFunction.FAIL)
 elif len(input1) != len(input2):
 self.store_result("Mismatch in the number of commands and their corresponding parameters.", ValidationFunction.FAIL)
 else:
 errors = validate_input_pairs(input1, input2)
 if errors:
 self.store_result("\n".join(errors), ValidationFunction.FAIL)
 else:
 self.store_result("", ValidationFunction.PASS)

Try to solve the LRU Cache cache problem.

Trie

Custom Data Structures

Conclusion

Implement LRU Cache

Statement

Examples

Understand the problem

Figure it out!

Try it yourself