## Problem Two players take turns claiming tiles from a 1D array of integer-valued tiles. Each turn, the current player must take from either the left end or the right end. Both play optimally to maximize their own score. Return the score difference (player 1 score minus player 2 score) at the end of the game. ```python def winning_tiles(tiles: list[int]) -> int: """Return score_player1 - score_player2 assuming optimal play.""" pass ``` ``` Input: tiles = [5, 3, 7, 10] Output: 7 # P1 takes 10 (right), P2 takes 7, P1 takes 5, P2 takes 3 # P1=15, P2=10 -> diff=5 # OR P1 takes 5, P2 takes 10, P1 takes 7, P2 takes 3 -> P1=12, P2=13 -> diff=-1 # Optimal: P1 takes 10, then 7 -> P1=17, P2=8 -> diff=9? trace carefully. Input: tiles = [1, 5, 2] Output: 4 # P1 takes 2, P2 takes 5, P1 takes 1 -> P1=3, P2=5 -> diff=-2 # P1 takes 1, P2 takes 2, P1 takes 5 -> P1=6, P2=2 -> diff=4 <-- optimal ``` ## Follow-ups 1. Define the recurrence `dp[i][j]` = best score difference achievable by the current player on subarray `[i..j]`. 2. What is the time and space complexity of the DP solution? 3. If tiles can have negative values, does optimal play change (can a player pass)? 4. Extend to 3 players — does the same DP structure work?

InterviewDB Question

Winning Tiles: Determine the Victor in a Tile-Claiming Game

phone

Question Details

Problem Two players take turns claiming tiles from a 1D array of integer-valued tiles. Each turn, the current player must take from either the left end or the right end. Both play optimally to maximize their own score. Return the score difference (player 1 score minus player 2 score) at the end of the game. Follow-ups Define the recurrence dp[i][j] = best score difference achievable by the current player on subarray [i..j]. What is the time and space complexity of the DP solution? If tiles can h…

Full Details

🔒

Unlock all Ziphq questions

Full insider details, leaked discussions, and candidate experiences.

Get full access — $100 a year, unlimited access

About This Question

This is a reported interview question from a ziphq interview during the phone round.

It covers the following topics: Dynamic Programming, Phone, Coding, Arrays, Onsite .

Topics

Dynamic Programming Phone Coding Arrays Onsite

Winning Tiles: Determine the Victor in a Tile-Claiming Game

Question Details

Full Details

About This Question

Topics

More Ziphq Interview Questions