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 hard difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Voleon.

What role is this question designed for?

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

Solve classic coding interview problems

Quick Overview

These problems evaluate algorithmic problem-solving skills including dynamic programming and combinatorics for the egg-dropping scenario, array manipulation and duplicate-handling for zero-sum triplets, and grid transformation, counting, and optimization for the Y-shape recoloring.

Company: Voleon

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Technical Screen

Solve the following algorithmic problems: 1. Egg testing with limited resources: You are given k identical eggs and a building with n floors. An egg breaks if it is dropped from a floor higher than some unknown critical floor F, and it survives otherwise. Determine the minimum number of drops needed in the worst case to identify F. 2. Find zero-sum triplets: Given an integer array nums, return all unique triplets [a, b, c] such that a + b + c = 0. The same triplet may not appear more than once in the output. 3. Recolor a grid into a Y shape: You are given an odd integer n and an n x n grid whose cells contain only 0, 1, or 2. The Y-shape consists of the two diagonals from the top corners to the center cell, plus the center column from the center cell down to the last row. In one operation, you may change any cell to 0, 1, or 2. Find the minimum number of changes required so that all Y-shape cells have one common value, all non-Y cells have another common value, and the two values are different.

Quick Answer: These problems evaluate algorithmic problem-solving skills including dynamic programming and combinatorics for the egg-dropping scenario, array manipulation and duplicate-handling for zero-sum triplets, and grid transformation, counting, and optimization for the Y-shape recoloring.

Part 1: Egg testing with limited resources

You are given k identical eggs and a building with n floors. There exists an unknown critical floor F such that an egg survives if dropped from floor F or below, and breaks if dropped from any floor above F. Determine the minimum number of drops needed in the worst case to identify F exactly.

Constraints

1 <= k <= 100
0 <= n <= 10000
The critical floor F can be any integer from 0 to n inclusive

Examples

Input: (1, 0)

Expected Output: 0

Explanation: With no floors, no drops are needed.

Input: (1, 5)

Expected Output: 5

Explanation: With only one egg, you must test floors from bottom to top.

Input: (2, 6)

Expected Output: 3

Explanation: Three drops are enough in the worst case with two eggs.

Input: (3, 14)

Expected Output: 4

Explanation: With 3 eggs and 4 moves, you can cover 14 floors.

Input: (2, 100)

Expected Output: 14

Explanation: For two eggs, 14 moves can cover 105 floors, so 14 is sufficient and minimal.

Hints

Instead of asking 'what is the answer for k eggs and n floors?', ask 'with m moves and k eggs, how many floors can I guarantee to test?'
If you drop an egg from some floor, one move is used. If it breaks, you solve a smaller problem with one fewer egg; if it survives, you solve a smaller problem with the same number of eggs.

Part 2: Find zero-sum triplets

Given an integer array nums, return all unique triplets [a, b, c] such that a + b + c = 0. The same triplet may not appear more than once in the output. For deterministic testing, return each triplet in nondecreasing order, and return the full list in lexicographic order.

Constraints

0 <= len(nums) <= 3000
-100000 <= nums[i] <= 100000

Examples

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

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

Explanation: These are the only two unique triplets whose sum is 0.

Input: ([])

Expected Output: []

Explanation: An empty array cannot contain any triplet.

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

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

Explanation: Even though there are many ways to pick three zeros, the triplet appears only once.

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

Expected Output: []

Explanation: No three numbers sum to 0.

Input: ([-2, 0, 0, 2, 2])

Expected Output: [[-2, 0, 2]]

Explanation: Duplicate values must not create duplicate triplets.

Hints

Sorting the array makes it much easier to avoid duplicates and to search efficiently.
Fix one number, then use two pointers on the remaining suffix to find pairs that complete the sum to zero.

Part 3: Recolor a grid into a Y shape

You are given an odd integer n and an n x n grid whose cells contain only 0, 1, or 2. The Y-shape consists of the two diagonals from the top-left and top-right corners down to the center cell, plus the center column from the center cell down to the last row. In one operation, you may change any cell to 0, 1, or 2. Find the minimum number of changes required so that all Y-shape cells have one common value, all non-Y cells have another common value, and the two values are different.

Constraints

3 <= n <= 49
n is odd
grid.length == grid[i].length == n
Each grid[i][j] is 0, 1, or 2

Examples

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

Expected Output: 0

Explanation: The Y cells already all contain 1, and all non-Y cells already contain 0.

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

Expected Output: 4

Explanation: In a 3x3 grid, the Y has 4 cells. Recoloring those 4 cells to 0 or 1 is optimal.

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

Expected Output: 3

Explanation: The best choice is Y = 2 and non-Y = 0, which requires changing exactly three cells.

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

Expected Output: 7

Explanation: In a 5x5 grid, the Y has 7 cells. Recoloring the Y to 1 or 2 is optimal.

Hints

First determine which cells belong to the Y and which do not. Then count how many 0s, 1s, and 2s appear in each group.
Try all ordered pairs of distinct values: one for Y cells and one for non-Y cells. Since there are only 3 possible values, this is constant work after counting.

Quick Overview