Dil

Mülakatlar için TypeScript

Deyimler, koleksiyonlar, ListNode/TreeNode ve şablonların gerçekten çalıştırdığı heap. Node 24.

Sitenin şablonları TypeScript’tir ve JavaScript number olarak çalışır. CI’daki Node 24. Aşağıdaki her çit, silinebilir TypeScript’ten bir betiktir: node --experimental-strip-types çalıştırır.

number bir float64. Tam sayılar 2**53 - 1 (Number.MAX_SAFE_INTEGER) kadar tamdır. Bitwise operatörler yalnızca int32 görür. O kısım bit-manipülasyonu kalıp sayfasında.

Bölme ve kalan

function check(ok: boolean): void {
  if (!ok) throw new Error("check failed");
}

check(Math.trunc(-3 / 2) === -1);
check(Math.floor(-3 / 2) === -2);
check(-3 % 2 === -1);
check(2 ** 53 === 2 ** 53 + 1);
check(Number.isSafeInteger(2 ** 53 - 1));
check(!Number.isSafeInteger(2 ** 53));

Math.trunc sıfıra gider. Math.floor negatif sonsuza gider; Python // de öyle. Kalan, bölünenin işaretini alır. Tamsayı bölme operatörü yoktur. >> int32 üzerinde aritmetik kaydırmadır; negatif veya 2**31 - 1 ötesi için yanlış araçtır.

Dizgiler

function check(ok: boolean): void {
  if (!ok) throw new Error("check failed");
}

const s = "ab,cd";
check(s[0] === "a" && s.at(-1) === "d");
check(s.slice(1, 4) === "b,c");
check([...s].reverse().join("") === "dc,ba");
check(s.split(",")[0] === "ab" && s.split(",")[1] === "cd");
check(["ab", "cd"].join(" ") === "ab cd");
check(s.replace("ab", "xy") === "xy,cd");
check(s.startsWith("ab") && s.endsWith("cd"));
check(s.indexOf("z") === -1);
check(s.includes("cd"));
check("A".charCodeAt(0) === 65 && String.fromCharCode(65) === "A");
check("ada".repeat(2) === "adaada");

Sondan sonra s[i] undefined. s.at(-1) son karakter. Alt dizgi yoksa indexOf -1 döner. Ayırıcısız split her UTF-16 biriminde böler. Dizgiler değişmez; replace yeni dizgi döner ve global regex yoksa ilk eşleşmeyi değiştirir.

Şablon dizgi ${expr} ile interpolasyon yapar.

Diziler

function check(ok: boolean): void {
  if (!ok) throw new Error("check failed");
}
function same(a: readonly number[], b: readonly number[]): boolean {
  return a.length === b.length && a.every((v, i) => v === b[i]);
}

const lexical = [10, 2, 1].sort();
check(same(lexical, [1, 10, 2]));
const numeric = [10, 2, 1].sort((a, b) => a - b);
check(same(numeric, [1, 2, 10]));

const row = [0, 0];
const shared = [row, row];
shared[0]![0] = 1;
check(shared[1]![0] === 1);

const rows = Array.from({ length: 2 }, () => [0, 0]);
rows[0]![0] = 1;
check(rows[1]![0] === 0);

const nums = [1, 2, 3];
nums.push(4);
check(nums.pop() === 4);
check(nums.shift() === 1);
check(nums.slice(0, 1)[0] === 2);

Karşılaştırıcısız sort string forma göre sıralar; 10, 2’den önce gelir. Artan sayılar için (a, b) => a - b ver. Modern motorlar eşit elemanların orijinal sırasını korur.

Array.from({ length: n }, () => []) her satıra taze bir iç dizi kurar. Tek bir dizi nesnesiyle fill o nesneyi her yuvaya koyar.

push ve pop yığın uçlarıdır. shift ve unshift sonraki her elemanı kaydırır. Queue-deque şablonu indeksleri bir dizide tutar ve önde shift çağırır.

function check(ok: boolean): void {
  if (!ok) throw new Error("check failed");
}
function same(a: readonly number[], b: readonly number[]): boolean {
  return a.length === b.length && a.every((v, i) => v === b[i]);
}

