某公司两个题面跪了 - 未名空间MITBBS历史存档

f*42013-03-25 07:03

1 楼

公司在国内，3年前拿到过offer。
电面水过。在没有给头结点的单链表中删除某结点，给出做法并问了缺陷。面完后告诉
mm说以前做过这题但当场没自首，被鄙视了一番。
一面：1 给三个杯子容量a/b/c,怎么最快得到n升水。说了穷举法用来判断，被鄙
2 返回二叉树哪一层的结点数最多。快写完了面试官说你这好像是递归啊我不要
递归
二面：项目设计及改进；讨论用4k buffer来包装系统read这题，如何判定是暂时没数
据还是网络错误。
三面：看面试官的面相是搞过acm的。先是系统设计，完了问约瑟夫问题，鉴于之前被
鄙视就自招了刚听过有3行代码解法。acmer马上说换一个。看他矗着想题顿感不妙。说
有一堆扑克牌N张，点面是0~N，可能有重复，但算作不同的牌，依次取牌，只能从点数
不超过手中扑克数量的牌中取，求取法数。
没到第四轮就被带出门。倒水杯在面试官走出门想到二爷常用的方法，扑克牌在回家路
上默默知道真相了眼泪差点掉出来。发现面试中遇到没做过的题就很难发挥出底下练题
时的水准，可能是从没发面筋吧。.。

C*L2013-03-25 07:03

2 楼

请问倒水杯比较简单的方法是什么？

l*82013-03-25 07:03

3 楼

第三轮是DP吧？

【在 f*******4 的大作中提到】

: 公司在国内，3年前拿到过offer。
: 电面水过。在没有给头结点的单链表中删除某结点，给出做法并问了缺陷。面完后告诉
: mm说以前做过这题但当场没自首，被鄙视了一番。
: 一面：1 给三个杯子容量a/b/c,怎么最快得到n升水。说了穷举法用来判断，被鄙
: 2 返回二叉树哪一层的结点数最多。快写完了面试官说你这好像是递归啊我不要
: 递归
: 二面：项目设计及改进；讨论用4k buffer来包装系统read这题，如何判定是暂时没数
: 据还是网络错误。
: 三面：看面试官的面相是搞过acm的。先是系统设计，完了问约瑟夫问题，鉴于之前被
: 鄙视就自招了刚听过有3行代码解法。acmer马上说换一个。看他矗着想题顿感不妙。说

c*r2013-03-25 07:03

4 楼

第一题好像是DP吧，爬楼梯的变形？

f*42013-03-25 07:03

5 楼

具体是这样的：a,b,c三个整数为杯子容量，用总共为c的水量，最快怎么得到n的量

【在 c********r 的大作中提到】

: 第一题好像是DP吧，爬楼梯的变形？

n*42013-03-25 07:03

6 楼

倒水杯是考linear combination吧三维空间一条直线找feasible 借就行

A*o2013-03-25 07:03

7 楼

太高深了，爱莫能助啊

【在 f*******4 的大作中提到】

: 公司在国内，3年前拿到过offer。
: 电面水过。在没有给头结点的单链表中删除某结点，给出做法并问了缺陷。面完后告诉
: mm说以前做过这题但当场没自首，被鄙视了一番。
: 一面：1 给三个杯子容量a/b/c,怎么最快得到n升水。说了穷举法用来判断，被鄙
: 2 返回二叉树哪一层的结点数最多。快写完了面试官说你这好像是递归啊我不要
: 递归
: 二面：项目设计及改进；讨论用4k buffer来包装系统read这题，如何判定是暂时没数
: 据还是网络错误。
: 三面：看面试官的面相是搞过acm的。先是系统设计，完了问约瑟夫问题，鉴于之前被
: 鄙视就自招了刚听过有3行代码解法。acmer马上说换一个。看他矗着想题顿感不妙。说

e*g2013-03-25 07:03

8 楼

一面的第二题...我曾经给我国内老板研究生面试出过一个一摸一样的, 递归就normal
了吧, 你面的哪个公司啊...lol, 好奇的问一下...

【在 f*******4 的大作中提到】

