TIP102 Unit 3 Session 2 Advanced (Click for link to problem statements)
Understand what the interviewer is asking for by using test cases and questions about the problem.
artifacts
, representing the strengths of magical artifacts, and an integer k
, representing the number of strongest artifacts to return.k
magical artifacts based on their strength relative to the median of the artifacts.Plan the solution with appropriate visualizations and pseudocode.
General Idea: First, determine the median of the artifacts. Then, use a two-pointer approach to select the strongest k
artifacts by comparing the absolute differences of the artifact strengths from the median.
1. Sort the `artifacts` array to determine the median.
2. Calculate the median as the middle element of the sorted array.
3. Initialize two pointers: `left` at the start of the array and `right` at the end of the array.
4. Initialize an empty list `strongest` to store the `k` strongest artifacts.
5. While the list `strongest` contains fewer than `k` artifacts:
1. Compare the absolute difference between `artifacts[left]` and the median with the absolute difference between `artifacts[right]` and the median.
2. If the difference for `artifacts[right]` is greater or equal, append `artifacts[right]` to the `strongest` list and move the `right` pointer left.
3. Otherwise, append `artifacts[left]` to the `strongest` list and move the `left` pointer right.
6. Return the `strongest` list as the result.
⚠️ Common Mistakes
def get_strongest_artifacts(artifacts, k):
# Step 1: Sort the artifacts to find the median
artifacts.sort()
n = len(artifacts)
median = artifacts[(n - 1) // 2]
# Step 2: Use two pointers to find the k strongest artifacts
left, right = 0, n - 1
strongest = []
while len(strongest) < k:
if abs(artifacts[right] - median) >= abs(artifacts[left] - median):
strongest.append(artifacts[right])
right -= 1
else:
strongest.append(artifacts[left])
left += 1
return strongest
# Example usage
print(get_strongest_artifacts([1, 2, 3, 4, 5], 2)) # Output: [5, 1]
print(get_strongest_artifacts([1, 1, 3, 5, 5], 2)) # Output: [5, 5]
print(get_strongest_artifacts([6, 7, 11, 7, 6, 8], 5)) # Output: [11, 8, 6, 6, 7]