function maxSlidingWindow(nums: number[], k: number): number[] {
  const dq: number[] = [];
  const res: number[] = [];
  for (let i = 0; i < nums.length; i++) {
    while (dq.length && dq[0]! <= i - k) dq.shift();
    while (dq.length && nums[dq[dq.length - 1]!]! <= nums[i]!) dq.pop();
    dq.push(i);
    if (i >= k - 1) res.push(nums[dq[0]!]!);
  }
  return res;
}

check(same(maxSlidingWindow([1, 3, -1, -3, 5, 3, 6, 7], 3), [3, 3, 5, 5, 6, 7]));

nums[i]! tip denetleyicisine indeksin var olduğunu söyler. Çalışma anında kontrol etmez. Şablonlardaki !, bir uzunluk testinden veya o yuvayı dolduran bir yazmadan sonra durur.

const bağlamayı sabitler. İşaret ettiği dizi veya nesne hâlâ değişebilir.

Karşılaştırma ve eksik değerler

function check(ok: boolean): void {
  if (!ok) throw new Error("check failed");
}

check(0 == false);
check(!(0 === false));
check((0 || 5) === 5);
check((0 ?? 5) === 0);
check(("" || "default") === "default");
check(("" ?? "default") === "");
check((null as number | null)?.toFixed === undefined);
check([1, 2, 3].at(9) === undefined);

const bag: Record<string, number> = {};
bag[1] = 4;
check(Object.keys(bag)[0] === "1");

=== zorlamadan karşılaştırır. == zorlar, bu yüzden 0 == false doğrudur. || 0 ve "" değerlerini eksik sayar. ?? yalnızca null ve undefined yerine geçer.

Düz bir nesnenin anahtarları string’dir. Map 1 ile "1"’i ayrı tutar.

?. null veya undefined üzerinde kısa devre yapar. Aralık dışı indeks istisna değil, undefined.

Map, Set ve two-sum

Bu, hashing şablonunun şeklidir.

function check(ok: boolean): void {
  if (!ok) throw new Error("check failed");
}
function same(a: readonly number[], b: readonly number[]): boolean {
  return a.length === b.length && a.every((v, i) => v === b[i]);
}

function twoSum(nums: number[], target: number): number[] {
  const seen = new Map<number, number>();
  for (let i = 0; i < nums.length; i++) {
    const need = target - nums[i]!;
    if (seen.has(need)) return [seen.get(need)!, i];
    seen.set(nums[i]!, i);
  }
  throw new Error("no solution");
}

check(same(twoSum([2, 7, 11, 15], 9), [0, 1]));

const uniq = new Set([1, 1, 2]);
check(uniq.size === 2 && uniq.has(2));
uniq.add(3);
uniq.delete(1);
check(!uniq.has(1) && uniq.has(3));

Anahtar yoksa Map.get undefined döner. Üyelik testi has. Set’in indeksi yoktur; for...of ile dolaş. Ekleme sırası korunur.

Döngüler ve kontrol akışı

function check(ok: boolean): void {
  if (!ok) throw new Error("check failed");
}
function same(a: readonly number[], b: readonly number[]): boolean {
  return a.length === b.length && a.every((v, i) => v === b[i]);
}

const seen: number[] = [];
for (const [i, value] of ["a", "b"].entries()) seen.push(i);
check(same(seen, [0, 1]));

const keys: string[] = [];
for (const k in { a: 1, b: 2 }) keys.push(k);
check(keys[0] === "a" && keys[1] === "b");

let found = -1;
for (const value of [1, 3, 4]) {
  if (value % 2 === 0) {
    found = value;
    break;
  }
}
check(found === 4);

const doubled = [1, 2, 3].map((x) => x * 2);
check(same(doubled, [2, 4, 6]));
check([1, 2, 3].filter((x) => x % 2 === 1).length === 2);
check([1, 2, 3].reduce((a, b) => a + b, 0) === 6);

for...of değerleri gezer. for...in enumerable anahtarları gezer, özel prototipte kalıtılanlar dahil; nesne veri ise Object.keys veya Map yeğle. entries() indeks-plus-değer biçimidir.

map / filter / reduce tahsis eder. İç gövde algoritmaysa for döngüsü maliyeti görünür tutar.

Ternary cond ? a : b. switch === ile karşılaştırır.

Fonksiyonlar

function check(ok: boolean): void {
  if (!ok) throw new Error("check failed");
}

