Chapter 61 Bloomberg 2017

61.1 Blow off leaf nodes of binary tree

http://www.1point3acres.com/bbs/thread-223980-1-1.html

The first problem should be solved by a bi-map. This is a classic many to many relation, like student-course relation.

map<student,set<course>> m1;
map<course,set<student>> m2;

void dfs(TreeNode* c, int k, int& md) {
  if (!c) { md = 0; return; }
  if (!c->l && !c->r) { md = 1; return; }
  int d1 = 0, d2 = 0;
  dfs(c->l, k, d1);
  dfs(c->r, k, d2);
  md = max(d1, d2) + 1;
  if (md == k + 1) {
    c->l = c->r = 0;
  }
}
TreeNode * blowoff(TreeNode *R, int k) {
  if (!R || k <= 0) return R;
  int mdep = 0;
  dfs(R, k, mdep);
  return R;
}

This is pretty much like the problem of maxdepth and print leaf nodes.

int dfs(TreeNode* c, int k) {
  if (!c) { return 0; }
  if (!c->l && !c->r) { return 1; }
  int md = max(dfs(c->l, k), dfs(c->r, k)) + 1;
  if (md == k + 1)
    c->l = c->r = 0;
  return md;
}

61.2 Knight’s tour

http://www.1point3acres.com/bbs/thread-225765-1-1.html

这题是算number,但是仍然可以用dfs来求解. 注意这道题并不适用于counting princple的rule of product!

Counting Princple(ITP P45): There are \(n_1\) possible results at the first stage. For Every possible resust at the first stage, there are \(n_2\) possible results at the second stage. The total possible results are \(n_1 x n_2\).

对红点来说,有8种可能的move,但是对这8种move,不是每个都有相同的move数: 有的8种,有的6种.所以rule of product不能使用.我们需要用DFS去找到every possible next move对应的next next move number,然后加起来.

namespace _knighttour {
#define valid(x,y) (int)(x>=0 && y>=0 && x<R && y<C)
  vector<pair<int,int>> dirs={{ -1,-2 },{ -2,-1 }, { 1,2 },{ 2,1 },
                              { -1,2 },{ 2,-1 }, { 1,-2 },{ -2,1 }};
  map<pair<int, int>, int> m;//position to num to cache result
  int getnum(int R, int C, int x, int y) {
    if (m.count({ x,y })) return m[{x, y}];
    int r = 0;
    for (auto pr : dirs) r += valid(x+pr.first,y+pr.second);
    return m[{x, y}] = r;
  }
  int dfs(int R, int C, int x, int y, int k) {
    if (k < 1) return 0;
    if (k == 1) return getnum(R, C, x, y);
    int r = 0;
    for (auto pr : dirs) {
      int nx = x + pr.first, ny = y + pr.second;
      if (valid(nx, ny)){
        r += dfs(R, C, nx, ny, k - 1);
      }
    }
    return r;
  }
  void test() {
    assert(dfs(8, 8, 0, 0, 1) == 2);
    assert(dfs(8, 8, 1, 0, 1) == 3);
    assert(dfs(8, 8, 2, 2, 1) == 8);
    assert(dfs(8, 8, 4, 4, 2) == 56);
    assert(dfs(8, 8, 1, 0, 4) == 628);
    assert(dfs(8, 8, 4, 4, 4) == 1978);
  }
}

https://en.wikipedia.org/wiki/Knight's_tour

Check this animation!

Given an mxn chessboard, if the position (x,y) of the knight is given, find the path which covers all the blocks of the chessboard without repeating.

https://discuss.leetcode.com/topic/31129/knight-s-tour-problem

61.3 Design booking system

http://www.1point3acres.com/bbs/thread-230348-1-1.html

61.4 Flood Fill a Matrix

https://en.wikipedia.org/wiki/Flood_fill

