2
$\begingroup$

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.

allowed inputs

1) 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. 2) 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 search_list in.

expected output

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?

Edit

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?

Other notes:

  • search_list cannot have repeating words. Items must be unique.
$\endgroup$
  • 3
    $\begingroup$ The meaning of 'closest occurrence' isn't very clear. Do you want to find the minimum size range in a list such that all given elements occur at least once in this range? Can there be duplicates in 'search_list' and if so, must the range contain at least as many elements as in the search_list? $\endgroup$ – Discrete lizard Jan 3 '18 at 16:54
  • 1
    $\begingroup$ I've updated the question to answer your questions. $\endgroup$ – Angel Carlisle Jan 3 '18 at 17:29
  • 1
    $\begingroup$ Your examples seems contradictory. In the first example, why isn't it [0,2,3,8]? Please specify the problem properly. That is, what are allowed inputs, and what is the expected output given an arbitrary (allowed) input? $\endgroup$ – Raphael Jan 3 '18 at 17:56
  • 1
    $\begingroup$ Wow - I really messed that up. Apologies. I've updated the examples and will go back through and add your suggestions. $\endgroup$ – Angel Carlisle Jan 3 '18 at 19:50
  • $\begingroup$ An example is not a substitute for a clear specification of the problem, so no, editing to add an example doesn't suffice to clear this up. I'd still like to see a clear specification of what the output should be, with all terms defined. The term "closest occurrences" is never defined. $\endgroup$ – D.W. Jan 4 '18 at 7:11
1
$\begingroup$

Go over the list, and maintain the last occurrence of each word in the search list. Whenever you find a word in the search list, find the minimum last occurrence among all other words in the search list - this gives you a candidate closest occurrence, which you take note of if it's the best seen so far. In the end, return the best closest occurrence observed.

To execute this algorithm efficiently, you need an efficient array-like data structure which supports the following operations:

  • Change the value of item $i$.
  • Return the minimum value of all items other than item $i$.

When the search list is very short, you can just use an array. For large search lists, you can probably use a modified heap to support all of these operations in $O(\log m)$ time, where $m$ is the size of the search list. The end result is an $O(n\log m)$ algorithm, where $n$ is the size of the main list.

$\endgroup$
1
$\begingroup$

Here's a simple algorithm.

  1. For each word $w$ in search_list,
    1. find the left-most occurrence of $w$ in given_list and label all entries to the right with $\leftarrow_w$, and
    2. find the right-most occurrence of $w$ in given_list and label all entries to the left of it with $\rightarrow_w$.
  2. Find the right-most entry $l$ that is labelled with all $\rightarrow_w$.
  3. Find the left-most entry $r$ that is labelled with all $\leftarrow_w$.

You can implement the labels as bitmask; assuming you can manipulate bits and compare the whole masks in constant time, this algorithm runs in time $\Theta(mn)$, with $n$ and $m$ be the number of elements in the two lists.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.