p*********w
发帖数: 606 | 1 上周五面的，刚刚收到拒信。
我本来说想面bing或者azure，不过hr临时给安排了office的一个做排版的组。总共面了
四轮。
第一轮：一个俄罗斯人，三道白板coding。
1. atoi
2. 判断两二叉树全等（在可以交换左右子树的条件下），进一步给出需要多少次交换。
时间复杂度，如何优化。
3. 一个NxN矩阵，每个格子有一个整型数，从左上角到右下角找一条路径使得经过的格
子数字和最大。只能向右和下移动。时间复杂度，如何优化。
第二轮：lunch interview，俄罗斯人，几道智力题。
1. 什么东西是小的，绿色的，住在地面三英尺以下？
2. 从地面挖一个洞下去，打通地球另一面出来。然后这面扔一个石头下去，问石头会怎
么样。
3. 16个硬币排成4x4的方阵，怎么样拿掉6个，使得剩下的硬币每一行每一列都是偶数。
4. 一个方形的表面，一堆小的方形棋子，a和b轮流把棋子放到表面上。唯一的条件是棋
子不能重叠。如果一方找不到空间放棋子就算输了，问有无必胜策略。
5. 一列士兵横排站开，军官第一秒喊口令"about face"，然后士兵有的会左转有的会右
转，这样转完后一些士兵会... 阅读全帖 |
|
g*****e
发帖数: 282 | 2 回馈版面，抛砖引玉
atoi, itoa
sqrt
height of a tree
min-depth of a tree/node |
|
|
g*********s
发帖数: 1782 | 4 发信人: lolhaha (haha), 信区: JobHunting
标 题: Re: str2int中overflow该如何处理？
发信站: BBS 未名空间站 (Sun Feb 20 18:18:40 2011, 美东)
之前处理也可以，也许更直接
目标 result*10+str[i]-'0'<=MAX_INT
1) result
2) result=MAX_INT/10 && str[i]-'0'<=MAX_INT/10
but notice the negative bound is different from the positive bound. that's
why i say it's tricky. |
|
|
|
R***r
发帖数: 120 | 7 A的电面，就两题
写atoi，电话里读代码，不太习惯，还好不难。
设计一个饭店的预订系统，要自己想所有use case，问得超详细，几乎连code都要写出
来了，感觉不太好。
请教一下这饭店预订系统该用什么样的数据结构比较有效呢？ |
|
y******5
发帖数: 43 | 8 看你面哪个组了。当时我电面的时候HM就问了几个Unix command，不到15分钟，然后就
让我去onsite。结果到了之后开始面HM才说想要会perl的，我说我也可以用python，他
不是很满意。其他人的问题都很简单，atoi这种档次的。中饭都不给吃直接面到下午，
回来后一个星期毫无悬念地被拒。所以我现在对这家公司很不爽，纯粹耽误我时间。 |
|
g*****r
发帖数: 1037 | 9 问了PHD 做的一些PROJECT，最后有道简单的PROGRAMMING题目，用C实现ATOI一时没想
起来最优解法，悲剧。。。。 |
|
r********r
发帖数: 2912 | 10 atoi还有什么优不优的啊？不是一位一位算吗... |
|
g*********s
发帖数: 1782 | 11 the point of atoi() is not using bit operation to simulate *. |
|
s*****y
发帖数: 897 | 12 Why we do not look at the opensoruce software to see how they implenment?
Many of their implenmentation of atoi also have bug. |
|
t*******i
发帖数: 4960 | 13 我会把数字转换成字符串处理。
如果是正数的话，
找第一个比它右边小的数字，调换过来
比如：
257634 => 257643，好像就是答案了
如果找到的第一个数字不是刚好在上面这个位置
比如
257643，找到5，然后跟右边大于5的最小的一个数字换过来-》267543，然后6以后的数
字从小到大排列 =》 263457，好像是答案了
然后在 atoi换成数字
注意如果转换以后的字符串长度是1，直接返回。
如果是负数，转成正数，不过要找的是小于转换以后的正数的最大数。
不保证对啊。 |
|
t*******i
发帖数: 4960 | 14 打的一个草稿，不处理负数
int NextP(int num){
if (num < 0)
throw -1;
char str[11];
itoa(num, str, 10);
if (strlen(str) == 1)
throw -1;
pos = len-1;
while (pos >= 1){
if (str[pos] > str[pos - 1])
break;
pos --;
}
if (pos == 0)
throw -1;
--pos;
int min = findLargerMin(str, pos + 1, len – 1, str[pos]);
swap(str, pos, min);
sort(str, pos + 1, len - 1);
return atoi(str);
} |
|
A*****i
发帖数: 3587 | 15 刚被factset拒了，就看到这帖子，攒人品发面经好了
三轮技术面，一轮和VP面，中间加一顿午饭和俩码工
三轮技术面第一个是改bug，我最特么讨厌改别人的烂代码，5个错误，挑出4个，很简
单，当时太紧张了回头想想真不该
第二个俩题，一个是设计chess，一个是写个atoi，都不难，但是都不完美
第三个俩题，一个是设计他们交易系统的客户端GUI，一个就是BT的LCA，带父指针那种
，不知道怎么回事当时就蒙了，最后还是靠对方提醒才做出来⋯⋯
经验就是：factset出题都不难，很常规，但是千万要答的完美，在对方指出bug之前就
自己改好
唉⋯⋯马上OPT就开始了，还是没有fulltime，不知道还得多久⋯&#
8943; |
|
a********m
发帖数: 15480 | 16 背景：
5月底layoff。layoff那天请假和朋友出门挖贝壳了，没赶上开会。。。然后就开始了漫长的找工作（心理感觉）长征。知道消息一下就晕菜了。赶快查了h1b的规定还有写信问hr和律师公司的规定。律师真是忙，写邮件要几天才恢复，约后几天的半小时时间谈谈，结果错过了两次。。。干脆不理it了，先转b2再说。
申请：
一些公司猎头闻风而来，公司hr也帮俺们这帮倒霉蛋群发申请工作邮件，开始还是感觉良好的。折了几个电面和programming test以后走向另外一个极端。。。主要就是还从打击中恢复，还没准备好面试就被突然袭击。其中有几个非常想去的公司都挂了，郁闷的要死。还好6月中混到2个onsite.开始集中精力准备onsite,也暂停发简历。
面试:
先说折掉的D. 飞德州晚点2小时，11点多才到旅馆，晚上，照常出门逛一下，看看热闹，自己安慰自己是熟悉环境，实际是不喜欢看书。。。话说austin真热。。。下午走的时候是108度。。面试非常顺利。题目难度一般。真正算法也就是A*寻路算法。其他都是实际应用中的问题。还有点到直线距离一类的几何问题。总的来说游戏行业对算法要求不高，有实际经验再准... 阅读全帖 |
|
b*******y
发帖数: 2048 | 17 强贴前排就座
了漫长的找工作（心理感觉）长征。知道消息一下就晕菜了。赶快查了h1b的规定还有
写信问hr和律师公司的规定。律师真是忙，写邮件要几天才恢复，约后几天的半小时时
间谈谈，结果错过了两次。。。干脆不理it了，先转b2再说。
觉良好的。折了几个电面和programming test以后走向另外一个极端。。。主要就是还
从打击中恢复，还没准备好面试就被突然袭击。其中有几个非常想去的公司都挂了，郁
闷的要死。还好6月中混到2个onsite.开始集中精力准备onsite,也暂停发简历。
闹，自己安慰自己是熟悉环境，实际是不喜欢看书。。。话说austin真热。。。下午走
的时候是108度。。面试非常顺利。题目难度一般。真正算法也就是A*寻路算法。其他
都是实际应用中的问题。还有点到直线距离一类的几何问题。总的来说游戏行业对算法
要求不高，有实际经验再准备下都不太难。后来挂的地方是午饭时间一个俗到不能再俗
的问题。。。你的弱点是什么。。。俺找了一个n年前年轻时候的不好的习惯，然后强
调这n年都在不断注意和改进。。。结果it只听了前半: 句。另外一个是complishment
。本着谦虚... 阅读全帖 |
|
P**********c
发帖数: 3417 | 18 赞。
了漫长的找工作（心理感觉）长征。知道消息一下就晕菜了。赶快查了h1b的规定还有
写信问hr和律师公司的规定。律师真是忙，写邮件要几天才恢复，约后几天的半小时时
间谈谈，结果错过了两次。。。干脆不理it了，先转b2再说。
觉良好的。折了几个电面和programming test以后走向另外一个极端。。。主要就是还
从打击中恢复，还没准备好面试就被突然袭击。其中有几个非常想去的公司都挂了，郁
闷的要死。还好6月中混到2个onsite.开始集中精力准备onsite,也暂停发简历。
闹，自己安慰自己是熟悉环境，实际是不喜欢看书。。。话说austin真热。。。下午走
的时候是108度。。面试非常顺利。题目难度一般。真正算法也就是A*寻路算法。其他
都是实际应用中的问题。还有点到直线距离一类的几何问题。总的来说游戏行业对算法
要求不高，有实际经验再准备下都不太难。后来挂的地方是午饭时间一个俗到不能再俗
的问题。。。你的弱点是什么。。。俺找了一个n年前年轻时候的不好的习惯，然后强
调这n年都在不断注意和改进。。。结果it只听了前半: 句。另外一个是complishment
。本着谦虚的态度。... 阅读全帖 |
|
w********h
发帖数: 48 | 19 ① 设计一个类来保存一些整数，提供两个接口：增加一个整数、获取中位数。提供
不同的实现分别优化这两个接口。
② 反转链表。分别用递归和循环实现。
③ 面向对象设计：在线二十一点游戏
④ 分层打印一个二叉树，每层格式自由
⑤ 在一个整数序列中寻找一个和最大的连续子序列。（空序列是非法输入输出）
⑥ 面向对象设计：类Unix文件系统
⑦ 两个数组A1、A2，长度分别为L1、L1+L2。A1和A2的前L2个元素均已分别排序好
。请合并A1和A2的前L2个元素到A2中。
⑧ 一个文本文件，每行有三列：shipment ID, UPC code, quantity，写Unix
shell命令输出quantity最大的十行。
⑨ 实现atoi函数。请考虑各种可能情况及如何错误处理。
⑩ 排序后旋转的数组内查询元素
⑪ 判断一个二叉树是否是二叉排序树。
⑫ 现在是周三，你有一个系统计划下周一交付运营。另外一个组告诉你系统
依赖的web service原计划本周一交付，但他们在忙于其它项目，不得不推迟两到三... 阅读全帖 |
|
y******n
发帖数: 47 | 20 周五面完最后一个onsite, 累的惨兮兮的, 好容易爬回家. 不管结果如何, 这段时间找
工作算是告一段落了.
下面把这段时间面试中被问到的题目整理一下, 供大家参考. 我也就不说具体是那些公
司了, 都是很典型的面试题, 到哪里都有可能会被问到.
* implement memcpy? How to improve? how to determine if a system is
32bit or 64bit?
* how is static keyword used in Java?
* a list of intervals, no overlapping and sorted, write a function to
insert an interval into the list and still keep the list sorted and no
overlapping.
* given a function on sorted dictionary to retrieve word by index,
string getWord(int i), how to i... 阅读全帖 |
|
f*******t
发帖数: 7549 | 21 google atoi you can find 一大堆 code |
|
y*******g
发帖数: 6599 | 22 小题目，比如atoi,merge,Binary search的变体, 10-15min是上限吧。
不过不能为了速度忽视交流。问题要问，limit，input output要搞清楚，写的时候要
讲思路，我觉得至少每个loop要说明一下loop invariant
其实面试题目的代码不会超过20行，思路清晰了写起来也就5分钟，主要是思路，特殊
条件要想清楚。
大题目时间上可能会因人而异差别大。
参考面试官的一手信息：
The worst candidates don’t even manage to implement the fizzbuzz solution
in 45 minutes. The best implement a memoized solution in 10 minutes
http://thenoisychannel.com/2011/08/08/retiring-a-great-intervie |
|
y*******g
发帖数: 6599 | 23 小题目，比如atoi,merge,Binary search的变体, 10-15min是上限吧。
不过不能为了速度忽视交流。问题要问，limit，input output要搞清楚，写的时候要
讲思路，我觉得至少每个loop要说明一下loop invariant
其实面试题目的代码不会超过20行，思路清晰了写起来也就5分钟，主要是思路，特殊
条件要想清楚。
大题目时间上可能会因人而异差别大。
参考面试官的一手信息：
The worst candidates don’t even manage to implement the fizzbuzz solution
in 45 minutes. The best implement a memoized solution in 10 minutes
http://thenoisychannel.com/2011/08/08/retiring-a-great-intervie |
|
y*******g
发帖数: 6599 | 24 面试的时候和面试官提一下就好了，
常见问题比如atoi可以参考标准库是怎么处理的。
工作中具体情况具体处理 |
|
y*******g
发帖数: 6599 | 25 面试的时候和面试官提一下就好了，
常见问题比如atoi可以参考标准库是怎么处理的。
工作中具体情况具体处理 |
|
w****x
发帖数: 2483 | 26 很多题还是要想想的,
特别是题目不难, 逻辑比较繁琐的比如wild char match, 三分数组之类的题目感觉逻
辑出来的还是很慢, 虽然大体知道怎么做. 比如3分数组这种题我做过两遍了, 现在还
叫我做估计20分钟内还是写不出没bug的代码. 还有atoi我做过两遍了, 要考虑的东西
多(特别是溢出, 负数比正数个数多一个还~~~), 实在很难像某些人说的15分钟无bug,
这么说我个人感觉基本扯蛋， 又不是ACM比赛。估计我练到第1000题还是很难提高，
特别是在逻辑思考和处理上， 除非把代码背下来， 那更扯蛋了。 |
|
q****x
发帖数: 7404 | 27 atoi(), write the plain one and then work on overflow issue. no need to do
it in one pass.
, |
|
n*******w
发帖数: 687 | 28 google“dutch national flag problem”
个人一点体会。
做题得彻底理解，特别题目中最容易卡思路的地方以及薄弱的题型。不然过段时间碰到
了还是会卡同样的地方。
比如三分数组，最巧妙的地方就是3个指针。分别指向某部分的头或者尾。
感觉最容易卡住的地方就是中间那部分。得利用中间那部分每个数都相等，可以只swap
1次把整个中间部分后移一位。而且这样做本质上是unstable的。理解了这点应该就能
很快写出bug-free code。
atoi的话，先把exception定义在那里，最后去实现。 |
|
S*******0
发帖数: 198 | 29 正数和负数的overflow判断不一样，
public static int atoi(String str) throws Exception{
String expression = str.trim();
if(expression==null||expression.equals("")){
throw new Exception("expression is empty");
}
int sign = 1;
int index = 0;
if(expression.charAt(0) == '-'){
sign = -1;
}
if(expression.charAt(0) == '-' || expression.charAt(0) == '+'){
index++;
if(expression.length()==1){
... 阅读全帖 |
|
d*******l
发帖数: 338 | 30 我现在觉得面试要考察的有知识的掌握，临场应变，交流沟通能力，背景的匹配程度等
多方面，解算法题只占一小部分。像楼主说的那些问题都是边界比较多的，快速写出来
全无bug非常困难，三分数组要是在平时我一定倾向于用两次典型的qsort的partition
来做到，这样不容易出错。atoi我也不会一上来就处理溢出。
我现在觉得算法水平在所有人中达到90%就不错了，再往上提高很不容易，还不如用来
准备design或者是别的问题。临场的时候能展现出真实水平我就很满意了。 |
|
r****t
发帖数: 10904 | 31 不是-1 是 0 吧，你这个“标准的atoi”哪儿看来的？ |
|
r****t
发帖数: 10904 | 32 atoi 是不能 throw 的，除非自己的山寨版本。
明天该能试试三分数组了，顶这个经验贴。
swap |
|
l*****a
发帖数: 14598 | 33 好
atoi,reverse number,tree traverse(recursion,stack,parent pointer)
写吧 |
|
|
K*****k
发帖数: 430 | 35 还有，那本PIE书上提到的itoa法也不是很直接，那个从尾部开始的求模法，结果却是
逆置的。 |
|
|
q****x
发帖数: 7404 | 37 这题就不必照本宣科了。知道大致思路即可。还背答案？
逆序很容易处理。 |
|
x*******7
发帖数: 223 | 38 总结一下哪些是基本题？ binary search, atoi, duplicates of array/llist? |
|
v***a
发帖数: 365 | 39
冲突
多谢分享！比atoi有意思多了。。。。
感觉32位Unicode字符统计BST或许会好点。
分布的情况貌似可以这样：
1）所有机器的Top 1% freqent unicodes. 得到这些集合的交集 X。
2）如果 X 是空集，扩展到2%，重做，直到X不是空集。
3）频率最高的在 X 中，统计X中所有unicodes的频率，取最高
肯定code不出来了，涉及到了BST, Heap, Hash, Disjoint Set and splay tree.
而且最坏情况还是传输了所有机器的 BST……比 hash 还糟糕点，呵呵
攒点字数，RP守恒！ |
|
O******i
发帖数: 269 | 40 写了一个，要考虑的情况真多...
假定是16位整数，范围是-32768到+32767
bool my_atoi(const char* str, int16& num)
{
if (str == NULL || str[0] == '\0')
return false;
int i = 0;
bool IsNeg = (str[0] == '-')? true : false;
if (str[0] == '+' || str[0] == '-')
{
if (str[1] == '\0')
return false;
i = 1;
}
num = 0;
const int num_limit = 3276;
const int digit_limit = (IsNeg)? 8 : 7;
int digit = 0;
bool max_int_reached = false;
for (; str[... 阅读全帖 |
|
P**l
发帖数: 3722 | 41 弱弱地问，我要是输入"thirty-five"，能输出啥 |
|
n*******w
发帖数: 687 | 42 这个题面试中经常问。最好一次性写到bug free。
个人感觉，一开始先别考虑那么多exception。容易忘。
另外还有一个处理exception的方法。可以尽量parse input string并返回一个整数值
。感觉更好。比如输入 “-123abc”，不要抛出异常，返回-123. |
|
|
g*********8
发帖数: 64 | 44 int str2int(string s){
assert(s.length()>0);
bool isNeg=false;
unsigned int num=0,i=0,d=0;
if(s[0]=='-'){
isNeg=true;
i=1;
}
while(i
d=s[i]-'0';
num=num*10+d;
assert(d>=0&&d<=9);
assert(num<=INT_MAX);
i++;
}
if(isNeg) num=-1*num;
return num;
}
我写的代码，望指正，处理了溢出，负数，非数值，还有什么异常没有处理？ |
|
g*********8
发帖数: 64 | 45 测试用例： -123
1222121212212121
-1222121212212121
-dfd
"" |
|
r****t
发帖数: 10904 | 46 溢出以后结果值也在 INT_MIN, INT_MAX范围内，如果不查检查如何知道会溢出？
不过原版的也不查，咱们山寨也不用了。 |
|
r****t
发帖数: 10904 | 47 this is required from the man page. |
|
j*******g
发帖数: 4 | 48 见过很多次这个题目了，一直没有招，下面写了一个又臭又长的， 方法很笨， 求建议
， 欢迎批评和指正
这样的代码面试可以通过吗？
////////////////////////////////////////////////////////////////
#include
#include
using namespace std;
//假设16位的整型
// -32768 , +32767
const char MAX_INT[] = "32767";
const char MIN_INT[] = "32768";
const int MAX_STRLEN = 5;
bool my_atoi(const char *str, int &res)
{
if(str == NULL)
{
cout << "Invalid pointer" << endl;
return false;
}
int index = 0;
if(str[index] == '-' || s... 阅读全帖 |
|
|
g*********e
发帖数: 14401 | 50 请问 INT_MAX INT_MIN是要自己define吗？c貌似不自带这个吧。 |
|
