Group Assessment

第一部分

20分钟的group discussion，给了三张代码（解决同一道问题），小组讨论给出排名，然后给面试官陈述结果和理由。
Tips：

• 一定要说出自己的想法，要有leadership但不要太aggressive。
• 注意先看code有没有明显的错误
• 好好审题，看清所有条件。（对时间空间复杂度的要求）
• 比较不同实现方法之间时间空间复杂度的区别，对照题目的要求来评分。
• 考虑scalability，extendability和robustness。

第二部分

题目大意：给定

• 每个货仓的库存
• 货仓到目的地的运输方式（用时及费用）

要求：

1. 给定订单信息（商品、目的地、数量和要求送达时间），返回所有货仓-运输方式-用时-费用-目的地的list。
2. 给定每个仓库的库存量，求出货方式，使得
   • 更快送达
     或者
   • 送得更多（无效订单更少）
3. 优化费用。

思路：

• 数据结构：

struct transInfo {
  string name, whs, dest;
  int transType;
  int time, price;
  transInfo(string s1, string s2, string s3, int t, int x, int y) {
    name = s1;
    whs = s2;
    dest = s3;
    transType = t;
    time = x;
    price = y;
  }
  void print() {
    cout << name << ": from " << whs << " to " << dest << " via " << transType << endl;
  }
};

struct transInfo_byWHS {
  unordered_map<string, vector<transInfo*> > WHSmap;
  void add(transInfo* new_trans) {
    new_trans->print();
    WHSmap[new_trans->whs].push_back(new_trans);
    return;
  }
  void print() {
    for ( auto it = WHSmap.begin(); it != WHSmap.end(); it++ ) {
      cout << "    warehouse location " << it->first << " :" << endl;
      for ( int i = 0; i < int(it->second.size()); i++ ) {
        cout << "      transportation type: " << it->second[i]->transType << endl;
        cout << "      time:                " << it->second[i]->time << endl;
        cout << "      price:               " << it->second[i]->price << endl;
        cout << endl;
      }
    }
  }
};

struct item {
  string name;
  unordered_map<string, transInfo_byWHS*> DESTmap;
  item(string x): name(x) {}
  void print() {
    cout << "item name: " << name << endl;
    for ( auto it = DESTmap.begin(); it != DESTmap.end(); it++ ) {
      cout << "  destination:        " << it->first << endl;
      it->second->print();
    }
  }
  void add(transInfo* new_trans) {
    if ( DESTmap.find(new_trans->dest) == DESTmap.end() ) {
      transInfo_byWHS* whs_map = new transInfo_byWHS();
      DESTmap[new_trans->dest] = whs_map;
    }
    DESTmap[new_trans->dest]->add(new_trans);
    return;
  }
};

struct item_map {
  unordered_map<string, item*> map;
  void add(string s) {
    int n = s.size();
    vector<string> strs(1, "");
    for ( int i = 0; i < n; i++ ) {
      if ( s[i] == ',' ) strs.push_back("");
      else strs.back() += s[i];
    }
    transInfo* new_trans = new transInfo(strs[0], strs[1], strs[2], stoi(strs[3]), stoi(strs[4]), stoi(strs[5]));
    if ( map.find(new_trans->name) == map.end() ) {
      item* new_item = new item(new_trans->name);
      map[new_trans->name] = new_item;
    }
    map[new_trans->name]->add(new_trans);
    return;
  }
  void print() {
    for ( auto it = map.begin(); it != map.end(); it++ ) it->second->print();
    return;
  }
  void findTransport(string item_name, string dest) {
    cout << "To ship item " << item_name << " to " << dest << ", " << "following way(s) are available: " << endl;
    if ( map.find(item_name) == map.end() ) return;
    if ( map[item_name]->DESTmap.find(dest) == map[item_name]->DESTmap.end() )  return;
    map[item_name]->DESTmap[dest]->print();
  }
};

测试代码：

int main() {
  item_map map;
  ifstream file("test.txt");
  if ( file.is_open() ) {
    string line;
    while ( getline(file,line) ) map.add(line);
  }
  else cout << "cannot open file" << endl;
  map.print();

  string item_name = "soap";
  string dest = "hangzhou";
  map.findTransport(item_name, dest);
  return 0;
}

Practice

• C++文件读写

#include <iostream>
#include <fstream>
using namespace std;

int main() {
  ofstream file;
  string fileName = "test.txt";
  file.open(fileName);
  file << "Writing to this file.\n";
  file.close();
  return 0;
}

#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

int main() {
  string fileName = "test.txt";
  ifstream file(fileName);
  string line;
  vector<string> str_v;
  if ( file.is_open() ) {
    while ( getline(file, line)) {
      str_v.push_back(line);
    }
  }
  for ( int i = 0; i < (str_v.size()); i++ ) cout << str_v[i] << endl;
  return 0;
}

最大订单满足(最小化没货的情况)

针对特定的货物

• 仓库：在$$i$$仓库有$$xi$$件货物，寄到$$j$$地需要$$l{ij}$$~$$u_{ij}$$天。
• 订单k：在$$t_k$$天内寄到$$j_k$$地。

对每一个订单$$k$$，遍历所有仓库到$$jk$$的信息，看有哪些是无论如何都无法实现的，（要求的天数$$t_k$$小于最小的$$l{ij}$$）。剔除这些订单，剩下的订单是可以满足的上限！

• 每次visit一个订单的时候，将所有仓库按照这个货物的库存量从多到少排序，然后从多到少遍历仓库，选取第一个运送时间满足的仓库。