1. Intro to Natural Language Processing
題目整理
給定長度相同的正向句子 positive 與負向句子 negative，先收集所有句子的 unique words，按照字典序排列，並從 1 開始分配 token ID。接著把每句話轉成 ID sequence，再以 0 補齊到最長句子的 word count T。輸出 tensor shape 必須是 (2N, T)，而且 positive rows 全部在前、negative rows 全部在後，兩組內部皆維持原順序。
Embedding table 需要用整數 ID 查表；這題就是先定義 word token、建立 word → ID 映射，並把 variable-length sentences 整理成可進入 batch 的矩形 tensor。建議先完成 Word Embeddings ↗。
解法說明
把兩組輸入串成 sentences = positive + negative，這一步同時保證輸出 row order。用 set comprehension 收集所有 sentence.split() 的 word，再 sorted 建立 deterministic vocabulary；enumerate(..., start=1) 特別把 0 保留給 padding。每句轉成一維 float tensor 後，交給 pad_sequence(..., batch_first=True, padding_value=0) 一次補齊。
import torch
import torch.nn as nn
from torchtyping import TensorType
from typing import List
class Solution:
def get_dataset(
self,
positive: List[str],
negative: List[str],
) -> TensorType[float]:
sentences = positive + negative # Positive rows must come first.
if not sentences:
return torch.empty((0, 0), dtype=torch.float32)
vocabulary = sorted({
word
for sentence in sentences
for word in sentence.split()
})
word_to_id = {
word: token_id
for token_id, word in enumerate(vocabulary, start=1)
}
encoded = [
torch.tensor(
[word_to_id[word] for word in sentence.split()],
dtype=torch.float32,
)
for sentence in sentences
]
return nn.utils.rnn.pad_sequence(
encoded,
batch_first=True,
padding_value=0.0,
)Interview Explanation Flow
Step 1: Define the representation
"I will build one shared word-level vocabulary across both classes. Sorting the unique words makes token IDs deterministic, and I start IDs at 1 because 0 is reserved for padding."
Step 2: Preserve the required row order
"I concatenate positive + negative before encoding. That naturally places every positive sample first while preserving the original order within each list."
Step 3: Walk through the example
positive = ["Dogecoin to the moon"]
negative = ["I will short Tesla today"]
sorted vocabulary:
Dogecoin=1, I=2, Tesla=3, moon=4, short=5,
the=6, to=7, today=8, will=9
encoded positive -> [1, 7, 6, 4]
encoded negative -> [2, 9, 5, 3, 8]
pad_sequence(..., batch_first=True, padding_value=0)
-> [[1, 7, 6, 4, 0],
[2, 9, 5, 3, 8]]Step 4: Explain padding
"The sentences have different lengths, so pad_sequence writes a rectangular (2N, T) tensor. batch_first=True puts samples on axis 0, and padding ID 0 cannot collide with a real word because real IDs start at 1."
Step 5: Complexity
"Collecting and encoding words is linear in the input size, sorting costs O(V log V), and materializing the padded tensor costs O(2N·T)."
Possible follow-ups
- Case sensitivity? "I follow the prompt literally, so sorting is case-sensitive; if normalization were required, I would apply it before both vocab construction and encoding."
- Why return float? "The provided signature expects
TensorType[float], so I explicitly create float32 tensors even though the values represent token IDs."
中文：重點是共用 vocab、字典序從 1 編號、positive rows 在前，以及用 0 padding 成 (2N, T)。
額外題目：Bag of Words
完成官方 tokenization 題後，再實作 Bag of Words：把原始文字正規化、斷詞、建立 vocabulary，並把句子轉成 word-count vector。與官方題輸出的 token sequence 不同，BoW 的每個維度代表某個 word 的出現次數，因此會丟失詞序。
解法說明
preprocess 用 lower() 統一大小寫，再以正規表示式 [a-z0-9']+ 抓出 word。BagOfWords 從 corpus 收集排序後的 vocab 建 stoi；vectorize 掃過 token 並累加對應維度，沒看過的 word 直接忽略。
import re
from typing import Dict, List
def preprocess(text: str) -> List[str]:
text = text.lower()
return re.findall(r"[a-z0-9']+", text) # Words = maximal alnum runs.
class BagOfWords:
def __init__(self, corpus: List[str]):
vocab = sorted({tok for doc in corpus for tok in preprocess(doc)})
self.stoi: Dict[str, int] = {word: i for i, word in enumerate(vocab)}
def vectorize(self, text: str) -> List[int]:
vector = [0] * len(self.stoi)
for token in preprocess(text):
if token in self.stoi: # Ignore out-of-vocabulary words.
vector[self.stoi[token]] += 1
return vectorvectorize O(L)，L 是句子的 token 數。Extra Interview Flow · Bag of Words
Step 1: Contrast it with the official task
"The official tokenizer preserves word order as a sequence of token IDs. Bag of Words instead returns one fixed-size count vector whose dimensions correspond to vocabulary words."
corpus = ["The cat sat.", "The dog ran!"]
vocab = ["cat", "dog", "ran", "sat", "the"]
vectorize("the cat the")
-> [1, 0, 0, 0, 2]Step 2: State the limitation
"Because only counts remain, 'dog bites man' and 'man bites dog' produce the same vector. The representation is also sparse and grows with vocabulary size."
中文：官方題保留 token 順序；Bag of Words 只保留每個字的次數，因此更簡單但失去詞序。
額外延伸：Unicode-aware preprocessing
上面的 preprocess 只吃 ASCII：[a-z0-9'] 遇到 café、Zürich、北京、Москва 會把重音字、非拉丁字母切爛或丟掉。以下是不改動原題解、額外提供的 Unicode 版本；Python 3 的 \w 對 str pattern 預設就是 Unicode。
import re
import unicodedata
def preprocess_unicode(text: str) -> list:
text = unicodedata.normalize("NFC", text) # 1. Compose accents to canonical form.
text = text.casefold() # 2. Unicode-aware lowercasing.
# 3. Word = run of Unicode letters/digits (not underscore), keeping contractions.
return re.findall(r"[^\W_]+(?:['’][^\W_]+)*", text)三個步驟各修一個 Unicode 陷阱：
normalize("NFC")：é可能是單一 codepointU+00E9，也可能是e+ 結合重音U+0301；兩者外觀相同但是不同字串，會讓 vocab 對不上。NFC 先合成成同一種標準形式。casefold()取代lower()：casefold 是給「無視大小寫比對」用的正確版本。例如德文"Straße".casefold()→'strasse'、希臘文字尾 sigma 也處理正確，lower()都會漏。[^\W_]+(?:['’][^\W_]+)*：[^\W_]是「Unicode 詞字元但排除底線」（純\w會把_也算進去）；後面允許詞內單引號，且同時吃 ASCII'與真實文本常見的 Unicode 右單引號’（U+2019），讓it's/it’s都保持完整。
行為對比：
s = "Café Zürich — it's naïve. 北京 Москва don’t"
# 原題 ASCII 版
re.findall(r"[a-z0-9']+", s.lower())
-> ['caf', 'z', 'rich', "it's", 'na', 've', 'don'] # 重音與非拉丁字母被切爛
preprocess_unicode(s)
-> ['café', 'zürich', "it's", 'naïve', '北京', 'москва', 'don’t'] # 保持完整\w+ 會貪婪抓一整串詞字元，但中文／日文／泰文不用空白斷詞，所以 北京大学 會變成一個 token而不是 北京 + 大学。若真的需要 CJK 詞邊界，regex 不夠，得用斷詞器（中文 jieba、日文 fugashi / MeCab）；bag-of-words baseline 常見的便宜替代是對 CJK 改用字元級切分。