TIP102 Unit 7 Session 1 Advanced (Click for link to problem statements)
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:
1st building.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.2 starting from the building immediately clockwise of the building that was just sunk and repeat.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?
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.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:
Plan the solution with appropriate visualizations and pseudocode.
General Idea:
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
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) % nReview the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.
find_last_building function with the input n = 5, k = 2. The function should return 3 after correctly eliminating the buildings in sequence.n = 1, k = 1. The function should return 1, correctly identifying the only building as the last one standing.Evaluate the performance of your algorithm and state any strong/weak or future potential work.
O(N), where N is the number of buildings. The function makes a recursive call for each building, leading to a linear time complexity.O(N), due to the recursion stack. The depth of recursion is proportional to the number of buildings.