Hunny Hunt - codepath/compsci_guides GitHub Wiki

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

Problem Highlights

• 💡 Difficulty: Easy
• ⏰ Time to complete: 5 mins
• 🛠️ Topics: Lists, Linear Search, Iteration

U-nderstand

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

• Q: What is the input to the function?

  • A: The input is a list items and a target value that needs to be found in the list.

• Q: What is the expected output of the function?

  • A: The function should return the first index of target in the list items, and -1 if target is not found.

• Q: Are there any constraints or special conditions?

  • A: The function should not use any built-in functions and should handle all types of elements that might be in the list.

• Q: What if the list is empty?

  • A: If the list is empty, the function should return -1.

• The function linear_search() should take a list of items and a target value, returning the first index of target in items. If target is not found, it should return -1. Built-in functions should not be used.

HAPPY CASE
Input: items = ['haycorn', 'haycorn', 'haycorn', 'hunny'], target = 'hunny'
Expected Output: 3

Input: items = ['bed', 'blue jacket', 'red shirt', 'hunny'], target = 'red balloon'
Expected Output: -1

EDGE CASE
Input: items = [], target = 'hunny'
Expected Output: -1

Input: items = ['hunny'], target = 'hunny'
Expected Output: 0

P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Use a ranged for loop to iterate through the list, checking each element against the target.

1. Define the function `linear_search(items, target)`.
2. Iterate through the list using a ranged for loop based on the length of `items`.
3. For each index, check if the current element matches the target.
4. If a match is found, return the index.
5. If the loop completes without finding a match, return -1.

⚠️ Common Mistakes

• Forgetting to handle the case of an empty list.
• Not returning the index for the first occurrence of the target.

I-mplement

Implement the code to solve the algorithm.

def linear_search(items, target):
    # Iterate through the list with a ranged for loop
    for index in range(len(items)):
        # Check if the current element matches the target
        if items[index] == target:
            return index  # Return the index if target is found
    # If target is not found, return -1
    return -1