function add(a: number, b = 0): number {
  return a + b;
}
check(add(1) === 1 && add(1, 2) === 3);

const times = (n: number) => (x: number) => x * n;
check(times(3)(4) === 12);

function rest(first: number, ...more: number[]): number {
  return first + more.reduce((a, b) => a + b, 0);
}
check(rest(1, 2, 3) === 6);

const fns = [];
for (var i = 0; i < 3; i++) fns.push(() => i);
check(fns[0]!() === 3 && fns[1]!() === 3);

const bound: number[] = [];
for (let j = 0; j < 3; j++) bound.push(j);
check(bound[0] === 0 && bound[2] === 2);

Varsayılan çağrıda hesaplanır. Python [] varsayılanı gibi paylaşılan değişken varsayılan yoktur.

var fonksiyon kapsamlıdır; for (var …) döngüsü üzerindeki closure son değeri görür. let ve const blok kapsamlıdır. Ok fonksiyonları this’i miras alır; function metodunun kendi this’i vardır.

Sınıflar ve this

function check(ok: boolean): void {
  if (!ok) throw new Error("check failed");
}

class Counter {
  private n: number;
  constructor(n = 0) {
    this.n = n;
  }
  inc(): number {
    return ++this.n;
  }
  get value(): number {
    return this.n;
  }
}

const c = new Counter();
check(c.inc() === 1 && c.value === 1);

class NamedCounter extends Counter {
  readonly name: string;
  constructor(name: string) {
    super(0);
    this.name = name;
  }
}
check(new NamedCounter("ticks").name === "ticks");

extends this’ten önce super(...) ister. Sınıf alanı oku inc = () => ++this.n this’i örneğe bağlar; prototip metodu bağlamaz. Parametre özellikleri (constructor(private n = 0)) geçerli TypeScript’tir; Node’un strip-types yükleyicisi kabul etmez.

Destructure

function check(ok: boolean): void {
  if (!ok) throw new Error("check failed");
}

let a = 1, b = 2;
[a, b] = [b, a];
check(a === 2 && b === 1);

const [head, ...tail] = [1, 2, 3];
check(head === 1 && tail[0] === 2 && tail[1] === 3);

const point = { x: 3, y: 4 };
const { x, y: yy } = point;
check(x === 3 && yy === 4);

function pair([left, right]: [number, number]): number {
  return left + right;
}
check(pair([2, 5]) === 7);

İki bağlamayı [a, b] = [b, a] ile takas et. Dizide rest kalan elemanlardır. Alanı y: yy ile yeniden adlandır. İç içe kalıplar parametrelerde de çalışır.

Matematik ve BigInt

function check(ok: boolean): void {
  if (!ok) throw new Error("check failed");
}

check(Math.max(1, 4, 2) === 4);
check(Math.min(...[1, 4, 2]) === 1);
check(Math.abs(-3) === 3);
check(Math.hypot(3, 4) === 5);
check(Number.isInteger(3) && !Number.isInteger(3.1));
check(Number.parseInt("08", 10) === 8);
check(1e9 + 7 === 1_000_000_007);

const wide = 2n ** 53n + 1n;
check(wide + 1n === 2n ** 53n + 2n);
check(BigInt(Number.MAX_SAFE_INTEGER) === 2n ** 53n - 1n);

Argümansız Math.max -Infinity. Boş olmayan diziyi spread et. Radix’siz parseInt bazı ortamlarda baştaki 0’ı octal sayar; 10 ver.

BigInt ayrı bir tiptir. number ile karıştırınca motor fırlatır. number üzerinde bitwise hâlâ int32; kaydırma 31’in ötesindeki bitleri tutacaksa BigInt kullan.

Heap

Standart kütüphanede heap yoktur. Top-K şablonu her eklemede k boyutlu diziyi sıralar. Push ve pop’un ait olduğu yapı ikili heap’tir. Bu bir min-heap. Max-heap için, güvenli tamsayı aralığında, negatifi it.

function check(ok: boolean): void {
  if (!ok) throw new Error("check failed");
}

class MinHeap {
  private a: number[] = [];

  push(x: number): void {
    this.a.push(x);
    this.up(this.a.length - 1);
  }

  pop(): number {
    const a = this.a;
    if (a.length === 0) throw new Error("empty");
    const top = a[0]!;
    const last = a.pop()!;
    if (a.length > 0) {
      a[0] = last;
      this.down(0);
    }
    return top;
  }

