f***g
发帖数: 214 | 1 三男：
1. 两个圆在什么条件下相交？
就是两圆心和两半径的关系？
比如：!(D > (R1 + R2) || (D + R1) < R2) ？
2. m*n的矩阵in place rotation?
关键是数据是怎么保存的吧。
解决了这个是不是可以rotate m*m
然后递归。
白男：
1. n个城市之间的距离要存下来，怎么存最省空间？
二维数组？
2. 前序中序重建树。
经典。
国女：
1. 64 bit的integer,怎么数里面1的个数？
followup: 要是多次使用你怎么办？你不觉得要用空间的太多了吗，怎么办？
查表 table[256]
2. p*q的matrix,从左下到右上路径数？
followup: 你这个算的会有什么问题？你怎么解决？
经典。可以直接算
followup: matrix中有障碍呢？
DP就行了吧
三女：
1. m长的array，长度为k的sliding window,求每次slide一下window里的最大值。
然后问test cases.
经典。
... 阅读全帖 |
|
E***n
发帖数: 166 | 2 假设矩阵是n * n的，
中数必然在从右上到左下的对角线上,所以找到这条对角线上的中数就行了，对角线上
一共有m+n个元素，时间复杂度O（n）
如果找到第k个元素，我的方法是先拿出每行的第一个元素，组成一个最小堆，然后不
断的extracMin,然后从对应的行再取下一个元素，放入最小堆中，Reheap。连续k次
extractMin可以得到k th element
最小堆有n个元素，这样需要k * log n时间
貌似通过DP有更好的方法，我忘了 |
|
E***n
发帖数: 166 | 3 我改掉了，我的方法只能处理方阵
你这个例子,5恰好是从右上到左下的对角线上（3，5，7）的“中数”啊 |
|
E***n
发帖数: 166 | 4
我的算法对这个例子也没问题啊，就是找右上到左下的对角线（2，3）的中数，结果是
2.5（depends on definition）, 或者是2或3 |
|
d*******l
发帖数: 338 | 5 先明确一下，这题要求的是最后的不规则图形的边界点，这个理解上没有异议吧？你的
例子中就是A的左下、左上，AB的那个交点，以及B的左上、右上、右下。这个不画出来
要讲清楚确实有点难，你这个图中，B的一条边把A分成了两个矩形，A的一条边（所在
直线）也把B分成了两个矩形，所以我们有4个单位区间上的矩形，第二个区间上有两个
小矩形，一个来自A，一个来自B，我们取高的那个。然后对于每两个相邻的单位区间，
只要有高度差就有两个边界点，否则就没有。 |
|
d*******l
发帖数: 338 | 6 上面代码中矩形的表示方式是左下和右上顶点的坐标。所有矩形的左下顶点必须都是共
线的。测试的时候这样就可以：
int main()
{
FindVertex fv;
fv.add(1, 0, 5, 2);
fv.add(2, 0, 6, 3);
fv.add(4, 0, 8, 4);
fv.solve();
return 0;
}
最后顺时针输出所有边界上的顶点。 |
|
p*****u
发帖数: 310 | 7 谁说所有矩形的左下顶点必须都是共线的？难道不能右上顶点和其他矩形的左下顶点共
线？ |
|
i**********e
发帖数: 1145 | 8 是先假设 ：
“已经放了 n-1 个棋子在 n*n 个格子里，而这个不能填满”
然后扩展与 n+1*n+1 个格子，就把之前这结果引申过来，这时候只能选择左上/下角，右上/下角都不重要，不影响最后结论。
然后这时候你只能选一个格子放一个棋子作为 n+1*n+1 棋盘的起点，他的证明就是不管你怎么放，最后都是不可能填满棋盘。 |
|
|
l*****a
发帖数: 14598 | 10 问一下你们的PM
右上/右下 people you may know出现两次，完全一样
是咋回事？ |
|
z*********n
发帖数: 5 | 11 一个矩阵，比如m*n
从一个点可以访问它的八个相邻点（上、下、左、右、左上、左下、右上、右下）
如果一个方向上的点已经被访问过了，则可以继续访问这个方向上的下一个未被访问的
点（比如当前点是(5,5)，如果（5,4）已经被访问，则可以访问(5,3)，如果(5,3)也被
访问了，则可以访问（5,2）…… 对角线方向的也是如此,(5,5)可以访问(4,4)，如果(
4,4)已经被访问，可以访问(3,3)……）
现在需要遍历这个矩阵上的所有点，则有多少种可能性？（起点和终点不限） |
|
h****n
发帖数: 1093 | 12 dfs 访问标记 counter
不过递归总归开销太大 不知道有没有直观的dp解法
一个矩阵，比如m*n从一个点可以访问它的八个相邻点（上、下、左、右、左上、左下
、右上、右下）如果一个方向上的点已经被访问过了，则可以继续访问这个方向上的下
一个未被访问的点（比如........
★ Sent from iPhone App: iReader Mitbbs Lite 7.56 |
|
f*****e
发帖数: 2992 | 13 来自主题: JobHunting版 - G 家面经 (0,2,2,1)不在45度对角线上，所以不用算。只算45度对角线上的。
一层一层推进，就可以到达右上端点(m,n) |
|
f*****e
发帖数: 2992 | 14 来自主题: JobHunting版 - G 家面经 (0,2,2,1)不在45度对角线上，所以不用算。只算45度对角线上的。
一层一层推进，就可以到达右上端点(m,n) |
|
j******2
发帖数: 362 | 15 分成四区，每次递归到右上或左下那个，我觉得是log(n)+log(m), n,m是矩阵的长宽。
大家觉得呢？ |
|
z****e
发帖数: 54598 | 16 复杂度是(lgn)^2 ＝ n
跟从右上开始是一样的 |
|
g*****g
发帖数: 212 | 17 Sorry，没仔细看题
首先想象2个排序数组，这些2 2 之和构成的young氏矩阵，
查找一个数是否在young氏矩阵中的方法，最快是可以Log（n），
也即，从左下或者右上开始，分别对行和列二分查找. 具体可以看wiki。
数组排序本身也是 logn
对于第三个数组，无需排序，对每个元素在矩阵中查找 0-C[i]
这个问题的复杂度在于，你不能建这个矩阵并保存，因为建立矩阵的复杂度就是N^2了，
你只能用逻辑上的矩阵执行查找。
比如 M[i]行的元素
就是A[i] + B[0...n] |
|
x****g
发帖数: 1512 | 18 抛砖引玉一下? 呵呵.
1: "its children"我的理解是直属子节点? 如果间接也算方法类似?
每个节点保持2个值表示以自己为根子树,改节点参与和不参与的最大node set.
那么有NULL节点0,0. 那么
dp[root][0] = max(dp[root->left][0],dp[root->left][1]) +
max(dp[root->right][0],dp[root->right][1])
dp[root][1] = dp[root->left][0]+dp[root->right][0] + 1
//0表示自己不参与,1表示自己参与.
实际代码只要f(node, inMax&, notInMax&)递归就可以了,最后返回跟节点2个数字
中大的那个即可.
4: "X形状" 我理解为奇数的n*n? 对于任何一个点 i,j,分4个方向分别表示以该点为
右下,左下,右上,左上斜着的连续的1的个数(含自己).
那么该点为中心的最大X中1的个数为min(4个方向计数)*4-3.
这... 阅读全帖 |
|
p********n
发帖数: 165 | 19 M[i][j] 记录从木头的第 i 段 到第j段 之间 的subsolution。
细节：
首先对角线上的元素(从左上到右下)都初始化0, 因为 i 到i 段不用cut，所以cost 为
0
从i,j 之间，假设我们只能cut 两个大段， 左大段和右大段，则总共有 i-j-1种cut
方法(i j之间每个可能cut的地方都试一次)
M[i][j] ＝ A[j] - A[i] (注释：i-j之间的木头长度) +
min(M[i][i] + M[i+1][j], M[i][i+1] + M[i+2][j]), ... M[i][j-1] + M[j
][j]);
这个M矩阵，我们从下往上计算，每层从右往左计算， 只有矩阵的右上一半被计算，
左下方不管。
24。 |
|
W*********y
发帖数: 481 | 20 从右上开始找，
若大于input，move down
若小于input，move left,
若等于input, return
一直找到左壁或者下壁。ruturn false.
这样扫 2*n个元素必能找到， |
|
W*********y
发帖数: 481 | 21 从右上开始找，
若大于input，move down
若小于input，move left,
若等于input, return
一直找到左壁或者下壁。ruturn false.
这样扫 2*n个元素必能找到， |
|
|
z******t
发帖数: 59 | 23 的第8个例题。
这个题目通常有两个解法：
1、在对角线上二分查找。在对角线上找到比指定数字小的最大数，然后用这个数把二
维数组分成4个子数组。目标数字只有可能出现在刚才找到数组的右上子数组或者左下
子数组。接着在这两个子数组中递归查找。
这个思路的代码实现稍微有点复杂，在面试过程中不容易一次性写对。
2、每次拿数组右上角的数字和目标数字比较。如果相等，找到了。如果比目标数字大
，去掉最右边的一列；如果比目标数字小，去掉做上面的一行。接着用同样的思路，在
剩下的数组中继续拿右上角的数字和目标数字比较。
这个思路一旦把思路想清楚，写代码容易很多。这是面试过程中推荐的解法。 |
|
g***a
发帖数: 58 | 24 连通域是按照相邻关系来定义的，所有相邻的值相同的pixel组成的区域
相邻可以定义成4联通(上下左右, VN neighborhood)，或者8连通(加上左上，右下，左
下，右上，Moore neighborhood)，这个要和面试官confirm一下.
比如下面这个例子
0 0 1 0
1 0 0 0
1 1 0 1
4联通的话，“1”组成的连通域有3个，“0”组成的连通域只有1个。
题目比较基本，用graph traversal就可以了。 |
|
|
e********2
发帖数: 495 | 26 第一题就用heap + flood sweep向右上扫。
第二题其实就是同时找最大正的连续和和最小负的连续和。 |
|
发帖数: 1 | 27 下图，底线中点到右上顶点的距离比上单根火柴就是根号7。用毕达哥拉斯定理证明。
__
/\ /
/__\/
一个边长2根火柴的等边三角形可以用4个边长为1根火柴的等边三角形拼起来。 |
|
z*********n
发帖数: 1451 | 28 总结了一下常见的反对刷题的观点。逐一批驳。
省的我一段话复制粘贴好几次，以后直接贴这帖子里的引用就好了。先写这么多，将来
慢慢补充。
对刷题有疑问的直接在帖子里找到自己问题，对号入座就好了。
0.我压根就不想跳槽，我很满意现在生活，能不能不刷：
答：能。此帖和你没什么事了，请点左上/右上X号。
1.刷了500LC，结果不会交流，面试挂了，刷题刷傻了吧。
答：刷题不是只刷算法题，系统设计题，Behavioral questions, OOD， 甚至口语加情
商都得刷。你面专门职位比如DS/ML，domain knowledge也得刷。题=面试题，不是就LC
。刷如果理解不了，念成“练”，或者“极其努力的练”。你去面试，我让你极其努力
的练面试题，你敢说我说的有问题？
2.刷的题工作中都不用，浪费时间。
答：举例回答，国足招门将，测百米，你跑了1分钟，测5000米，你跑了3小时，然后被
拒了。你说你有10年门将经验扔了不看，谁TM当门将的在场上冲百米，跑5000米？刷题
测的是程序员基本素养，你基本素养不合格，只能说明你那10年经验是在低级别队伍混
的，一文不值。
3.刷题就是年龄歧视。
... 阅读全帖 |
|
l******a
发帖数: 16364 | 29 我用google map,右上有个能下拉的菜单，里面有路况，地名等选项。把地名点掉就行。 |
|
w**7
发帖数: 1265 | 30 ☆─────────────────────────────────────☆
faithjing (蛋，Sammy的妈咪) 于 (Sun Mar 13 23:55:42 2011, 美东) 提到:
只给链接，不给详细信息，不贴大方位图，小方位图，和内部结构图，都不给看。
有问题在这个帖子上问，我有空上来回答。只回答和房子风水有关的，不给人看命算卦
。
请你把信息跟帖，不要发在我邮箱里，邮箱都满了。 不要单单把买房链接给我，那样
根本看不准。
需要介绍的是
小区周围环境，
偏远，安静，闹市，之类的
地理，高低坡，平地，小河，湖之类的。
房屋内的特点
拱形门，内部有房梁，门对窗之类的。
最好自己画一个一楼建筑图。打听一下前主人的来去信息。
我给大家详细看，信息越多，分析的就越精确。
由于没法看到实物，网上批会存在误差，请个别挑剔人士绕道。
☆─────────────────────────────────────☆
wshxzt (wshxzt) 于 (Mon Mar 14 00:07:49 2011, 美东) 提到:
http://www.redfin.com/W... 阅读全帖 |
|
O***C
发帖数: 1219 | 31 右上侧紧邻门牙边的一颗小牙磕掉了半个，不知要花多少钱补？
我是AETNA DMO保险。
谢谢指教！ |
|
|
v*******e
发帖数: 11604 | 33
前上，前中，前下；
后上，后中，后下；
左上，左中，左下；
右上，右中，右下；
另外附近的铁皮风管也来几张。 |
|
m******9
发帖数: 223 | 34 gas water heater 是Rheem 2008年造的但是挂GE的牌子卖的，是 75gallon。heater
顶部有3个管子接到heater 上。 右边是冷水管，左边是热水管，中间是接vent到 屋外
的。前一段时间发现地上周围有水。一看heater顶端冷水管和heater connection 的地
方有积水并且冷水管有腐蚀。顶部中间和vent 对应的地方用手摸摸也有水，热水管那
边没问题。用一个盆子放在Temperature and pressure tube下面测了测， TP valve
and tube 没问题。
打manufacturer 的电话， 说还在6年limited warranty 以内。 但只管材料费（如果
repairable 只管提供零件，如果不是repairable， 只提供一个新的heater）。 不包
括 inspection fee， 维修和replacement 安装的labor。heater 本身的费用估计在
800左右， 安装和把旧的拖走我想三四百怎么也够了吧。 我问能不能给replace 一个
新的heater？他们说现在不能定。 他... 阅读全帖 |
|
m******9
发帖数: 223 | 35 gas water heater 是Rheem 2008年造的但是挂GE的牌子卖的，是 75gallon。heater
顶部有3个管子接到heater 上。 右边是冷水管，左边是热水管，中间是接vent到 屋外
的。前一段时间发现地上周围有水。一看heater顶端冷水管和heater connection 的地
方有积水并且冷水管有腐蚀。顶部中间和vent 对应的地方用手摸摸也有水，热水管那
边没问题。( 不知道为什么图片右边显示不出来， 但你点击图片就能看到）。用一个
盆子放在Temperature and pressure tube下面测了测， TP valve
and tube 没问题。
打manufacturer 的电话， 说还在6年limited warranty 以内。 但只管材料费（如果
repairable 只管提供零件，如果不是repairable， 只提供一个新的heater）。 不包
括 inspection fee， 维修和replacement 安装的labor。heater 本身的费用估计在
800左右， 安装和把旧的拖走我想三四百怎么也够了吧。 我问能不能... 阅读全帖 |
|
i***e
发帖数: 9429 | 36 这个relay,现在我没有接线图，
你需要在relay 上记下:
左上街头(1)：什么颜色线，接到哪儿去？
左下街头(2)：什么颜色线，接到哪儿去？
右上街头(3)：什么颜色线，接到哪儿去？
右下街头(4)：什么颜色线，接到哪儿去？ |
|
|
|
|
J**G
发帖数: 1829 | 40 我也想说，毫无层次感，茎断神不断这中最基本的技巧都没有。右上几个枝垭，东倒西
歪，没骨感，没美感。。。 |
|
y***j
发帖数: 11235 | 41 放大100倍从右上往左下数第8个葱花的发白部分有倒影 |
|
p**********g
发帖数: 9558 | 42 我忽略了这个部分
“放大100倍从右上往左下数第8个葱花的发白部分有倒影”
其他的都看了 |
|
s****p
发帖数: 124 | 43 【 以下文字转载自 Seattle 讨论区 】
发信人: sodcap (sodcap), 信区: Seattle
标 题: 冰箱冷藏室最上面一层漏水，怎么回事？
发信站: BBS 未名空间站 (Tue Mar 18 23:25:36 2014, 美东)
家里的冰箱是2011年买的Whirlpool Gold，左右两门的那种。具体型号见：
http://www.whirlpool.com/-%5BGSC25C6EYY%5D-1002918/GSC25C6EYY/
一周前开始，我每天早上都发现右边冷藏室最上面一格漏出一大片的水，都流到冰箱下
面的地板上了。据我观察，发现水似乎是从右上面的Water Filter里面漏出来的，因为
Filter正下方的盒装豆腐盒上满满都是水。冰箱里装了不少食物，很重且没有滑轮，我
还没有把冰箱整个拖出来检查后面的各种水管。我怀疑是那个Filter的瓶子本身漏水，
今天早上把Filter瓶子给抽出来了。但今天晚上发现下面的豆腐盒上还是很多水。
Water Filter小格和Filter瓶子见图片。
这个是否可能那个Filter瓶子坏了造成漏水，还是可能冰箱... 阅读全帖 |
|
b*****o
发帖数: 715 | 44 （1）宽度。主要有30和36两种。36的贵，而且不是每个厨房都能放下36的。
（2）厚度。有normal和counter depth（即shallow depth）两种。shallow的容量小，
贵，但是美观。
（3）高度。一般都是70。但是有些四门冰箱会更高些。
（4）即使是french door。也有可能是2门（左右），3门（左上，右上，下），4门（
即一个田字形状）。价格是2<3<4
（5）icemaker和water filter一般冰箱都有，区别在于是dispenser在门上，还是在冰
箱内。在门上的贵。
（6）冷冻和冷藏的大小比例。即使总容量一样，有的冰箱会冷藏部分大些或小些。
（7）是不是声音太响。
暂时就想到这些。 |
|
f****y
发帖数: 53 | 45 刚测完，上面两根线应该就是你说的line，下面的应该是load?
右上黑线对中间的钉子（ground）120V，左上白线对地0V，两线之间0V
disconnect连着的时候下面两根黑线同样
难道电闸出了问题，附图，看起来没有tripped,多谢大神指导，下一步怎么办？ |
|
b*******c
发帖数: 20683 | 46 美国超市里买来的糖和盐不就在罐子里了？不理解为啥要倒出来。我家平时放炉子右上
方的橱柜里，做菜都是拿出来直接倒的，用完放回柜子里。小勺...说实话没那个美国
时间中间多一道程序。中餐调料不就是凭感觉么，要是没感觉，想精确，就上厨房秤。
实在要分装，又要漂亮的容器，又要看着整洁，我能想到的是以前Costco 看到的卖一
套的各种西餐调料的，玻璃小瓶子，开口可以撒的，带个调料架，平时就是不藏起来，
直接放台面上，也挺漂亮的。要是喜欢西餐调料的话，可以买一套，用完了装中餐调料。 |
|
y***l
发帖数: 6963 | 47 实际照片现在没有
这个是lot的
storm drain在右上 |
|
t****z
发帖数: 8931 | 48 啥金色事务，难道做个金边框，怎么呼应
我发现这个画有右上侧光时，
有立体感非常艺术高大上a，
因为丙烯堆起来浮雕式的，侧光增加很多阴影，明暗金银色有光泽。
但是正面光就很平淡
如果是另一个方向侧光，看起来很nasty，脏兮兮 |
|
e**o
发帖数: 126 | 49 控制器设定低温后，一会就有噪音了。似乎是制冷工作了。而且下图中，右上那个隔热
管表面有水，与箱子连接处有冰。
您能不能指一下哪个是blower电容？
3年的空调，似乎不应该坏了。
谢谢。 |
|
e**o
发帖数: 126 | 50 中午发现我昨天犯错了。我昨天把AC的电源关了。可能这是不制冷的原因。
经过是这样：
星期天换了air filter, 星期一晚上下雨了。
星期二早上空调不工作，cool 设定到低温（比如72F)后，无论fan在 auto 还是on上，
出风口都没有冷风吹出来。
中午时试着检查电源，blower等， 结果把 AC电源关了，（后来一直忘了开），测了
blower 和控制器的电压，都是24V。 后来把控制器设置fan --on , cool上，结果出风
口就吹出冷风了（大概是1-2小时后）。再看blower那个箱子底下一大滩水， 有个管子
也在流水。我以为空调工作了。
结果下午到晚饭的时候，温度都降不到设定。
晚上只好出去住了。带着发烧的娃，太麻烦了。
星期三上午发现AC电源关了， 重新打开AC电源，温度可以下到73F,却到不了设定的70F.
星期三下午，外面公司的人来了，看到又结冰了（四楼图中右上那个黑色管子，白色是
冰）
那个公司的人 打开了出blower上方， 指给我看里面结冰了。说那个冰堵了出风口。我
让他看户外机， 发现也结冰了， 他说必须等冰化了，才能检测。 他把cool 变of... 阅读全帖 |
|
