Two Sigma 面经

maplain 发表于 2015-11-24 04:44
根据楼主的提示，我对下午第一面第一问的想法是：

用一个map存company -> prices，其中prices用BST来 ...

就是这样的

caigaa 发表于 2015-11-24 05:14
就是这样的

好的，谢谢楼主！顺祝感恩节快乐。

按照楼上的讨论，附上解法，请指正
class BstTreeNode;
typedef std::shared_ptr<BstTreeNode> BstTreeNodePtr;

class BstTreeNode {
public:
  BstTreeNode(float price, long quantity)
      : m_price(price), m_quantity(quantity) {}

private:
  friend class BstTree;
  // double have much better precision than float, but in general stock price
  // will only have
  // less than 3 decimal digits.
  float m_price;
  // I would say long is good enough, its maximum value are just more than 2
  // billion.
  // You can switch to unsigned long if you want.
  long m_quantity;

  BstTreeNodePtr m_left, m_right;
};

class BstTree {
public:
  BstTree() : m_root(new BstTreeNode(0, 0)) {}
  void AddNode(float price, long quantity) {
    BstTreeNodePtr curr(m_root), parent;
    while (curr) {
      parent = curr;
      if (curr->m_price == price) {
        curr->m_quantity += quantity;
        return;
      } else if (curr->m_price > price) {
        curr = curr->m_left;
      } else {
        curr = curr->m_right;
      }
    }

    if (parent->m_price > price)
      parent->m_left = std::make_shared<BstTreeNode>(price, quantity);
    else
      parent->m_right = std::make_shared<BstTreeNode>(price, quantity);
  }
  float GetMinSellPrice() {
    return m_root->m_right ? m_root->m_right->m_price : 0;
  }
  float GetMaxBuyPrice() {
    BstTreeNodePtr curr(m_root);
    while (curr->m_left) {
      curr = curr->m_left;
    }
    return curr->m_price;
  }
// Need use double here, total cost coulbe be more than 2 billion.
  // Very rare, but can't rule out that possibility.
  double GetTotalCost() {
    BstTreeNodePtr curr(m_root->m_left);
    if (!curr) return 0;
    double reval(0);
    std::stack<BstTreeNodePtr> my_stack;
    my_stack.push(curr);
    while (!my_stack.empty()) {
      curr = my_stack.top();
      reval += (curr->m_price * curr->m_quantity);
      my_stack.pop();
      if(curr->m_left)my_stack.push(curr->m_left);
      if(curr->m_right)my_stack.push(curr->m_right);
    }
    return reval;
  }
private:
  BstTreeNodePtr m_root;
};

typedef std::shared_ptr<BstTree> BstTreePtr;

enum TradeType {
  BUY,
  SELL
};
class TradeBook {
public:
  TradeBook() {}
  void AddTrade(const std::string& symbol, const std::string& company,
                float price, const long quantity, const TradeType& trade_type) {
    if (m_company_price_mapper.count(company) == 0) {
      m_company_price_mapper[company] = std::make_shared<BstTree>();
      m_symbol_company_mapper[symbol] = company;
    }
    if (trade_type == BUY) price = -price;
    m_company_price_mapper[company]->AddNode(price, quantity);
  }

  void Delete(const std::string& symbol) {
    if (m_symbol_company_mapper.count(symbol) == 0) return;
    const std::string company(m_symbol_company_mapper[symbol]);
    m_company_price_mapper.erase(company);
    m_symbol_company_mapper.erase(symbol);
  }

  float GetMinSellPrice(const std::string& company) {
    if (m_company_price_mapper.count(company) == 0) return 0;
    return m_company_price_mapper[company]->GetMinSellPrice();
  }

  float GetMaxBuyPrice(const std::string& company) {
    if (m_company_price_mapper.count(company) == 0) return 0;
    return  - m_company_price_mapper[company]->GetMaxBuyPrice();
  }