public void floodfill(int[][] matrix, int x, int y, int newColor) {
  dfs(matrix, x, y, matrix[x][y], newColor);
}
public void dfs(int[][] matrix, int x, int y, int previous, int current) {
  if (x<0 || x>matrix.length - 1 || y<0 || y>matrix[0].length - 1) {
    return;
  }
  if (matrix[x][y] != previous) {
    return;
  }
  matrix[x][y] = current;
  dfs(matrix, x + 1, y, previous, current);
  dfs(matrix, x - 1, y, previous, current);
  dfs(matrix, x, y + 1, previous, current);
  dfs(matrix, x, y - 1, previous, current);
}

BFS also can do.

哩哩哩哩不消停发表于 2017-2-24 06:58 人坐桌子,车停车位,感觉就是一个parking lot的OOD

还是不太一样因为客人是预约,所以系统需要1.告诉客人指定的时间有没有符合要求的桌子2.如果没有,则返回离指定时间最近的有桌子的时间.感觉parking lot不需要这些功能吧.

Tazdingo 发表于 2017-2-25 01:12 感觉很像meeting roomII

最后跟小伙伴讨论过该用hashmap+linkedlist或者BST来做我之前也觉得像meeting room但后来觉得不是哦哦那就又成了LRU那样的结构了吧…

61.5 295. Find Median from Data Stream

http://www.1point3acres.com/bbs/thread-231245-1-1.html

61.6 LFU Cache

http://www.1point3acres.com/bbs/thread-224748-1-1.html

Nanthan_ford 发表于 2017-2-6 04:54 楼主那个六位数的是啥思路,求指教啊

就是6位数,前三位的和和后三位的和一样,求这样6位数总共多少. 我面这道题的时候,写了一个简答的backtracking,面试官表示太复杂了.让我直接从100到999便利就好….然后我还没来得及鄙视面试官的算法水平,然后就来了一道红黑树的实现,然后就被按在桌子上嘿嘿嘿了

61.7 49. Group Anagrams

https://leetcode.com/problems/anagrams

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector<vector<string>> r;
        map<string, vector<int>> ss2idx;
        for(int i=0;i<strs.size();++i){
            string s=strs[i];
            sort(s.begin(), s.end());
            ss2idx[s].push_back(i);
        }
        for(auto pr: ss2idx){
            vector<string> p;
            for_each(pr.second.begin(), pr.second.end(), 
                [&p,&strs](int i){p.push_back(strs[i]);});
            sort(p.begin(),p.end());
            r.push_back(p);
        }
        return r;
    }
};

61.8 Flip zeroes

http://www.1point3acres.com/bbs/thread-207350-1-1.html

http://www.geeksforgeeks.org/find-zeroes-to-be-flipped-so-that-number-of-consecutive-1s-is-maximized/
Algo: Sliding Window

http://www.geeksforgeeks.org/add-greater-values-every-node-given-bst/
Algo: Reverse Inorder Traversal

61.9 Rate Limiter

http://www.1point3acres.com/bbs/thread-225389-1-1.html
http://www.1point3acres.com/bbs/thread-225974-1-1.html

Rate limiter的设计考虑两个

http://systemdesigns.blogspot.com/2015/12/rate-limiter.html

https://redis.io/commands/INCR#pattern-rate-limiter

https://en.wikipedia.org/wiki/Leaky_bucket

https://en.wikipedia.org/wiki/Token_bucket

Leaky Bucket的思想是认为有一个会漏水的桶,水以恒定速率滴出,上方会有水滴(请求)进入水桶.显然,如果上方水滴进入速率超过水滴出的速率,那么水桶就会溢出,这里的溢出就是traffic shaping和traffic policing的条件,即执行某个过载任务的时候.

Token Bucket的思想是同样有一个桶,令牌以恒定速率放入桶,桶内的令牌数有上限,每个请求会acquire一个令牌,如果某个请求来到而桶内没有令牌了,请说明这个请求是过载的.和Lecky Bucket不同的是,Token Bucket存在burst rate.比如当前令牌放入速率4个每秒,桶的令牌上限是8,第一秒内没有请求,第二秒实际就可以处理8个请求!虽然平均速率还是4个每秒,但是爆发速率是8个每秒.