: 公司在国内，3年前拿到过offer。
: 电面水过。在没有给头结点的单链表中删除某结点，给出做法并问了缺陷。面完后告诉
: mm说以前做过这题但当场没自首，被鄙视了一番。
: 一面：1 给三个杯子容量a/b/c,怎么最快得到n升水。说了穷举法用来判断，被鄙
: 2 返回二叉树哪一层的结点数最多。快写完了面试官说你这好像是递归啊我不要
: 递归
: 二面：项目设计及改进；讨论用4k buffer来包装系统read这题，如何判定是暂时没数
: 据还是网络错误。
: 三面：看面试官的面相是搞过acm的。先是系统设计，完了问约瑟夫问题，鉴于之前被
: 鄙视就自招了刚听过有3行代码解法。acmer马上说换一个。看他矗着想题顿感不妙。说

n*n2013-03-25 07:03

9 楼

It is possible to always achieve the target n with three cups? How to prove
this?
I'm imaging another case with only two cups:
Assume there is a large enough holder cup to hold the target water, and
there are two measured cups,
cups = 3,2
target: 7 = 3+3+(3-2) ; get 2 3cup into holder and then get the remaining
water in 3cup-2cup into it
cups = 9,8
target: 7 = 8-(9-8) ; it might not be possible to do this with cups,
possible way is: 7 = (9-8) + (9-8) + ...
cups = 9,5 ; with these two cups we can get (4)=9cup-5cup
target: 2, 3, 6, 7, 11, 15 ; can not be generated
target: 10=5x2, 12=(4)x3, 13=9+(4), 14=9+5, 16=(4)x4, 17=9+(4)x2, 18=9x2, 19
=9+5x2, ; now we have 4 consecutive numbers, all numbers can be generated
with +(4), although not the simplest form 20=(4)x5, 21=(4)x3+9, 22=9x2+(4),
23=9x2+5, 24=(4)x6, 25=5x5, 26=22+(4), ...

【在 f*******4 的大作中提到】

: 具体是这样的：a,b,c三个整数为杯子容量，用总共为c的水量，最快怎么得到n的量

y*k2013-03-25 07:03

10 楼

什么职位呀？
倒水那个是数学。

y*a2013-03-25 07:03

11 楼

倒水那个条件好像没说清楚吧？应该有一些约束，楼主没说。

q*c2013-03-25 07:03

12 楼

这是面试的人有病，你没见过的题目才是真实水平，
但是现在的人都不想看真实水平，要看虚假水平－－要看你背过某道题没有。

【在 f*******4 的大作中提到】

: 公司在国内，3年前拿到过offer。
: 电面水过。在没有给头结点的单链表中删除某结点，给出做法并问了缺陷。面完后告诉
: mm说以前做过这题但当场没自首，被鄙视了一番。
: 一面：1 给三个杯子容量a/b/c,怎么最快得到n升水。说了穷举法用来判断，被鄙
: 2 返回二叉树哪一层的结点数最多。快写完了面试官说你这好像是递归啊我不要
: 递归
: 二面：项目设计及改进；讨论用4k buffer来包装系统read这题，如何判定是暂时没数
: 据还是网络错误。
: 三面：看面试官的面相是搞过acm的。先是系统设计，完了问约瑟夫问题，鉴于之前被
: 鄙视就自招了刚听过有3行代码解法。acmer马上说换一个。看他矗着想题顿感不妙。说

c*w2013-03-25 07:03

13 楼

counter example:
cups = 2,4,6,8,10.....
n = 1,3,5,7,9......

prove

【在 n**n 的大作中提到】

: It is possible to always achieve the target n with three cups? How to prove
: this?
: I'm imaging another case with only two cups:
: Assume there is a large enough holder cup to hold the target water, and
: there are two measured cups,
: cups = 3,2
: target: 7 = 3+3+(3-2) ; get 2 3cup into holder and then get the remaining
: water in 3cup-2cup into it
: cups = 9,8
: target: 7 = 8-(9-8) ; it might not be possible to do this with cups,

f*42013-03-25 07:03

14 楼

是这么问：给三个杯子(容量a/b/c为整数)，两个为空，另一个装满水。现在要用这杯
水通过三个杯子互相倒，得到容量为n的水。返回最少的倒腾次数，无法得到则返回-1。
当时就说，用a/b/c的最大公因子除n来界定循环次数，brute force出所有的可行，从
中判定最少操作数。正想如何判定最少次数的时候，面试官说时间不够下一题吧。
后来想应该是期望得到BFS的回答

【在 y**********a 的大作中提到】

: 倒水那个条件好像没说清楚吧？应该有一些约束，楼主没说。

i*m2013-03-25 07:03

15 楼

第一题DP，coinChange 的变形。