HRT Algo Dev 最新电面题

第一题可以用造Random variable做。denote rv S_n为 Indicator(color at n differs from color at n-1)，这样你有2n-1个这样的indicator RV。那么total number of sequences就是1+ \sum_{i=1}^{2n-1} S_i。显然S_i是不independent的。不过没关系，你只要知道expectation。那么又因为对称，所以每个S_i的期望相等。每个期望就是n/2n-1，那么得到结果1+n。证毕