两个算法的实现上,Leaky Bucket还分meter和queue,meter看起来需要定时器辅助,queue不太符合我的需求.Token Bucket虽然有burst rate,但是只要调整为和rate一样就可以了,而且实现起来不需要定时器. Token Bucket的实现原理是计算请求时间和上一次请求时间之间内增加的令牌数放入桶,比较桶内的令牌数是否足够用于请求,如果不够就认为过载,否则减去响应令牌,设置上一次请求时间为本次请求时间.注意下面的take方法实现,虽然只有不到十行,但准确地解决了请求速度限制问题.

static class TokenBucket {
  private final int capacity;
  private final int tokensPerSeconds;
  private int tokens = 0;
  private long timestamp = System.currentTimeMillis();
  public TokenBucket(int tokensPerUnit, TimeUnit unit) {
    capacity = tokensPerSeconds = (int) (tokensPerUnit / unit.toSeconds(1L));
  }
  public boolean take() {
    long now = System.currentTimeMillis();
    tokens += (int) ((now - timestamp) * tokensPerSeconds / 1000);
    if (tokens > capacity) tokens = capacity;
    timestamp = now;
    if (tokens < 1) return false;
    tokens--;
    return true;
  }
}
public static void main(String[] args) throws InterruptedException {
  TokenBucket bucket = new TokenBucket(250, TimeUnit.MINUTES);
  Thread.sleep(1000L);
  for (int i = 0; i < 5; i++) {
    System.out.println(bucket.take());
  }
  Thread.sleep(1000L);
  for (int i = 0; i < 5; i++) {
    System.out.println(bucket.take());
  }
}

Nginx

http://nginx.org/en/docs/http/ngx_http_limit_req_module.html

Haproxy

http://blog.serverfault.com/2010/08/26/1016491873/

Linux Kernel

http://blog.csdn.net/dog250/article/details/6945502

61.10 61.11 463. Island Perimeter

http://www.1point3acres.com/bbs/thread-233641-1-1.html

61.12 Design room reservation system

主要问了, 如何handle 大量的并发请求, 同时如何保证data consistence, 同时如何处理 runtime server failure.

61.13 Intersection of Linked List

http://www.1point3acres.com/bbs/thread-218493-1-1.html

http://www.1point3acres.com/bbs/thread-229445-1-1.html

给一个字符串,只含有小写字母,然后把重复的用下一个字母代替,比如aaaaa -> abcde, aabbc –> abbcc 这个我用了哈希表去记有几个重复,然后遇到重复的用chr(ord(string[i]) + 重复的次数),就是现在要替代的字母,在他的提醒下知道如果遇到z 需要循环回 a, 于是加了 % 运算返回.

http://www.1point3acres.com/bbs/thread-244233-1-1.html

61.14 Marathon Ranking TopK

主要问题是,如何保持每个sensor所“拥有”的player有先后顺序,而且如何快速删除其中某一个player(突然跑快了进入下一个sensor),并append到下一个sensor的队列中.可以用下面的图来表示:

61.14.1 Update(player, sensor)

当有新的信息进来时, 格式为(player,sensor), 比如内容为(p1,s2), 那我们知道就要把p1从s2-1对应的list里面删除掉. 从list里面进行O(1)的删除(erase)需要用到iterator, 所以我们根据map[p1]得到iterator, 根据M[s2-1]得到list; 删了之后还要加入新的list,就是M[s2], push_back就可以了. 这样update可以做到O(1).

61.14.2 topK()

为了取前k个player,当sensor较多player比较稀疏时,如何取了一部分后知道下一个有player的sensor是谁???

上面那个图是用的array,不能做到O(K),因为要受M的影响.其实可以把array换成list. 在array中,index包含sensor的信息.现在用list这个信息丢失了,可以用一个map<sensor,list<list<player>>::iterator>来达到这个目的.

Pros: topK()真正做到O(K),而且节省空间,空间复杂度变成了O(min(M,N)).
Cons: 有可能不停的create和erase list node,实际性能不一定好.

