Tiktok - Onsite

Passed but didn't complete team match. Pretty hard. During team match hiring manager ask may ask you System Design questions out of no where.

Round 1: TikTok 3474. Lexicographically Smallest Generated String

• Problem Overview: You are given two strings,
  1. str1

  复制代码
  (consisting of 'T' and 'F') of length n, and
  1. str2

  复制代码
  of length m. You need to generate the lexicographically smallest string of length n + m - 1.
• • If
    1. str1[i] == 'T'

    复制代码
    , the substring starting at index i of length m must equal
    1. str2

    复制代码
    .
  • If
    1. str1[i] == 'F'

    复制代码
    , the substring starting at index i of length m must not equal
    1. str2

    复制代码
    .
• Core Strategy (Greedy + Two-Pass):
• • Initialize: Build an array of length n + m - 1 filled initially with 'a' to keep it lexicographically smallest.
  • Pass 1 ('T' Constraints): Iterate through
    1. str1

    复制代码
    . Whenever you encounter a 'T', lock in the characters of
    1. str2

    复制代码
    at those positions. If a conflict occurs (a position is already locked with a different character), return
    1. ""

    复制代码
    . Mark these positions as "fixed".
  • Pass 2 ('F' Constraints): Check every 'F' window. If a window accidentally matches
    1. str2

    复制代码
    , you must break the equality by changing the rightmost unfixed character in that window to 'b'. If no unfixed character is available to change, it's impossible, so return
    1. ""

    复制代码
    .

Round 2: TikTok BFS (Escape Virus / Contain Virus)

• Similar Problem: LeetCode 749. Contain Virus.
• Problem Overview: A grid has uninfected cells (0) and infected cells (1). Each round, the virus spreads to adjacent uninfected cells by 1 step. Resources are limited, so each day you must choose one contiguous viral region that threatens the most uninfected cells and quarantine it by building walls around its perimeter.
• Core Strategy (Simulation + BFS/DFS):
• • Identify Regions: Use BFS or DFS to find all disconnected continuous blocks of infected cells (1s).
  • Evaluate Threat: For each region, calculate two things: the number of uninfected cells it will infect next night, and the number of walls required to quarantine it (its perimeter).
  • Greedy Action: Select the region with the maximum threat, permanently wall it off (add its perimeter to your total wall count, and mark its cells as contained), and let all other active virus regions spread by 1 step. Repeat until no active uninfected cells or uncontained viruses remain.

Round 3: TikTok Calculate Elements (Parsing Chemical Formulas)

• Problem Overview: Given a chemical formula string containing nested parentheses, numbers, and element names (e.g.,
  1. H2O

  复制代码
  ,
  1. H2(O2(H2)2)

  复制代码
  ), compute the total count of each element (like total Hydrogen and total Oxygen). This is identical to LeetCode 726: Number of Atoms.
• Core Strategy: Use a Stack or Recursion to handle nested parentheses and multipliers.
• • Traverse the string from right-to-left (or use a stack for left-to-right).
  • When you encounter numbers, parse the full integer multiplier.
  • When you encounter closing parentheses ), push a new scope onto the stack.
  • When you encounter opening parentheses (, pop the scope, multiply all element counts inside by the multiplier immediately following the closing parenthesis, and merge them into the outer scope.

Example Walkthrough:

1. H2(O(H)2)2

复制代码

• Inner Group
  1. (H)2

  复制代码
  :
• • Contains
    1. H

    复制代码
    with count 1.
  • Multiplier after )2 is 2, so
    1. H

    复制代码
    count = 1 * 2 = 2.
• Outer Group
  1. (O(H)2)2

  复制代码
  :
• • Inside we have
    1. O

    复制代码
    (count 1) and the inner group
    1. H

    复制代码
    (count 2). Total inside:
    1. O: 1, H: 2

    复制代码
    .
  • Multiplier after this parenthesis is 2, so we multiply everything inside by 2:
    1. O: 1 * 2 = 2

    复制代码
    ,
    1. H: 2 * 2 = 4

    复制代码
    .
• Leading
  1. H2

  复制代码
  :
• • Adds
    1. H: 2

    复制代码
    to the final sum.

• Final Result:
• • Total
    1. H

    复制代码
    = 4 + 2 = 6
  • Total
    1. O

    复制代码
    = 2