m*****k
发帖数: 731 | 1 与100, 200有关系么？
1. set lastPoped = null,
2. print root,
3. push root into a stack S,
3. while (s.size()>0):
if not s.peek().hasChildren():
lastPoped = s.pop()
else:
s.push(s.peek().getSibling(lastPoped) )
Node.getSibling(Node childX) will return first Child if childX is null,
otherwise return x's next sibling.
看来来出题人默认stack不会out of mem，否者来个极端的例子， 内存只允许stack存2
个Node，没法玩了。
或者也许我理解错了题意？ |
|
w********g
发帖数: 106 | 2 你说得对，面试官当时对我说问题的关键就是你所说的“然后接着递归第101~200”。
就这一步怎么做？
我已经用stack把从根到第101个节点的path记录下来了。
（只记录了类似root - child - grand child - ...... - 101节点，这样的路径） |
|
l******6
发帖数: 340 | 3 struct node;
void print100(stack& waitStack);
struct childList{
node* curNode;
childList* next;
};
struct node{
void* data;
childList* children;
};
void print(node* root)
{
if(!root)
return;
childList* dummy = new childList();
dummy -> curNode = root;
dummy -> next = NULL;
stack waitStack;
waitStack.push(dummy);
while(!waitStack.empty())
{
print100(waitStack);
}
delete dummy;
}
void print1... 阅读全帖 |
|
w********g
发帖数: 106 | 4 这个方法没有用递归。题目要求必须用递归才行。我觉得这才是最难的地方。如果用
iteration，一个for循环就能实现向右的移动。可是如果必须用递归，怎么解决递归向
右和依靠push右侧兄弟导致的重复呢？
我的解决办法是：
任何一个node都只向下递归打印第一个child；
除了叶子以外，任何node都不向右递归自己的sibling；
只有叶子才向右侧递归打印；
只有当前node没有右侧的sibling时才递归打印栈顶的node，
这个栈顶的node其实就是当前node的先根遍历时的next node。
很多特殊情况还没考虑，但是大意就是这样。明天写一下code。 |
|
l******6
发帖数: 340 | 5
void printn(stack& waitStack , int n)
{
if(n == 0 || waitStack.empty())
return;
childList* curHead = waitStack.top();
waitStack.pop();
dealWith(curHead -> curNode -> data);
if(curHead -> next)
waitStack.push(curHead -> next);
if(curHead -> curNode -> children)
waitStack.push(curHead -> curNode -> children);
printn(waitStack , n-1);
} |
|
s**x
发帖数: 7506 | 6 这个就是变相的问你iterative preorder scan 怎么整？ |
|
w********g
发帖数: 106 | 7 太强了！！！你的最后一行code我写了很多行实现，分了各种情况。看了你的code，才
发现其实那么多种情况本质上就是递归调用到栈顶，顿时佩服得五体投地。万分感谢赐
教！
void printn(stack& waitStack , int n)
{
if(n == 0 || waitStack.empty())
return;
childList* curHead = waitStack.top();
waitStack.pop();
dealWith(curHead -> curNode -> data);
if(curHead -> next)
waitStack.push(curHead -> next);
if(curHead -> curNode -> children)
waitStack.push(curHead -> curNode -> children);
printn(waitStack , n-1);
} |
|
|
z****u
发帖数: 41 | 9 不清楚这里的 "curHead -> next" 是不是在使用指向sibling的指针？题目中不是说没
有指向sibling的指针么？还是我理解错了？ |
|
z****u
发帖数: 41 | 10 楼主啊，他的代码这里的 "curHead -> next" 貌似使用了指向sibling的指针，不是没
有指向sibling的指针么？
我怎么觉得这一题就是iterative inorder 的题目呢，只是不是binary tree而已。pop
一次，n++,till n==100或者stack.empty(). chenglg的代码本质就是用了吧while(n++
<100) 改成了 f(n) = sth + f(--n)而已。 |
|
|
p**o
发帖数: 3409 | 12 “内存都够大。只是打印机的内存不够大，不能一次把所
有的node都存在打印机内存里，所以需要分批次打印。” 是什么意思？
整棵树在不在内存里？
如果在内存里，那么把遍历过程简单地写成迭代器，
每次不就可以从上次暂停的地方继续遍历和打印了？
是不是树太大要放磁盘上，每次只能载一部分到内存里，而你没有理解题意？ |
|
|
l******6
发帖数: 340 | 14 struct childList{
node* curNode;
childList* next;
};
struct node{
void* data;
childList* children;
};
curHead is a pointer of childList type , not a node type. childlist have
sibling pointer while node doesn't have.
It is true it is only a preorder iterative traverse, the point is to modify
the code so that parameter can be passed to the printn() function nicely. |
|
|
w*******l
发帖数: 33 | 16 请问 CHILDLIST* next 什么时候会被赋值 （不为null）？
在dealwith（）funct 里面吗？ |
|
r*******h
发帖数: 315 | 17 感觉树像文件系统的目录结构，企业环境中数百万个文件和目录的文件系统太常见了，
要求的前序遍历像unix命令tree。关键是如果栈溢出时，就得把栈的内容写入磁盘，比
如一次写一个文件，栈空的时候再按后写先读的顺序把文件一个个读入栈进行处理，其
余就是典型的前序遍历的算法。还可以考虑多线程双缓冲，这样遍历和栈的磁盘读写都
可以同时进行了。 |
|
|
l**********1
发帖数: 415 | 19 试着写了一个，求指导。
print100(Stack stack, TreeNode root, int index){
if(stack.isEmpty()) return;
if(index==101) return;
System.out.println(root.val);
stack.push(root);
if(root.left!=null)
print100(stack, root.left, index+1);
else if(root.right!=null)
print100(stack, root.right, index+1);
else{
while(!stack.isEmpty() && root.right==null){
root=stack.pop();
}
print100(stack, root.right, index+1);
}
}
initialize
Stack stack = new Stack();
stack.add(root);
every time when call ... 阅读全帖 |
|
m*****n
发帖数: 2152 | 20 完全被虐死了，中间恨不得把电话给扔了。
下面说说过程，首先说明，全程面试官从来没说过我的任何回答是对还是错，我下面的
回答可能很多是错的。
一个西亚或者印度（口音不太像）面试官 A，一开始聊了一下background，然后丫说先
给你一道简单题做做吧，就是一楼的题。
一开始，听到二维平面，最多点，斜率，还以为是那到最多点共线的问题呢？心中一喜
，然后自己重复问题的时候，A 感觉完全不知道我在说什么。丫又重复了一遍问题，这
时才听懂。
当时第一反应是对一个维度排序，然后DP，说给A听了。
A：时间复杂度是多少？
me: O(n^2)
A: 不行，要nlog(n)。
me: （心理一紧，完蛋了，DP都不行）嘴上说好像可以剪枝。
A: How？
me: (心理说我怎么知道)，胡说半天，说什么用tree啦，找parent啦，连我自己都不知
道在说什么。
A: 好吧，假设你有2维的nlogn的算法了，3维怎么办？
me: 先找一个2维最多的点集，再对这个点集的第3维在做一次这个算法。
A: M维怎么办？
me： 依次类推。
A: 时间复杂度多少？
me: 大概是最坏是m*n*logn吧。
A: ... 阅读全帖 |
|
w*****t
发帖数: 485 | 21 分块, 然后归并排序吧.
nlogn.
"1PB数据排序", 后面还有个"10T数据",这个啥意思? |
|
l*****n
发帖数: 246 | 22 分块，然后归并排序会不会太慢？
10T数据是指硬盘空间是10T
总共1PB也就是需要100台机器 |
|
d********w
发帖数: 363 | 23 http://dongfei.baijia.baidu.com/article/54768
提到大数据分析平台，不得不说Hadoop系统，Hadoop到现在也超过10年的历史了，很多
东西发生了变化，版本也从0.x进化到目前的2.6版本。我把2012年后定义成后Hadoop平
台时代，这不是说不用Hadoop，而是像NoSQL （Not Only SQL）那样，有其他的选型补
充。我在知乎上也写过Hadoop的一些入门文章 如何学习Hadoop - 董飞的回答，为了给
大家有个铺垫，简单讲一些相关开源组件。
背景篇
Hadoop: 开源的数据分析平台，解决了大数据（大到一台计算机无法进行存储，一台计
算机无法在要求的时间内进行处理）的可靠存储和处理。适合处理非结构化数据，包括
HDFS，MapReduce基本组件。
HDFS：提供了一种跨服务器的弹性数据存储系统。
MapReduce：技术提供了感知数据位置的标准化处理流程：读取数据，对数据进行映射
（Map），使用某个键值对数据进行重排，然后对数据进行化简（Reduce）得到最终的
输出。
Amazon Elastic Map Red... 阅读全帖 |
|
d********w
发帖数: 363 | 24 http://dongfei.baijia.baidu.com/article/54768
提到大数据分析平台，不得不说Hadoop系统，Hadoop到现在也超过10年的历史了，很多
东西发生了变化，版本也从0.x进化到目前的2.6版本。我把2012年后定义成后Hadoop平
台时代，这不是说不用Hadoop，而是像NoSQL （Not Only SQL）那样，有其他的选型补
充。我在知乎上也写过Hadoop的一些入门文章 如何学习Hadoop - 董飞的回答，为了给
大家有个铺垫，简单讲一些相关开源组件。
背景篇
Hadoop: 开源的数据分析平台，解决了大数据（大到一台计算机无法进行存储，一台计
算机无法在要求的时间内进行处理）的可靠存储和处理。适合处理非结构化数据，包括
HDFS，MapReduce基本组件。
HDFS：提供了一种跨服务器的弹性数据存储系统。
MapReduce：技术提供了感知数据位置的标准化处理流程：读取数据，对数据进行映射
（Map），使用某个键值对数据进行重排，然后对数据进行化简（Reduce）得到最终的
输出。
Amazon Elastic Map Red... 阅读全帖 |
|
g*****g
发帖数: 34805 | 25 一种做法是分块，并行 UDP。见 Aspera. |
|
T****U
发帖数: 3344 | 26 有一个暴力法
第一次遍历求出联通union find的矩阵，分块存储，合并也很简单。
第二次在找出是和边界联通的水，变成2；比如找m[2][4]是否联通，找到他的parent是
m[100][100]在第5个硬盘存储块上,就要把第5个存储块读进来，一直找到最后的parent。
第三次找到和边界或者2联通的1，就是3
剩下的就是合并块的思路。这个方法超级多硬盘读写，不知道能不能被通过 |
|
a********5
发帖数: 1631 | 27 早期公司就是追求快糙猛，软工里面追求的那些东西凑合一下就行，本来做的东西也没
到达那么庞大的LEVEL。
对于快糙猛的标准来说，JAVA太冗余，JAVA框架太HEAVY了。JAVA本就是软工的产物，
和快糙猛是矛盾的。
等融资、盈利、用户等各方面稳定了，有需要再用JAVA之类的语言分块做SOA。
对于公司来说用什么技术永远不是第一位的。 |
|
k******a
发帖数: 44 | 28 题目没有说，但是总体是要求统计词频吧
可不可以这样，
先分块，每块都能够用现有内存出，统计词频，按照字母排序，输出到一个文件。
然后中间文件两两合并，合并的时候边读边写，比如A,B，相当于磁头，读入数据A,B，
如果是同一个单词的，合并结果输出，如果不同先输出字母顺序小得，再输出大得，继
续。。 这个过程用不了多少内存
可能思路上还是外部排序。 |
|
k******a
发帖数: 44 | 29 题目没有说，但是总体是要求统计词频吧
可不可以这样，
先分块，每块都能够用现有内存出，统计词频，按照字母排序，输出到一个文件。
然后中间文件两两合并，合并的时候边读边写，比如A,B，相当于磁头，读入数据A,B，
如果是同一个单词的，合并结果输出，如果不同先输出字母顺序小得，再输出大得，继
续。。 这个过程用不了多少内存
可能思路上还是外部排序。 |
|
k***e
发帖数: 1931 | 30 假设数组长度为N，以长度n=sqrt(N)将其分块。 |
|
y******s
发帖数: 92 | 31 1. Design IP black List
- 这个题乍看一下感觉就是一个HashSet就可以解决了,最多一个HashSet放不下，就用
模除法shard到多个server，这里可以扯一下load balancer和consistent hashing啥的
。还能想到的一点改进是，如果是IPv4的话，所有的地址可以用一个1GB大小的bitmap
放下。但是在IPv6就不可以了。
不知道还有什么注意点吗？
2. Design log monitor system: 好多机器，每个都有log,内容包括exception和error
等，设计一个系统检测这些错误，然后找出之前一段时间最多的错误等。
- 这个题我觉得有点像Top K URLs。我能想到的是：在机器端，根据错误的种类，分块
LOG，比如Error_1 都放在Log_1中，Error_2都放在Log_2中。有另外的一些server，比
如Server_1从所有的机器中读取Log_1，然后汇总报告。
不知道还能改进吗？
多谢~ |
|
m********8
发帖数: 44 | 32 第一个follow up 感觉可以用一个一维数组来记录上一个边界的情况然后跟下一个分块
merge， 不知道是否有更省空间的方法。
第二个follow up 㐈 union-find 然后优化是用weighted quick-union with
path compression, 这样时间复杂度就是 preprocess 的O（mn） + O（K * lg(mn)）
m 和 n代表边数，K代表总共数岛的次数。 这样find和union都是lg(mn)union之所以是
lg(mn)是因为要先找两个节点的根节点再把根节点连一起。优化后在leetcode上的时间
从486ms 优化到了26ms。
没有优化的解法很简单，优化的有点小技巧但是也不是很难，如果有兴趣的话建议你看
下Princeton 算法课讲union-find的PPT，讲的浅显易懂。 |
|
k****r
发帖数: 807 | 33 谢谢你的回答！
1. 如果分块，是不是每个块要计算4个方向的边界情况？这样的话，每个边界会被计算
2次，也就是说有2次重复的岛树减少，总体再加回来一次是不是就ok了，用个以为
array记录减少的次数也行，但每个element是不是可以用4个方向？这样下次计算相同
边界就不用再次计算了；或是所有块都计算左上两个方向？这样没有重复计算。
2。还是有点不清楚union的复杂度，拿lc那道题来讲，一个solution是用一个array来
表示每个点的root的，当add一个新点，只要看新点4个方向的root即可，加入之后如果
有union，好像不更新4个方向的root情况。。。。 。。。 。。。突然觉得还是应该更
新的。。。。不然下次其他点怎么判断是不是已经被连起来的岛。。。。好吧，我似乎
明白O(lg(mn))了。
） |
|
e***a
发帖数: 1661 | 34 美国人把电脑程序员当成“高科技人才”；
日本人把电脑程序员当成“流水线工人”。
日本公司用尽一切手段加强管理，把程序员当成 高级键盘工。
日本软件公司的组织风格 类似于他们的传统制造企业，
分为三级：系统分析员，系统工程师，程序员。
软件项目制作 多采用分块集成的方式。
90年代，日本普遍紧缺电脑程序员，许多文科专业大学生也被抓去编程序，
许多日本小男孩高中毕业培训一年就去充当 VB/SQL programmer。
鉴于大多数日本大学生 讨厌这种“低智能，高强度”的技术职业，
日本公司就把大量的软件项目外包到中国，
在过去的二十多年，日本一直是中国最大的软件外包来源国。
在中国的日资软件外包企业 具有“三低”特征：
技术含量低，人员素质要求低，利润低。
上海地区的日资软件公司的薪酬待遇 体现了中国大多数软件工程师的收入水平。 |
|
发帖数: 1 | 35 两维数组，如果很大，1billion ＊ 1billion，怎么存。答分块，然后存到不同的机器
上，用上下左右，来存周边的机器。然后估算要多少台机器，答如果每个数4bytes，4g
的机器，则需要1billion的机器。1billion机器太多，问怎么办，答假如array 是
sparse 的话，可以压缩。面试官说所有的数都不重复。那怎么办，我说能不能给个提
示，他说增加内存到8g，我说那还需要半个billion机器。感觉他最后只是在糊弄。请
问大家这个怎么答。 |
|
z*********8
发帖数: 2070 | 36 kdtree quadtree不还是把地图分块的思想吗。。。实际上uber就是用的google s2
library把地图分成若干cell |
|
N******u
发帖数: 435 | 37 银行都会告诉你，closing cost分成两部分：
诸如title insurance,home insurance这种，算是第三方的收费，一般对于不同lender
都是一样的，由seller指定的title company收取，或者buyer自己shopping around.
另外一部分是lender收取的费用，比较lender's cost就是比较这一部分。
50K贷款要7K有点多哦，也许这也是他们能做促销的原因，利润空间大啊。
有的realtor也有在closing cost上分块蛋糕的。 |
|
w******c
发帖数: 525 | 38 想把家里一楼的地毯换成地板，那么多家具怎么办？
装修师傅负责搬家具吗？是不是要分块弄？
家里换过地板的给分享一下经验？ |
|
t***z
发帖数: 5112 | 39 主要是不太成功，弄了好多次。。。地面情况不一样估计方法就得变。所以不太好总结
阿。就是去youtube上搜一下如何用，会有很多视频的，看看就知道怎么弄了，但是具
体操作起来差别太大了。现在觉得最有效的就是分块level，有针对性地。不过也会导
致局部level整体不level的问题。总之不是那么简单啊。。。 |
|
d**********0
发帖数: 13081 | 40 挑天气好的时候做试验。
拿水管喷墙。 上下左右分块喷， 看喷那块的时候里面发潮。 |
|
|
s****a
发帖数: 9912 | 42 看到一个中文答案
水泥混凝土路面有膨胀性，在铺筑水泥混凝土路面时，按以下工序进行：1、铺筑之前
底层处理，如果比较软，要进行硬化处理（排水、沥干、填碎石、卵石等）；2、用砂
砾石整平，水泥混凝土不能直接与泥土接触，至少要隔离一层砂砾；3、为了使路面比
较整齐，必须在路面边缘装模，模板高度与你的路面厚度一样高；4、在路面的端点、
转交处，要考虑放置偶角钢筋（防止重物压塌崩裂；5、水泥混凝土路面整版面积最大
为25平方米，最大长边不能大于5米；所以当路面长度大于5米很多时，要分块隔离（当
宽度大于6米时，最好考虑做两幅浇筑）；隔离可以考虑用厚0.5cm泡沫板；6、当水泥
混凝土路面凝固差不多了，可以将缝中泡沫板上面部分掉，涂上石油沥青。 |
|
t******o
发帖数: 1470 | 43 在犹豫要不要把后院分块
然后用镐和锹挖一尺深，过一遍工地的筛子，弄出石头，然后把挖出来的土跟买的好土
混合，然后填回去
担心工程太累人，而且不知道是不是能够解决问题 |
|
z*********n
发帖数: 94654 | 44 水泥开裂如果你知道咋防止，上个专利估计能成千万富翁以上，呵呵
一般能做到的就是分块吧，不要一下铺一块太大的 |
|
m**i
发帖数: 5072 | 45 拔智齿一定要找special list做，放狗找一下就好了。没有保险可以跟医生商量一下，
付现金可以得到一些减免。费用大约是$400--600。专门surgeon一般是把牙打碎再分块
取出，这样可以减少疮面，千万别图省钱去找那些据说万能的医生，搞不好自己受罪，
还有可能丢了小命。 |
|
l*h
发帖数: 4124 | 46 在绝大多数有这方面法律的国家都是严重犯罪的行为，竟然还当成美德宣传，比25年前
还要差。一些人就是要把病人都当成傻子。国内可是有这方面的规定的，当然规定也很
混蛋就是了。
妻子改写化验单 患癌丈夫多活了一年
据新华网报道，“活着，就有希望。”为了能使患肺癌晚期的丈夫更坚强乐观地面对病
情，妻子连续１５个月都执著地去复印店里修改几乎宣告死亡的化验报告单。善意的谎
言不仅使丈夫多活了一年，也让他在生命最后的一程依旧充满了笑容。
“
做妻子的，总希望能替丈夫分担一些，也总希望能多和他走一段路。”１７日，妻子林
芸（化名）再次向记者讲述了这个伤感又温暖的故事。
肺癌晚期被判“能
活几个月”
林芸和丈夫祝伟（化名）１９年前在杭州，经人介绍认识、相
爱。婚后，小两口的日子很美满，用林芸的话说，“结婚１７年，几乎没吵过架。”而
且两人同在金融行业，收入稳定。令人惋惜的是，不到５０岁的祝伟前年被查出患了肺
癌，而且已经到中晚期。
动了手术后，情况依旧不容乐观，医院宣告只能
活几个月。
“能多活一天是一天，说不定有奇迹。”林... 阅读全帖 |
|
B********n
发帖数: 12753 | 47 你的问题估计和我差不多是一个问题
我加好那张新信用卡之后，账户里是2个分块，第一块是以前的checking saving 和cc
第二块单独是个cc，中间有个明显的分隔
后来终于转到了个靠谱的IT部门的人，帮我改了，然后进去以后就正常了
先checking 再saving，然后所有cc在一起
肯定是做关联的时候，弄错了，另外freedom 10%不是年底给的，每笔消费看得出，你
点你每笔消费详细里，看看有没有每次多给10% |
|
t****8
发帖数: 511 | 48 罐头的菜品种类太少，开始要准备给娃吃罐头以外的辅食了。有一个很傻的问题。
我家有保姆，应该可以每天花些时间给娃现做先吃，但是应该时间不会特别多。7-8个
月的娃娃吃的蔬菜肉等都要弄得很烂很碎，应该是要蒸熟，打碎，之类的。应该挺麻烦
的，所以现做我想应该不能放很多种类的菜。
我看到妈妈们有说可以把蔬菜一次做很多大量的，然后分块冻起来，每天烧粥的时候放
一些。
大家觉得是现做的但是种类少一些好呢，还是吃冻的，但是种类可以比较多好？
另一个问题，娃喝得粥是否还需要打碎呢？煮烂的米粒可以吗？
谢谢了。 |
|
g********g
发帖数: 299 | 49 要想母乳喂养 就多做些肉类 比如猪脚煮好冷藏 下回用时拿出来烧就减少好多时间
大块牛肉烧酱汁 煮好分块冷藏 吃时拿一块出来化了切着吃
馄饨饺子啥的也可以包一些 |
|
x****u
发帖数: 44466 | 50 引产是先生下来再处置。。。
三个月堕胎的时候胎儿小，可以先把脑袋拽掉分块拉出来。七个月你拉脑袋它身体就跟
着出来了。还得抢救，除非想办法弄死。 |
|
