Get Rank - codepath/compsci_guides GitHub Wiki

Unit 5 Session 1 (Click for link to problem statements)

TIP102 Unit 5 Session 1 Standard (Click for link to problem statements)

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

Problem Highlights

  • 💡 Difficulty: Medium
  • ⏰ Time to complete: 10-15 mins
  • 🛠️ Topics: Classes, Linked List, Recursion

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?
  • What is the task?
    • Implement a function get_place() to determine the position of a player in the race based on how many players are ahead of them.
HAPPY CASE
Input: my_player = Player("Luigi", "Super Blooper", mario)
Output: 3
Explanation: Luigi is third in the race, with Mario and Peach ahead of him.

EDGE CASE
Input: my_player = Player("Peach", "Daytripper")
Output: 1
Explanation: Peach is first in the race, with no one ahead of her.

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 linked-list-like traversal problems, we want to consider the following approaches:

  • Iteratively move through the ahead links until reaching the player at the front.
  • Count the number of steps taken to determine the rank.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Traverse through the linked list structure by following the ahead attribute and counting the number of players ahead of my_player.

1) Create a function `get_place(my_player)` that initializes `place` to 1.
2) Set `current` to `my_player`.
3) While `current.ahead` is not None, increment `place` by 1 and move `current` to `current.ahead`.
4) Return `place` after the loop.

⚠️ Common Mistakes

  • Forgetting to initialize place to 1 since the player is at least in some position.
  • Not correctly traversing the ahead links.

4: I-mplement

Implement the code to solve the algorithm.

def get_place(my_player):
    place = 1  # Start counting from 1 as the player is at least in some place
    current = my_player
    while current.ahead:
        place += 1
        current = current.ahead
    return place

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 your code with the following input:

  • my_player = luigi
  • Verify that the output is 3 since Luigi has two players ahead of him.
  • my_player = peach
  • Verify that the output is 1 since Peach has no one ahead of her.

6: E-valuate

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

  • Time Complexity: O(N) where N is the number of players ahead of my_player.
  • Space Complexity: O(1) as we only use a few variables to store state during the traversal."