P**********c
发帖数: 3417 | 1 一个面经很少的大公司。
有几道题不是很清楚，另外基础的东西有些细节也没有搞清楚，挂掉了。感觉面试细节还是很重要的，必须多写多练才行。类似copy constructure, assignment operator哪些地方应该用const, 哪些地方为什么用reference，不要搞混了. 本来以为自己这些都是知道的，没想到现场一步一步的写，还是出了很多小错，当时就感觉给面试官印象不好了。写程序的时候要先想一想，以前写过看过什么类似的程序，需要注意什么问题。不要急着下笔。有的面试官问题问题很多，频率很快。很容易让你自己很心急，希望回答更多的题目，但是保证正确才是最重要的。
1. destructor里面不能throw exception, 那something bad happens应该用什么.
2. 在一个平面上有n个点，设计算法看能不能找出四个点构成一个正方形，分析时间复杂度。
3. 一个平面上有一些点，有些互相是相连的。每条边用一个data structure表示，比如(3,5)和(4,6)之间的叫"a", 那就表示为
(3, 5, 4, 6, "a")
给你一串这样的structure, 打印出类似connected component的结果，比如。(3,5,4,6,"a")和(4,6,8,2,"b")是连在一起的, 又比如c和d是连在一起的，那打出来应该是
0 a
0 b
1 c
1 d
4. 今天版上讨论的类似的一个题，有4 billion个unsorted的整数，找missing的数，
只有50 byte的memory. 找到一个即可。
还有一个判断class object占多大空间的题，以前其实遇到过，知道要考memory alignment, 但是面试的时候不知道怎么想的，一紧张还是忘了，这种基本的东西感觉答错失分很严重. 算法题目看了很多，但是实际面试中只有一道题很眼熟，感觉对有些公司能复习到题目的概率其实不大，这样基础的东西不出错就尤其重要。Anyway, move on了。希望大家多讨论一下，找到最佳的解法。下周还有一个onsite, 希望能调整好状态。 | f*******t
发帖数: 7549 | | P**********c
发帖数: 3417 | 3 嗯，感觉不容易。希望大家多讨论讨论。
【在 f*******t 的大作中提到】
: 好难啊
| t**r
发帖数: 3428 | 4 第一题我记得EFFECTIVE上讲过。应该尽量处理掉EXCEPTION，不要THROW。
处理掉要具体问题具体分析。
P.S。 什么公司，给点提示？ | s*****n
发帖数: 5488 | 5 google c++ faq and read it.
【在 t**r 的大作中提到】
: 第一题我记得EFFECTIVE上讲过。应该尽量处理掉EXCEPTION，不要THROW。
: 处理掉要具体问题具体分析。
: P.S。 什么公司，给点提示？
| P**********c
发帖数: 3417 | 6 那个的回答我看过，很简单的说了一句。不知道是不是就是答案。
【在 s*****n 的大作中提到】
: google c++ faq and read it.
| s*****n
发帖数: 5488 | 7 1. C++ faq
2. 线段hashtable,然后对每个bucket 操作找。
3.DFS
4.
节还是很重要的，必须多写多练才行。类似copy constructure, assignment operator
哪些地方应该用const, 哪些地方为什么用reference，不要搞混了. 本来以为自己这些
都是知道的，没想到现场一步一步的写，还是出了很多小错，当时就感觉给面试官印象
不好了。写程序的时候要先想一想，以前写过看过什么类似的程序，需要注意什么问题
。不要急着下笔。有的面试官问题问题很多，频率很快。很容易让你自己很心急，希望
回答更多的题目，但是保证正确才是最重要的。
复杂度。
比如(3,5)和(4,6)之间的叫"a", 那就表示为
,6,"a")和(4,6,8,2,"b")是连在一起的, 又比如c和d是连在一起的，那打出来应该是
【在 P**********c 的大作中提到】
: 一个面经很少的大公司。
: 有几道题不是很清楚，另外基础的东西有些细节也没有搞清楚，挂掉了。感觉面试细节还是很重要的，必须多写多练才行。类似copy constructure, assignment operator哪些地方应该用const, 哪些地方为什么用reference，不要搞混了. 本来以为自己这些都是知道的，没想到现场一步一步的写，还是出了很多小错，当时就感觉给面试官印象不好了。写程序的时候要先想一想，以前写过看过什么类似的程序，需要注意什么问题。不要急着下笔。有的面试官问题问题很多，频率很快。很容易让你自己很心急，希望回答更多的题目，但是保证正确才是最重要的。
: 1. destructor里面不能throw exception, 那something bad happens应该用什么.
: 2. 在一个平面上有n个点，设计算法看能不能找出四个点构成一个正方形，分析时间复杂度。
: 3. 一个平面上有一些点，有些互相是相连的。每条边用一个data structure表示，比如(3,5)和(4,6)之间的叫"a", 那就表示为
: (3, 5, 4, 6, "a")
: 给你一串这样的structure, 打印出类似connected component的结果，比如。(3,5,4,6,"a")和(4,6,8,2,"b")是连在一起的, 又比如c和d是连在一起的，那打出来应该是
: 0 a
: 0 b
: 1 c
| s*****n
发帖数: 5488 | 8 4. binary search.
operator
【在 s*****n 的大作中提到】
: 1. C++ faq
: 2. 线段hashtable,然后对每个bucket 操作找。
: 3.DFS
: 4.
:
: 节还是很重要的，必须多写多练才行。类似copy constructure, assignment operator
: 哪些地方应该用const, 哪些地方为什么用reference，不要搞混了. 本来以为自己这些
: 都是知道的，没想到现场一步一步的写，还是出了很多小错，当时就感觉给面试官印象
: 不好了。写程序的时候要先想一想，以前写过看过什么类似的程序，需要注意什么问题
: 。不要急着下笔。有的面试官问题问题很多，频率很快。很容易让你自己很心急，希望
| s*****n
发帖数: 5488 | 9 应该是了，还要啰啰嗦嗦讲stack unwind呢。
【在 P**********c 的大作中提到】
: 那个的回答我看过，很简单的说了一句。不知道是不是就是答案。
| i**********e
发帖数: 1145 | 10 2. 正方形是 axis-aligned 的吗？如果不是的话（可以允许有角度），对没学过图形
来说是很复杂的。
3. 感觉是这个是 merge intersected lines，需要判断是否与其他所有直线相交？
4. programming pearls 里的经典题，思路是用 binary search。
节还是很重要的，必须多写多练才行。类似copy constructure, assignment operator
哪些地方应该用const, 哪些地方为什么用reference，不要搞混了. 本来以为自己这些
都是知道的，没想到现场一步一步的写，还是出了很多小错，当时就感觉给面试官印象
不好了。写程序的时候要先想一想，以前写过看过什么类似的程序，需要注意什么问题
。不要急着下笔。有的面试官问题问题很多，频率很快。很容易让你自己很心急，希望
回答更多的题目，但是保证正确才是最重要的。
复杂度。
比如(3,5)和(4,6)之间的叫"a", 那就表示为
,6,"a")和(4,6,8,2,"b")是连在一起的, 又比如c和d是连在一起的，那打出来应该是
【在 P**********c 的大作中提到】
: 一个面经很少的大公司。
: 有几道题不是很清楚，另外基础的东西有些细节也没有搞清楚，挂掉了。感觉面试细节还是很重要的，必须多写多练才行。类似copy constructure, assignment operator哪些地方应该用const, 哪些地方为什么用reference，不要搞混了. 本来以为自己这些都是知道的，没想到现场一步一步的写，还是出了很多小错，当时就感觉给面试官印象不好了。写程序的时候要先想一想，以前写过看过什么类似的程序，需要注意什么问题。不要急着下笔。有的面试官问题问题很多，频率很快。很容易让你自己很心急，希望回答更多的题目，但是保证正确才是最重要的。
: 1. destructor里面不能throw exception, 那something bad happens应该用什么.
: 2. 在一个平面上有n个点，设计算法看能不能找出四个点构成一个正方形，分析时间复杂度。
: 3. 一个平面上有一些点，有些互相是相连的。每条边用一个data structure表示，比如(3,5)和(4,6)之间的叫"a", 那就表示为
: (3, 5, 4, 6, "a")
: 给你一串这样的structure, 打印出类似connected component的结果，比如。(3,5,4,6,"a")和(4,6,8,2,"b")是连在一起的, 又比如c和d是连在一起的，那打出来应该是
: 0 a
: 0 b
: 1 c
| | | P**********c
发帖数: 3417 | 11 stack unwind是回答为什么不能用throw exception吧。这个题目一开始就告诉你不能
了，问你能用什么其他的办法。FAQ里对这个的回答是：
Write a message to a log-file. Or call Aunt Tilda.
当然也可能面试的就是想让你解释下为什么不能throw exception.
【在 s*****n 的大作中提到】
: 应该是了，还要啰啰嗦嗦讲stack unwind呢。
| s*****n
发帖数: 5488 | 12 一般会被追问为什么吧。
【在 P**********c 的大作中提到】
: stack unwind是回答为什么不能用throw exception吧。这个题目一开始就告诉你不能
: 了，问你能用什么其他的办法。FAQ里对这个的回答是：
: Write a message to a log-file. Or call Aunt Tilda.
: 当然也可能面试的就是想让你解释下为什么不能throw exception.
| P**********c
发帖数: 3417 | 13 第3题DFS你要先有图的structure才行，怎么从已知的structure构建图？
operator
【在 s*****n 的大作中提到】
: 1. C++ faq
: 2. 线段hashtable,然后对每个bucket 操作找。
: 3.DFS
: 4.
:
: 节还是很重要的，必须多写多练才行。类似copy constructure, assignment operator
: 哪些地方应该用const, 哪些地方为什么用reference，不要搞混了. 本来以为自己这些
: 都是知道的，没想到现场一步一步的写，还是出了很多小错，当时就感觉给面试官印象
: 不好了。写程序的时候要先想一想，以前写过看过什么类似的程序，需要注意什么问题
: 。不要急着下笔。有的面试官问题问题很多，频率很快。很容易让你自己很心急，希望
| P**********c
发帖数: 3417 | 14 嗯。 4我是用的是每次分两端数个数。code写完后问可不可以优化，没想出来，结果他说是当一边个数是0的时候那一边全miss, 所以可以直接退出，感觉蛮搞的。
3. 我是一个一个比较写的code。没有时间想更好的解法了。转成图的过程(比如adjacency list)感觉很不好写。
2. 是axis aligned的。
operator
【在 i**********e 的大作中提到】
: 2. 正方形是 axis-aligned 的吗？如果不是的话（可以允许有角度），对没学过图形
: 来说是很复杂的。
: 3. 感觉是这个是 merge intersected lines，需要判断是否与其他所有直线相交？
: 4. programming pearls 里的经典题，思路是用 binary search。
:
: 节还是很重要的，必须多写多练才行。类似copy constructure, assignment operator
: 哪些地方应该用const, 哪些地方为什么用reference，不要搞混了. 本来以为自己这些
: 都是知道的，没想到现场一步一步的写，还是出了很多小错，当时就感觉给面试官印象
: 不好了。写程序的时候要先想一想，以前写过看过什么类似的程序，需要注意什么问题
: 。不要急着下笔。有的面试官问题问题很多，频率很快。很容易让你自己很心急，希望
| s*****n
发帖数: 5488 | 15 I see. 不知道题目怎么要求的。如果顺序无关的。可以用disjoint-set forest. 快速
建立联通关系。对树编号，然后traverse每个树打印即可。
【在 P**********c 的大作中提到】
: 第3题DFS你要先有图的structure才行，怎么从已知的structure构建图？
:
: operator
| P**********c
发帖数: 3417 | 16 题目要求是给你一串structure, 比如放到一个array里。每个array element是一条线
段，里面包括起始点的横纵坐标，终止点的横纵坐标，和线段的名字。
【在 s*****n 的大作中提到】
: I see. 不知道题目怎么要求的。如果顺序无关的。可以用disjoint-set forest. 快速
: 建立联通关系。对树编号，然后traverse每个树打印即可。
| d*******l
发帖数: 338 | 17 第二题可以先把所有点放进hashtable，然后枚举对角线（点对），如果是正方形的话
，确定一条对角线整个形状也就确定了，只要检查另外两个顶点是否在hashtable中就
可以。复杂度是O(n^2)。
第三题直接的做法是建图之后dfs，图的顶点是“边”，两个顶点之间有边的条件是两
个“边”共享顶点。只要用O(n^2)时间建起图然后O(n)的dfs就行。
上面提到用并查集，我认为确实可以提高效率，可以建立一个key是点的坐标，value是
list of structure的hashtable，然后把每个“边”都放到其两个端点对应的bucket里
，然后对每个bucket里的所有“边”进行union操作。最后得到每个“边”及其所属的
group编号，如果要有序输出的话可以排个序再输出，感觉比直接的做法还是要好一些。
第一题直接就不会了，有没有人有明确点的说法？
第4题也不是很清楚，careercup上有道类似的题，是用位来标记是否出现，但这题就
50byte内存好像不能走这条路线，有没有人说说binary search怎么做？数组不是无序
的吗？ | c****p
发帖数: 6474 | 18 第4题那4bn个数存在哪？内存里？
节还是很重要的，必须多写多练才行。类似copy constructure, assignment operator
哪些地方应该用const, 哪些地方为什么用reference，不要搞混了. 本来以为自己这些
都是知道的，没想到现场一
复杂度。
比如(3,5)和(4,6)之间的叫"a", 那就表示为
,6,"a")和(4,6,8,2,"b")是连在一起的, 又比如c和d是连在一起的，那打出来应该是
【在 P**********c 的大作中提到】
: 一个面经很少的大公司。
: 有几道题不是很清楚，另外基础的东西有些细节也没有搞清楚，挂掉了。感觉面试细节还是很重要的，必须多写多练才行。类似copy constructure, assignment operator哪些地方应该用const, 哪些地方为什么用reference，不要搞混了. 本来以为自己这些都是知道的，没想到现场一步一步的写，还是出了很多小错，当时就感觉给面试官印象不好了。写程序的时候要先想一想，以前写过看过什么类似的程序，需要注意什么问题。不要急着下笔。有的面试官问题问题很多，频率很快。很容易让你自己很心急，希望回答更多的题目，但是保证正确才是最重要的。
: 1. destructor里面不能throw exception, 那something bad happens应该用什么.
: 2. 在一个平面上有n个点，设计算法看能不能找出四个点构成一个正方形，分析时间复杂度。
: 3. 一个平面上有一些点，有些互相是相连的。每条边用一个data structure表示，比如(3,5)和(4,6)之间的叫"a", 那就表示为
: (3, 5, 4, 6, "a")
: 给你一串这样的structure, 打印出类似connected component的结果，比如。(3,5,4,6,"a")和(4,6,8,2,"b")是连在一起的, 又比如c和d是连在一起的，那打出来应该是
: 0 a
: 0 b
: 1 c
| s*****n
发帖数: 5488 | 19 这样还是dfs.第二题，细化了一下。
1. 对于每一对点，求线段中点，长度和角度，加入hashtable O(n^2).
2. 查询：对于所有线段，用中点，长度和角度旋转90度，查询。如果击中，则找到一
个正方形。
【在 P**********c 的大作中提到】
: 题目要求是给你一串structure, 比如放到一个array里。每个array element是一条线
: 段，里面包括起始点的横纵坐标，终止点的横纵坐标，和线段的名字。
| c****p
发帖数: 6474 | 20 如果只找axis aligned正方形的话，只把|x1-x2| = |y1 - y2|的点对放进hash table就
可以了吧。
另外找另外的点对的时候，直接找(x1,y2)和(x2,y1)是不是存在就行了。
【在 s*****n 的大作中提到】
: 这样还是dfs.第二题，细化了一下。
: 1. 对于每一对点，求线段中点，长度和角度，加入hashtable O(n^2).
: 2. 查询：对于所有线段，用中点，长度和角度旋转90度，查询。如果击中，则找到一
: 个正方形。
| | | d*******l
发帖数: 338 | 21 我觉得没有必要放点对进hashtable，只要放点就行了。就像你说的最后只要判断某个
点是否存在。点对的话直接O(n^2)枚举就行。
table就
【在 c****p 的大作中提到】
: 如果只找axis aligned正方形的话，只把|x1-x2| = |y1 - y2|的点对放进hash table就
: 可以了吧。
: 另外找另外的点对的时候，直接找(x1,y2)和(x2,y1)是不是存在就行了。
| P**********c
发帖数: 3417 | 22 你把2，3混淆了。
【在 s*****n 的大作中提到】
: 这样还是dfs.第二题，细化了一下。
: 1. 对于每一对点，求线段中点，长度和角度，加入hashtable O(n^2).
: 2. 查询：对于所有线段，用中点，长度和角度旋转90度，查询。如果击中，则找到一
: 个正方形。
| c****p
发帖数: 6474 | 23 正方形帮助简化第三点和第四点的寻找。
【在 P**********c 的大作中提到】
: 你把2，3混淆了。
| i**********e
发帖数: 1145 | 24 第 4 题是把 integer 看成 32 bit，4 billion 里必有至少一个 missing，因为 4
billion < 2^32.
因为内存有限，首先把所有 first bit 为 0 的写进 文件A，然后 first bit 为 1 的
写进文件B.这时候如果文件 A 里的数是 <= 2 billion （必定有一个文件符合这条件
），那就代表 missing integer 的 first bit 必定为 0. 这时候就以文件 A 来当作
新的 input，然后看 second bit,以此类推。当扫描完 32 bit 的时候，也就知道
missing integer 是什么了。
复杂度是 O(n)。每次最坏情况能消除 n/2.
所以复杂度:
n + n/2 + n/4 +... = O(n) | P**********c
发帖数: 3417 | 25 第三题我当时是一个一个比较的，用每条线段的起终点坐标跟其他线段的起终点坐标比较，如果相等则标记已访问过，并且标上component的值，这个也是O(n^2)吧。回来也没想出有什么错误。
第4题我是4 billion的数一个一个读进内存，因为每个数的范围是0~2^32, 所以先看她属于0～2^31还是后面，这样数范围，如果数完发现左半边缺数，下次数的时候就只看左边，继续分成两半。总共需要读原文件32次。不能用careercup那个做法。面试的人似乎认为我的思路是对的，他只是说我的算法肯定要读文件32次，有没有方法是在有些情况下不需要读32次的。我以为是很复杂的方法，结果我前面提到了，他说是每次数的时候如果有半边范围个数是0，那就随便返回一个那半边范围里的数。
些。
【在 d*******l 的大作中提到】
: 第二题可以先把所有点放进hashtable，然后枚举对角线（点对），如果是正方形的话
: ，确定一条对角线整个形状也就确定了，只要检查另外两个顶点是否在hashtable中就
: 可以。复杂度是O(n^2)。
: 第三题直接的做法是建图之后dfs，图的顶点是“边”，两个顶点之间有边的条件是两
: 个“边”共享顶点。只要用O(n^2)时间建起图然后O(n)的dfs就行。
: 上面提到用并查集，我认为确实可以提高效率，可以建立一个key是点的坐标，value是
: list of structure的hashtable，然后把每个“边”都放到其两个端点对应的bucket里
: ，然后对每个bucket里的所有“边”进行union操作。最后得到每个“边”及其所属的
: group编号，如果要有序输出的话可以排个序再输出，感觉比直接的做法还是要好一些。
: 第一题直接就不会了，有没有人有明确点的说法？
| c****p
发帖数: 6474 | 26 你是遍历线段还是遍历点哦？
线段数就是O(n^2)了，逐对比较还得再平方一次啊。。你用hashtable了？
找对角线的方法，用hashtable的话一共也就O(n^2)。
如果坐标点是整数的话，把各点按x坐标分类，逐一比对x相同的点对，然后再找对应的
另外两点，ms更快，当然要求是axis aligned
【在 P**********c 的大作中提到】
: 第三题我当时是一个一个比较的，用每条线段的起终点坐标跟其他线段的起终点坐标比较，如果相等则标记已访问过，并且标上component的值，这个也是O(n^2)吧。回来也没想出有什么错误。
: 第4题我是4 billion的数一个一个读进内存，因为每个数的范围是0~2^32, 所以先看她属于0～2^31还是后面，这样数范围，如果数完发现左半边缺数，下次数的时候就只看左边，继续分成两半。总共需要读原文件32次。不能用careercup那个做法。面试的人似乎认为我的思路是对的，他只是说我的算法肯定要读文件32次，有没有方法是在有些情况下不需要读32次的。我以为是很复杂的方法，结果我前面提到了，他说是每次数的时候如果有半边范围个数是0，那就随便返回一个那半边范围里的数。
:
: 些。
| P**********c
发帖数: 3417 | 27 不是啊，我是说第3题啊，不是找正方形啊。
【在 c****p 的大作中提到】
: 你是遍历线段还是遍历点哦？
: 线段数就是O(n^2)了，逐对比较还得再平方一次啊。。你用hashtable了？
: 找对角线的方法，用hashtable的话一共也就O(n^2)。
: 如果坐标点是整数的话，把各点按x坐标分类，逐一比对x相同的点对，然后再找对应的
: 另外两点，ms更快，当然要求是axis aligned
| c****p
发帖数: 6474 | 28 这个4billion是4*10^9还是4*2^30？
较，如果相等则标记已访问过，并且标上component的值，这个也是O(n^2)吧。回来也
没想出有什么错误。
她属于0～2^31还是后面，这样数范围，如果数完发现左半边缺数，下次数的时候就只
看左边，继续分成两半。总共需要读原文件32次。不能用careercup那个做法。面试的
人似乎认为我的思路是对的，
【在 P**********c 的大作中提到】
: 第三题我当时是一个一个比较的，用每条线段的起终点坐标跟其他线段的起终点坐标比较，如果相等则标记已访问过，并且标上component的值，这个也是O(n^2)吧。回来也没想出有什么错误。
: 第4题我是4 billion的数一个一个读进内存，因为每个数的范围是0~2^32, 所以先看她属于0～2^31还是后面，这样数范围，如果数完发现左半边缺数，下次数的时候就只看左边，继续分成两半。总共需要读原文件32次。不能用careercup那个做法。面试的人似乎认为我的思路是对的，他只是说我的算法肯定要读文件32次，有没有方法是在有些情况下不需要读32次的。我以为是很复杂的方法，结果我前面提到了，他说是每次数的时候如果有半边范围个数是0，那就随便返回一个那半边范围里的数。
:
: 些。
| P**********c
发帖数: 3417 | 29 前者，因为一定有miss的数，这个条件跟careercup书上是一样的。
【在 c****p 的大作中提到】
: 这个4billion是4*10^9还是4*2^30？
:
: 较，如果相等则标记已访问过，并且标上component的值，这个也是O(n^2)吧。回来也
: 没想出有什么错误。
: 她属于0～2^31还是后面，这样数范围，如果数完发现左半边缺数，下次数的时候就只
: 看左边，继续分成两半。总共需要读原文件32次。不能用careercup那个做法。面试的
: 人似乎认为我的思路是对的，
| P**********c
发帖数: 3417 | 30 第二题正方形确定任何一条边整个形状也就确定了吧。我当时的解法是对每个点，水平
方向上找同样高度的点，然后对找到的每个点看另外两点是否存在，是不是跟你的思路
其实是一样的？
不过我没有提到implement的细节，比如hashtable, hashtable的两个坐标怎么弄成key
比较好？
些。
【在 d*******l 的大作中提到】
: 第二题可以先把所有点放进hashtable，然后枚举对角线（点对），如果是正方形的话
: ，确定一条对角线整个形状也就确定了，只要检查另外两个顶点是否在hashtable中就
: 可以。复杂度是O(n^2)。
: 第三题直接的做法是建图之后dfs，图的顶点是“边”，两个顶点之间有边的条件是两
: 个“边”共享顶点。只要用O(n^2)时间建起图然后O(n)的dfs就行。
: 上面提到用并查集，我认为确实可以提高效率，可以建立一个key是点的坐标，value是
: list of structure的hashtable，然后把每个“边”都放到其两个端点对应的bucket里
: ，然后对每个bucket里的所有“边”进行union操作。最后得到每个“边”及其所属的
: group编号，如果要有序输出的话可以排个序再输出，感觉比直接的做法还是要好一些。
: 第一题直接就不会了，有没有人有明确点的说法？
| | | g*****k
发帖数: 623 | 31 第3题错了，
第1：并不一定是其他线段的终点
第2：component没有propogate,也就是没有进行set union
第3题，不太明白，4 billion的数一个一个读进内存，还能只读原文件32次？
请问这是如何做到的?
较，如果相等则标记已访问过，并且标上component的值，这个也是O(n^2)吧。回来也
没想出有什么错误。
她属于0～2^31还是后面，这样数范围，如果数完发现左半边缺数，下次数的时候就只
看左边，继续分成两半。总共需要读原文件32次。不能用careercup那个做法。面试的
人似乎认为我的思路是对的，
【在 P**********c 的大作中提到】
: 第三题我当时是一个一个比较的，用每条线段的起终点坐标跟其他线段的起终点坐标比较，如果相等则标记已访问过，并且标上component的值，这个也是O(n^2)吧。回来也没想出有什么错误。
: 第4题我是4 billion的数一个一个读进内存，因为每个数的范围是0~2^32, 所以先看她属于0～2^31还是后面，这样数范围，如果数完发现左半边缺数，下次数的时候就只看左边，继续分成两半。总共需要读原文件32次。不能用careercup那个做法。面试的人似乎认为我的思路是对的，他只是说我的算法肯定要读文件32次，有没有方法是在有些情况下不需要读32次的。我以为是很复杂的方法，结果我前面提到了，他说是每次数的时候如果有半边范围个数是0，那就随便返回一个那半边范围里的数。
:
: 些。
| d*******l
发帖数: 338 | 32 我认为就是一样的，边与坐标轴对齐会简化一点操作，但方法还是一样。我总觉得对角
线让人感觉更可靠。。
还需要自己设计hash函数？这个可以把hashtable当作黑盒来用吧？
key
【在 P**********c 的大作中提到】
: 第二题正方形确定任何一条边整个形状也就确定了吧。我当时的解法是对每个点，水平
: 方向上找同样高度的点，然后对找到的每个点看另外两点是否存在，是不是跟你的思路
: 其实是一样的？
: 不过我没有提到implement的细节，比如hashtable, hashtable的两个坐标怎么弄成key
: 比较好？
:
: 些。
| c****p
发帖数: 6474 | 33 找边简单点。
找边只在一个方向上找，找对角线需要在所有点中找
【在 d*******l 的大作中提到】
: 我认为就是一样的，边与坐标轴对齐会简化一点操作，但方法还是一样。我总觉得对角
: 线让人感觉更可靠。。
: 还需要自己设计hash函数？这个可以把hashtable当作黑盒来用吧？
:
: key
| P**********c
发帖数: 3417 | 34 嗯，第3题确实做错了。
第4题我说得读32次，就是scan 32次的意思，呵呵。
【在 g*****k 的大作中提到】
: 第3题错了，
: 第1：并不一定是其他线段的终点
: 第2：component没有propogate,也就是没有进行set union
: 第3题，不太明白，4 billion的数一个一个读进内存，还能只读原文件32次？
: 请问这是如何做到的?
:
: 较，如果相等则标记已访问过，并且标上component的值，这个也是O(n^2)吧。回来也
: 没想出有什么错误。
: 她属于0～2^31还是后面，这样数范围，如果数完发现左半边缺数，下次数的时候就只
: 看左边，继续分成两半。总共需要读原文件32次。不能用careercup那个做法。面试的
| d*******l
发帖数: 338 | 35 第三题我觉得有些不妥，一方面起点终点相互之间四种比较都可以让两条“边”发生关
联，另外一方面你的方法中比较顺序如果就是按数组存储的顺序的话，那要保证正确性
的话实现上会有一些无法解决的问题。这个比较微妙，但我认为单单一个二重循环很难
出结果。
较，如果相等则标记已访问过，并且标上component的值，这个也是O(n^2)吧。回来也
没想出有什么错误。
她属于0～2^31还是后面，这样数范围，如果数完发现左半边缺数，下次数的时候就只
看左边，继续分成两半。总共需要读原文件32次。不能用careercup那个做法。面试的
人似乎认为我的思路是对的，他只是说我的算法肯定要读文件32次，有没有方法是在有
些情况下不需要读32次的。我以为是很复杂的方法，结果我前面提到了，他说是每次数
的时候如果有半边范围个数是0，那就随便返回一个那半边范围里的数。
【在 P**********c 的大作中提到】
: 第三题我当时是一个一个比较的，用每条线段的起终点坐标跟其他线段的起终点坐标比较，如果相等则标记已访问过，并且标上component的值，这个也是O(n^2)吧。回来也没想出有什么错误。
: 第4题我是4 billion的数一个一个读进内存，因为每个数的范围是0~2^32, 所以先看她属于0～2^31还是后面，这样数范围，如果数完发现左半边缺数，下次数的时候就只看左边，继续分成两半。总共需要读原文件32次。不能用careercup那个做法。面试的人似乎认为我的思路是对的，他只是说我的算法肯定要读文件32次，有没有方法是在有些情况下不需要读32次的。我以为是很复杂的方法，结果我前面提到了，他说是每次数的时候如果有半边范围个数是0，那就随便返回一个那半边范围里的数。
:
: 些。
| c****p
发帖数: 6474 | 36 设两个变量，一个叫left，一个叫right。
设两个端点，begin和end，
设一个threshold = (begin + end)>>1。
如果读进来的数在[begin,end]之间的话：
若它小于threshold，left++，否则right++。
读完以后根据left和right的值确定下一次应该二分哪个区间，并确定相应的新的thres
hold。
最衰的情况下，每一位都需要一次二分，每二分一次都需要读一次原始文件。
不过话说无论如何都用不着32次吧。
【在 g*****k 的大作中提到】
: 第3题错了，
: 第1：并不一定是其他线段的终点
: 第2：component没有propogate,也就是没有进行set union
: 第3题，不太明白，4 billion的数一个一个读进内存，还能只读原文件32次？
: 请问这是如何做到的?
:
: 较，如果相等则标记已访问过，并且标上component的值，这个也是O(n^2)吧。回来也
: 没想出有什么错误。
: 她属于0～2^31还是后面，这样数范围，如果数完发现左半边缺数，下次数的时候就只
: 看左边，继续分成两半。总共需要读原文件32次。不能用careercup那个做法。面试的
| P**********c
发帖数: 3417 | 37 2^32个数，二分不就是log(2^32)=32 么。
thres
【在 c****p 的大作中提到】
: 设两个变量，一个叫left，一个叫right。
: 设两个端点，begin和end，
: 设一个threshold = (begin + end)>>1。
: 如果读进来的数在[begin,end]之间的话：
: 若它小于threshold，left++，否则right++。
: 读完以后根据left和right的值确定下一次应该二分哪个区间，并确定相应的新的thres
: hold。
: 最衰的情况下，每一位都需要一次二分，每二分一次都需要读一次原始文件。
: 不过话说无论如何都用不着32次吧。
| P**********c
发帖数: 3417 | 38 坐标是2个数啊。比如careerup上10.6上存直线都把slope和y intercept ｜了一下，那
还是Java code呢。
【在 d*******l 的大作中提到】
: 我认为就是一样的，边与坐标轴对齐会简化一点操作，但方法还是一样。我总觉得对角
: 线让人感觉更可靠。。
: 还需要自己设计hash函数？这个可以把hashtable当作黑盒来用吧？
:
: key
| c****p
发帖数: 6474 | 39 因为实际上只有4e9个数，而2^32是4294967296。
缺额超过5%，可能很早就会发生一侧为空。
那提个新问题：
如果发现一侧为空就停止继续读文件，那至多要读多少次？至少要读多少次？
【在 P**********c 的大作中提到】
: 2^32个数，二分不就是log(2^32)=32 么。
:
: thres
| d*******l
发帖数: 338 | 40 反正C++里我肯定就用map, int>了。hashtable的key是一个对象没问题
吧，java里没有pair就自行封装一下？
【在 P**********c 的大作中提到】
: 坐标是2个数啊。比如careerup上10.6上存直线都把slope和y intercept ｜了一下，那
: 还是Java code呢。
| | | c****p
发帖数: 6474 | 41 自己弄个1-to-1的mapping，把两数弄成一个数也可以。。。
【在 d*******l 的大作中提到】
: 反正C++里我肯定就用map, int>了。hashtable的key是一个对象没问题
: 吧，java里没有pair就自行封装一下？
| P**********c
发帖数: 3417 | 42 对。因为我本来写的code没有考虑为空的时候就跳出，所以他才说是一定32次。为空的时候就跳出的话，最少可以scan一次就退出。最多我觉得应该还是32次吧。比如如果code是左边优先，那每次碰上的都是左边缺一个，右边缺好多的情况，是32次吧。当然如果每次都选择缺的数多的那边，那要仔细想想。
【在 c****p 的大作中提到】
: 因为实际上只有4e9个数，而2^32是4294967296。
: 缺额超过5%，可能很早就会发生一侧为空。
: 那提个新问题：
: 如果发现一侧为空就停止继续读文件，那至多要读多少次？至少要读多少次？
| c****p
发帖数: 6474 | 43 最少不可能是1次。
最少的次数的条件应该是这个差额包含了某次读文件时一侧的全部，这个可以算出来。
最多的次数的条件应该是缺额的数是平均分布在2^32的空间内的，这个我还没太想好。
的时候就跳出的话，最少可以scan一次就退出。最多我觉得应该还是32次吧。比如如果
code是左边优先，那每次碰上的都是左边缺一个，右边缺好多的情况，是32次吧。当然
如果每次都选择缺的数多的
【在 P**********c 的大作中提到】
: 对。因为我本来写的code没有考虑为空的时候就跳出，所以他才说是一定32次。为空的时候就跳出的话，最少可以scan一次就退出。最多我觉得应该还是32次吧。比如如果code是左边优先，那每次碰上的都是左边缺一个，右边缺好多的情况，是32次吧。当然如果每次都选择缺的数多的那边，那要仔细想想。
| c****p
发帖数: 6474 | 44 最多应该还是32次。
【在 c****p 的大作中提到】
: 最少不可能是1次。
: 最少的次数的条件应该是这个差额包含了某次读文件时一侧的全部，这个可以算出来。
: 最多的次数的条件应该是缺额的数是平均分布在2^32的空间内的，这个我还没太想好。
:
: 的时候就跳出的话，最少可以scan一次就退出。最多我觉得应该还是32次吧。比如如果
: code是左边优先，那每次碰上的都是左边缺一个，右边缺好多的情况，是32次吧。当然
: 如果每次都选择缺的数多的
| P**********c
发帖数: 3417 | 45 如果4个billion的数都是2^32-1, 不是一次就扫出来了吗？
【在 c****p 的大作中提到】
: 最少不可能是1次。
: 最少的次数的条件应该是这个差额包含了某次读文件时一侧的全部，这个可以算出来。
: 最多的次数的条件应该是缺额的数是平均分布在2^32的空间内的，这个我还没太想好。
:
: 的时候就跳出的话，最少可以scan一次就退出。最多我觉得应该还是32次吧。比如如果
: code是左边优先，那每次碰上的都是左边缺一个，右边缺好多的情况，是32次吧。当然
: 如果每次都选择缺的数多的
| c****p
发帖数: 6474 | 46 呃。。。。。。这样啊。。。我是假设没有重复的数的。
有重复的数确实一次就够了。。
【在 P**********c 的大作中提到】
: 如果4个billion的数都是2^32-1, 不是一次就扫出来了吗？
| g**********y
发帖数: 14569 | 47 看大家讨论第3题，我怎么觉得没那么复杂呢？
问：给定一个线段序列，求所有有公共点的线段对
解：对每个点，建一个Set, 包含所有这个点所在的边。然后对每个点，假如有k条边共
点，那就有k(k-1)/2对线段共点。
这看上去是个很straight-forward的问题，复杂度也很低。不需要DFS。
还是我有什么没理解到？请指出。 | b*******8
发帖数: 37364 | 48 4. 既然有50个字节，为啥每次只分成两段计数？可以分成4段或8段吧？然后其中一段
发现缺数，再继续下去
比较，如果相等则标记已访问过，并且标上component的值，这个也是O(n^2)吧。回来
也没想出有什么错误。
她属于0～2^31还是后面，这样数范围，如果数完发现左半边缺数，下次数的时候就只
看左边，继续分成两半。总共需要读原文件32次。不能用careercup那个做法。面试的
人似乎认为我的思路是对的，他只是说我的算法肯定要读文件32次，有没有方法是在有
些情况下不需要读32次的。我以为是很复杂的方法，结果我前面提到了，他说是每次数
的时候如果有半边范围个数是0，那就随便返回一个那半边范围里的数。
【在 P**********c 的大作中提到】
: 第三题我当时是一个一个比较的，用每条线段的起终点坐标跟其他线段的起终点坐标比较，如果相等则标记已访问过，并且标上component的值，这个也是O(n^2)吧。回来也没想出有什么错误。
: 第4题我是4 billion的数一个一个读进内存，因为每个数的范围是0~2^32, 所以先看她属于0～2^31还是后面，这样数范围，如果数完发现左半边缺数，下次数的时候就只看左边，继续分成两半。总共需要读原文件32次。不能用careercup那个做法。面试的人似乎认为我的思路是对的，他只是说我的算法肯定要读文件32次，有没有方法是在有些情况下不需要读32次的。我以为是很复杂的方法，结果我前面提到了，他说是每次数的时候如果有半边范围个数是0，那就随便返回一个那半边范围里的数。
:
: 些。
| g**********y
发帖数: 14569 | 49 算法复杂度是一样的，code还更复杂。从概率讲，你那个可能会更有效。但是不改变问
题的实质。
【在 b*******8 的大作中提到】
: 4. 既然有50个字节，为啥每次只分成两段计数？可以分成4段或8段吧？然后其中一段
: 发现缺数，再继续下去
:
: 比较，如果相等则标记已访问过，并且标上component的值，这个也是O(n^2)吧。回来
: 也没想出有什么错误。
: 她属于0～2^31还是后面，这样数范围，如果数完发现左半边缺数，下次数的时候就只
: 看左边，继续分成两半。总共需要读原文件32次。不能用careercup那个做法。面试的
: 人似乎认为我的思路是对的，他只是说我的算法肯定要读文件32次，有没有方法是在有
: 些情况下不需要读32次的。我以为是很复杂的方法，结果我前面提到了，他说是每次数
: 的时候如果有半边范围个数是0，那就随便返回一个那半边范围里的数。
| d*******l
发帖数: 338 | 50 题目的意思应该是要求连通分量，也就是所有能连到一起的线段都被放到一块输出
【在 g**********y 的大作中提到】
: 看大家讨论第3题，我怎么觉得没那么复杂呢？
: 问：给定一个线段序列，求所有有公共点的线段对
: 解：对每个点，建一个Set, 包含所有这个点所在的边。然后对每个点，假如有k条边共
: 点，那就有k(k-1)/2对线段共点。
: 这看上去是个很straight-forward的问题，复杂度也很低。不需要DFS。
: 还是我有什么没理解到？请指出。
| | | g**********y
发帖数: 14569 | 51 要是那样也是disjoint set合并问题，也不用DFS吧。
【在 d*******l 的大作中提到】
: 题目的意思应该是要求连通分量，也就是所有能连到一起的线段都被放到一块输出
| d*******l
发帖数: 338 | 52 都是可以的吧。直接建图再dfs想法比较直接，union的话效率应该会高一点。
【在 g**********y 的大作中提到】
: 要是那样也是disjoint set合并问题，也不用DFS吧。
| a********1
发帖数: 750 | 53 c＋＋考的好底层。
节还是很重要的，必须多写多练才行。类似copy constructure, assignment operator
哪些地方应该用const, 哪些地方为什么用reference，不要搞混了. 本来以为自己这些
都是知道的，没想到现场一
复杂度。
比如(3,5)和(4,6)之间的叫"a", 那就表示为
,6,"a")和(4,6,8,2,"b")是连在一起的, 又比如c和d是连在一起的，那打出来应该是
【在 P**********c 的大作中提到】
: 一个面经很少的大公司。
: 有几道题不是很清楚，另外基础的东西有些细节也没有搞清楚，挂掉了。感觉面试细节还是很重要的，必须多写多练才行。类似copy constructure, assignment operator哪些地方应该用const, 哪些地方为什么用reference，不要搞混了. 本来以为自己这些都是知道的，没想到现场一步一步的写，还是出了很多小错，当时就感觉给面试官印象不好了。写程序的时候要先想一想，以前写过看过什么类似的程序，需要注意什么问题。不要急着下笔。有的面试官问题问题很多，频率很快。很容易让你自己很心急，希望回答更多的题目，但是保证正确才是最重要的。
: 1. destructor里面不能throw exception, 那something bad happens应该用什么.
: 2. 在一个平面上有n个点，设计算法看能不能找出四个点构成一个正方形，分析时间复杂度。
: 3. 一个平面上有一些点，有些互相是相连的。每条边用一个data structure表示，比如(3,5)和(4,6)之间的叫"a", 那就表示为
: (3, 5, 4, 6, "a")
: 给你一串这样的structure, 打印出类似connected component的结果，比如。(3,5,4,6,"a")和(4,6,8,2,"b")是连在一起的, 又比如c和d是连在一起的，那打出来应该是
: 0 a
: 0 b
: 1 c
| q****x
发帖数: 7404 | 54 1. destructor里面不能throw exception, 那something bad happens应该用什么.
abort()?
2. 在一个平面上有n个点，设计算法看能不能找出四个点构成一个正方形，分析时间复
杂度。
seems hard. some classical comp geo algo?
3. 一个平面上有一些点，有些互相是相连的。每条边用一个data structure表示，比
如(3,5)和(4,6)之间的叫"a", 那就表示为
(3, 5, 4, 6, "a")
给你一串这样的structure, 打印出类似connected component的结果，比如。(3,5,4,6
,"a")和(4,6,8,2,"b")是连在一起的, 又比如c和d是连在一起的，那打出来应该是
0 a
0 b
1 c
1 d
input: a set of edges
ask for: connected component
set of edges -> graph -> bfs.
4. 今天版上讨论的类似的一个题，有4 billion个unsorted的整数，找missing的数，
只有50 byte的memory. 找到一个即可。
programming pearls?
节还是很重要的，必须多写多练才行。类似copy constructure, assignment operator
哪些地方应该用const, 哪些地方为什么用reference，不要搞混了. 本来以为自己这些
都是知道的，没想到现场一步一步的写，还是出了很多小错，当时就感觉给面试官印象
不好了。写程序的时候要先想一想，以前写过看过什么类似的程序，需要注意什么问题
。不要急着下笔。有的面试官问题问题很多，频率很快。很容易让你自己很心急，希望
回答更多的题目，但是保证正确才是最重要的。
复杂度。
比如(3,5)和(4,6)之间的叫"a", 那就表示为
,6,"a")和(4,6,8,2,"b")是连在一起的, 又比如c和d是连在一起的，那打出来应该是
【在 P**********c 的大作中提到】
: 一个面经很少的大公司。
: 有几道题不是很清楚，另外基础的东西有些细节也没有搞清楚，挂掉了。感觉面试细节还是很重要的，必须多写多练才行。类似copy constructure, assignment operator哪些地方应该用const, 哪些地方为什么用reference，不要搞混了. 本来以为自己这些都是知道的，没想到现场一步一步的写，还是出了很多小错，当时就感觉给面试官印象不好了。写程序的时候要先想一想，以前写过看过什么类似的程序，需要注意什么问题。不要急着下笔。有的面试官问题问题很多，频率很快。很容易让你自己很心急，希望回答更多的题目，但是保证正确才是最重要的。
: 1. destructor里面不能throw exception, 那something bad happens应该用什么.
: 2. 在一个平面上有n个点，设计算法看能不能找出四个点构成一个正方形，分析时间复杂度。
: 3. 一个平面上有一些点，有些互相是相连的。每条边用一个data structure表示，比如(3,5)和(4,6)之间的叫"a", 那就表示为
: (3, 5, 4, 6, "a")
: 给你一串这样的structure, 打印出类似connected component的结果，比如。(3,5,4,6,"a")和(4,6,8,2,"b")是连在一起的, 又比如c和d是连在一起的，那打出来应该是
: 0 a
: 0 b
: 1 c
| g***s
发帖数: 3811 | 55 考虑到是大文件扫描，最坏情况３２次(每次分为２组)和７次(动态选择分组数目)还是
差别很大的。
而且，分为多组，得到empty的概率也更大。
7次最坏的分组方式是
group worst max item number in next search
14 2 ^ 29
16 2 ^ 25
19 2 ^ 21
17 2 ^ 27
33 2 ^ 12
67 2 ^ 6
65 0
对上面的不容易理解的，用下面这个。最坏情况一样。但是效率不如上面的。
group worst max item number in next search
8 2 ^ 29
16 2 ^ 25
16 2 ^ 21
16 2 ^ 27
32 2 ^ 12
64 2 ^ 6
128 0
【在 g**********y 的大作中提到】
: 算法复杂度是一样的，code还更复杂。从概率讲，你那个可能会更有效。但是不改变问
: 题的实质。
| r*******g
发帖数: 1335 | 56 第二题如果和axis平行的话，岂不是可以先对x axis和y axis排序，这样如果出现横坐
标或者纵坐标相等就直接选出来。这样就不是n^2了。先找出这样的重复的点对，然后
再判断能否变成正方形就要简单的多了。
比如得到A,B的横坐标相同，CD横坐标相同，这个时候就要求AC, BD纵坐标也相同，所
以此时可以再看看这些pair是否同时出现坐标相同。
key
【在 P**********c 的大作中提到】
: 第二题正方形确定任何一条边整个形状也就确定了吧。我当时的解法是对每个点，水平
: 方向上找同样高度的点，然后对找到的每个点看另外两点是否存在，是不是跟你的思路
: 其实是一样的？
: 不过我没有提到implement的细节，比如hashtable, hashtable的两个坐标怎么弄成key
: 比较好？
:
: 些。
| r*******g
发帖数: 1335 | 57 这个方法号，学习了
哪位大侠有programming pearls这本书，能否分享下。
【在 i**********e 的大作中提到】
: 第 4 题是把 integer 看成 32 bit，4 billion 里必有至少一个 missing，因为 4
: billion < 2^32.
: 因为内存有限，首先把所有 first bit 为 0 的写进 文件A，然后 first bit 为 1 的
: 写进文件B.这时候如果文件 A 里的数是 <= 2 billion （必定有一个文件符合这条件
: ），那就代表 missing integer 的 first bit 必定为 0. 这时候就以文件 A 来当作
: 新的 input，然后看 second bit,以此类推。当扫描完 32 bit 的时候，也就知道
: missing integer 是什么了。
: 复杂度是 O(n)。每次最坏情况能消除 n/2.
: 所以复杂度:
: n + n/2 + n/4 +... = O(n)
| r*******g
发帖数: 1335 | 58 你和你上面的不同是上面那个需要额外的硬盘空间存储，这样每次读的次数可以减少，
你这个是每次维护两个数，分别表示一半一半的个数，然后累加，以此确定每次是哪一
半有问题。但是需要每次把所有数都遍历一遍。不管怎么说，内存不能hold住所有的
4billion个数。
不知道我理解对了没有。
看不明白为何肯定要读32次。
比较，如果相等则标记已访问过，并且标上component的值，这个也是O(n^2)吧。回来
也没想出有什么错误。
她属于0～2^31还是后面，这样数范围，如果数完发现左半边缺数，下次数的时候就只
看左边，继续分成两半。总共需要读原文件32次。不能用careercup那个做法。面试的
人似乎认为我的思路是对的，他只是说我的算法肯定要读文件32次，有没有方法是在有
些情况下不需要读32次的。我以为是很复杂的方法，结果我前面提到了，他说是每次数
的时候如果有半边范围个数是0，那就随便返回一个那半边范围里的数。
【在 P**********c 的大作中提到】
: 第三题我当时是一个一个比较的，用每条线段的起终点坐标跟其他线段的起终点坐标比较，如果相等则标记已访问过，并且标上component的值，这个也是O(n^2)吧。回来也没想出有什么错误。
: 第4题我是4 billion的数一个一个读进内存，因为每个数的范围是0~2^32, 所以先看她属于0～2^31还是后面，这样数范围，如果数完发现左半边缺数，下次数的时候就只看左边，继续分成两半。总共需要读原文件32次。不能用careercup那个做法。面试的人似乎认为我的思路是对的，他只是说我的算法肯定要读文件32次，有没有方法是在有些情况下不需要读32次的。我以为是很复杂的方法，结果我前面提到了，他说是每次数的时候如果有半边范围个数是0，那就随便返回一个那半边范围里的数。
:
: 些。
| k*j
发帖数: 153 | 59 想问下第三题有结论了没？线段求component的那题。
节还是很重要的，必须多写多练才行。类似copy constructure, assignment operator
哪些地方应该用const, 哪些地方为什么用reference，不要搞混了. 本来以为自己这些
都是知道的，没想到现场一步一步的写，还是出了很多小错，当时就感觉给面试官印象
不好了。写程序的时候要先想一想，以前写过看过什么类似的程序，需要注意什么问题
。不要急着下笔。有的面试官问题问题很多，频率很快。很容易让你自己很心急，希望
回答更多的题目，但是保证正确才是最重要的。
复杂度。
比如(3,5)和(4,6)之间的叫"a", 那就表示为
,6,"a")和(4,6,8,2,"b")是连在一起的, 又比如c和d是连在一起的，那打出来应该是
【在 P**********c 的大作中提到】
: 一个面经很少的大公司。
: 有几道题不是很清楚，另外基础的东西有些细节也没有搞清楚，挂掉了。感觉面试细节还是很重要的，必须多写多练才行。类似copy constructure, assignment operator哪些地方应该用const, 哪些地方为什么用reference，不要搞混了. 本来以为自己这些都是知道的，没想到现场一步一步的写，还是出了很多小错，当时就感觉给面试官印象不好了。写程序的时候要先想一想，以前写过看过什么类似的程序，需要注意什么问题。不要急着下笔。有的面试官问题问题很多，频率很快。很容易让你自己很心急，希望回答更多的题目，但是保证正确才是最重要的。
: 1. destructor里面不能throw exception, 那something bad happens应该用什么.
: 2. 在一个平面上有n个点，设计算法看能不能找出四个点构成一个正方形，分析时间复杂度。
: 3. 一个平面上有一些点，有些互相是相连的。每条边用一个data structure表示，比如(3,5)和(4,6)之间的叫"a", 那就表示为
: (3, 5, 4, 6, "a")
: 给你一串这样的structure, 打印出类似connected component的结果，比如。(3,5,4,6,"a")和(4,6,8,2,"b")是连在一起的, 又比如c和d是连在一起的，那打出来应该是
: 0 a
: 0 b
: 1 c
| k*j
发帖数: 153 | 60 想问下第三题有结论了没？线段求component的那题。
节还是很重要的，必须多写多练才行。类似copy constructure, assignment operator
哪些地方应该用const, 哪些地方为什么用reference，不要搞混了. 本来以为自己这些
都是知道的，没想到现场一步一步的写，还是出了很多小错，当时就感觉给面试官印象
不好了。写程序的时候要先想一想，以前写过看过什么类似的程序，需要注意什么问题
。不要急着下笔。有的面试官问题问题很多，频率很快。很容易让你自己很心急，希望
回答更多的题目，但是保证正确才是最重要的。
复杂度。
比如(3,5)和(4,6)之间的叫"a", 那就表示为
,6,"a")和(4,6,8,2,"b")是连在一起的, 又比如c和d是连在一起的，那打出来应该是
【在 P**********c 的大作中提到】
: 一个面经很少的大公司。
: 有几道题不是很清楚，另外基础的东西有些细节也没有搞清楚，挂掉了。感觉面试细节还是很重要的，必须多写多练才行。类似copy constructure, assignment operator哪些地方应该用const, 哪些地方为什么用reference，不要搞混了. 本来以为自己这些都是知道的，没想到现场一步一步的写，还是出了很多小错，当时就感觉给面试官印象不好了。写程序的时候要先想一想，以前写过看过什么类似的程序，需要注意什么问题。不要急着下笔。有的面试官问题问题很多，频率很快。很容易让你自己很心急，希望回答更多的题目，但是保证正确才是最重要的。
: 1. destructor里面不能throw exception, 那something bad happens应该用什么.
: 2. 在一个平面上有n个点，设计算法看能不能找出四个点构成一个正方形，分析时间复杂度。
: 3. 一个平面上有一些点，有些互相是相连的。每条边用一个data structure表示，比如(3,5)和(4,6)之间的叫"a", 那就表示为
: (3, 5, 4, 6, "a")
: 给你一串这样的structure, 打印出类似connected component的结果，比如。(3,5,4,6,"a")和(4,6,8,2,"b")是连在一起的, 又比如c和d是连在一起的，那打出来应该是
: 0 a
: 0 b
: 1 c
| | | R****i
发帖数: 104 | 61 尽量处理错误信息。如果不行，写log file。析构函数中抛出异常会把C++程序挂掉。 |
|
