Design

马拉松

就是沿途不同地方有sensor 可知道谁跑过该sensor. 主要query 是查现在runners的排名，问如何设计该系统。

Thoughts
For each runner, we need to record which is the last sensor that has detected him. We first simply use an array for that:

vector<int> last_sensor

For each sensor, we need to record which runners have passed it in the right time order. We first an a 2D array for that:

vector<vector<int>> sensor_rankings

When a runneri_runner passing a sensori_sensor, we need to do the following things:

• add it to the sensor_ranking[i_sensor]

  void add(int i_runner, int i_sensor ) {
    sensor_rankings[i_sensor].push_back(i_runner);
  }
  

• remove it from last_sensor[i_runner]

  void remove(int i_runner, int i_sensor) {
    int n = sensors_ranking[i_sensor].size();
    int i = 0;
    for ( i = 0; i <= n-1; i++ ) {
        if ( sensors_ranking[i_sensor][i] == i_runner ) break;
    }
    for (; i <= n-2; i++ ) sensors_ranking[i_sensor][i] = sensors_rankingi_sensor[][i+1];
    sensors_ranking[i_sensor].erase(sensor_ranking[i_sensor].end()-1);
  }
  

• update last_sensor: last_sensor[i_runner] = i_sensor

  void update (int i_runner, int i_sensor) {
    last_sensor[i_runner] = i_sensor;
  }
  

• To get the overall ranking:

  getRanking(){
    vector<int> overall_ranking;
    for (int i = n_sensors-1; i >= 0; i-- ) {
      int n = sensors_ranking[i].size();
      for ( int j = 0; j <= n-1; j++ ) {
        overall_ranking.push_back[sensors_ranking[i][j]];
      }
    }
  }
  

Below is the design after second-thought

class marathon {
  private:
    struct runner {
      int ID, ranking;
      int last_sensor;
      runner(int x): ID(x), ranking(-1), last_sensor(-1){};
    };

    struct sensor {
      vector<int> s_rankings;
      int high;
      sensor(): s_rankings(0, 0), high(0){};
    };

    int n_runner, n_sensor;
    vector<runner*> runners;
    vector<sensor*> sensors;
    vector<int> rankings;

  public:
    // initialize the class
    marathon(int x, int y) {
      n_runner = x;
      n_sensor = y;
      for ( int i = 0; i <= n_runner-1; i++ ) {
        runner* tmp = new runner(i);
        runners.push_back(tmp);
        rankings.push_back(-1);
      }
      for ( int i = 0; i <= n_sensor-1; i++ ) {
        sensor* tmp = new sensor();
        sensors.push_back(tmp);
      }
    }

    // remove ruuner #ir from sensor #is
    // note to change the ranking records
    void remove(int ir, int is) {
      sensors[is]->high += 1;
      int i = 0, n = sensors[is]->s_rankings.size();
      while ( sensors[is]->s_rankings[i] != ir ) {
        int ID = sensors[is]->s_rankings[i];
        runners[ID]->ranking += 1;
        int new_ranking = runners[ID]->ranking;
        rankings[new_ranking] = ID;
        i += 1;
      }

      for (; i <= n-2; i++ ) sensors[is]->s_rankings[i] = sensors[is]->s_rankings[i+1];
      sensors[is]->s_rankings.erase(sensors[is]->s_rankings.end()-1);
      return;
    }

    // add runner #ir to sensor #is
    // note to update the ranking of #ir
    void add(int ir, int is ) {
      sensors[is]->s_rankings.push_back(ir);
      int n = sensors[is]->s_rankings.size();
      int new_ranking = sensors[is]->high + n -1;
      runners[ir]->ranking = new_ranking;
      runners[ir]->last_sensor = is;
      rankings[new_ranking] = ir;
    }

    // basically its removing + adding
    void update(int ir, int is) {
      cout << "runner #" << ir << " has passed sensor #" << is << ". " << endl;
      int last_s = runners[ir]->last_sensor;
      if ( last_s != -1 ) remove(ir, last_s);
      add(ir, is);
    }

    vector<int> getRanking() {
      for ( int i = 0; i <= n_runner-1; i++ ) cout << rankings[i] << ", ";
      cout << endl;
      return rankings;
    }
};

int main() {
  marathon* M = new marathon(3, 2);
  M->getRanking();
  M->update(0, 0);
  M->getRanking();
  M->update(2, 0);
  M->getRanking();
  M->update(1, 0);
  M->getRanking();
  M->update(1, 1);
  M->getRanking();
  return 0;
}

The output is:

-1, -1, -1, 
runner #0 has passed sensor #0. 
0, -1, -1, 
runner #2 has passed sensor #0. 
0, 2, -1, 
runner #1 has passed sensor #0. 
0, 2, 1, 
runner #1 has passed sensor #1. 
1, 0, 2,

停车场

音乐播放器

电梯

扑克牌

聊天服务？

NewsFeed?