FastPrepLast Person Left in a Counting Circle
Problems/Last Person Left in a Counting Circle

Last Person Left in a Counting Circle

Expedia logoExpedia● MediumINTERNONSITE INTERVIEW

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: A post from December 2020 about Expedia's September 2019 campus hiring for interns names this task in its second technical interview and links an article on it. The round also pushed for faster solutions.

The post itself gives no rules, examples or limits. Here, people are numbered from 1. Counting starts at person 1 and counts that person as 1. The k-th person counted leaves, and you return the number of the last person left. With n up to 1,000,000 and k up to 10^9, removing people one at a time from a list is too slow, so a linear method is needed.

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

There are n people standing in a circle, numbered 1 to n clockwise. After person n comes person 1 again.

The game goes like this:

  1. Start at person 1.
  2. Count k people clockwise, counting the person you start at as 1. The count wraps around the circle as many times as needed.
  3. The k-th person counted leaves the circle.
  4. If more than one person is left, start again at the person just clockwise of the one who left, and go back to step 2.

Return the number of the last person left in the circle.

Function

findTheWinner(n: int, k: int) → int

Examples

Example 1

n = 7k = 4return = 2

Counting starts at person 1. The 4th person counted each time leaves: 4, then 1 (counting 5, 6, 7, 1), then 6, then 5, then 7, then 3. Person 2 is left.

Example 2

n = 3k = 5return = 1

k can be larger than the circle. Counting 1, 2, 3, 1, 2 makes person 2 leave. Counting goes on from person 3: 3, 1, 3, 1, 3, so person 3 leaves and person 1 is left.

Example 3

n = 8k = 1return = 8

With k = 1, the first person counted always leaves, so people leave in order 1, 2, 3, ..., 7 and person 8 is left.

Constraints

  • 1 <= n <= 10^6
  • 1 <= k <= 10^9

More Expedia Onsite Interview questions

  • Scramble StringONSITE INTERVIEW · Seen Sep 2026
  • Smallest Sufficient TeamONSITE INTERVIEW · Seen Sep 2026
  • Check Anagram Pairs Index by IndexONSITE INTERVIEW · Seen Oct 2025
  • Fresh Oranges Left After Rotting StopsONSITE INTERVIEW · Seen Oct 2025
  • Longest Increasing SubsequenceONSITE INTERVIEW · Seen Oct 2025
  • Lowest Common Ancestor with Repeated and Missing ValuesONSITE INTERVIEW · Seen Oct 2025
  • Shortest Substring with Exactly K OnesONSITE INTERVIEW · Seen Oct 2025
  • Middle Element of a Linked ListONSITE INTERVIEW · Seen Nov 2024
  • Minimum in a Rotated Sorted ArrayONSITE INTERVIEW · Seen Sep 2024
  • Mirror Image Binary TreesONSITE INTERVIEW · Seen Sep 2024

Similar questions at other companies

  • Path Between Two Nodes of a Fibonacci TreeDatabricks · ONSITE INTERVIEWDatabricks interview questions
  • Babysitter Quote with Hourly RatesUpstart · ONSITE INTERVIEWUpstart interview questions
  • Expected Value of Modified DiceJane Street · ONSITE INTERVIEWJane Street interview questions
  • Fractional Share Inventory FlatteningRobinhood · PHONE SCREEN · ONSITE INTERVIEWRobinhood interview questions
  • Merge Sort Report with a Noisy ComparatorMercor · ONSITE INTERVIEWMercor interview questions
  • Reservoir Sampling with Recorded DrawsMeta · ONSITE INTERVIEWMeta interview questions
  • Group-Relative Policy AdvantagesAmazon · ONSITE INTERVIEW
  • Reservoir Sampling with Recorded DrawsStackAdapt · ONSITE INTERVIEWStackAdapt interview questions
  • Iterate Canonical IPv6 AddressesOpenAI · ONSITE INTERVIEWOpenAI interview questions
  • Nth Staged License PlateGoogle · ONSITE INTERVIEWGoogle interview questions

Expedia interview experiences

  • Expedia Intern Final Round in 2021: 28 Experiences (Part 4 of 6)
  • Expedia Intern Finals Before 2020: 14 Experiences (Part 6 of 6)
  • Expedia Intern Final Round in 2020: 24 Experiences (Part 5 of 6)
  • Expedia Intern Final Round in 2022: 15 Experiences (Part 3 of 6)
  • Expedia Intern Final Round in 2023: 17 Experiences (Part 2 of 6)
  • Expedia SWE Intern Final Round: 126 Experiences (Part 1 of 6)
All Expedia interview questionsSee Expedia hiring insights
Saved
class Solution {
    public int findTheWinner(int n, int k) {
        // Write your code here.
    }
}
Checking account…