Counting Vibranium Deposits - codepath/compsci_guides GitHub Wiki

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

Problem 7: Counting Vibranium Deposits

In Wakanda, vibranium is the most precious resource, and it is found in several deposits. Each deposit is represented by a character in a string (e.g., "V" for vibranium, "G" for gold, etc.)

Given a string resources, write a recursive function count_deposits() that returns the total number of distinct vibranium deposits in resources.

Problem Highlights

  • 💡 Difficulty: Easy
  • ⏰ Time to complete: 10-15 mins
  • 🛠️ Topics: Recursion, String Processing

1: U-nderstand

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

  • Q: What is the main task in this problem?
    • A: The task is to count the number of distinct 'V' characters in the string resources using recursion.
  • Q: Can we use iteration or should the solution be purely recursive?
    • A: The solution should be purely recursive as per the problem statement.
HAPPY CASE
Input: "VVVVV"
Output: 5
Explanation: There are five 'V' characters in the string.

Input: "VXVYGA"
Output: 2
Explanation: There are two 'V' characters in the string.

EDGE CASE
Input: "
Output: 0
Explanation: The string is empty, so the count is 0.

Input: "GXGXA"
Output: 0
Explanation: There are no 'V' characters in the string.

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 Counting Specific Characters, we want to consider the following approaches:

  • Recursive Character Counting: Count the 'V' characters by checking each character recursively and adding to the count if it matches 'V'.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea:

  • Use recursion to traverse the string. If the first character is 'V', add 1 to the count and recurse on the rest of the string. If not, just recurse on the rest of the string without adding to the count.

Recursive Approach:

1) Base case: If the string `resources` is empty, return 0.
2) Recursive case:
   a) If the first character of `resources` is 'V', return 1 plus the result of the recursive call on the rest of the string.
   b) If the first character is not 'V', return the result of the recursive call on the rest of the string.

⚠️ Common Mistakes

  • Not handling the empty string as the base case, which can lead to an infinite recursion loop.
  • Incorrectly checking or processing characters, leading to missed 'V' counts.

4: I-mplement

Implement the code to solve the algorithm.

def count_deposits(resources):
    if not resources:
        return 0
    elif resources[0] == 'V':
        return 1 + count_deposits(resources[1:])
    else:
        return count_deposits(resources[1:])

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 count_deposits function with the input "VVVVV". The function should return 5 after five recursive calls.
  • Trace through the function with the input "VXVYGA". The function should return 2 after recursively counting the 'V' characters.

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 length of the string. The function makes one recursive call per character, leading to linear time complexity.
  • Space Complexity: O(N) due to the recursion stack. The depth of recursion is proportional to the length of the string, leading to linear space usage.