数据结构改动之后,update()也要改.如果新信息为(p1,s2), 旧的list通过s2-1可以定位,而它肯定在map m2里面.通过m1可以找到要删除的那个player的iterator,这样就可以erase了.如果erase之后旧的list为空,我们可以将其删除. 然后把p1加入新的list,如果m2里面有s2这个key,就可以直接push_back,如果没有,要新建一个list<player>并插入大的list<list<player>>.

这个解法可以叫做: 1 List of List + 2 Maps. List放data, Map定位.

一些描述这个题目的面筋:
http://www.1point3acres.com/bbs/thread-225621-1-1.html
http://www.1point3acres.com/bbs//forum.php?mod=viewthread&tid=201705
http://www.1point3acres.com/bbs/thread-231207-1-1.html..

这题还有个考法. 改变条件, 让进入了同一个sensor之后的所有player的排序相同.这样的话,在方案1中,可以省去map. 直接用一个array of set搞定:

下面这个面经说的就是这个情况: http://www.1point3acres.com/bbs/thread-206443-1-1.html (不用map)

可以看出这道题和LFU极其相似. LFU - 1 List of Set + 1 Map

http://www.1point3acres.com/bbs/thread-225621-1-1.html

http://www.1point3acres.com/bbs/thread-227497-1-1.html

http://www.1point3acres.com/bbs/thread-223157-1-1.html

https://instant.1point3acres.com/thread/224770

http://www.1point3acres.com/bbs/thread-204939-1-1.html

http://www.1point3acres.com/bbs/thread-235481-1-1.html

61.15 Segregate even and odd nodes in a Linked List

http://www.1point3acres.com/bbs/thread-244492-1-1.html

ListNode* Segregate_even_and_odd_nodes(ListNode* p) {
  ListNode h1(0), h2(0);
  ListNode *c1 = &h1, *c2 = &h2;
  while (p) {
    if (p->val & 1)
      c1->next = p, c1 = p;
    else
      c2->next = p, c2 = p;
    p = p->next;
  }
  c2->next = h1.next;
  c1->next = 0;////
  return h2.next;
}
// odd is in reversed order
ListNode* Segregate_even_and_odd_nodes2(ListNode* p) {
  ListNode h2(0);////
  ListNode *c1 = 0, *c2 = &h2;
  while (p) {
    if (p->val & 1) {
      ListNode *t = p->next;
      p->next = c1, c1 = p;
      p = t;
    } else {
      c2->next = p, c2 = p;
      p = p->next;
    }
  }
  c2->next = c1;
  //c1->next = 0;////
  return h2.next;
}

61.16 Compress String

http://www.1point3acres.com/bbs/thread-247535-1-1.html

string encode_list_with_dups(const string& s) {
  string r;
  char last = 0;
  int count = 0;
  for (char c : s) {
    if (c == last) {
      count++;
    } else if (count>0) {
      r += (count>1 ? to_string(count) : string("")) + last;
      last = c, count = 1;
    } else {
      last = c, count++;
    }
  }
  if (count>0) r += (count>1 ? to_string(count) : string("")) + last;
  return r;
}

2016(10-12月) 码农类 硕士 全职 Facebook - 内推 - Onsite |Fail在职跳槽
楼主一年半工作经验,在computer network最大的一家工作
内推了几个职位,最后被hr拉去面sde, network
电面:两题都是地里面经题,有细微改动,问复杂度
onsite:
1. system design:design a memcache,给出了内存空间要求,其余的数据量大小要你自己问
2. algo: lc 158, 改成read4k
3. bq+algo: 一些行为题和做过的类似project,还有一道palindrome的题
4. algo: lc 325, 有细微改动,这一轮卡了一会,只做了一道题,感觉偏少
5. system design(training process, shadow烙印): 嵌入式系统设计,设计一个子系统,读入声音信号量(vectered i/0), 
输出声音波形.涉及dma,cpu polling/interrupt,loop back queue等.这一轮很晕,答得很不好,shadow看我get lost最后出
了一道设计子系统计算笛卡尔乘积,向量sparse如何处理,地里有面经,时间不够只答出了算法.

半个月后hr打电话通知rej.第一次面fb,五轮很累,尤其两轮system design很晕

