e****e
发帖数: 418 | 1 一电：
１。给定一个数组，求次大值。
２。给定两个排好序的数组，要求返回一个排好序合并的数组。引申问题，如果数组里
的元素类型不是整数型，可能是String, double, Date...，如何处理？
二电：
１。给一个文件，从中找电话号码。
２。什么是哈希表？解决冲突的方法？
３。分层打印二叉数。
４。二维坐标里n个点，求离原点坐标最近的k个点。
５。面向对象的设计题：停车场。
面对面一：
１。问简历
２。给定一个长度为n整数型数组，看是否满足以下条件，相临数字之差的绝对值，刚
好可以组成 1,2,...,n-1。
例子：2 5 4 6 --> 1, 2, 3 成立。
2 5 4 7 --> 1, 3, 3 不成立。
1 2 3 4 --> 1, 1, 1 不成立。
引申问题：没有相邻数字的条件，可以是任何位置的数字和其他任何位置的数字的差值
的绝对值，其他条件都一样。找个小于n平方的时间复杂度的方法。
面二：
１。问简历
２。求次方，底是个浮点型，指数是整型。
３。面向对象的设计题：从数据模型的角度设计购物网站。主要有哪些类，类里主要有
哪些域，如何交互，数据是怎么流的？
面三：
招聘经理，行为问题＋午饭。
面四：
１。问简历
２。给定一个区间数组和一个区间，求数组里和这个给定区间重合区间的数目。
引申问题：如果数组很大，如何优化。可以花很多时间和空间做预处理，最后得到重合
区的数目的操作要尽可能快。
面五：抬杆者
１。问简历
２。系统设计题：给定一个场景（需要解决的问题）和已有的设计，你能发现存在什么
问题，如何改进。
问题场景：即时在线客户服务（聊天服务，每个大站上都有，你懂的）。
基本用例：客户在其自己的机器上找客服聊天。
现有设计：客户的聊天请求走到一个聊天服务器里，服务器里有一个队列，聊天请求放
入队列，客服们从队列里拿到聊天请求，进行聊天服务。
系统设计示意图如下：（此图为抬杆者所画，这里是文字版。）
客户(多个) <-----> 聊天服务器（一个）<-----> 客服（多人）
对此场景的这个设计，你能发现什么问题，如何改进？ | j*****y
发帖数: 1071 | 2 thanks for sharing.
bless
【在 e****e 的大作中提到】
: 一电：
: １。给定一个数组，求次大值。
: ２。给定两个排好序的数组，要求返回一个排好序合并的数组。引申问题，如果数组里
: 的元素类型不是整数型，可能是String, double, Date...，如何处理？
: 二电：
: １。给一个文件，从中找电话号码。
: ２。什么是哈希表？解决冲突的方法？
: ３。分层打印二叉数。
: ４。二维坐标里n个点，求离原点坐标最近的k个点。
: ５。面向对象的设计题：停车场。
| e****e
发帖数: 418 | 3 谢bless, 已经被拒了.
【在 j*****y 的大作中提到】
: thanks for sharing.
: bless
| f*****e
发帖数: 2992 | 4 不错！有点难！good luck！
【在 e****e 的大作中提到】
: 一电：
: １。给定一个数组，求次大值。
: ２。给定两个排好序的数组，要求返回一个排好序合并的数组。引申问题，如果数组里
: 的元素类型不是整数型，可能是String, double, Date...，如何处理？
: 二电：
: １。给一个文件，从中找电话号码。
: ２。什么是哈希表？解决冲突的方法？
: ３。分层打印二叉数。
: ４。二维坐标里n个点，求离原点坐标最近的k个点。
: ５。面向对象的设计题：停车场。
| b****g
发帖数: 192 | 5 第一次店面的两个题怎么做？有trick吗难道？？？
【在 e****e 的大作中提到】
: 一电：
: １。给定一个数组，求次大值。
: ２。给定两个排好序的数组，要求返回一个排好序合并的数组。引申问题，如果数组里
: 的元素类型不是整数型，可能是String, double, Date...，如何处理？
: 二电：
: １。给一个文件，从中找电话号码。
: ２。什么是哈希表？解决冲突的方法？
: ３。分层打印二叉数。
: ４。二维坐标里n个点，求离原点坐标最近的k个点。
: ５。面向对象的设计题：停车场。
| f*****e
发帖数: 2992 | 6 我靠！过五关斩六将！A也太不给面子了吧！
【在 e****e 的大作中提到】
: 谢bless, 已经被拒了.
| f*****e
发帖数: 2992 | 7 面4，第二题:
f(x) = number of intervals with at least one end <= x (i.e. left end <= x)
g(x) = number of intervals with both ends <= x (i.e. right end <= x)
given an interval A=[x1,x2]
number of intervals intersecting A = f(x2) - g(x1)
【在 e****e 的大作中提到】
: 一电：
: １。给定一个数组，求次大值。
: ２。给定两个排好序的数组，要求返回一个排好序合并的数组。引申问题，如果数组里
: 的元素类型不是整数型，可能是String, double, Date...，如何处理？
: 二电：
: １。给一个文件，从中找电话号码。
: ２。什么是哈希表？解决冲突的方法？
: ３。分层打印二叉数。
: ４。二维坐标里n个点，求离原点坐标最近的k个点。
: ５。面向对象的设计题：停车场。
| f*****e
发帖数: 2992 | 8 面1，第2题：
看n个数是否contiguous with each other？
【在 e****e 的大作中提到】
: 一电：
: １。给定一个数组，求次大值。
: ２。给定两个排好序的数组，要求返回一个排好序合并的数组。引申问题，如果数组里
: 的元素类型不是整数型，可能是String, double, Date...，如何处理？
: 二电：
: １。给一个文件，从中找电话号码。
: ２。什么是哈希表？解决冲突的方法？
: ３。分层打印二叉数。
: ４。二维坐标里n个点，求离原点坐标最近的k个点。
: ５。面向对象的设计题：停车场。
| b****g
发帖数: 192 | 9 给定一个长度为n整数型数组，看是否满足以下条件，相临数字之差的绝对值，刚
好可以组成 1,2,...,n-1。
例子：2 5 4 6 --> 1, 2, 3 成立。
2 5 4 7 --> 1, 3, 3 不成立。
1 2 3 4 --> 1, 1, 1 不成立。
引申问题：没有相邻数字的条件，可以是任何位置的数字和其他任何位置的数字的差值
的绝对值，其他条件都一样。找个小于n平方的时间复杂度的方法。
不会做。。。
【在 e****e 的大作中提到】
: 一电：
: １。给定一个数组，求次大值。
: ２。给定两个排好序的数组，要求返回一个排好序合并的数组。引申问题，如果数组里
: 的元素类型不是整数型，可能是String, double, Date...，如何处理？
: 二电：
: １。给一个文件，从中找电话号码。
: ２。什么是哈希表？解决冲突的方法？
: ３。分层打印二叉数。
: ４。二维坐标里n个点，求离原点坐标最近的k个点。
: ５。面向对象的设计题：停车场。
| f*****e
发帖数: 2992 | 10 面5，除了加机器还有什么办法吗？
【在 e****e 的大作中提到】
: 一电：
: １。给定一个数组，求次大值。
: ２。给定两个排好序的数组，要求返回一个排好序合并的数组。引申问题，如果数组里
: 的元素类型不是整数型，可能是String, double, Date...，如何处理？
: 二电：
: １。给一个文件，从中找电话号码。
: ２。什么是哈希表？解决冲突的方法？
: ３。分层打印二叉数。
: ４。二维坐标里n个点，求离原点坐标最近的k个点。
: ５。面向对象的设计题：停车场。
| | | l*******b
发帖数: 2586 | 11 连通以后可不可以绕过服务器,直接对话.结束通话后服务端报告给服务器加入下个队列
【在 f*****e 的大作中提到】
: 面5，除了加机器还有什么办法吗？
| f*******7
发帖数: 943 | | p*****p
发帖数: 379 | 13 LZ面的java？
写些自己的解法，求指导：
一电：
1. 两个变量
2. 两个index，typeof比较类型然后调用compare？
二电：
1. 不清楚，如果电话号码是确定格式xxx-xxx-xxxx的话直接线性查找或者KMP之类？
2. 冲突用list储存？
3. 两个list
4. O(n)求到原点距离，然后quick select
onsite1：
2. 线性扫一遍
followup：排序后线性扫一遍？
onsite2：
2. 二分
3. 不清楚数据模型的角度是啥
onsite4：
2. 线性比较一下
followup：排序一下？这个不清楚
onsite5：
2. 我能想到的问题有：
每个人等待时间不同，时间长的应该有high priority，优先服务
聊天服务器可以有多个，牵扯到数据同步、负载平衡等等问题
【在 e****e 的大作中提到】
: 一电：
: １。给定一个数组，求次大值。
: ２。给定两个排好序的数组，要求返回一个排好序合并的数组。引申问题，如果数组里
: 的元素类型不是整数型，可能是String, double, Date...，如何处理？
: 二电：
: １。给一个文件，从中找电话号码。
: ２。什么是哈希表？解决冲突的方法？
: ３。分层打印二叉数。
: ４。二维坐标里n个点，求离原点坐标最近的k个点。
: ５。面向对象的设计题：停车场。
| e****e
发帖数: 418 | 14 常见题，没有trick。
【在 b****g 的大作中提到】
: 第一次店面的两个题怎么做？有trick吗难道？？？
| e****e
发帖数: 418 | 15 我用了个布耳数组，走一遍原数组，两两求差，差值作为布耳数组下标，置其值为true.
【在 f*****e 的大作中提到】
: 面1，第2题：
: 看n个数是否contiguous with each other？
| p*****p
发帖数: 379 | 16 诶这个办法不错
true.
【在 e****e 的大作中提到】
: 我用了个布耳数组，走一遍原数组，两两求差，差值作为布耳数组下标，置其值为true.
| e****e
发帖数: 418 | 17
是。
根据不同的类型，写不同的comparator，再把comparator 传进那个最初的算法（最初
的算法是针对数组元素是整数型。）
1. grep + regular expression
2. list或者open address
3. 我用了一个list, 两个list也能解决。
4. 我是用的heap, quick select更好。
：onsite1：
：2. 线性扫一遍
： followup：排序后线性扫一遍？
同意。排序后线性扫一遍还是n平方的时间复杂度。这个followup问题我没有回答出来
，至今也不知到有小于n平方的解法。
：onsite2：
：2. 二分
：3. 不清楚数据模型的角度是啥
是。data model.
：onsite4：
：2. 线性比较一下
followup：排序一下？这个不清楚
是线性比较，我的思路：有两种情况是没有overlap, 有四种情况是overlap,所以只用
看是没有overlap，再取反就行了。
followup, 预处理：按照区间数组里所有的点之间《分段》，计算每段上所重合
interval的个数。当给定区间来了，两分法找到那些《分段》，取其中的count的最大
值就是重合的数目。时间复杂度是lg(n)+m， n是《分段》的个数，m是给定区间在《分
段》上的个数。
：onsite5:
你说得挺好，我会单独回帖说这道题。
【在 p*****p 的大作中提到】
: LZ面的java？
: 写些自己的解法，求指导：
: 一电：
: 1. 两个变量
: 2. 两个index，typeof比较类型然后调用compare？
: 二电：
: 1. 不清楚，如果电话号码是确定格式xxx-xxx-xxxx的话直接线性查找或者KMP之类？
: 2. 冲突用list储存？
: 3. 两个list
: 4. O(n)求到原点距离，然后quick select
| p*****p
发帖数: 379 | 18 n方那个题看错了……排序不解决问题……我再想想，看来要是面这个就跪了
【在 e****e 的大作中提到】
:
: 是。
: 根据不同的类型，写不同的comparator，再把comparator 传进那个最初的算法（最初
: 的算法是针对数组元素是整数型。）
: 1. grep + regular expression
: 2. list或者open address
: 3. 我用了一个list, 两个list也能解决。
: 4. 我是用的heap, quick select更好。
: ：onsite1：
: ：2. 线性扫一遍
| f*****e
发帖数: 2992 | 19 题目说刚好是1,...,n-1。因为都是整数，所以
数组中肯定没有两个数是相等的，要不然0也是其中之一。然后数组中任何两个数的
差不能超过n-1。那么只能是n个连续的整数了。
【在 p*****p 的大作中提到】
: n方那个题看错了……排序不解决问题……我再想想，看来要是面这个就跪了
| f*****e
发帖数: 2992 | 20 面4.2很简单的:
记每个interval是[Li,Hi]，给定一个interval A=[x1,x2]
找{L1,L2,...,Ln}中小于等于x2的个数，记为n1，
找{H1,H2,...,Hn}中小于等于x1的个数，记为n2。
与A相交的interval个数就是n1-n2
如果对上限和下限排序，然后再二分查找就可以得到n1和n2。
所以是复杂度是O(lgN)
【在 e****e 的大作中提到】
:
: 是。
: 根据不同的类型，写不同的comparator，再把comparator 传进那个最初的算法（最初
: 的算法是针对数组元素是整数型。）
: 1. grep + regular expression
: 2. list或者open address
: 3. 我用了一个list, 两个list也能解决。
: 4. 我是用的heap, quick select更好。
: ：onsite1：
: ：2. 线性扫一遍
| | | e****e
发帖数: 418 | 21 原数组不是n个连续的整数，见我的第一个例子，差数组是n-1个连续的整数,从1开始。
【在 f*****e 的大作中提到】
: 题目说刚好是1,...,n-1。因为都是整数，所以
: 数组中肯定没有两个数是相等的，要不然0也是其中之一。然后数组中任何两个数的
: 差不能超过n-1。那么只能是n个连续的整数了。
| e****e
发帖数: 418 | 22 这是一个好办法。
【在 f*****e 的大作中提到】
: 面4.2很简单的:
: 记每个interval是[Li,Hi]，给定一个interval A=[x1,x2]
: 找{L1,L2,...,Ln}中小于等于x2的个数，记为n1，
: 找{H1,H2,...,Hn}中小于等于x1的个数，记为n2。
: 与A相交的interval个数就是n1-n2
: 如果对上限和下限排序，然后再二分查找就可以得到n1和n2。
: 所以是复杂度是O(lgN)
| s***y
发帖数: 203 | | m****s
发帖数: 1197 | | f*****e
发帖数: 2992 | 25 我就是说的差数组啊。差数组A是1至(n-1)，
对于第二问的follow，差数组中的元素是原数组B中任意两个元素的差的绝对值所组成
的集合，对原数组B的分析就是我上面那样的，原数组B中不可能有两个是相等的，要不
然A中肯定有0，然后B中不可能有两个的差大于n-1。所以B中就是n个连续的整数。
【在 e****e 的大作中提到】
: 原数组不是n个连续的整数，见我的第一个例子，差数组是n-1个连续的整数,从1开始。
| h**u
发帖数: 35 | 26 "引申问题：没有相邻数字的条件，可以是任何位置的数字和其他任何位置的数字的差值
的绝对值，其他条件都一样。找个小于n平方的时间复杂度的方法。"
Totally, We have n*(n-1)/2 differences. Does that mean these differences
must constitute a consequtive sequence 1, 2 .. n-1 by allowing duplicates in
it? Otherwise we could use 1 2 4 5 to generate an 1 2 3.
【在 f*****e 的大作中提到】
: 题目说刚好是1,...,n-1。因为都是整数，所以
: 数组中肯定没有两个数是相等的，要不然0也是其中之一。然后数组中任何两个数的
: 差不能超过n-1。那么只能是n个连续的整数了。
| h**u
发帖数: 35 | 27 "引申问题：没有相邻数字的条件，可以是任何位置的数字和其他任何位置的数字的差值
的绝对值，其他条件都一样。找个小于n平方的时间复杂度的方法。"
Totally, We have n*(n-1)/2 differences. Does that mean these differences
must constitute a consequtive sequence 1, 2 .. n-1 by allowing duplicates in
it? Otherwise we could use 1 2 4 5 to generate an 1 2 3.
【在 f*****e 的大作中提到】
: 题目说刚好是1,...,n-1。因为都是整数，所以
: 数组中肯定没有两个数是相等的，要不然0也是其中之一。然后数组中任何两个数的
: 差不能超过n-1。那么只能是n个连续的整数了。
| f*****e
发帖数: 2992 | 28 1 2 4 5 =>
1 2 3 4
差值
in
【在 h**u 的大作中提到】
: "引申问题：没有相邻数字的条件，可以是任何位置的数字和其他任何位置的数字的差值
: 的绝对值，其他条件都一样。找个小于n平方的时间复杂度的方法。"
: Totally, We have n*(n-1)/2 differences. Does that mean these differences
: must constitute a consequtive sequence 1, 2 .. n-1 by allowing duplicates in
: it? Otherwise we could use 1 2 4 5 to generate an 1 2 3.
| s*********s
发帖数: 140 | 29 没明白为什么 “原数组B中不可能有两个是相等的，然后B中不可能有两个的差大于n-1
-> B中就是n个连续的整数”能成立。楼主给的例子： 2， 5， 4，6 -》 1，2，3 在
原题和follow up题都符合，但不是n个连续整数。 你是想说n-1个连续整数吗？
【在 f*****e 的大作中提到】
: 我就是说的差数组啊。差数组A是1至(n-1)，
: 对于第二问的follow，差数组中的元素是原数组B中任意两个元素的差的绝对值所组成
: 的集合，对原数组B的分析就是我上面那样的，原数组B中不可能有两个是相等的，要不
: 然A中肯定有0，然后B中不可能有两个的差大于n-1。所以B中就是n个连续的整数。
| f*****e
发帖数: 2992 | 30 原题说“刚好”产生1到n-1的数，也就是不多也不少，2，4，5，6 => 1,2,3,4，就是1
到n了，多了一个n。4, 6, 5, 3就正好，4个连续整数，顺序被打乱了。
-1
【在 s*********s 的大作中提到】
: 没明白为什么 “原数组B中不可能有两个是相等的，然后B中不可能有两个的差大于n-1
: -> B中就是n个连续的整数”能成立。楼主给的例子： 2， 5， 4，6 -》 1，2，3 在
: 原题和follow up题都符合，但不是n个连续整数。 你是想说n-1个连续整数吗？
| | | s*********s
发帖数: 140 | 31 是啊，在原题里，n=4时，只考虑相邻两个数字的差，刚好是产生3个啊。。。
你2，5，4，6->1，2，3，4里的4是怎么产生出来的。。。
lz给的例子是2，5，4，6，不是2，4，5，6。
是1
【在 f*****e 的大作中提到】
: 原题说“刚好”产生1到n-1的数，也就是不多也不少，2，4，5，6 => 1,2,3,4，就是1
: 到n了，多了一个n。4, 6, 5, 3就正好，4个连续整数，顺序被打乱了。
:
: -1
| f*****e
发帖数: 2992 | 32 引申问题：没有相邻数字的条件，可以是任何位置的数字和其他任何位置的数字的差值
的绝对值，其他条件都一样。找个小于n平方的时间复杂度的方法。
【在 s*********s 的大作中提到】
: 是啊，在原题里，n=4时，只考虑相邻两个数字的差，刚好是产生3个啊。。。
: 你2，5，4，6->1，2，3，4里的4是怎么产生出来的。。。
: lz给的例子是2，5，4，6，不是2，4，5，6。
:
: 是1
| c********t
发帖数: 5706 | 33 lz说了 第一题 2，5，4，6相邻差值=》1,2,3 成立
follow up不用相邻，意思就是，给你6,2,4，5或任意组合，你能够转排序为 2,5,4,6
或 6，4,5,2 或 6，5,2,4,或4,2,5,6，总之能够相邻差值为1,2,3，这样就是true,无
论什么顺序都得不到 1，2,。。，n-1,就是false.
不好做，想不出比O(N^2)更好的解。排序似乎没用啊。
【在 f*****e 的大作中提到】
: 引申问题：没有相邻数字的条件，可以是任何位置的数字和其他任何位置的数字的差值
: 的绝对值，其他条件都一样。找个小于n平方的时间复杂度的方法。
| f*****e
发帖数: 2992 | 34 我觉得完整的表述是：
引申问题：给定一个长度为n整数型数组，看是否满足以下条件，任何位置的数字和其他
任何位置的数字的差值的绝对值，刚好可以组成 1,2,...,n-1。
找个小于n平方的时间复杂度的方法。
6
【在 c********t 的大作中提到】
: lz说了 第一题 2，5，4，6相邻差值=》1,2,3 成立
: follow up不用相邻，意思就是，给你6,2,4，5或任意组合，你能够转排序为 2,5,4,6
: 或 6，4,5,2 或 6，5,2,4,或4,2,5,6，总之能够相邻差值为1,2,3，这样就是true,无
: 论什么顺序都得不到 1，2,。。，n-1,就是false.
: 不好做，想不出比O(N^2)更好的解。排序似乎没用啊。
| e****e
发帖数: 418 | 35 instant video
【在 s***y 的大作中提到】
: 感谢面经，LZ是面的哪个组啊？
| e****e
发帖数: 418 | 36 对原问题，差数组是1至(n-1)，如果返回true, 原数组两两之差值，只能是从1至(n-1)
并只出现一次。
followup,差值有可能重复，只要差值能够组成/形成1至(n-1)的数组就返回true,不能
形成就返回false.我原贴里的“刚好”可能误导了大家，sorry...
【在 f*****e 的大作中提到】
: 我就是说的差数组啊。差数组A是1至(n-1)，
: 对于第二问的follow，差数组中的元素是原数组B中任意两个元素的差的绝对值所组成
: 的集合，对原数组B的分析就是我上面那样的，原数组B中不可能有两个是相等的，要不
: 然A中肯定有0，然后B中不可能有两个的差大于n-1。所以B中就是n个连续的整数。
| e****e
发帖数: 418 | | e****e
发帖数: 418 | 38 我觉得排序也没用，还是O(N^2)。
6
【在 c********t 的大作中提到】
: lz说了 第一题 2，5，4，6相邻差值=》1,2,3 成立
: follow up不用相邻，意思就是，给你6,2,4，5或任意组合，你能够转排序为 2,5,4,6
: 或 6，4,5,2 或 6，5,2,4,或4,2,5,6，总之能够相邻差值为1,2,3，这样就是true,无
: 论什么顺序都得不到 1，2,。。，n-1,就是false.
: 不好做，想不出比O(N^2)更好的解。排序似乎没用啊。
| e****e
发帖数: 418 | 39 ”刚好“这个词我用的不好，应该删去。
其他
【在 f*****e 的大作中提到】
: 我觉得完整的表述是：
: 引申问题：给定一个长度为n整数型数组，看是否满足以下条件，任何位置的数字和其他
: 任何位置的数字的差值的绝对值，刚好可以组成 1,2,...,n-1。
: 找个小于n平方的时间复杂度的方法。
:
: 6
| c********t
发帖数: 5706 | 40 我的问题是每个元素能用几次？
第一问 2,5,4,6 每个元素被用2次（头尾只用1次）
而根据你对follow up的描述，似乎1,2,3,4，可以用2-1,3-1,4-1来组成差值？
1)
【在 e****e 的大作中提到】
: 对原问题，差数组是1至(n-1)，如果返回true, 原数组两两之差值，只能是从1至(n-1)
: 并只出现一次。
: followup,差值有可能重复，只要差值能够组成/形成1至(n-1)的数组就返回true,不能
: 形成就返回false.我原贴里的“刚好”可能误导了大家，sorry...
| | | e****e
发帖数: 418 | 41 我来说说bar raiser的系统设计题。
最大的问题是如果用户过多，聊天服务器处理不过来（可能是带宽不够，机器性能不够
）. 面试官还让我估计了大概在多大的带宽下，多少用户会因为带宽不够造成拥塞。
解决的办法就是负载均衡服务器和其后面的集群。集群里的每台机器就是一个聊天服务
器。
数据是如何流动的？
客户请求到达负载均衡器，负载均衡器根据集群里机器的负载情况，把客户请求发给负
载最轻的机器（关于如何负载均衡器如何知道集群机器的负载情况，可以用push或pull
这两种方式之一。），负载最轻的机器把用户请求放在其队列里，等待客服取得。
客服通过询问负载均衡器，去负载最重的聊天服务器取得客户请求。
客服取得客户请求之后，和客户建立连接，这时，客服知道服务哪个客户，客户知道被
哪个客服服务，他们之间就可以不通过负载均衡器或者聊天服务器，而直接通信。这种
架构就是P2P的模式，bt和电驴是P2P的典范。
这时面试官又抛出一个问题，你还能发现什么问题，如何改进？ | e****e
发帖数: 418 | 42 你的理解是对的。follow up里，每个元素可以用n-1次。
【在 c********t 的大作中提到】
: 我的问题是每个元素能用几次？
: 第一问 2,5,4,6 每个元素被用2次（头尾只用1次）
: 而根据你对follow up的描述，似乎1,2,3,4，可以用2-1,3-1,4-1来组成差值？
:
: 1)
| a***o
发帖数: 1182 | 43 机器挂了怎么办?
pull
【在 e****e 的大作中提到】
: 我来说说bar raiser的系统设计题。
: 最大的问题是如果用户过多，聊天服务器处理不过来（可能是带宽不够，机器性能不够
: ）. 面试官还让我估计了大概在多大的带宽下，多少用户会因为带宽不够造成拥塞。
: 解决的办法就是负载均衡服务器和其后面的集群。集群里的每台机器就是一个聊天服务
: 器。
: 数据是如何流动的？
: 客户请求到达负载均衡器，负载均衡器根据集群里机器的负载情况，把客户请求发给负
: 载最轻的机器（关于如何负载均衡器如何知道集群机器的负载情况，可以用push或pull
: 这两种方式之一。），负载最轻的机器把用户请求放在其队列里，等待客服取得。
: 客服通过询问负载均衡器，去负载最重的聊天服务器取得客户请求。
| e****e
发帖数: 418 | 44 哪个/哪种 机器？
【在 a***o 的大作中提到】
: 机器挂了怎么办?
:
: pull
| a***o
发帖数: 1182 | 45 客服吧?
【在 e****e 的大作中提到】
: 哪个/哪种 机器？
| c********t
发帖数: 5706 | 46 客服不是很重要吧，挂了一个server 重启就是了.如果是重要的话，要persistant
queue.这应该不是问题吧。lz设计很好啊，还会有什么问题呢？
【在 a***o 的大作中提到】
: 机器挂了怎么办?
:
: pull
| e****e
发帖数: 418 | 47 客服或客户机器都有可能挂掉。
如果客户机器挂掉，服务这个客户的客服可以把客户请求转发给异常处理服务器上“断
掉的队列”，异常处理服务器时不时ping一下“断掉的队列”的客户请求的机器，看客
户在线了没有，如果在线了，就把客户请求放在本机上“已恢复队列”，客服优先处理
异常处理服务器上“已恢复队列”的客户请求。前次对话的历史信息保存在某个地方（
也许有个chatting记录服务器），当恢复时，前次对话的历史信息也一同发给客服。
如果客服机器挂掉，客户再次发个客户请求，这个请求是个异常处理请求，负载均衡器
直接把请求转发给异常处理服务器上“已恢复队列”。下面步骤和客户机器挂掉时一样。
The end. | f*****e
发帖数: 2992 | 48 说得天花乱坠，你到底有没有相应的经验啊？还是你现在的工作就是干这个的？
样。
【在 e****e 的大作中提到】
: 客服或客户机器都有可能挂掉。
: 如果客户机器挂掉，服务这个客户的客服可以把客户请求转发给异常处理服务器上“断
: 掉的队列”，异常处理服务器时不时ping一下“断掉的队列”的客户请求的机器，看客
: 户在线了没有，如果在线了，就把客户请求放在本机上“已恢复队列”，客服优先处理
: 异常处理服务器上“已恢复队列”的客户请求。前次对话的历史信息保存在某个地方（
: 也许有个chatting记录服务器），当恢复时，前次对话的历史信息也一同发给客服。
: 如果客服机器挂掉，客户再次发个客户请求，这个请求是个异常处理请求，负载均衡器
: 直接把请求转发给异常处理服务器上“已恢复队列”。下面步骤和客户机器挂掉时一样。
: The end.
| d**********x
发帖数: 4083 | 49 没吃过猪肉应该也看过猪跑吧。。
我现在天天看猪跑，他说的是一个方面，但是不是全部。。
【在 f*****e 的大作中提到】
: 说得天花乱坠，你到底有没有相应的经验啊？还是你现在的工作就是干这个的？
:
: 样。
| e****e
发帖数: 418 | 50 没有，不是，以上全是yy。。。，为了混过面试。。。
【在 f*****e 的大作中提到】
: 说得天花乱坠，你到底有没有相应的经验啊？还是你现在的工作就是干这个的？
:
: 样。
| | | e****e
发帖数: 418 | 51 我若有相应的经验，估计不会问我这个题。考点是如何分析/解决问题，答案如何是第
二位。
【在 f*****e 的大作中提到】
: 说得天花乱坠，你到底有没有相应的经验啊？还是你现在的工作就是干这个的？
:
: 样。
| f*****e
发帖数: 2992 | 52 我也不太了解，不过被你唬到了。
【在 e****e 的大作中提到】
: 我若有相应的经验，估计不会问我这个题。考点是如何分析/解决问题，答案如何是第
: 二位。
| f*****e
发帖数: 2992 | | e****e
发帖数: 418 | | s*******r
发帖数: 2697 | 55 想不到avg 小于O(N^2)的算法
不过排序有助于做一些优化 对某些情况可以快速返回 不必做O(N^2)次计算
比如 1 2 2 2 3, O(NlogN)排序后, O(1)检查最大差值2
当然 如果只是找最大差值O(N)就够了 但排序可能还有助于其他一些case的优化
【在 e****e 的大作中提到】
: 我觉得排序也没用，还是O(N^2)。
:
: 6
| e****e
发帖数: 418 | 56 说得不错，十分赞同。
【在 s*******r 的大作中提到】
: 想不到avg 小于O(N^2)的算法
: 不过排序有助于做一些优化 对某些情况可以快速返回 不必做O(N^2)次计算
: 比如 1 2 2 2 3, O(NlogN)排序后, O(1)检查最大差值2: 当然 如果只是找最大差值O(N)就够了 但排序可能还有助于其他一些case的优化
| d*****y
发帖数: 1365 | 57 先排序,x1=i.其他位置填零
.当然构建这个矩阵是N^2.但是如下所述,我们只需要算2*N个数就可以了.
问题变成找这个矩阵A的最大的N个值.由于A右上角是最大值,所以维持一个max-heap,最
开始的时候把右上角放在heap.然后每次从这个heap里面娶一个数,就把她的左边和下边
放到heap里面,由于对于每个数,每次最多放两个数去heap. 所以O(n log n)
但是这条题目太难了一点,让我面试的时候做,是打死我也做不出来的.
【在 e****e 的大作中提到】
: 说得不错，十分赞同。
| e****e
发帖数: 418 | 58 算上矩阵构建的时间，还是N^2。
我觉得是没有小于N^2，因为只有在对每两个元素求差之后，才知道是否是产生1, 2, .
..(n-1)。我当时就告诉面试官了，他问我：你确定末没有小于N^2的解法？咱当时就无
言以对了。
sunfaquir 提出快速返回的思路，我觉得不错。套用一下，可以弄个布尔数组和计数器
，计数器初始值为零，每次布尔数组里有个元素由false置为true，计数器加一，当计
数器为n-1时，就返回true. 时间复杂度还是N^2。使用方法在一般情况下能提早返回
true。
【在 d*****y 的大作中提到】
: 先排序,x1=i.其他位置填零
: .当然构建这个矩阵是N^2.但是如下所述,我们只需要算2*N个数就可以了.
: 问题变成找这个矩阵A的最大的N个值.由于A右上角是最大值,所以维持一个max-heap,最
: 开始的时候把右上角放在heap.然后每次从这个heap里面娶一个数,就把她的左边和下边
: 放到heap里面,由于对于每个数,每次最多放两个数去heap. 所以O(n log n)
: 但是这条题目太难了一点,让我面试的时候做,是打死我也做不出来的.
| s*********s
发帖数: 140 | 59 如果用dp的话，应该不用构建N*N矩阵吧？只需要一个2行N列的矩阵就行了，当一个row
是current row时，另一个是previous row.
首先我觉得不能被面试官唬住了。有可能他是故意唬你，有可能他对于“复杂度”的理
解和你不同（average or worst?），也有小几率他是错的。这个题，感觉worst case
就是N^2，需要把所有的两两差值都检查一遍。但实际的程序可能在检查所有差值之前
就发现不对提前返回false了，从而avrerage complexity < N^2。这是我的理解，如果
面试官非要说有小于N^2解法的话。
我大致的思路是：首先预操作把duplicate元素去掉。然后排序（前面的回复也提到了
），排序后得到的数组为arr。假设有两个index：i
- arr[i] > 0, 其次 arr[j+1] - arr[i] > arr[j] - arr[i]，第三如果arr[j]-arr[
i]小于了一个数x，那么arr[j-1] - arr[i]必然小于x。
上面的第三条是用来判断结论是否false从而跳出的条件。
设一个2*N的矩阵matrix.matrix[current][i]存第i到第j个元素的差值。 令dif = j -
i. dif=N-1初始化matrix。然后dif递减，
matrix[i][current] = matrix[i][previous] - （arr[i+dif]-arr[i+dif-1]).
同时用一个N长度的boolean数组做checklist。用maxNotfound存储当前还没找到的最大
值,初始值是N-1。利用第三条，所有matrix[current][i]中的最大值必须大于等于
maxNotfound.一旦不符合就return false。
.
【在 e****e 的大作中提到】
: 算上矩阵构建的时间，还是N^2。
: 我觉得是没有小于N^2，因为只有在对每两个元素求差之后，才知道是否是产生1, 2, .
: ..(n-1)。我当时就告诉面试官了，他问我：你确定末没有小于N^2的解法？咱当时就无
: 言以对了。
: sunfaquir 提出快速返回的思路，我觉得不错。套用一下，可以弄个布尔数组和计数器
: ，计数器初始值为零，每次布尔数组里有个元素由false置为true，计数器加一，当计
: 数器为n-1时，就返回true. 时间复杂度还是N^2。使用方法在一般情况下能提早返回
: true。
| c***w
发帖数: 134 | 60 这个是几年经验的面试？每次看都把我们刚工作的吓了一下。。。 | | | d*****y
发帖数: 1365 | 61 我的帖子里面写了，不需要把矩阵完全构建出来。我用矩阵只是为了描述的方便。
实际上每次找到一个数，就把他左边和下边的数算出来，这样的话，挑N个数，每个数
要算他的左邻和下方的邻居。一共只需要算2*N个值，heap操作是 N log N, 排序nlogn
, 所以总共的复杂度nlog n
.
【在 e****e 的大作中提到】
: 算上矩阵构建的时间，还是N^2。
: 我觉得是没有小于N^2，因为只有在对每两个元素求差之后，才知道是否是产生1, 2, .
: ..(n-1)。我当时就告诉面试官了，他问我：你确定末没有小于N^2的解法？咱当时就无
: 言以对了。
: sunfaquir 提出快速返回的思路，我觉得不错。套用一下，可以弄个布尔数组和计数器
: ，计数器初始值为零，每次布尔数组里有个元素由false置为true，计数器加一，当计
: 数器为n-1时，就返回true. 时间复杂度还是N^2。使用方法在一般情况下能提早返回
: true。
| e****e
发帖数: 418 | 62 4， 工作经验对这次面试没啥用。。。
【在 c***w 的大作中提到】
: 这个是几年经验的面试？每次看都把我们刚工作的吓了一下。。。
| e****e
发帖数: 418 | 63 明白了。谢谢。duplicate如何处理？
nlogn
【在 d*****y 的大作中提到】
: 我的帖子里面写了，不需要把矩阵完全构建出来。我用矩阵只是为了描述的方便。
: 实际上每次找到一个数，就把他左边和下边的数算出来，这样的话，挑N个数，每个数
: 要算他的左邻和下方的邻居。一共只需要算2*N个值，heap操作是 N log N, 排序nlogn
: , 所以总共的复杂度nlog n
:
: .
| d*****y
发帖数: 1365 | 64 拍完序以后,先计算a(1,n) = x_n -x_1, 这是最大的差值,所以直接选中.a(1,n)选中以
后,再计算a(1,n-1)和a(2,n),把这两个存到max heap里面.然后挑选出两者中间最大的
那个,假定是a(2,n),那就把a(2,n)pop出来,再把左邻a(2,n-1)和下邻a(3,n)算出来存进
max heap.....一共进行n次这样的操作,得到差值里面最大的前N个数,如果这前N个数是
连续的,就返回true.所以整个操作是n log n.
这个讨论是假定这些差值都不相等,如果相等的话,复杂度能最坏到O(n^2).但是如果考
虑到,上面在判断出现不连续的差值的时候就可以直接跳过下面的操作返回false. 所以
平均复杂度是 n log n. 就像qsort那样.
nlogn
【在 d*****y 的大作中提到】
: 我的帖子里面写了，不需要把矩阵完全构建出来。我用矩阵只是为了描述的方便。
: 实际上每次找到一个数，就把他左边和下边的数算出来，这样的话，挑N个数，每个数
: 要算他的左邻和下方的邻居。一共只需要算2*N个值，heap操作是 N log N, 排序nlogn
: , 所以总共的复杂度nlog n
:
: .
| e****e
发帖数: 418 | 65 多谢详细解答。差值相等的情况应该比较常见，例如第一个例子2 5 4 6里，差值2和1
各有两个duplicates.
我在想，也许heap或者改进型的heap或者其他类似数据结构，可以处理数值想等的情况
，就是多pop出几次相同的最大数而已。或者heap的元素类型就是list。unique的数值
， list含一个值，duplicate的数值，list含多个值，反正heap的元素类型要包含i和j
的值，i和j是原数组的下标智，它们的差值的绝对值就是a(i,j)，也是heap insert(),
max()运算的依据。
【在 d*****y 的大作中提到】
: 拍完序以后,先计算a(1,n) = x_n -x_1, 这是最大的差值,所以直接选中.a(1,n)选中以
: 后,再计算a(1,n-1)和a(2,n),把这两个存到max heap里面.然后挑选出两者中间最大的
: 那个,假定是a(2,n),那就把a(2,n)pop出来,再把左邻a(2,n-1)和下邻a(3,n)算出来存进
: max heap.....一共进行n次这样的操作,得到差值里面最大的前N个数,如果这前N个数是
: 连续的,就返回true.所以整个操作是n log n.
: 这个讨论是假定这些差值都不相等,如果相等的话,复杂度能最坏到O(n^2).但是如果考
: 虑到,上面在判断出现不连续的差值的时候就可以直接跳过下面的操作返回false. 所以
: 平均复杂度是 n log n. 就像qsort那样.
:
: nlogn
| s*********s
发帖数: 140 | 66 能否解释一下为什么是要找所有差值的最大的前N个？不是找1到N-1的差值吗？好像是
最小的N个差值啊？有点没想明白。
【在 d*****y 的大作中提到】
: 拍完序以后,先计算a(1,n) = x_n -x_1, 这是最大的差值,所以直接选中.a(1,n)选中以
: 后,再计算a(1,n-1)和a(2,n),把这两个存到max heap里面.然后挑选出两者中间最大的
: 那个,假定是a(2,n),那就把a(2,n)pop出来,再把左邻a(2,n-1)和下邻a(3,n)算出来存进
: max heap.....一共进行n次这样的操作,得到差值里面最大的前N个数,如果这前N个数是
: 连续的,就返回true.所以整个操作是n log n.
: 这个讨论是假定这些差值都不相等,如果相等的话,复杂度能最坏到O(n^2).但是如果考
: 虑到,上面在判断出现不连续的差值的时候就可以直接跳过下面的操作返回false. 所以
: 平均复杂度是 n log n. 就像qsort那样.
:
: nlogn
| d*****y
发帖数: 1365 | 67 我的感觉:差值相等的情况集中在比较小的那些差值(a(i,j)中i和j比较接近)当中,而这
些值更多的时候是不会被考虑到的.
比如你给的这个例子,这个矩阵
0 2 3 4
0 0 1 2
0 0 0 1
可见相等的差值一般就是集中在对角线附近.这个例子里面差值1不会造成任何烦恼,差
值2会稍微麻烦一点.
当然要严格证明还是挺难的.
不过面试的时候出这种题真是挺变态的.
1
和j
),
【在 e****e 的大作中提到】
: 多谢详细解答。差值相等的情况应该比较常见，例如第一个例子2 5 4 6里，差值2和1
: 各有两个duplicates.
: 我在想，也许heap或者改进型的heap或者其他类似数据结构，可以处理数值想等的情况
: ，就是多pop出几次相同的最大数而已。或者heap的元素类型就是list。unique的数值
: ， list含一个值，duplicate的数值，list含多个值，反正heap的元素类型要包含i和j
: 的值，i和j是原数组的下标智，它们的差值的绝对值就是a(i,j)，也是heap insert(),
: max()运算的依据。
| d*****y
发帖数: 1365 | 68 题目里面是让找出一个从1到x_n-x_1的连续序列吧?
【在 s*********s 的大作中提到】
: 能否解释一下为什么是要找所有差值的最大的前N个？不是找1到N-1的差值吗？好像是
: 最小的N个差值啊？有点没想明白。
| e****e
发帖数: 418 | 69 反正是要找1,2,...,N(如果N是原数组的长度，其实是1,2, ...,N-1)，从1开始到N,或
者从N开始到1不是一样末。
【在 s*********s 的大作中提到】
: 能否解释一下为什么是要找所有差值的最大的前N个？不是找1到N-1的差值吗？好像是
: 最小的N个差值啊？有点没想明白。
| e****e
发帖数: 418 | 70 猜猜给了我几分钟解决这道follow up题?
5分钟!
【在 d*****y 的大作中提到】
: 我的感觉:差值相等的情况集中在比较小的那些差值(a(i,j)中i和j比较接近)当中,而这
: 些值更多的时候是不会被考虑到的.
: 比如你给的这个例子,这个矩阵
: 0 2 3 4
: 0 0 1 2
: 0 0 0 1
: 可见相等的差值一般就是集中在对角线附近.这个例子里面差值1不会造成任何烦恼,差
: 值2会稍微麻烦一点.
: 当然要严格证明还是挺难的.
: 不过面试的时候出这种题真是挺变态的.
| | | d*****y
发帖数: 1365 | 71 佬印面试官?
【在 e****e 的大作中提到】
: 猜猜给了我几分钟解决这道follow up题?
: 5分钟!
| e****e
发帖数: 418 | 72 不是。东南亚。
【在 d*****y 的大作中提到】
: 佬印面试官?
|
|
