5
\$\begingroup\$

Question Description:

Given a list of companies, eg {ABC, BBC} and a large list of data looks like below:

Timestamp Security
10000000  IBM
10000001  Apple
10000005  PEAR
10000008  ABC
10000012  BBC

Find minimum time range where you can find all companies from list above.

My solution works and is brute force. But it has 3 loops. Can someone point out some ways to improve this solution in terms of runtime?

import java.util.*;

public class MinimumTimeRange {
    public static int findMinimumTimeRange(String [] list, String [] input){
        int n = list.length;
        Set<String> mySet = new HashSet<String>(Arrays.asList(list));
        int result = Integer.MAX_VALUE;
        for(int i=0; i<=(input.length-n);i++){
            for(int idx =n; idx<=(input.length-i);idx++){
                int [] timeList = new int [idx];
                Set<String> compSet = new HashSet<String>();
                for(int j=0;j<idx;j++){

                    String[] tokens = input[i+j].split(" ");
                    String time = tokens[0];
                    String comp = tokens[1];
                    timeList[j]=Integer.parseInt(time);
                    compSet.add(comp);
                }
                if(compSet.containsAll(mySet)&& (timeList[idx-1]-timeList[0])<result){
                    result = timeList[idx-1]-timeList[0];
                }
            }

        }
        return result;
    }
    public static void main(String[] args){
        String [] listCompanies = {"IBM","GE","GOOGLE"};
        String [] input = {
                "10000000 IBM",
                "10000001 Apple",
                "10000005 GOOGLE",
                "10000012 IBM",
                "10000013 TEST",
                "10000014 GE"
        };
        System.out.println(findMinimumTimeRange(listCompanies, input));
    }
}

Above code output 9, which is correct.

Other test examples:

String [] listCompanies = {"ABC","APPLE"};
String [] input = {
                    "1 ABC",
                    "2 TEST",
                    "3 APPLE",
                    "4 BBC",
                    "12 APPLE",
                    "13 ABC"
            };

Output: 1

\$\endgroup\$
4
  • \$\begingroup\$ Are you trying to build the sorting algorithm yourself, or are you looking for a quick way to sort it? \$\endgroup\$ Jul 31, 2017 at 22:14
  • \$\begingroup\$ hi, it's not a sort. the first column is Time, so it's trying to search for a range of time that those string in listCompanies appeared. \$\endgroup\$
    – Angela P
    Jul 31, 2017 at 22:16
  • \$\begingroup\$ So the input is always expected to be sorted in time? \$\endgroup\$ Jul 31, 2017 at 23:13
  • \$\begingroup\$ @PanayiotisPoularakis yes \$\endgroup\$
    – Angela P
    Jul 31, 2017 at 23:51

1 Answer 1

2
\$\begingroup\$

This can be reduced to a common problem : smallest range containing elements from k lists.

Assuming \$N\$ is the number of inputs and \$M\$ the number of companies in listCompanies.

In your problem, what you would do is make a set from your listCompanies (\$M \log M\$). Make a map where the keys are those companies and the values are lists (\$M \log M\$). Then, loop your input and if it's a company of interest (it has a key on the map), add that time to the list of that company.

So in your first example, IBM would be [10000000, 10000012]. After you have done this, you have now the common problem of finding the minimum range in which you can have one item from each of those lists (minimum range that has each of your companies in listCompanies).

You can then apply the algorithm linked and end up with a complexity of (\$N \log M\$ -> each element will enter and leave a heap of size \$M\$ only once). \$N\$ in this case will be the amount of inputs that are related to companies from your listCompanies.

Here is a C++ implementation.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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