  double GetTotalCost(const std::string & company) {
    if (m_company_price_mapper.count(company) == 0) return 0;
    return  - m_company_price_mapper[company]->GetTotalCost();
  }
private:
  std::unordered_map<std::string, std::string> m_symbol_company_mapper;
  std::unordered_map<std::string, BstTreePtr> m_company_price_mapper;
};

挖坟水一夏

请问楼主，第2题的解法如果遇到这种情况怎么解决：

Q1: [1.0, 1.1]   pending items for Q1 [1.2, 3.5]
Q2: [1.4] pending items for Q2 [1.6]

如果按照楼主的方法，从Q2取出1.4以后，和Q1中的每个元素比较，然后依次输出有效的pair，但是比较完成之后的1.4如何处理呢？因为后边Q1的pending元素1.2也能够和1.4形成有效的pair并输出，所以此时就把1.4删除并不合适吧。但是如果保留的话，下次1.6进来的时候，我一定还要从1.4遍历起吗？感觉并不好，因为会输出很多重复元素。

请问楼主对这个问题是怎么想的？谢谢！

nostal 发表于 2016-12-28 12:43
挖坟水一夏

同样在挖坟，估计楼主不会回复我，请问你对我刚刚的回复有没有想法？请多多指教！

taybson 发表于 2017-1-17 13:59
请问楼主，第2题的解法如果遇到这种情况怎么解决：

Q1: [1.0, 1.1]   pending items for Q1 [1.2, 3.5]
...

按照地里现在有的代码答案，假设你的两个stream是：
S1[1.0, 1.1, 1.2, 3.5]
S2[1.4, 1.6]
然后你自己有两个q存着每次读出来的数，假设现代到了你说的
Q1[1.0,1.1]
Q2[]
此时Q2为空，并且thread2从S2里读出了1.4，拿1.4去和所有Q1里的数比较，print出[1.0 1.4, 1.1 1.4]
然后Q2变为[1.4]，Q1不变
下次1.6进来的时候，做一样的事，拿1.6和所有的Q1比较。并不会重复输出。

不会有机会让1.0，1.1和1.4重新比较，因为它们应该比较的时候Q2为空，什么都不会print出来。

光的那道题。这是我的想法：
玻璃有三块反射面，让我们定义“最终反射点”为一束光永远离开玻璃们的最后的反射点，
那么如果“最终反射点”在两个外层玻璃的反射光可以衍生出 两个  +1 反射的反射光。而“最终反射点”在中间的反射光只能衍生出一条 +1 反射的反射光。
另外一个特性在于如果这次最终反射点在中间的玻璃，那么下一个反射点必然在外层玻璃， 而这次最终反射点在外层玻璃，那么必然下次反射有两个反射点，
一个在内层玻璃而一个在外层玻璃。
设定 Ki 为经历过i次反射且最终反射点在外层玻璃的个数， 设定 Pi 为经历过 i 次反射且最终反射光在内层玻璃的个数。
那么 i = 1 时， K1 = 1, P1 = 1, 加上没射入玻璃的那束光一共三束光，  n = K1 + P1 + 1 = 3;
i = 2 时， K2 = K1 + P1 = 2, P2 = K1 = 1,  n = K2 + P2 = 3;
i = 3 时， K3 = K2 + P2 = 3, P3 = K2 = 2, n = K3 + P3 = 5;
i = 4 时， K4 = K3 + P3 = 5, P4 = K3 = 3, n = K4 + P4 = 8;

抛开 i = 0 为特殊情况，
i= 0 时， 经历了0次反射的光有0束
i= 1 时， 经历了1次反射的光有3束（其中一束的最终反射点在外层玻璃，没有进入玻璃的那束光不算）
i= 2 时， 经历了2次反射的光有3束 （其中两束光是由i=1的那束最终反射点在外层玻璃的光衍生而来，另外一束则是由最终反射点在内层玻璃的那束光衍生而来）
i= 3 时， 经历了3次反射的光有5束
i= 4 时， 经历了4次反射的光有8束

楼主是学物理的吗？会被问到反射问题？ 哈哈哈