FastPrepDelete and Freeze Game
Problems/Delete and Freeze Game

Delete and Freeze Game

Rubrik logoRubrik● HardINTERNOA

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: This was the fourth of four questions in a 75-minute Rubrik online assessment for a CPD intern role. The writer could not find a matching known problem and did not solve it. But the writer wrote out the rules of the game and the limits on n and a[i].

The post does not say what the score is when only one element is frozen, which happens when n is 3. Here, that score is 0, and Bob must always freeze an element that is not frozen yet. The post also does not say whether Bob may pick an element that is already frozen, so this version does not allow it.

Our version is about 90% the same as the reported question.

You are given an integer array a of length n. Alice and Bob play a game on it, taking turns, and Alice moves first.

  • On Alice's turn, she deletes exactly one element that is not frozen.
  • On Bob's turn, he freezes exactly one element that is neither deleted nor frozen. A frozen element can never be deleted.

The game ends as soon as every element that is still in the array is frozen. The frozen elements keep their original order and form the final array b.

The score of the game is the largest value of b[j] - b[i] over all pairs of indices i < j in b. The score can be negative. If b has fewer than two elements, the score is 0.

Alice plays to make the score as small as possible, and Bob plays to make it as large as possible. Return the score when both play optimally.

Function

finalScore(a: int[]) → int

Examples

Example 1

a = [1,2,3,4]return = 1

Bob freezes two elements in this game. Alice first deletes 4. From [1, 2, 3], Bob freezes some element, and Alice then deletes the partner that would give Bob the bigger score. For every choice Bob makes, what is left gives a score of 1. For example, Bob freezes 1, Alice deletes 3, and Bob freezes 2, so b = [1, 2].

If Alice first deleted 2 instead, Bob could freeze 1, whose partners 3 and 4 both give at least 2. If she first deleted 3, Bob could freeze 4, whose partners 1 and 2 both give at least 2. If she first deleted 1, then from [2, 3, 4] every element Bob freezes again leaves him a score of 1. No first move holds Bob below 1, so the answer is 1.

Example 2

a = [1,5,2]return = 0

Alice deletes one element, Bob freezes one, and Alice deletes the last unfrozen one. Only one element stays, so the score is 0.

Example 3

a = [5,4,3,2,1]return = -2

Every pair gives a negative difference, and two elements closer together in the array give a less negative one. Alice first deletes 3.

Call two elements neighbors when they were next to each other in the original array. A pair of neighbors gives -1, the best score possible here. After 3 is gone, no element has a neighbor on both sides. Whatever Bob freezes, Alice deletes its one remaining neighbor, so the best Bob can do is two elements two places apart in the original array, such as b = [4, 2] with score 2 - 4 = -2.

If Alice deleted any other element first, Bob could freeze an element with a neighbor on each side, and keep one of them for a score of -1. So the answer is -2.

Constraints

  • 3 <= n <= 10^5
  • 1 <= a[i] <= 10^9

More Rubrik Online Assessment questions

  • Delete K Subsets for Maximum ScoreOA · Seen Nov 2026
  • Distribute Elements Into Two Arrays IIOA · Seen Nov 2026
  • Minimum Replacements to Sort the ArrayOA · Seen Nov 2026
  • Minimum Swaps To Binary PalindromeOA · Seen Apr 2026
  • Get Minimum OperationsOA · Seen Nov 2024
  • Horizontal Pod AutoscalerOA · Seen Nov 2024
  • Stock PricesOA · Seen Nov 2024
  • StarlightOA · Seen Oct 2024
  • Energy CrisisOA · Seen Sep 2024
  • Mike and GemsOA · Seen Sep 2024

Similar questions at other companies

  • Maximize Revenue from Decreasing InventoryChubb · OAChubb interview questions
  • Maximum Three-Server Difficulty ScoreVisa · OAVisa interview questions
  • Minimum Fuel Car AlignmentFivetran · PHONE SCREENFivetran interview questions
  • Maximize K-Element AND with an Increment BudgetAmazon · OA
  • Most Segments That Sort the ArrayRippling · OARippling interview questions
  • Most Items Within Budget from a Start IndexHudson River Trading · OAHudson River Trading interview questions
  • Luna and the Colorful SocksPhonePe · OAPhonePe interview questions
  • Minimum Starting Coins to Buy All ProductsMicrosoft · OAMicrosoft interview questions
  • Lock CodeGoldman Sachs · OAGoldman Sachs interview questions
  • Power Update After K-th Largest InsertionGoogle · OAGoogle interview questions
All Rubrik interview questionsSee Rubrik hiring insights
Saved
class Solution {
    public int finalScore(int[] a) {
        // Write your code here.
    }
}
Checking account…