骨骼面经，求好运

12-19 骨骼面经, sunnyvale，发个面经求个好运

每一轮都是直接题目，最后有时间尬聊

第一轮Reversi board game. 一个grid上 两个人轮流下棋，落子的位置，必须保证，要么该行、要么该列、要么所在对角线上，离自己最近的棋子间全是对方的棋子。
举个例子           1 1 x，    两个感叹号表示了1这一轮所有valid落子的位置。   假设输入是一个棋盘，已经有一些棋子了，求出玩家1所有valid的落子位置

                               x 0 x
                               x  !  !

第二轮，  对一只股票价

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

数个还是偶数个就可以了。




补充内容 (2019-1-22 04:47):
补充下后续：
面试后经历圣诞节＋新年
１.4 要本科成绩单
1.11 通知过hc
1.16 PA match上　search

通过ＨＣ之后没多久就冻结了，感叹一下这拨运气真好，
顺便找一波今年入职search PA的同学！　有的话，私信联系

mysteryjoe 发表于 2018-12-31 10:37
求问O(min(m,n))的方法是啥

没写程序。你凑合看看。

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

穿袈裟的流氓 发表于 2019-1-1 10:39
求问 current time怎么在O(1)时间内得到

e.g.1000XX01，    第一个x才是valid，   第二个不是，应该中间不能有空的格子， 我bfs做的

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

谢谢楼主分享！

请问第二轮听着像是用treemap搞定了

zhangzitong001 发表于 2018/12/24 04:38:25
请问第二轮听着像是用treemap搞定了

请问第二轮需要O（constant）知道股票最大价格吗？  还是只需要支持delete  update和 current prices

第一题是不是说行，列，对角线上最近的都不是对手的？
另外棋盘是N*N方阵？

请问楼主第三题有constant space做法吗？谢谢

mysteryjoe 发表于 2018-12-26 12:23
第一题是不是说行，列，对角线上最近的都不是对手的？
另外棋盘是N*N方阵？

同问这一题

所以那个快照的题目 最优解是啥？ 我能做出插入 删除O(logn) 最大和最新O(1)的方法 可行么

1. class Stock{
   
2. private:
   
3.         // 所有的价格，multiset里的数据是排好序的
   
4.         multiset<int> prices;
   
5.         // 每个时间点以及对应的价格
   
6.         unordered_map<int, multiset<int>::iterator> time_price;
   
7.         // 所有的时间
   
8.         set<int> cur_time;
   
9. 
   
10. public:
    
11.         Stock(){
    
12.         }
    
13. 
    
14.         void newPrice(int time, int price){
    
15.                 prices.insert(price);
    
16.                 auto it = lower_bound(prices.begin(), prices.end(), price);
    
17.                 time_price[time] = it;
    
18.                 cur_time.insert(time);
    
19.         }
    
20. 
    
21.         bool deletePrice(int time){
    
22.                 if(time_price.count(time) < 1) return false;
    
23.                 auto it = time_price[time];
    
24.                 prices.erase(it);
    
25.                 time_price.erase(time);
    
26.                 cur_time.erase(time);
    
27.                 return true;
    
28.         }
    
29. 
    
30.         void updatePrice(int time, int price){
    
31.                 if(deletePrice(time)){
    
32.                         newPrice(time, price);
    
33.                 }
    
34.         }
    
35. 
    
36.         int getCurrent(){
    
37.                 int now = *(cur_time.rbegin());
    
38.                 return *(time_price[now]);
    
39.         }
    
40. 
    
41.         int getMax(){
    
42.                 return *(prices.rbegin());
    
43.         }
    
44. 
    
45.         int getPrice(int time){
    
46.                 if(time_price.count(time) < 1) return -1;
    
47.                 return *(time_price[time]);
    
48.         }
    
49. 
    
50. };

复制代码

那个再来一碗 发表于 2018-12-27 01:36
请问楼主第三题有constant space做法吗？谢谢

同问
如果是 m*n 的矩阵 O(min(m,n))的方法好做

anywho 发表于 2018-12-31 08:17
同问
如果是 m*n 的矩阵 O(min(m,n))的方法好做

求问O(min(m,n))的方法是啥