裸聊onsite面经

ymy

1. 第一轮 word break
+ N, t; W9 a- t# _( [

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
/ N* u; B# A. T- J7 R【i】s = "leetcode",
【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

/ p2 c- G$ F- o/ b; e& w) T

output

Alice 16

|-Bob 8

| |-Carol 3

| \_David 2

\_Eve 3

  \_Ferris 1

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

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

* h1 F+ j. V9 T& o+ Y9 V

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

! I' z9 I7 ~9 m( I# d* q) Z

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的做法

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

5 j* Z5 F2 [$ ]5 ~* [5 y

ymy

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

Sophia

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