Layihə Yeraltı Sistemi Leetcode Həll

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Amazon Bloomberg
Layihə HashMap SimBaxılıb 43

Sistem dizaynı ilə bağlı müsahibə sualları o qədər açıq ola bilər ki, düzgün hazırlaşmağı bilmək çox çətindir. İndi satın aldıqdan sonra Amazon, Microsoft və Adobe-nin dizayn dövrlərini sındıra bilirəm Bu kitabı. Gündəlik bir yenidən nəzərdən keçirin dizayn sualı və söz verirəm ki, dizayn dövrünü sındıra bilərsiniz.

Layihə Yeraltı Sistemi Leetcode HəllPin

Problem bəyanat

The Layihə Yeraltı Sistemi LeetCode Həll - “Yeraltı Sistemi Dizayn” sizdən müştərilərin iki stansiya arasında səyahət vaxtlarını izləmək üçün dəmir yolu sistemi dizayn etməyi xahiş edir. Bir stansiyadan digərinə getmək üçün lazım olan orta vaxtı hesablamaq lazımdır.

həyata keçirməliyik Yeraltı Sistem sinif:

  • Qeydiyyat: Kart ID-si bərabər olan müştəri id, stansiyada yoxlanılır stationName vaxtında t.
  • Checkout: Kart ID-si bərabər olan müştəri id, stansiyadan çıxır stationName vaxtında t.
  • GetAverageTime: Səyahət üçün lazım olan orta vaxtı qaytarır startStation üçün endStation. Orta vaxt birbaşa baş vermiş başlanğıc stansiyadan son stansiyaya qədər bütün əvvəlki səyahət vaxtlarından hesablanır.

Misal:

Input:  ["UndergroundSystem","checkIn","checkIn","checkIn","checkOut","checkOut","checkOut","getAverageTime","getAverageTime","checkIn","getAverageTime","checkOut","getAverageTime"]
[[],[45,"Leyton",3],[32,"Paradise",8],[27,"Leyton",10],[45,"Waterloo",15],[27,"Waterloo",20],[32,"Cambridge",22],["Paradise","Cambridge"],["Leyton","Waterloo"],[10,"Leyton",24],["Leyton","Waterloo"],[10,"Waterloo",38],["Leyton","Waterloo"]]
Output: [null,null,null,null,null,null,null,14.00000,11.00000,null,11.00000,null,12.00000]

Explanation:

  • (45, Leyton, 3) ünvanında qeydiyyatdan keçin. Qeydiyyat (32, Paradise, 8), Checkin (32, Paradise, 8).
  • (45, Waterloo, 15) ünvanında yoxlayın.
  • (27, Waterloo, 20) ünvanında yoxlayın.
  • Checkout(32, Kembric, 22).
  • Orta Vaxt (Cənnət, Kembric) = 14/1 = 14.
  • Orta vaxt(Leyton, Waterloo) = (10+12)/2 = 11.
  • Orta vaxt (Leyton, Waterloo) = 11.
  • Checkout(10, Waterloo, 38).
  • Orta vaxt(Leyton, Waterloo) = (10+12+14)/3 = 12.

Yanaşma

Idea:

  1. Bu problemi həll etmək üçün əsas fikir a hashmap.
  2. Saxlamaq iki müxtəlif həşməplər, biri qeydiyyat üçün, digəri isə marşrutlar üçün.
  3. İndi hər qeydiyyat üçün daxil edin stansiyanın adı və cari vaxtı olan id.
  4. Həmçinin, hər check-out üçün, giriş hashmap üçün girişi silin. Həmçinin, formalaşmış marşrutu daxil edin marşrutun həşməpindəki qeydiyyat məntəqəsindən buraxılış məntəqəsinə qədər.
  5. Say və cəm girişlərinin köməyi ilə orta vaxtı hesablayın marşrut hashmap.

Kodu

Dizayn Yeraltı Sistemi Leetcode C++ Həlli:

class UndergroundSystem {
public:
    unordered_map<int, pair<string, int>> checkins;
    unordered_map<string, pair<int, int>> routes;
    void checkIn(int id, string stationName, int t) {
        checkins[id] = {stationName, t};
    }
    void checkOut(int id, string stationName, int t) {
        auto [stn, start] = checkins[id];
        checkins.erase(id);
        string route = stn + "," + stationName;
        routes[route].first++, routes[route].second += t - start;
    }
    double getAverageTime(string startStation, string endStation) {
        auto& [count, sum] = routes[startStation + "," + endStation];
        return (double)sum / count;
    }
};

Layihə Yeraltı Sistemi Leetcode Java Həlli:

class UndergroundSystem {
    Map<Integer, Pair<String, Integer>> checkins = new HashMap<>();
    Map<Pair<String, String>, int[]> routes = new HashMap<>();
    public void checkIn(int id, String stationName, int t) {
        checkins.put(id, new Pair(stationName, t));
    }
    public void checkOut(int id, String stationName, int t) {
        Pair<String, Integer> cIn = checkins.get(id);
        checkins.remove(id);
        Pair<String, String> route = new Pair(cIn.getKey(), stationName);
        int[] trip = routes.getOrDefault(route, new int[2]);
        trip[0]++;
        trip[1] += t - cIn.getValue();
        routes.put(route, trip);
    }
    public double getAverageTime(String startStation, String endStation) {
        int[] trip = routes.get(new Pair(startStation, endStation));
        return (double)trip[1] / trip[0];
    }
}

Layihə Yeraltı Sistemi Leetcode Həlli üçün Mürəkkəblik Təhlili

Zamanın mürəkkəbliyi

Yuxarıdakı kodun zaman mürəkkəbliyi O (logN) hər bir funksiya çağırışı üçün burada N = maksimum qeydiyyat/çıxış sayı.

Kosmik Mürəkkəblik

Yuxarıdakı kodun kosmik mürəkkəbliyi O (N).

arayış https://docs.oracle.com/javase/8/docs/api/java/util/HashMap.html

Crack Sistemi Dizayn Müsahibələri
Translate »