  peek(): number {
    if (this.a.length === 0) throw new Error("empty");
    return this.a[0]!;
  }

  get size(): number {
    return this.a.length;
  }

  private up(i: number): void {
    const a = this.a;
    while (i > 0) {
      const p = (i - 1) >> 1;
      if (a[p]! <= a[i]!) break;
      [a[p], a[i]] = [a[i]!, a[p]!];
      i = p;
    }
  }

  private down(i: number): void {
    const a = this.a;
    for (;;) {
      let smallest = i;
      const l = i * 2 + 1;
      const r = l + 1;
      if (l < a.length && a[l]! < a[smallest]!) smallest = l;
      if (r < a.length && a[r]! < a[smallest]!) smallest = r;
      if (smallest === i) break;
      [a[smallest], a[i]] = [a[i]!, a[smallest]!];
      i = smallest;
    }
  }
}

const heap = new MinHeap();
for (const x of [3, 1, 4, 2]) heap.push(x);
check(heap.pop() === 1 && heap.pop() === 2 && heap.pop() === 3 && heap.peek() === 4);

function findKthLargest(nums: number[], k: number): number {
  const h = new MinHeap();
  for (const x of nums) {
    h.push(x);
    if (h.size > k) h.pop();
  }
  return h.peek();
}

check(findKthLargest([3, 2, 1, 5, 6, 4], 2) === 5);

İkili arama

İkili arama şablonu lo + ((hi - lo) >> 1) ile yarılar. İki uç da negatif olmayan indekstir; kaydırma pozitif int32 aralığında kalır.

function check(ok: boolean): void {
  if (!ok) throw new Error("check failed");
}

function binarySearch(nums: number[], target: number): number {
  let lo = 0;
  let hi = nums.length;
  while (lo < hi) {
    const mid = lo + ((hi - lo) >> 1);
    if (nums[mid]! < target) lo = mid + 1;
    else hi = mid;
  }
  return lo < nums.length && nums[lo] === target ? lo : -1;
}

check(binarySearch([1, 3, 3, 7], 3) === 1);
check(binarySearch([1, 3, 3, 7], 4) === -1);
check(binarySearch([], 1) === -1);

Bağlı listeler

Bağlı liste şablonu bu düğüm artı reverse ve dummy-head birleştirmesidir.

function check(ok: boolean): void {
  if (!ok) throw new Error("check failed");
}

class ListNode {
  val: number;
  next: ListNode | null;
  constructor(val = 0, next: ListNode | null = null) {
    this.val = val;
    this.next = next;
  }
}

function reverseList(head: ListNode | null): ListNode | null {
  let prev: ListNode | null = null;
  let cur = head;
  while (cur) {
    const nxt = cur.next;
    cur.next = prev;
    prev = cur;
    cur = nxt;
  }
  return prev;
}

function toArray(head: ListNode | null): number[] {
  const out: number[] = [];
  while (head) {
    out.push(head.val);
    head = head.next;
  }
  return out;
}

const a = new ListNode(1, new ListNode(2, new ListNode(3)));
check(toArray(reverseList(a)).join(",") === "3,2,1");

while (cur) ile yürü. Dummy head, birleştirme döngüsünün ilk düğümü özel saymasını engeller. Boş liste null.

Ağaçlar

function check(ok: boolean): void {
  if (!ok) throw new Error("check failed");
}

