Search and rescue assistance in Drone Programming - Time & Space Complexity

Time Complexity: Search and rescue assistance

O(n)

Understanding Time Complexity

When drones assist in search and rescue, they often scan areas to find targets. Understanding how the time to complete this search grows as the area or number of targets grows is important.

We want to know how the drone's work changes when the search area or number of points to check increases.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function searchArea(points, target) {
  for (let i = 0; i < points.length; i++) {
    if (points[i] === target) {
      return i
    }
  }
  return -1
}
    

This code checks each point in the search area one by one to find the target. It stops when it finds the target or finishes checking all points.

Identify Repeating Operations

• Primary operation: Looping through the list of points to check each one.
• How many times: Up to once for each point in the list, until the target is found or all points are checked.

How Execution Grows With Input

As the number of points grows, the drone may need to check more points to find the target.

Input Size (n)	Approx. Operations
10	Up to 10 checks
100	Up to 100 checks
1000	Up to 1000 checks

Pattern observation: The number of checks grows roughly in direct proportion to the number of points.

Final Time Complexity

Time Complexity: O(n)

This means the time to find the target grows linearly with the number of points to check.

Common Mistake

[X] Wrong: "The search always takes the same time no matter how many points there are."

[OK] Correct: The drone may find the target early sometimes, but in the worst case it must check every point, so time grows with the number of points.

Interview Connect

Understanding how search time grows helps you explain how drones handle bigger areas or more targets. This skill shows you can think about real-world problems clearly.

Self-Check

"What if the points were sorted and the drone used a faster search method? How would the time complexity change?"

Practice

1. What is the main purpose of a drone programmed for search and rescue assistance?

easy

A. To find missing persons and send their location quickly

B. To deliver packages to remote areas

C. To take aerial photos for tourism

D. To monitor weather patterns

Solution

1. Step 1: Understand the role of search and rescue drones

   These drones are designed to locate missing people or targets in emergency situations.

2. Step 2: Identify the key function

   The main function is to find and report the location quickly to help rescue teams.

3. Final Answer:

   To find missing persons and send their location quickly -> Option A

4. Quick Check:

   Search and rescue = find and report location [OK]

Hint: Search and rescue drones find and report targets fast [OK]

Common Mistakes:

• Confusing delivery drones with rescue drones
• Thinking drones only take photos
• Assuming drones monitor weather in rescue missions

2. Which of the following is the correct syntax to start a drone's search function in drone programming?

easy

A. startSearch()

B. search.start()

C. begin_search

D. searchStart[]

Solution

1. Step 1: Identify correct function call syntax

   Functions are called with parentheses like startSearch().

2. Step 2: Check other options for syntax errors

   search.start() is method call but not standard here; begin_search lacks parentheses; searchStart[] uses brackets incorrectly.

3. Final Answer:

   startSearch() -> Option A

4. Quick Check:

   Function calls use parentheses () [OK]

Hint: Function calls always use parentheses () [OK]

Common Mistakes:

• Omitting parentheses when calling functions
• Using brackets [] instead of parentheses
• Confusing method call syntax with function call

3. What will the following drone program output if the target is found at coordinates (10, 20)?

def search_area():
    target = (10, 20)
    found = True
    if found:
        return f"Target located at {target}"
    else:
        return "Target not found"

print(search_area())

medium

A. Target not found

B. Error: target undefined

C. Target located at (10, 20)

D. None

Solution

1. Step 1: Analyze the function logic

   The variable found is True, so the if condition is met.

2. Step 2: Determine the returned string

   The function returns the string with the target coordinates formatted inside.

3. Final Answer:

   Target located at (10, 20) -> Option C

4. Quick Check:

   found=True returns target location string [OK]

Hint: If found is True, function returns location string [OK]

Common Mistakes:

• Assuming found is False and returning 'Target not found'
• Confusing tuple printing with string output
• Expecting an error due to variable scope

4. Identify the error in this drone search code snippet:

def scan_area():
    target_found = False
    if target_found = True:
        print("Target found!")
    else:
        print("Searching...")

scan_area()

medium

A. Function scan_area is not called

B. Missing parentheses in print statements

C. Variable target_found is not defined

D. Using assignment '=' instead of comparison '==' in if condition

Solution

1. Step 1: Check the if condition syntax

   The condition uses '=' which assigns value, but it should compare using '=='.

2. Step 2: Verify other parts of the code

   Print statements have parentheses, function is called, and variable is defined correctly.

3. Final Answer:

   Using assignment '=' instead of comparison '==' in if condition -> Option D

4. Quick Check:

   Use '==' for comparison in if statements [OK]

Hint: Use '==' to compare, '=' is for assignment [OK]

Common Mistakes:

• Confusing '=' with '==' in conditions
• Forgetting to call the function
• Missing parentheses in print (Python 3)

5. You want a drone to scan multiple zones and report all found targets with their locations. Which code snippet correctly collects and returns all found targets in a dictionary with zone names as keys? Options: A)

def scan_zones(zones):
    results = {}
    for zone in zones:
        found = scan(zone)
        if found:
            results[zone] = found
    return results

B)

def scan_zones(zones):
    results = []
    for zone in zones:
        found = scan(zone)
        if found:
            results.append({zone: found})
    return results

C)

def scan_zones(zones):
    results = {}
    for zone in zones:
        found = scan(zone)
        results[zone] = found
    return results

D)

def scan_zones(zones):
    results = {}
    for zone in zones:
        if scan(zone):
            results.append(zone)
    return results

hard

A. Collects found targets in a list of dictionaries, not a single dict

B. Collects found targets in a dictionary with zone keys correctly

C. Adds all zones including those without targets (found may be False)

D. Uses append on a dictionary, which causes an error

Solution

1. Step 1: Understand the goal

   We want a dictionary with zones as keys and found targets as values, only if found.

2. Step 2: Analyze each option

   The snippet that adds only found targets to a dict is correct; the one that uses a list of dicts produces the wrong structure; the one that adds all zones includes those without targets; the one that tries to append to a dict causes an error.

3. Final Answer:

   Collects found targets in a dictionary with zone keys correctly -> Option B

4. Quick Check:

   Dict with keys for found targets only = Collects found targets in a dictionary with zone keys correctly [OK]

Hint: Use dict and add only found targets with keys [OK]

Common Mistakes:

• Adding all zones even if no target found
• Using list instead of dictionary for key-value pairs
• Trying to append to a dictionary (invalid)