Optimize Search for Massive Data | Dataford Interview Questions

How would you optimize a search algorithm for a massive dataset with high latency?

Implement a two-level search over ordered, non-empty sorted shards. First identify the only shard that could contain target, then binary-search within that shard. Return the shard and element indices, or [-1, -1] when the value is absent.

Function: search_shards(shards, target). shards is a list of sorted integer lists whose value ranges do not overlap and are ordered by value.

Constraints

1 <= len(shards) <= 10^6
Each shard is non-empty and sorted in strictly increasing order
The value ranges of shards do not overlap
Shards are ordered by increasing value range
The total number of values is at most 10^7
-10^9 <= target <= 10^9

Function Signature

def search_shards(shards, target):

Your question is Optimize Search for Massive Data. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem

How would you optimize a search algorithm for a massive dataset with high latency?

Function: search_shards(shards, target). shards is a list of sorted integer lists whose value ranges do not overlap and are ordered by value.

Constraints

1 <= len(shards) <= 10^6
Each shard is non-empty and sorted in strictly increasing order
The value ranges of shards do not overlap
Shards are ordered by increasing value range
The total number of values is at most 10^7
-10^9 <= target <= 10^9

Function Signature

def search_shards(shards, target):

Your question is Optimize Search for Massive Data. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.