У меня есть постановка задачи, которая должна реализовать некоторую структуру данных, которая в свою очередь реализует две функции

Question

Безопасность сопоставляется с категорией активов. За определенный период времени безопасность может перейти в другую категорию. Ниже приведена таблица, например,

Security   Asset_category     Start_date   End_date
-----------------------------------------------------
aalp       US_LARGE_CAP       1/1/2015     2/17/2015
aalp       US_LARGE_GROWTH    2/18/2015    3/16/2015

Я должен реализовать две функции

fetchAssetCategory(String security , Date inputDate) 

Будет возвращено имя категории актива, которое присутствовало для обеспечения безопасности на тот момент

validateSecurity(String security , String assetCat , Date inputDate)

подтвердит безопасность в этот момент времени.

Пример ввода

fetchAssetCategory("aalp", "1/20/2015") : return : US_LARGE_CAP
validateSecurity("aalp", "US_LARGE_GROWTH", 2/17/2015) : return false

Приходится использовать структуру данных и упоминать сложность времени и пространства

Я пробовал с Hashmap, но застрял в середине

Любая помощь будет принята с благодарностью.

public String fetchAssetCategory(String security, Date inputDate) throws ParseException {
    // Approach-1
    SimpleDateFormat sdf = new SimpleDateFormat("MM/dd/yyyy");
    sdf.setLenient(false);
    /*
     * String date = sdf.format(inputDate); System.out.println(date);
     */

    ArrayList<Date> startDates = new ArrayList<>();
    startDates.add(sdf.parse("01/01/2015"));
    startDates.add(sdf.parse("02/18/2015"));
    startDates.add(sdf.parse("08/18/2015"));
    startDates.add(sdf.parse("03/17/2015"));
    startDates.add(sdf.parse("05/18/2015"));

    ArrayList<Date> endDates = new ArrayList<>();
    endDates.add(sdf.parse("02/17/2015"));
    endDates.add(sdf.parse("03/16/2015"));
    endDates.add(sdf.parse("12/15/2015"));
    endDates.add(sdf.parse("05/17/2015"));
    endDates.add(sdf.parse("08/17/2015"));

    ArrayList<Security> addRecords = new ArrayList<>();
    Security s1 = new Security("AAPL", "US LARGE CAP VALUE", startDates.get(0), endDates.get(0));
    Security s2 = new Security("AAPL", "US LARGE CAP GROWTH", startDates.get(1), endDates.get(1));
    Security s3 = new Security("AAPL", "US MID CAP VALUE", startDates.get(2), endDates.get(2));
    Security s4 = new Security("AAPL", "US LARGE CAP VALUE", startDates.get(3), endDates.get(3));
    Security s5 = new Security("AAPL", "US MID CAP GROWTH", startDates.get(4), endDates.get(4));
    addRecords.add(s1);
    addRecords.add(s2);
    addRecords.add(s3);
    addRecords.add(s4);
    addRecords.add(s5);

    for (int i = 0; i < addRecords.size(); i++) {
        if (security.equalsIgnoreCase(addRecords.get(i).getSecurity())
                && (inputDate.before(addRecords.get(i).getEndDate())
                        && inputDate.after(addRecords.get(i).getStartDate()))) {
            return (addRecords.get(i).getAssetCategory());
        }
    }

    return "";
}

public static void main(String args[]) {
    SecurityAssest sa = new SecurityAssest();
    try {
        SimpleDateFormat sdf = new SimpleDateFormat("MM/dd/yyyy");
        java.util.Date yourDate = sdf.parse("01/20/2015");
        sa.fetchAssetCategory("AAPL", yourDate);
    } catch (Exception e) {
        e.printStackTrace();
    }
}
}

Answer 1

Вы можете улучшить это, упорядочив список категорий, чтобы мы могли выполнить двоичный поиск, чтобы найти даты.Здесь предполагается, что для категорий для одной и той же ценной бумаги не существует перекрывающихся дат.

Для этого мы собираемся создать компаратор, который будет соответствовать любым категориям активов, которые имеют пересечение.

public class IntersectComparator implements Comparator<AssetCategory> {
    public int compare(AssetCategory l, AssetCategory r) {
        if (l.getEnd().isBefore(r.getStart())) {
            return -1;
        }
        if (r.getEnd().isBefore(l.getStart())) {
            return 1;
        }
        return 0;
    }
}

Это позволяет нам как вычислить позицию вставки, так и выполнить двоичный файлsearch.

public class AssetCategories {
    private final static Comparator<AssetCategory> COMPARATOR = new IntersectComparator();

    private Map<String, List<AssetCategory>> assets = new HashMap<>();

    public void add(AssetCategory assetCategory) {
        List<AssetCategory> categories = assets.computeIfAbsent(assetCategory.getAsset(), k -> new ArrayList<>());
        int insert = Collections.binarySearch(categories, assetCategory, COMPARATOR);
        if (insert >= 0) {
            throw new IllegalArgumentException("Asset category dates intersect with existing asset category");
        }
        categories.add(-insert - 1, assetCategory);
    }

    public AssetCategory fetchAssetCategory(String asset, LocalDate date) {
        List<AssetCategory> categories = assets.get(asset);
        if (categories == null) {
            return null;
        }
        int index = Collections.binarySearch(categories,
                new AssetCategory(asset, "SEARCH", date, date),
                COMPARATOR);

        return index < 0 ? null : categories.get(index);
    }

    public boolean validateAssetCategory(String asset, String category, LocalDate date) {
        AssetCategory assetCategory = fetchAssetCategory(asset, date);
        return assetCategory != null && assetCategory.getCategory().equalsIgnoreCase(category);
    }
}

И вы бы использовали его следующим образом:

        AssetCategories categories = new AssetCategories();
        categories.add(new AssetCategory("AAPL", "US LARGE CAP VALUE", LocalDate.parse("2015-01-01"), LocalDate.parse("2015-02-17")));
        categories.add(new AssetCategory("AAPL", "US LARGE CAP GROWTH", LocalDate.parse("2015-02-18"), LocalDate.parse("2015-03-16")));
        categories.add(new AssetCategory("AAPL", "US MID CAP VALUE", LocalDate.parse("2015-08-18"), LocalDate.parse("2015-12-15")));
        categories.add(new AssetCategory("AAPL", "US LARGE CAP VALUE", LocalDate.parse("2015-03-17"), LocalDate.parse("2015-05-17")));
        categories.add(new AssetCategory("AAPL", "US MID CAP GROWTH", LocalDate.parse("2015-05-18"), LocalDate.parse("2015-08-17")));

        AssetCategory assetCategory = categories.fetchAssetCategory("AAPL", LocalDate.parse("2015-12-14"));
        boolean valid = categories.validateAssetCategory("AAPL", "US MID CAP VALUE", LocalDate.parse("2015-12-15"));

Хотя это похоже на курсовую работу, поэтому ваш лектор может искать для вас карту деревьев в качествеструктура данных.