I've been trying to get better at writing algorithms and came across a problem that was something like this:
Given a list of words:
search_list = ["this", "is", "an", "issue"]
Find the closest occurrences of all of these words in another list, and return the first occurrence and last occurrence:
given_list = ["this", "tv", "is", "an", "state", "node", "is", "this", "issue", "issue", "an"]
Given these two lists, the correct result would be
[6, 10], because the closest occurrences of the
search_list, would start with the
"is" at index 6, and finish with
"an", at index 10.
Having said that, here are more details:
closest occurrences - definition
closest occurrence is the smallest subset of
given_list in which all of the words occur. By "smallest subset", I simply mean the smallest absolute difference between the smallest occurring index, and the largest occurring index.
search_list - a list or set of words that will only contain unique words. Again, no repeating words will be in this input parameter. This is the set of words that will be used to search given_list to find the shortest/closest subset or occurrences of.
given_list - a list or array of words that may contain duplicate words. This is the list that we need to find the smallest/closest subset of
Find the closest occurrences of all of these words in another list, and return the first occurrence and last occurrence.
Here is what I've tried so far: To start, I thought it'd be helpful to find all of the occurrences of each word.
def find_sub_list(search_list, given_list): result_list =  for value in search_list: inner_list = [i for i, val in enumerate(given_list) if val == value] result_list.append(inner_list) return result_list
Given the variables above, this would result in:
[[0, 7], [2, 6], [3, 10], [8, 9]]
From these results, the correct answer would be
[6, 10], because 4 is the shortest distance in which the words occur. However, I can't seem to find a better way to find the closest occurrences without checking every possible outcome. Is there a particular data structure that would make this process faster?
To further define "closest occurrences", I'll give an example.
search_list = ["one", "two", "three"] given_list = ["one", "black", "two", "blue", "three", "green", "two", "three"]
The correct answer in this case would be [0, 4]. "two" and "three" occur at indices 6 and 7. However, "one" occurs at index 0, and "two" and "three"'s also occurs at 2 and 4. This subset with indices 0, 2, 4 is a smaller or closer subset than that of 0, 6, 7. Hopefully that makes more sense?
search_listcannot have repeating words. Items must be unique.