Last Building Standing - codepath/compsci_guides GitHub Wiki

TIP102 Unit 7 Session 1 Advanced (Click for link to problem statements)

Problem 3: Last Building Standing

In Atlantis, buildings are arranged in concentric circles. The Greek gods have become unhappy with Atlantis, and have decided to punish the city by sending floods to sink certain buildings into the ocean.

Assume there are n buildings in a circle numbered from 1 to n in clockwise order. Moving clockwise from the ith building brings you to the (i+1)th building for 1 <= i < n, and moving clockwise from the nth building brings you to the 1st building.

The gods are sinking buildings as follows:

  1. Start with the 1st building.
  2. Count the next k buildings in the clockwise direction including the building you started at. The counting wraps around the circle and may count some buildings more than once.
  3. The last building counted sinks and is removed from the circle.
  4. If there is still more than one building standing in the circle, go back to step 2 starting from the building immediately clockwise of the building that was just sunk and repeat.
  5. Otherwise, return the last building standing.

Problem Highlights

  • 💡 Difficulty: Medium
  • ⏰ Time to complete: 20-30 mins
  • 🛠️ Topics: Recursion, Circular Data Structures

1: U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

  • Established a set (2-3) of test cases to verify their own solution later.
  • Established a set (1-2) of edge cases to verify their solution handles complexities.
  • Have fully understood the problem and have no clarifying questions.
  • Have you verified any Time/Space Constraints for this problem?
  • Q: What is the main task in this problem?
    • A: The task is to determine the last building standing after sequentially removing buildings in a circular pattern.
  • Q: How does the circular pattern work?
    • A: Buildings are removed in a circular manner where counting wraps around the circle, and the last building standing is the result.
HAPPY CASE
Input: n = 5, k = 2
Output: 3
Explanation: Buildings are removed in this order: 2, 4, 1, 5, leaving building 3 as the last one standing.

Input: n = 6, k = 5
Output: 1
Explanation: Buildings are removed in this order: 5, 4, 6, 2, 3, leaving building 1 as the last one standing.

EDGE CASE
Input: n = 1, k = 1
Output: 1
Explanation: With only one building, it remains standing.

2: M-atch

Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.

For Finding the Last Building Standing, we want to consider the following approaches:

  • Recursive Elimination: This problem is a variation of the well-known "Josephus problem," where recursive elimination is used to determine the last remaining element in a circle.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea:

  • The problem can be solved using a recursive approach, where the base case is when there is only one building left. In each recursive step, eliminate one building and reduce the problem size.

Recursive Approach:

1) Define a helper function `find_last_building_helper(n, k)`:
    a) Base case: If `n` is 1, return 0 (the last building standing is at position 0 in 0-based indexing).
    b) Recursive case: Return `(find_last_building_helper(n - 1, k) + k) % n`, which gives the position of the last building standing when there are `n` buildings.
2) In the main function `find_last_building(n, k)`, adjust the result from the helper function to be 1-based by adding 1.

⚠️ Common Mistakes

  • Forgetting to adjust for 1-based indexing when returning the final result.
  • Misunderstanding the circular counting logic, leading to incorrect elimination sequences.

4: I-mplement

Implement the code to solve the algorithm.

def find_last_building(n, k):
    return find_last_building_helper(n, k) + 1  # Adjust for 1-based indexing

def find_last_building_helper(n, k):
    if n == 1:
        return 0  # Base case: the last building standing is at position 0 (0-based index)
    
    return (find_last_building_helper(n - 1, k) + k) % n

5: R-eview

Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.

  • Trace through the find_last_building function with the input n = 5, k = 2. The function should return 3 after correctly eliminating the buildings in sequence.
  • Test the function with edge cases like n = 1, k = 1. The function should return 1, correctly identifying the only building as the last one standing.

6: E-valuate

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

Time Complexity:

  • Time Complexity: O(N), where N is the number of buildings. The function makes a recursive call for each building, leading to a linear time complexity.
  • Space Complexity: O(N), due to the recursion stack. The depth of recursion is proportional to the number of buildings.

Discussion:

  • This recursive approach is an elegant solution to the Josephus problem, effectively determining the last building standing by simulating the elimination process.
  • While the recursive approach is straightforward, an iterative approach could be explored to reduce the space complexity by avoiding the recursion stack.