PracHub
QuestionsPremiumCoachesLearningGuidesInterview Prep
|Home/Coding & Algorithms/Dropbox

Compute worst-case guesses for adaptive hangman

Last updated: Apr 2, 2026

Quick Overview

This question evaluates algorithmic problem-solving, combinatorial reasoning, and adversarial information-theoretic thinking by requiring modeling of worst-case query strategies for adaptive letter-guessing.

  • medium
  • Dropbox
  • Coding & Algorithms
  • Software Engineer

Compute worst-case guesses for adaptive hangman

Company: Dropbox

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

You are given a set of distinct lowercase words, all of the same length. A hidden word is chosen from this set, but the host is adversarial: after each of your letter guesses, the host may switch to any other word in the set as long as it remains consistent with every answer revealed so far. On each turn, you guess one lowercase letter that you have not guessed before. The host then reveals the pattern for that letter with respect to some currently valid hidden word: every matching position is shown, or the host may report that the letter does not appear if there exists a consistent word without that letter. Your goal is to guarantee identification of the hidden word in the worst case. Return the minimum number of letter guesses needed if you choose guesses optimally and the host responds adversarially. You may assume the word is identified once only one candidate word remains consistent with all revealed patterns.

Quick Answer: This question evaluates algorithmic problem-solving, combinatorial reasoning, and adversarial information-theoretic thinking by requiring modeling of worst-case query strategies for adaptive letter-guessing.

Related Interview Questions

  • Return all files under a path - Dropbox (medium)
  • Build a hit/miss word guessing game - Dropbox (medium)
  • Implement feedback for word guessing game - Dropbox (medium)
  • Implement hierarchical folder access check - Dropbox (medium)
  • Review checkout code for defects and privacy - Dropbox (Medium)
Dropbox logo
Dropbox
Jan 25, 2026, 12:00 AM
Software Engineer
Onsite
Coding & Algorithms
4
0

You are given a set of distinct lowercase words, all of the same length. A hidden word is chosen from this set, but the host is adversarial: after each of your letter guesses, the host may switch to any other word in the set as long as it remains consistent with every answer revealed so far.

On each turn, you guess one lowercase letter that you have not guessed before. The host then reveals the pattern for that letter with respect to some currently valid hidden word: every matching position is shown, or the host may report that the letter does not appear if there exists a consistent word without that letter.

Your goal is to guarantee identification of the hidden word in the worst case. Return the minimum number of letter guesses needed if you choose guesses optimally and the host responds adversarially.

You may assume the word is identified once only one candidate word remains consistent with all revealed patterns.

Submit Your Answer to Earn 20XP

Sign in to leave a comment

Loading comments...

Browse More Questions

More Coding & Algorithms•More Dropbox•More Software Engineer•Dropbox Software Engineer•Dropbox Coding & Algorithms•Software Engineer Coding & Algorithms
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.