day09面试题

**Day09 面试题**

### 一、算法题#### 题目1:两数之和给定一个整数数组 `nums` 和一个目标值 `target`，找出两个数字，使得它们的和等于 `target`。返回这两个数字所对应的下标。

**示例1:**

输入：`nums = [2,7,11,15]`, `target =9`

输出：`[0,1]`

解释：因为 `nums[0] + nums[1] ==9`，所以返回 `[0,1]`。

**示例2:**

输入：`nums = [3,2,4]`, `target =6`

输出：`[1,2]`

解释：因为 `nums[1] + nums[2] ==6`，所以返回 `[1,2]`。

**示例3:**

输入：`nums = [3,3]`, `target =6`

输出：`[0,1]`

解释：因为 `nums[0] + nums[1] ==6`，所以返回 `[0,1]`。

def twoSum(nums, target):
 """
 Given an array of integers and a target value,
 find the two numbers that add up to the target.

 Args:
 nums (list): A list of integers.
 target (int): The target value.

 Returns:
 list: A list containing the indices of the two numbers.
 """
 num_dict = {} # Create an empty dictionary to store the numbers and their indices for i, num in enumerate(nums):
 # For each number in the array, check if its complement (target - num) is in the dictionary if target - num in num_dict:
 # If it is, return the current index and the index of the complement return [num_dict[target - num], i]
 # Otherwise, add the current number and its index to the dictionary num_dict[num] = i # If no solution is found, return an empty list return []

#### 题目2:最长公共子序列给定两个字符串 `s1` 和 `s2`，找到它们的最长公共子序列。

**示例1:**

输入：`s1 = "abcde"`, `s2 = "ace"`

输出：`"ace"`

解释：因为 `"ace"` 是 `s1` 和 `s2` 的最长公共子序列。

def longestCommonSubsequence(s1, s2):
 """
 Given two strings, find their longest common subsequence.

 Args:
 s1 (str): The first string.
 s2 (str): The second string.

 Returns:
 str: The longest common subsequence.
 """
 m, n = len(s1), len(s2) # Get the lengths of the two strings dp = [[0] * (n +1) for _ in range(m +1)] # Create a2D array to store the lengths of common subsequences for i in range(1, m +1):
 for j in range(1, n +1):
 if s1[i -1] == s2[j -1]:
 # If the current characters are equal, update the length of the common subsequence dp[i][j] = dp[i -1][j -1] +1 else:
 # Otherwise, take the maximum length from the previous row or column dp[i][j] = max(dp[i -1][j], dp[i][j -1])

 # Reconstruct the longest common subsequence from the2D array lcs = []
 i, j = m, n while i >0 and j >0:
 if s1[i -1] == s2[j -1]:
 lcs.append(s1[i -1])
 i -=1 j -=1 elif dp[i -1][j] > dp[i][j -1]:
 i -=1 else:
 j -=1 return "".join(reversed(lcs))

### 二、设计题#### 题目1:设计一个缓存系统设计一个缓存系统，能够存储和检索整数值。该系统应该支持以下操作：

* `put(int key, int value)`：将给定的键值对添加到缓存中。
* `get(int key)`：返回给定键的值，如果不存在，则返回 `-1`。

**示例1:**

输入：`["put","get"]`
输出：`[null,-1]`

解释：首先，调用 `put(1,1)` 将 (1,1) 添加到缓存中。然后，调用 `get(1)` 返回1，因为它存在于缓存中。

**示例2:**

输入：`["put","get","put","get"]`
输出：`[null,1,null,-1]`

解释：首先，调用 `put(1,1)` 将 (1,1) 添加到缓存中。然后，调用 `get(1)` 返回1，因为它存在于缓存中。接着，调用 `put(2,2)` 将 (2,2) 添加到缓存中。最后，调用 `get(1)` 返回 -1，因为它不存在于缓存中。

class Node:
 def __init__(self):
 self.key = None self.value = None self.prev = None self.next = Noneclass LRUCache:
 def __init__(self, capacity: int):
 """
 Initialize the LRU Cache.

 Args:
 capacity (int): The maximum size of the cache.
 """
 self.capacity = capacity self.cache = {}
 self.head = Node()
 self.tail = Node()

 # Connect the head and tail nodes self.head.next = self.tail self.tail.prev = self.head def put(self, key: int, value: int) -> None:
 """
 Add a new key-value pair to the cache.

 Args:
 key (int): The key.
 value (int): The value.
 """
 if key in self.cache:
 # If the key already exists, remove it from its current position node = self.cache[key]
 self._remove(node)

 # Create a new node for the key-value pair node = Node()
 node.key = key node.value = value # Add the new node to the end of the cache self._add(node)
 self.cache[key] = node def get(self, key: int) -> int:
 """
 Retrieve a value from the cache.

 Args:
 key (int): The key.

 Returns:
 int: The value if it exists in the cache; otherwise, -1.
 """
 if key in self.cache:
 # If the key exists, move its node to the end of the cache node = self.cache[key]
 self._remove(node)
 self._add(node)
 return node.value return -1 def _remove(self, node: Node) -> None:
 """
 Remove a node from the cache.

 Args:
 node (Node): The node to remove.
 """
 prev_node = node.prev next_node = node.next # Update the pointers of the adjacent nodes prev_node.next = next_node next_node.prev = prev_node def _add(self, node: Node) -> None:
 """
 Add a node to the end of the cache.

 Args:
 node (Node): The node to add.
 """
 prev_node = self.tail.prev prev_node.next = node node.prev = prev_node node.next = self.tail# Example usage:
cache = LRUCache(2)
cache.put(1,1)
print(cache.get(1)) # Output:1cache.put(2,2)
print(cache.get(1)) # Output: -1

### 三、系统设计题#### 题目1:设计一个分布式缓存系统设计一个分布式缓存系统，能够存储和检索整数值。该系统应该支持以下操作：

* `put(int key, int value)`：将给定的键值对添加到缓存中。
* `get(int key)`：返回给定键的值，如果不存在，则返回 `-1`。

**示例1:**

输入：`["put","get"]`
输出：`[null,-1]`

解释：首先，调用 `put(1,1)` 将 (1,1) 添加到缓存中。然后，调用 `get(1)` 返回1，因为它存在于缓存中。

**示例2:**

输入：`["put","get","put","get"]`
输出：`[null,1,null,-1]`

解释：首先，调用 `put(1,1)` 将 (1,1