How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at TikTok.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at TikTok during technical interviews.

Solve common string/DP/stack problems | TikTok Coding Question

Solve common string/DP/stack problems

Company: TikTok

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

You are given four independent coding tasks. For each task, describe your approach and analyze time and space complexity. ## Task 1: Longest substring with all distinct characters **Input:** A string `s` (ASCII or lowercase letters). **Output:** An integer = the maximum length of a contiguous substring of `s` that contains no repeated characters. **Example:** `s = "abcabcbb"` → output `3` (e.g., "abc"). **Constraints (typical):** `0 ≤ |s| ≤ 2e5`. --- ## Task 2: Largest rectangle in a histogram **Input:** An array `heights` of length `n`, where `heights[i]` is the height of the `i`-th bar in a histogram. Each bar has width `1`. **Output:** The maximum area of any axis-aligned rectangle that can be formed using one or more contiguous bars. **Example:** `heights = [2,1,5,6,2,3]` → output `10` (bars 5 and 6). **Constraints (typical):** `1 ≤ n ≤ 2e5`, `0 ≤ heights[i] ≤ 1e9`. --- ## Task 3: Minimum cost to reach the last index with 1–2 steps You start at index `0`. From index `i`, you may move to `i+1` or `i+2` (if within bounds). Visiting an index `i` incurs `cost[i]` (including index `0` and the last index). **Input:** Arrays `cost` (or `nums` + per-position `cost`) of length `n`. **Output:** The minimum total cost to reach index `n-1`. **Example:** `cost = [1,100,1,1,1,100,1,1,100,1]` → output `6`. **Constraints (typical):** `1 ≤ n ≤ 2e5`, `0 ≤ cost[i] ≤ 1e9`. --- ## Task 4: Longest palindromic substring **Input:** A string `s`. **Output:** A substring of `s` that is a palindrome and has maximum possible length. If multiple answers exist, return any one. **Example:** `s = "babad"` → output `"bab"` (or `"aba"`). **Constraints (typical):** `1 ≤ |s| ≤ 2e3` (or specify if larger and discuss tradeoffs).

Quick Answer: This set of four coding tasks evaluates proficiency in string algorithms, dynamic programming, sliding-window techniques, monotonic stack usage, and time/space complexity analysis.

Part 1: Longest Substring With All Distinct Characters

Given a string s, find the maximum length of a contiguous substring that contains no repeated characters. Return 0 if the string is empty.

Constraints

0 <= len(s) <= 200000
s may contain ASCII characters
An O(n) solution is expected for large inputs

Examples

Input: "abcabcbb"

Expected Output: 3

Explanation: The longest valid substring is 'abc', which has length 3.

Input: ""

Expected Output: 0

Explanation: An empty string has no non-empty substring.

Input: "bbbbb"

Expected Output: 1

Explanation: Every substring longer than 1 contains repeated 'b'.

Input: "abba"

Expected Output: 2

Explanation: The longest distinct substrings are 'ab' and 'ba'.

Input: "tmmzuxt"

Expected Output: 5

Explanation: One longest distinct substring is 'mzuxt'.

Hints

Try a sliding window with two pointers.
Store the most recent index of each character so you can move the left boundary quickly when a duplicate appears.

Part 2: Largest Rectangle in a Histogram

You are given a list heights where heights[i] is the height of the i-th histogram bar, and every bar has width 1. Return the maximum rectangular area that can be formed using one or more contiguous bars. If the list is empty, return 0.

Constraints

0 <= len(heights) <= 200000
0 <= heights[i] <= 1000000000
The answer can be as large as about 2 * 10^14

Examples

Input: [2, 1, 5, 6, 2, 3]

Expected Output: 10

Explanation: The best rectangle uses the bars with heights 5 and 6, giving area 5 * 2 = 10.

Input: []

Expected Output: 0

Explanation: An empty histogram contains no rectangle.

Input: [6]

Expected Output: 6

Explanation: The only possible rectangle uses the single bar.

Input: [2, 4]

Expected Output: 4

Explanation: The best area is 4, either from height 4 with width 1 or height 2 with width 2.

Input: [0, 0, 0]

Expected Output: 0

Explanation: All bars have height 0, so every rectangle has area 0.

Hints

For each bar, think about how far it can extend left and right before a shorter bar stops it.
A monotonic increasing stack helps you compute areas exactly when a smaller height appears.

Part 3: Minimum Cost to Reach the Last Index With 1-2 Steps

You start at index 0 of an array cost. Visiting an index i adds cost[i] to your total, including index 0 and the last index. From index i, you may move to i + 1 or i + 2 as long as the destination is within bounds. Return the minimum total cost needed to reach index n - 1.

Constraints

1 <= len(cost) <= 200000
0 <= cost[i] <= 1000000000
The answer can be as large as about 2 * 10^14

Examples

Input: [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]

Expected Output: 6

Explanation: A cheapest path is 0 -> 2 -> 4 -> 6 -> 7 -> 9 with total cost 6.

Input: [5]

Expected Output: 5

Explanation: You start on the last index, so you pay only cost[0].

Input: [1, 2, 3]

Expected Output: 4

Explanation: The best path is 0 -> 2, so the cost is 1 + 3 = 4.

Input: [0, 0, 0, 0]

Expected Output: 0

Explanation: All visited indices cost 0.

Input: [10, 1, 1, 10, 1]

Expected Output: 12

Explanation: The best path is 0 -> 2 -> 4 with total cost 10 + 1 + 1 = 12.

Hints

Let dp[i] be the minimum cost to reach index i.
Each state depends only on the previous two states, so you can optimize space to O(1).

Part 4: Longest Palindromic Substring

Given a string s, return a substring of s that is a palindrome and has maximum possible length. If multiple answers exist, returning any one of them is acceptable. If the input is empty, return an empty string.

Constraints

0 <= len(s) <= 2000
s may contain arbitrary characters
An O(n^2) solution is acceptable for this input size

Examples

Input: ""

Expected Output: ""

Explanation: The empty string has an empty longest palindromic substring.

Input: "a"

Expected Output: "a"

Explanation: A single character is always a palindrome.

Input: "cbbd"

Expected Output: "bb"

Explanation: The longest palindromic substring is 'bb'.

Input: "racecarxyz"

Expected Output: "racecar"

Explanation: The prefix 'racecar' is a palindrome of length 7.

Input: "forgeeksskeegfor"

Expected Output: "geeksskeeg"

Explanation: The longest palindromic substring is 'geeksskeeg'.

Hints

Every palindrome is centered either on a character or between two characters.
Expand outward from each possible center instead of checking every substring.

Quick Overview

This set of four coding tasks evaluates proficiency in string algorithms, dynamic programming, sliding-window techniques, monotonic stack usage, and time/space complexity analysis.