PracHub
QuestionsPremiumCoachesLearningGuidesInterview Prep

Quick Overview

This multi-part question evaluates competence in string processing and nested parsing, linked-list flattening and recursion depth management, dynamic set design for O(1) operations, and algorithmic complexity analysis with attention to edge-case handling.

  • medium
  • Bloomberg
  • Coding & Algorithms
  • Software Engineer

Solve sliding-window, flattening, decode, and O(1) random set

Company: Bloomberg

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

You are given four independent coding tasks. For each, describe your approach, time complexity, and handle edge cases. ## 1) Longest substring without repeating characters Given a string `s`, return the length of the longest contiguous substring that contains no repeated characters. - **Input:** `s` (may be empty) - **Output:** integer length - **Clarifications to handle:** - What should be returned for `s = ""`? - Character set assumptions (ASCII/Unicode) and implications - **Target complexity:** `O(n)` time ## 2) Flatten a linked list with `down` pointers You are given a linked structure where each node has two pointers: ```text class Node { int val; Node next; // next node in the same level Node down; // head of a sublist (may be null) } ``` Flatten the structure into a single-level list using only `next` pointers, in depth-first order: - For each node, its `down` list (recursively flattened) should appear immediately after the node, followed by the original `next` chain. - After flattening, all `down` pointers should be set to `null`. - **Input:** `head: Node` - **Output:** `head` of the flattened list - **Discuss:** recursive DFS vs iterative approach and stack-depth concerns ## 3) Lottery / raffle structure with O(1) delete Design an in-memory data structure that maintains a dynamic set of unique items and supports: - `insert(x)`: add item `x` if not present - `remove(x)`: delete item `x` if present - `getRandom()`: return a uniformly random item currently in the set - **Goal:** average `O(1)` time for all operations. - **Discuss:** why a plain list makes deletion `O(n)`, and how to achieve `O(1)` deletion. ## 4) Decode an encoded string with nesting Given an encoded string using the pattern `k[encoded_string]`, decode it. The encoding may be nested. Examples: - `"3[a]2[bc]" -> "aaabcbc"` - `"3[a2[c]]" -> "accaccacc"` - `"12[z]" -> "zzzzzzzzzzzz"` Rules/notes: - `k` is a positive integer and may have multiple digits. - Input is assumed valid. - **Discuss:** using a stack to handle nesting and efficient string concatenation.

Quick Answer: This multi-part question evaluates competence in string processing and nested parsing, linked-list flattening and recursion depth management, dynamic set design for O(1) operations, and algorithmic complexity analysis with attention to edge-case handling.

Part 1: Longest Substring Without Repeating Characters

Given a string s, return the length of the longest contiguous substring that contains no repeated characters. The substring must be contiguous. For an empty string, return 0. Treat each Python character as one symbol, so the same algorithm works for ASCII and Unicode input.

Constraints

  • 0 <= len(s) <= 100000
  • s may contain any Unicode characters.
  • The answer for the empty string is 0.
  • The target time complexity is O(n).

Examples

Input: ("",)

Expected Output: 0

Explanation: The empty string has no substrings.

Input: ("abcabcbb",)

Expected Output: 3

Explanation: The longest substrings without repeats include abc.

Input: ("bbbbb",)

Expected Output: 1

Explanation: Every valid substring can contain only one b.

Input: ("pwwkew",)

Expected Output: 3

Explanation: The longest valid substring is wke.

Input: ("你好你abc",)

Expected Output: 5

Explanation: The longest valid substring is 好你abc, length 5.

Hints

  1. Use a sliding window whose left boundary only moves forward.
  2. Store the most recent index where each character appeared so you can skip past duplicates quickly.

Part 2: Flatten a Linked List with Down Pointers

You are given a linked structure where each node has a next pointer and a down pointer. Flatten it in depth-first order: for each node, its down list should appear immediately after the node, followed by the original next chain. In a pointer-based implementation, all down pointers would be set to null. For platform-friendly input, nodes are represented by indices, and you should return the values in flattened order.

Constraints

  • 0 <= len(nodes) <= 100000
  • Each node entry has exactly three integers: [val, next_index, down_index].
  • next_index and down_index are either -1 or valid indices into nodes.
  • The reachable structure from head is acyclic.
  • Node values may repeat.

Examples

Input: ([], -1)

Expected Output: []

Explanation: An empty structure flattens to an empty list.

Input: ([[7, -1, -1]], 0)

Expected Output: [7]

Explanation: A single node with no children remains unchanged.

Input: ([[1, 1, 2], [2, -1, -1], [3, 3, -1], [4, -1, -1]], 0)

Expected Output: [1, 3, 4, 2]

