Unit 7 Session 1 (Click for link to problem statements)
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: "hello"
Output: 5
Explanation: The string "hello" has 5 characters.
EDGE CASE
Input: "
Output: 0
Explanation: An empty string has 0 characters.
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.
This problem is a fundamental example of using recursion to solve simple computational problems:
Plan the solution with appropriate visualizations and pseudocode.
General Idea: Write a recursive function to calculate the length of a string by processing one character at a time.
1) Base Case: If the string is empty, return 0.
2) Recursive Case: Return 1 plus the recursive call for the substring starting from the second character.
⚠️ Common Mistakes
Implement the code to solve the algorithm.
def string_length(s):
if s == ":
return 0
else:
return 1 + string_length(s[1:])
Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.
Evaluate the performance of your algorithm and state any strong/weak or future potential work.
O(n)
where n
is the length of the string, since each recursive call processes one character.O(n)
due to the recursion stack depth, which grows linearly with the length of the string.