home > research > flashcards > daily-coding-problem-wu-miller-drill (2024-09-05)

Daily Coding Problem Solutions: Two Sum, Binary Tree Level Order Traversal, LRU Cache, and Trie

Daily Coding Problem Solutions: Two Sum, Binary Tree Level Order Traversal, LRU Cache, and Trie

Table of Contents

Daily Coding Problem: Get exceptionally good at coding interviews by solving one problem every day - Drill Questions

Two Sum Problem   drill daily_coding_problem_wu_miller

Explain the "Two Sum" problem and provide an efficient solution.

Answer

The "Two Sum" problem asks to find two numbers in an array that add up to a target sum. An efficient solution uses a hash table:

  1. Create an empty hash table.
  2. Iterate through the array.
  3. For each element x, calculate the complement (target - x).
  4. If the complement exists in the hash table, return the pair.
  5. If not, add x to the hash table.
  6. If no solution is found, return an indication that no such pair exists.

This approach has O(n) time complexity and O(n) space complexity. 

def two_sum(nums, target):
    seen = {}
    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:
            return [seen[complement], i]
        seen[num] = i
    return []  # No solution found

# Example usage
print(two_sum([2, 7, 11, 15], 9))  # Output: [0, 1]

Binary Tree Level Order Traversal   drill daily_coding_problem_wu_miller

Describe the process of performing a level order traversal on a binary tree and implement it.

Answer

Level order traversal of a binary tree visits nodes level by level, from left to right. The process is:

  1. Start with the root node.
  2. Use a queue to keep track of nodes at each level.

  3. While the queue is not empty: a. Get the size of the queue (number of nodes at current level). b. Process all nodes at this level:

    • Remove node from queue front.
    • Add its value to current level's result.
    • Enqueue its left and right children (if they exist).

    c. Move to the next level.

Here's an implementation in Python: 

from collections import deque

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def levelOrder(root):
    if not root:
        return []
    
    result = []
    queue = deque([root])
    
    while queue:
        level_size = len(queue)
        current_level = []
        
        for _ in range(level_size):
            node = queue.popleft()
            current_level.append(node.val)
            
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        
        result.append(current_level)
    
    return result

# Example usage
root = TreeNode(3)
root.left = TreeNode(9)
root.right = TreeNode(20)
root.right.left = TreeNode(15)
root.right.right = TreeNode(7)

print(levelOrder(root))  # Output: [[3], [9, 20], [15, 7]]

This solution has a time complexity of O(n) and a space complexity of O(w), where n is the number of nodes and w is the maximum width of the tree.

Implement LRU Cache   drill daily_coding_problem_wu_miller

Explain the concept of an LRU (Least Recently Used) Cache and implement it with O(1) time complexity for both get and put operations.

Answer

An LRU Cache is a data structure that stores a limited number of items, discarding the least recently used item when it reaches capacity. The key features are:

  1. Fixed capacity
  2. Fast access (O(1) for get and put)
  3. Tracks of order of use

To implement an LRU Cache with O(1) operations:

  1. Use a hash map for fast key-value lookups
  2. Use a doubly linked list to maintain order of use
  3. Move accessed items to the front of the list
  4. Remove items from the back when at capacity

Here's a Python implementation: 

class Node:
    def __init__(self, key, val):
        self.key = key
        self.val = val
        self.prev = None
        self.next = None

class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.cache = {}
        self.head = Node(0, 0)
        self.tail = Node(0, 0)
        self.head.next = self.tail
        self.tail.prev = self.head

    def _add_node(self, node):
        node.prev = self.head
        node.next = self.head.next
        self.head.next.prev = node
        self.head.next = node

    def _remove_node(self, node):
        prev = node.prev
        new = node.next
        prev.next = new
        new.prev = prev

    def _move_to_head(self, node):
        self._remove_node(node)
        self._add_node(node)

    def get(self, key):
        if key in self.cache:
            node = self.cache[key]
            self._move_to_head(node)
            return node.val
        return -1

    def put(self, key, value):
        if key in self.cache:
            node = self.cache[key]
            node.val = value
            self._move_to_head(node)
        else:
            node = Node(key, value)
            self.cache[key] = node
            self._add_node(node)
            if len(self.cache) > self.capacity:
                lru = self.tail.prev
                self._remove_node(lru)
                del self.cache[lru.key]

# Example usage
cache = LRUCache(2)
cache.put(1, 1)
cache.put(2, 2)
print(cache.get(1))       # returns 1
cache.put(3, 3)           # evicts key 2
print(cache.get(2))       # returns -1 (not found)
cache.put(4, 4)           # evicts key 1
print(cache.get(1))       # returns -1 (not found)
print(cache.get(3))       # returns 3
print(cache.get(4))       # returns 4

This implementation ensures O(1) time complexity for both get and put operations.

Implement Trie (Prefix Tree)   drill daily_coding_problem_wu_miller

Describe the structure of a Trie (Prefix Tree) and implement its basic operations: insert, search, and startsWith.

Answer

A Trie, or Prefix Tree, is a tree-like data structure used to store and retrieve strings efficiently. It's particularly useful for prefix-based operations. The key features are:

  1. Each node represents a character in a string
  2. The root represents an empty string
  3. Each path from root to a node forms a prefix
  4. Nodes can have a boolean flag to mark the end of a word

Basic operations:

  1. Insert: Add a word to the trie
  2. Search: Check if a word exists in the trie
  3. StartsWith: Check if any word in the trie starts with a given prefix

Here's a Python implementation: 

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end = True

    def search(self, word):
        node = self._find_prefix(word)
        return node is not None and node.is_end

    def startsWith(self, prefix):
        return self._find_prefix(prefix) is not None

    def _find_prefix(self, prefix):
        node = self.root
        for char in prefix:
            if char not in node.children:
                return None
            node = node.children[char]
        return node

# Example usage
trie = Trie()
trie.insert("apple")
print(trie.search("apple"))      # returns True
print(trie.search("app"))        # returns False
print(trie.startsWith("app"))    # returns True
trie.insert("app")
print(trie.search("app"))        # returns True

This implementation provides efficient operations:

  • Insert: O(m) time complexity, where m is the length of the word
  • Search: O(m) time complexity
  • StartsWith: O(m) time complexity

The space complexity is O(n*m), where n is the number of words and m is the average length of words.

Author: Jason Walsh

j@wal.sh

Last Updated: 2024-09-05 15:06:08