Guida a Strategia per colloqui di programmazione · 3/6
Per ora questo capitolo è disponibile solo in inglese.
This chapter implements the three most common interview patterns in Python: two pointers, hash maps and sliding windows. The sliding window gets a line-by-line walkthrough and is then ported to C++, Java and TypeScript.
Both pointers move in the same direction: read visits every element and write marks where the next kept value goes. Everything happens in place, so extra space is O(1).
def dedupe_sorted(nums: list[int]) -> int:
"""Dedupe sorted nums in place; return the new length."""
write = 0
for read in range(len(nums)):
if read == 0 or nums[read] != nums[read - 1]:
nums[write] = nums[read]
write += 1
return write
data = [1, 1, 2, 3, 3, 3, 5]
count = dedupe_sorted(data)
print(count, data[:count]) # 4 [1, 2, 3, 5]In an unsorted array, find the indices of two elements that add up to the target. For the current value x the partner is target - x, so storing the index of every value seen so far lets one pass find the answer. Sorting would lose the original indices, so a hash map fits better than two pointers here.
def pair_indices(nums: list[int], target: int) -> tuple[int, int] | None:
index_of: dict[int, int] = {}
for i, x in enumerate(nums):
need = target - x
if need in index_of:
return index_of[need], i
index_of[x] = i # insert after the check so x never pairs with itself
return None
print(pair_indices([8, 3, 5, 11, 2], 13)) # (0, 2)
print(pair_indices([1, 2], 10)) # NoneFind the length of the longest substring with no repeated character. Grow right one step at a time while keeping the invariant that the window [left, right] has no repeats.
def longest_unique_window(s: str) -> int:
last_seen: dict[str, int] = {} # character -> last index where it appeared
left = best = 0
for right, ch in enumerate(s):
if last_seen.get(ch, -1) >= left:
left = last_seen[ch] + 1 # jump past the repeat inside the window
last_seen[ch] = right
best = max(best, right - left + 1)
return best
for text in ["tastedev", "aaaa", "interview", ""]:
print(repr(text), longest_unique_window(text))
# 'tastedev' 5 / 'aaaa' 1 / 'interview' 6 / '' 0Line by line:
last_seen stores the last index of each character, so the left edge can jump in one step instead of deleting characters one by one.last_seen.get(ch, -1) >= left means "this character is already inside the window". Positions left of the window must be ignored, hence the comparison with .leftleft moves just past the earlier occurrence. It only moves forward, so at most n times in total.right - left + 1 updates the best answer.Time is O(n) and space is O(min(n, σ)), where σ is the number of distinct characters. A classic bug is dropping the comparison with left, which lets the left edge move backwards on "abba"; the correct answer there is 2.
An std::unordered_map holds the positions; cast the size_t length explicitly.
#include <algorithm>
#include <iostream>
#include <string>
#include <unordered_map>
int longestUniqueWindow(const std::string& s) {
std::unordered_map<char, int> lastSeen;
int left = 0, best = 0;
for (int right = 0; right < static_cast<int>(s.size()); ++right) {
auto it = lastSeen.find(s[right]);
if (it != lastSeen.end() && it->second >= left) {
left = it->second + 1;
}
lastSeen[s[right]] = right;
best = std::max(best, right - left + 1);
}
return best;
}
int main() {
std::cout << longestUniqueWindow("tastedev") << '\n'; // 5
std::cout << longestUniqueWindow("abba") << '\n'; // 2
}HashMap.get can return null, so read it into an Integer and check.
import java.util.HashMap;
import java.util.Map;
public class LongestUniqueWindow {
static int longestUniqueWindow(String s) {
Map<Character, Integer> lastSeen = new HashMap<>();
int left = 0, best = 0;
for (int right = 0; right < s.length(); right++) {
char ch = s.charAt(right);
Integer prev = lastSeen.get(ch);
if (prev != null && prev >= left) {
left = prev + 1;
}
lastSeen.put(ch, right);
best = Math.max(best, right - left + 1);
}
return best;
}
public static void main(String[] args) {
System.out.println(longestUniqueWindow("tastedev")); // 5
System.out.println(longestUniqueWindow("abba")); // 2
}
}Array.from(s) keeps two-code-unit characters such as emoji whole.
function longestUniqueWindow(s: string): number {
const lastSeen = new Map<string, number>();
const chars = Array.from(s);
let left = 0;
let best = 0;
for (let right = 0; right < chars.length; right++) {
const prev = lastSeen.get(chars[right]);
if (prev !== undefined && prev >= left) left = prev + 1;
lastSeen.set(chars[right], right);
best = Math.max(best, right - left + 1);
}
return best;
}
console.log(longestUniqueWindow("tastedev")); // 5
console.log(longestUniqueWindow("abba")); // 2C++ char and Java charAt work on bytes and UTF-16 code units; mention this for non-ASCII input. For lowercase or ASCII input, an array of size 26 or 128 can replace the map.
Two pointers suit sorted data and in-place cleanup, hash maps answer "have I seen this value?", and sliding windows find the best contiguous range. In each, decide which invariant the loop keeps and make sure the pointers only move forward. Across languages only the hash map API and the notion of a character change.
0 commenti
Accedi · Accedi per lasciare un commento.