PracHub
QuestionsPremiumCoachesLearningGuidesInterview Prep

Quick Overview

This set of four problems evaluates a candidate's proficiency in core algorithmic competencies including string parsing and bracket validation, bitwise reasoning and flip-count optimization, interval coverage and greedy/coverage strategies for binary strings, and array partitioning with segment-sum equivalence.

  • medium
  • Virtu
  • Coding & Algorithms
  • Software Engineer

Solve Four Online Assessment Coding Tasks

Company: Virtu

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Take-home Project

Implement solutions for the following four independent coding problems. 1. **Validate bracket strings** You are given an array of strings. Each string contains only the characters `(`, `)`, `[`, `]`, `{`, and `}`. For each string, determine whether it is valid. A string is valid if every opening bracket is closed by the same type of bracket and brackets are closed in the correct nested order. 2. **Minimize bit flips to make numbers equal** You are given a non-empty array of non-negative integers. In one operation, choose any one number and flip any one bit in its binary representation. All numbers should be considered using the same unsigned binary width, large enough to represent the maximum number in the input. Return the minimum number of bit-flip operations required to make all numbers in the array equal. Example: for `[1, 2]`, the answer is `2`. 3. **Eliminate long runs of zeros** You are given a binary string `s` and two integers `m` and `k`. The final string must not contain `m` or more consecutive `0` characters. In one operation, choose a contiguous substring of exactly `k` positions and set every character in that substring to `1`. Return the minimum number of operations needed to satisfy the requirement. Return `-1` if it is impossible. 4. **Make two arrays equal by merging segment sums** You are given two arrays `a` and `b` of positive integers. In one operation on either array, choose a contiguous subarray and replace it with one number equal to the sum of that subarray. Repeated operations are equivalent to partitioning each original array into contiguous segments and replacing each segment by its sum. Find the largest possible final length `L` such that both arrays can be reduced to exactly the same length-`L` sequence of segment sums. Return `-1` if no common final sequence exists.

Quick Answer: This set of four problems evaluates a candidate's proficiency in core algorithmic competencies including string parsing and bracket validation, bitwise reasoning and flip-count optimization, interval coverage and greedy/coverage strategies for binary strings, and array partitioning with segment-sum equivalence.

Part 1: Validate Bracket Strings

You are given a list of strings. Each string contains only the bracket characters `(`, `)`, `[`, `]`, `{`, and `}`. For each string, determine whether it is valid. A string is valid if every opening bracket is closed by the same type of bracket and the closing order is properly nested. Return a list of booleans in the same order as the input.

Constraints

  • 0 <= len(brackets) <= 10000
  • 0 <= len(brackets[i]) <= 100000
  • The total length of all strings is at most 200000
  • Each string contains only the characters (), [], {}

Examples

Input: (['()', '([]){}', '([)]', ''],)

Expected Output: [True, True, False, True]

Explanation: The first two strings are valid, `([)]` is not properly nested, and the empty string is valid.

Input: (['(', ')', '{{[]}}'],)

Expected Output: [False, False, True]

Explanation: A single opening or closing bracket is invalid. `{{[]}}` is correctly nested.

Input: ([],)

Expected Output: []

Explanation: Edge case: an empty input list returns an empty result list.

Input: (['{[()()]}', '{[(])}', '][', '(()'],)

Expected Output: [True, False, False, False]

Explanation: Only the first string is valid.

Hints

  1. Use a stack to track opening brackets as you scan each string from left to right.
  2. When you see a closing bracket, it must match the most recent unmatched opening bracket.

Part 2: Minimize Bit Flips to Make Numbers Equal

You are given a non-empty array of non-negative integers. In one operation, you may choose any one number and flip any one bit in its binary representation. All numbers are viewed using the same unsigned binary width, large enough to represent the maximum value in the array. Return the minimum number of bit-flip operations required to make all numbers equal.

Constraints

  • 1 <= len(nums) <= 200000
  • 0 <= nums[i] <= 10^9

Examples

Input: ([1, 2],)

Expected Output: 2

Explanation: Using width 2, the numbers are `01` and `10`. One flip is needed in each bit position, for a total of 2.

Input: ([7, 7, 7],)

Expected Output: 0

Explanation: All numbers are already equal.

Input: ([0],)

Expected Output: 0

Explanation: Edge case: a single element needs no changes.

Input: ([0, 1, 3],)

Expected Output: 2

Explanation: Using width 2: bit 0 needs 1 flip, bit 1 needs 1 flip.

Input: ([8, 0, 8, 0],)

Expected Output: 2

Explanation: Only the highest bit differs, and two flips are needed there.

Hints

  1. Each bit position can be optimized independently from the others.
  2. For a fixed bit position, choose the final bit value that matches the majority of numbers at that position.

Part 3: Eliminate Long Runs of Zeros

You are given a binary string `s` and two integers `m` and `k`. The final string must not contain `m` or more consecutive `0` characters. In one operation, you choose a contiguous substring of exactly `k` positions and set every character in that substring to `1`. Return the minimum number of operations needed to satisfy the requirement. Return `-1` if it is impossible.

Constraints

  • 0 <= len(s) <= 200000
  • 1 <= m <= 200000
  • 1 <= k <= 200000
  • s contains only `0` and `1`

Examples

Input: ("00100", 2, 3)

Expected Output: 1

Explanation: Turning the middle length-3 substring into `111` gives `01110`, which has no `00`.

Input: ("000000", 3, 2)

Expected Output: 1

Explanation: One operation on the middle two positions yields `001100`, and the longest zero run is then 2.

Input: ("10101", 2, 2)

Expected Output: 0

Explanation: The string already has no run of two or more zeros.

Input: ("000", 2, 4)

Expected Output: -1

Explanation: Edge case: no length-4 operation fits inside the string, so the invalid run cannot be changed.

Input: ("01010", 1, 2)

Expected Output: 3

Explanation: When `m = 1`, every zero must be covered by at least one operation. Three operations are needed.

Hints

  1. The condition is equivalent to saying every length-`m` substring must contain at least one `1` in the final string.
  2. Focus on windows that are all zeros in the original string. Greedily fix the leftmost uncovered bad window by placing the operation as far right as possible.

Part 4: Make Two Arrays Equal by Merging Segment Sums

You are given two arrays `a` and `b` of positive integers. In one operation on either array, you may choose a contiguous subarray and replace it with its sum. Repeating this process is equivalent to partitioning each original array into contiguous segments and replacing every segment by its sum. Find the largest possible final length `L` such that both arrays can be reduced to exactly the same length-`L` sequence of segment sums. Return `-1` if no common final sequence exists.

Constraints

  • 1 <= len(a), len(b) <= 200000
  • 1 <= a[i], b[i] <= 10^9

Examples

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

Expected Output: 2

Explanation: One optimal common sequence is `[1, 3]`.

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

Expected Output: 1

Explanation: Both arrays can be reduced to `[2]`.

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

Expected Output: -1

Explanation: The total sums differ, so no common final sequence exists.

Input: ([5], [5])

Expected Output: 1

Explanation: Edge case: both arrays already match as a single segment.

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

Expected Output: 2

Explanation: One optimal common sequence is `[4, 2]`.

Hints

  1. If the total sums of the arrays are different, they can never become equal.
  2. Because all values are positive, common segment boundaries occur exactly at common cumulative sums.
Last updated: May 23, 2026

Related Coding Questions

  • Implement Connect Four Winner Detection - Virtu (medium)

Loading coding console...

PracHub

Master your tech interviews with 8,500+ 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.