Find the Nearest Target Character and Support Streaming Updates

Question

The candidate is asked to implement a function that finds the nearest target character in a string, while also supporting streaming updates to the string.

Codemia · Accepted Answer

To solve the problem of finding the nearest target character, we can maintain a list of indices for the target character as we process the string. When a character is updated, we will adjust this list accordingly. This allows us to efficiently find the nearest target character using binary search.

1. Initialize an empty list to store indices of the target character.
2. Iterate through the string to populate this list.
3. For each update, check if the updated character affects the target indices list.
4. Use binary search to find the nearest index of the target character for any query.

Here is a sample implementation in Python:
```python
class NearestTarget:
    def __init__(self, s: str, target: str):
        self.s = list(s)
        self.target = target
        self.indices = [i for i, char in enumerate(self.s) if char == target]

def update(self, index: int, char: str):
        if self.s[index] == self.target and char != self.target:
            self.indices.remove(index)
        elif self.s[index] != self.target and char == self.target:
            self.indices.append(index)
        self.s[index] = char

def nearest(self, index: int) -> int:
        if not self.indices:
            return -1
        # Binary search to find the nearest target
        left, right = 0, len(self.indices) - 1
        while left < right:
            mid = (left + right) // 2
            if self.indices[mid] < index:
                left = mid + 1
            else:
                right = mid
        # Check the closest index
        return self.indices[left] if abs(self.indices[left] - index) < abs(self.indices[left - 1] - index) else self.indices[left - 1]
```

The time complexity for the update operation is O(n) in the worst case, where n is the length of the string, due to the need to update the indices list. The nearest query operation runs in O(log m), where m is the number of occurrences of the target character, due to the binary search.

Consider edge cases such as:
- The target character does not exist in the string.
- The string is empty.
- Updates that change the target character to another character.
Handling these cases ensures the robustness of the solution.

Find the Nearest Target Character and Support Streaming Updates

Snowflake

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Approach

Algorithm

Submit Your Answer

Snowflake Software Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string