Spotify Full-Stack Developer (Junior Level) - Complete Interview Preparation Guide

def longest_palindrome(s: str) -> str:
    if not s:
        return ""
    # Transform: ^ and $ are sentinels to avoid bounds checks
    t = "^#" + "#".join(s) + "#$"
    n = len(t)
    P = [0] * n
    C = R = 0
    max_len = 0
    center_index = 0

    for i in range(1, n - 1):
        mirror = 2 * C - i
        if i < R:
            P[i] = min(R - i, P[mirror])
        # attempt to expand palindrome centered at i
        while t[i + 1 + P[i]] == t[i - 1 - P[i]]:
            P[i] += 1
        # update center and right boundary
        if i + P[i] > R:
            C, R = i, i + P[i]
        if P[i] > max_len:
            max_len = P[i]
            center_index = i

    # Extract start in original string
    start = (center_index - max_len) // 2
    return s[start:start + max_len]

def longest_palindrome(s: str) -> str:
    if not s:
        return ""
    start = 0
    max_len = 1

    def expand(l: int, r: int):
        nonlocal start, max_len
        while l >= 0 and r < len(s) and s[l] == s[r]:
            cur_len = r - l + 1
            if cur_len > max_len:
                max_len = cur_len
                start = l
            l -= 1
            r += 1

    for i in range(len(s)):
        expand(i, i)       # odd-length centers
        expand(i, i + 1)   # even-length centers

    return s[start:start + max_len]

import random

class CuckooHash:
    def __init__(self, capacity=11, max_kicks=50):
        self.n = 0
        self.capacity = capacity
        self.max_kicks = max_kicks
        self.table1 = [None] * capacity
        self.table2 = [None] * capacity
        # Use two independent hash seeds
        self.seed1 = random.randrange(1<<30)
        self.seed2 = random.randrange(1<<30)

    def _h1(self, key):
        return (hash((key, self.seed1)) % self.capacity)

    def _h2(self, key):
        return (hash((key, self.seed2)) % self.capacity)

    def contains(self, key):
        return self.table1[self._h1(key)] == key or self.table2[self._h2(key)] == key

    def remove(self, key):
        i = self._h1(key)
        if self.table1[i] == key:
            self.table1[i] = None
            self.n -= 1
            return True
        j = self._h2(key)
        if self.table2[j] == key:
            self.table2[j] = None
            self.n -= 1
            return True
        return False

    def insert(self, key):
        if self.contains(key):
            return True
        if self.n + 1 > self.capacity * 0.9:
            self._resize()
        cur = key
        for kick in range(self.max_kicks):
            i = self._h1(cur)
            if self.table1[i] is None:
                self.table1[i] = cur
                self.n += 1
                return True
            # kick occupant from table1 to table2
            cur, self.table1[i] = self.table1[i], cur
            j = self._h2(cur)
            if self.table2[j] is None:
                self.table2[j] = cur
                self.n += 1
                return True
            # kick occupant from table2 back to table1
            cur, self.table2[j] = self.table2[j], cur
        # failed after max_kicks -> resize and reinsert
        self._resize()
        return self.insert(cur)

    def _resize(self):
        old_items = [k for k in self.table1 if k is not None] + [k for k in self.table2 if k is not None]
        self.capacity *= 2
        self.table1 = [None] * self.capacity
        self.table2 = [None] * self.capacity
        self.seed1 = random.randrange(1<<30)
        self.seed2 = random.randrange(1<<30)
        self.n = 0
        for k in old_items:
            self.insert(k)