有几个问题.
1. 当时内推选的是new grad,第二个才是这个职位.请问是否工作一年以上不能再面new grad?
还是根据面试表现定级别?感觉onsite对system design要求比较高.
2. hr拖了两三周直接给电话rej是不是看面试成绩不好没送hc?
3. shadow轮是否算成绩?之前看面经有人说不算,但我感觉我肯定是算了成绩,shadow估计是投一次面人,加上是烙印.
前面很长一段时间我都没get到点,一旁的senior全程一言不发.这一轮自己感觉很不好,算成绩足以让我rej.

去年下半年尝试跳槽,flg都挂了,很不顺利.发帖希望今年运势能好一些

http://www.1point3acres.com/bbs/thread-226066-1-1.html

61.16.1 Finding longest subsequence with sum less than or equal to a fixed number

http://softwareengineering.stackexchange.com/questions/319817/finding-longest-subsequence-with-sum-less-than-or-equal-to-a-fixed-number

61.17 Design Lift System

2017(4-6月) 码农类硕士全职Bloomberg - 网上海投 - Onsite |Otherfresh grad应届毕业生
总的下来,两轮面试都聊的还行,但是挂点一直在想!呆在火车站写完我的这次纽约之行.抛开一切客观因素,我总结了下:1. 写在纸上的东西有点乱.2. 没有在第一时间给出理想的solution.3. 思路并不是那么清晰
正文:
住在f开头的酒店,lobby 有免费Wi-Fi,后面我发现这酒店网的认证系统有bug,如果你在lobby连上free的节点,再回房间连收费的节点,直接可以连上,不需要任何验证.开始跟其他面筋一样,bb 导游带你参观
第一轮:lc原题 ,判断是否是对称树,我给出recursive解秒.然后问我能不能iterative.我说definitely.写了葛bfs.然后另外一个面试官让我走一遍代码验证是否正确.另外提供其他的test case. 我按左边跟右边右边跟左边对称的两类test case.写完说cool.下一题设计
design LFU for database requests. 这里我稍微想了下.因为lc里面的解法比较复杂.我在想我要怎么阐述这个想法让他秒懂. 我画了几个图.然后给出了一些关键数据结构.谈完以后,然后写伪代码.他们一直在看表,估计时间快不够,因为前面聊太多我的项目和bq.然后说直接写step吧.我写完直接告诉他们.我觉得是不是挂在这里.没有把设计思路在一张纸上面清晰的表现出来.聊完我后面确认一下,问他们是否懂了我的想法,他们说都懂了.
第二轮: 三姐. 一道 fb面筋的高频题.lc也有类似题.一个屋子里面有n多人,给出一个人跟一些人谈话的关系.比如 <a,b,c,d> <c,a,b>,<e,f>,<g>. 问有多少个group. abcd,ef,g上面例子是3个.我开始想用uf.后面想有点复杂.三姐耶没懂.然后改用graph＋dfs,后面她就懂了.__第二个还是设计题:设计电梯系统.我说这个有点复杂,她说不需要考虑那么复杂,然后我在想起来地里里面应该有这个,但是具体解法我一时没想起来.后面三姐提示了一下.然后电梯有三个功能,up,down,stop,controler. 只需要在controler里面维持一个map某一层是否需要停.我说可以更省空间用bitset, 如果有up 或者down指令,就把某一层flip,如果电梯到了某一层,调用stop,然后再flip 回来.她表示满意.__后面她给我介绍了很多group的信息,以及train program . 最后说的不是good luck, 而是see you soon. 我说这句应该表示是有希望把.but hr 一进来介绍了自己,然后说,你有东西寄存了么,我带你去取.这意思就结束了.心里表示疑惑,hr送我下楼的时候她说她去看了dc 樱花节,然后就聊起来了.最后说一周之内给我答复.我想明天或者周一就有结果把
回到宾馆,一个三哥上来找我,说是不是bb面试,我说是,然后就聊起来了,他说他跟他friends都是两轮,一般四轮都有更大几率pass. 我在想他们是不是也有类似地里的东西在分享面筋.这些都知道. 不管咋样,只能继续move on…
http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=275400