Explanation: Node 1's down chain 3 -> 4 is visited before node 2.

Input: ([[1, 1, 3], [2, 2, 6], [3, -1, -1], [4, 4, -1], [5, -1, 5], [6, -1, -1], [7, -1, -1]], 0)

Expected Output: [1, 4, 5, 6, 2, 7, 3]

Explanation: Nested down pointers are recursively flattened before returning to the original next chain.

Hints

  1. Depth-first order means down is processed before the original next.
  2. An explicit stack can avoid recursion-depth issues: push next first, then down, so down is popped first.

Part 3: Lottery Set with O(1) Insert, Remove, and Random Access

Design the core logic for an in-memory set of unique integer items that supports insert, remove, and getRandom in average O(1) time. A plain list can append in O(1) and choose a random index in O(1), but deleting an arbitrary value requires searching. The standard solution combines a dense array of items with a hash map from item to its array index. For deterministic testing, each getRandom operation supplies the array index to return; in a real raffle, that index would be chosen uniformly at random.

Constraints

  • 0 <= len(operations) <= 100000
  • Items x are integers.
  • At any time, the set contains unique items only.
  • Operation [3, i] is only called when the set is non-empty.
  • For operation [3, i], 0 <= i < current set size under the required array-backed implementation.

Examples

Input: ([] ,)

Expected Output: []

Explanation: No operations produce no outputs.

Input: ([[1, 10], [1, 20], [3, 0], [2, 10], [3, 0]],)

Expected Output: [1, 1, 10, 1, 20]

Explanation: After removing 10, 20 is swapped into index 0.

Input: ([[1, 5], [1, 5], [2, 6], [2, 5]],)

Expected Output: [1, 0, 0, 1]

Explanation: Duplicate insertion and removing a missing item fail.

Input: ([[1, 1], [1, 2], [1, 3], [2, 2], [3, 1], [1, 4], [3, 2]],)

Expected Output: [1, 1, 1, 1, 3, 1, 4]

Explanation: Removing 2 swaps 3 into its slot, so index 1 returns 3.

Input: ([[1, 7], [2, 7], [1, 8], [3, 0]],)

Expected Output: [1, 1, 1, 8]

Explanation: Removing the last remaining item is handled correctly.

Hints

  1. Keep items in a list and maintain a dictionary mapping each item to its current list index.
  2. To remove in O(1), swap the item with the last list element, update the moved element's index, then pop.

Part 4: Decode a Nested Encoded String

Given an encoded string using the pattern k[encoded_string], return its decoded form. Encodings may be nested, and k is a positive integer that may contain multiple digits. The input is assumed valid. Use a stack to remember the string built before each opening bracket and the repeat count for that bracket.

Constraints

  • 0 <= len(s) <= 100000
  • The input string is valid.
  • Repeat counts k are positive integers and may have multiple digits.
  • The decoded output length is at most 1000000.
  • Digits appear only as repeat counts before brackets.

Examples

Input: ("",)

Expected Output: ""

Explanation: The empty string decodes to itself.

Input: ("3[a]2[bc]",)

Expected Output: "aaabcbc"

Explanation: Three a characters followed by two bc blocks.

Input: ("3[a2[c]]",)

Expected Output: "accaccacc"

Explanation: The nested block a2[c] becomes acc, repeated three times.

Input: ("12[z]",)

Expected Output: "zzzzzzzzzzzz"

Explanation: Multi-digit repeat counts must be parsed correctly.

Input: ("2[abc]3[cd]ef",)

Expected Output: "abcabccdcdcdef"

Explanation: Encoded blocks and plain trailing characters are both supported.

Hints

  1. When you see an opening bracket, push the current partial string and repeat count onto a stack.
  2. When you see a closing bracket, decode the current segment and append it to the previous partial string.
Last updated: Jun 15, 2026

Loading coding console...

PracHub

Master your tech interviews with 8,000+ real questions from top companies.

Product

  • Questions
  • Learning Tracks
  • Interview Guides
  • Resources
  • Premium
  • For Universities
  • Student Access

Browse

  • By Company
  • By Role
  • By Category
  • Topic Hubs
  • SQL Questions
  • Compare Platforms
  • Discord Community

Support

  • support@prachub.com
  • (916) 541-4762

Legal

  • Privacy Policy
  • Terms of Service
  • About Us

© 2026 PracHub. All rights reserved.

Related Coding Questions

  • Minimize Travel Assignment Cost - Bloomberg (medium)
  • Determine Balloon Popping Time - Bloomberg (medium)
  • Solve meeting and tree problems - Bloomberg (easy)
  • Check connectivity between two subway stations - Bloomberg (easy)
  • Minimize travel cost with two cities - Bloomberg (easy)