裸聊onsite面经

ymy

1. 第一轮 word break

Given a string 【i】s and a dictionary of words 【i】dict, determine if 【i】s can be segmented into a space-separated sequence of one or more dictionary words.

For example, given
【i】s = "leetcode",
6 q+ F8 P( a* ?6 ~+ l/ T& k+ t【i】dict = ["leet", "code"].

Return true because "leetcode" can be segmented as "leet code".

做法就是用DP存下来从开头到目前为止是否可以拆分。

lower median of a stream:  

比如 : 1 2 3 4 返回  1 1 2 2 及奇数位时候返回中间数，偶数位时候返回低位中间数，做法是用一个max heap一个min heap 整个过程中 max heap size顶多比min heap大一 或者相等，并且max heap中所有元素都小于min heap中所有元素

2. 第二轮:

input:

Employee,Manager,ItemsSold

Alice,,5

Bob,Alice,3

Carol,Bob,3

David,Bob,2

Eve,Alice,2

Ferris,Eve,1

/ q( c* F3 S0 b4 n8 i

output

Alice 16

|-Bob 8

| |-Carol 3

| \_David 2

\_Eve 3

  \_Ferris 1

输出的number包含了自己的和自己的底下的所有人的总和，做法是 先定义一个Employee class 包含姓名 个数  direct reports， 总个数

首先求出组织架构，然后更新总个数，最后打印，打印时候的输出比较triky 要格外小心

3. serialize 和 deserailize 一个graph，要求最节省空间。做法是存ajacent lists，期间还问了为什么不用matrix

; O  G* b0 w/ }4 B

4.  设计一个数据结构能实现以下api

void add(long timestamp, double value)

double getMin();

double getMax();

double getAvg();

最后三个均返回过去X分钟内的值。

add方法中的timestamp只会增加 不会减小，可以想象成一个push metrics的service

做法是用list 按时间顺序存 value，每次getAvg之前先移除expired的数据，再更新值。至于getMin和getMax则参考min stack的做法

' s5 i( e- D, G3 {( ]  [

他家要求挺高，现在可以用eclipse，但是要现场跑code，大家准备时候不可大意，我面完感觉还不错，最后还是悲剧了。他家面完第二天就知道结果了。祝大家好运

% W. n- Z* N: Q& ?( ~2 H8 ~
- t' {# W5 L! ^( D2 Y7 W' W9 r

ymy

本面经遵从 看着面后必须尽力分享面经原则，如果只看面经 不分享自己面经者 诅咒你们拿不到offer。
希望大家共享面经，造福同胞

Sophia

感谢您这么详细的面经分享~~~精华积分满满送上了~~~也祝福您拿下dream offer~~~