class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
  constructor(val = 0, left: TreeNode | null = null, right: TreeNode | null = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

function maxDepth(root: TreeNode | null): number {
  if (!root) return 0;
  return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}

function levelOrder(root: TreeNode | null): number[][] {
  if (!root) return [];
  const res: number[][] = [];
  const q: TreeNode[] = [root];
  while (q.length) {
    const size = q.length;
    const level: number[] = [];
    for (let i = 0; i < size; i++) {
      const n = q.shift()!;
      level.push(n.val);
      if (n.left) q.push(n.left);
      if (n.right) q.push(n.right);
    }
    res.push(level);
  }
  return res;
}

const root = new TreeNode(1, new TreeNode(2), new TreeNode(3, new TreeNode(4)));
check(maxDepth(root) === 3);
check(levelOrder(root).map((row) => row.join(",")).join("|") === "1|2,3|4");

left ve right üzerinde özyineleme DFS şablonudur. Seviye sırası q.length anlık görüntüsü alır; böylece yeni itilen çocuklar mevcut seviyeyi bozmaz.

Graflar

Graf-DFS şablonu number[][] komşuluk kurar. Izgara flood fill [r, c] hücrelerinin yığınıdır.

function check(ok: boolean): void {
  if (!ok) throw new Error("check failed");
}

function countComponents(n: number, edges: [number, number][]): number {
  const adj: number[][] = Array.from({ length: n }, () => []);
  for (const [a, b] of edges) {
    adj[a]!.push(b);
    adj[b]!.push(a);
  }
  const visited = new Array<boolean>(n).fill(false);
  let count = 0;
  for (let v = 0; v < n; v++) {
    if (!visited[v]) {
      dfs(v);
      count++;
    }
  }
  return count;

  function dfs(v: number) {
    visited[v] = true;
    for (const u of adj[v]!) if (!visited[u]) dfs(u);
  }
}

check(countComponents(4, [[0, 1], [2, 3]]) === 2);

function floodFill(
  image: number[][], sr: number, sc: number, newColor: number,
): number[][] {
  const orig = image[sr]![sc]!;
  if (orig === newColor) return image;
  const rows = image.length, cols = image[0]!.length;
  const stack: [number, number][] = [[sr, sc]];
  while (stack.length) {
    const [r, c] = stack.pop()!;
    if (r < 0 || c < 0 || r >= rows || c >= cols || image[r]![c] !== orig) continue;
    image[r]![c] = newColor;
    stack.push([r + 1, c], [r - 1, c], [r, c + 1], [r, c - 1]);
  }
  return image;
}

const filled = floodFill([[1, 1, 1], [1, 1, 0], [1, 0, 1]], 1, 1, 2);
check(filled[0]!.join(",") === "2,2,2" && filled[2]!.join(",") === "2,0,1");

orig === newColor aynı rengi sonsuz yeniden yazmayı kesen erken dönüştür.

Union-Find

Path compression artı rank’e göre birleştirme. union, iki düğümün farklı bileşenlerde olup olmadığını döner.

function check(ok: boolean): void {
  if (!ok) throw new Error("check failed");
}

class UnionFind {
  parent: number[];
  rank: number[];
  components: number;
  constructor(n: number) {
    this.parent = Array.from({ length: n }, (_, i) => i);
    this.rank = new Array(n).fill(0);
    this.components = n;
  }
  find(x: number): number {
    if (this.parent[x] !== x) this.parent[x] = this.find(this.parent[x]!);
    return this.parent[x]!;
  }
  union(a: number, b: number): boolean {
    let ra = this.find(a), rb = this.find(b);
    if (ra === rb) return false;
    if (this.rank[ra]! < this.rank[rb]!) [ra, rb] = [rb, ra];
    this.parent[rb] = ra;
    if (this.rank[ra] === this.rank[rb]) this.rank[ra]!++;
    this.components--;
    return true;
  }
}

const uf = new UnionFind(4);
check(uf.union(0, 1) && uf.union(2, 3));
check(!uf.union(0, 1));
check(uf.components === 2);

Trie

function check(ok: boolean): void {
  if (!ok) throw new Error("check failed");
}

class TrieNode {
  children = new Map<string, TrieNode>();
  isWord = false;
}
class Trie {
  root = new TrieNode();
  insert(word: string): void {
    let node = this.root;
    for (const ch of word) {
      if (!node.children.has(ch)) node.children.set(ch, new TrieNode());
      node = node.children.get(ch)!;
    }
    node.isWord = true;
  }
  search(word: string): boolean {
    const node = this.walk(word);
    return Boolean(node?.isWord);
  }
  startsWith(prefix: string): boolean {
    return this.walk(prefix) != null;
  }
  private walk(s: string): TrieNode | null {
    let node: TrieNode | null = this.root;
    for (const ch of s) {
      if (!node!.children.has(ch)) return null;
      node = node!.children.get(ch)!;
    }
    return node;
  }
}

const t = new Trie();
t.insert("apple");
check(t.search("apple") && !t.search("app"));
check(t.startsWith("app"));

search isWord ister. startsWith yalnızca yürüyüşün hayatta kalmasını ister.