为什么做了400道算法题还是那么菜 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

为什么做了400道算法题还是那么菜

为什么做了400道算法题还是那么菜# JobHunting - 待字闺中

w*x2011-11-04 07:11

1 楼

很多题还是要想想的,
特别是题目不难, 逻辑比较繁琐的比如wild char match, 三分数组之类的题目感觉逻
辑出来的还是很慢, 虽然大体知道怎么做. 比如3分数组这种题我做过两遍了, 现在还
叫我做估计20分钟内还是写不出没bug的代码. 还有atoi我做过两遍了, 要考虑的东西
多(特别是溢出, 负数比正数个数多一个还~~~), 实在很难像某些人说的15分钟无bug,
这么说我个人感觉基本扯蛋，又不是ACM比赛。估计我练到第1000题还是很难提高，
特别是在逻辑思考和处理上，除非把代码背下来，那更扯蛋了。

x*72011-11-04 07:11

2 楼

什么是3分数组?

,

【在 w****x 的大作中提到】

: 很多题还是要想想的,
: 特别是题目不难, 逻辑比较繁琐的比如wild char match, 三分数组之类的题目感觉逻
: 辑出来的还是很慢, 虽然大体知道怎么做. 比如3分数组这种题我做过两遍了, 现在还
: 叫我做估计20分钟内还是写不出没bug的代码. 还有atoi我做过两遍了, 要考虑的东西
: 多(特别是溢出, 负数比正数个数多一个还~~~), 实在很难像某些人说的15分钟无bug,
: 这么说我个人感觉基本扯蛋，又不是ACM比赛。估计我练到第1000题还是很难提高，
: 特别是在逻辑思考和处理上，除非把代码背下来，那更扯蛋了。

x*72011-11-04 07:11

3 楼

能举出所有要考虑的东西吗？负数多一个需要特别处理？

,

【在 w****x 的大作中提到】

q*x2011-11-04 07:11

4 楼

atoi(), write the plain one and then work on overflow issue. no need to do
it in one pass.

,

【在 w****x 的大作中提到】

a*12011-11-04 07:11

5 楼

不要光求数量，
一道题目草草一过太浪费了，参考这篇文章：
http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=
Here's your first exercise: take any problem in the Practice Rooms that you
haven't done. Fight through it, no matter how long it takes, and figure it
out (use the editorial from the competition as a last resort). Get it to
pass system tests, and then note how long you took to solve it. Next, clear
your solution out, and try to type it in again (obviously cutting and
pasting will ruin the effect). Again, get it to pass system tests. Note how
long it took you to finish the second time. Then, clear it out and do the
problem a third time, and again get it to pass system tests. Record this
final time.
The time it takes for your first pass is how long it takes you when you have
no expectations of the problem and no approach readily in mind. Your time
on the second pass is usually the first time minus the amount of time it
took you to understand the problem statement. (Don't be surprised at the
number of bugs you'll repeat in the second pass.) That final recorded time
is your potential, for you can solve it this fast in competition if you see
the correct approach immediately after reading it. Let that number encourage
you; it really is possible to solve some of these problems this quickly,
even without super fast typing ability. But what you should also learn from
the third pass is the feeling that you knew a working strategy, how the code
would look, where you would tend to make the mistakes, and so on. That's
what it feels like to have the right approach, and that feeling is your goal
for future problems in competition.
In most martial arts, there's a practice called kata where the martial
artist performs a scripted series of maneuvers in order, usually pretending
to defend (or sometimes actually defending) against an onslaught of fighters
, also scripted to come at the artist predictably. At first this type of
practice didn't make any sense, because it didn't seem realistic to the
chaotic nature of battle. Furthermore it seems to encourage the type of
pattern mining mentioned in the previous section. Only after triple-coding
many problems for a while can one comprehend the true benefit of this coding
kata. The kata demonstrates to its practitioners the mental experience of
having a plan, encouraging the type of discipline it takes to sit and think
the problem through. This plan of attack is your approach, and it carries
you through your coding, debugging, and submission.

w*x2011-11-04 07:11

6 楼

三分数组就是说一个数组，给一个值，左半部分是小于他的，右半部分是大于的，
中间是等于的

【在 x*******7 的大作中提到】

: 什么是3分数组?
:
: ,

f*t2011-11-04 07:11

7 楼

这个不是qsort的基础吗，多写几遍qsort就行了。。

【在 w****x 的大作中提到】

:
: 三分数组就是说一个数组，给一个值，左半部分是小于他的，右半部分是大于的，
: 中间是等于的

w*x2011-11-04 07:11

8 楼

正负号的合法性：比如-12 +123 123 合法，++123 --123 +-123非法
字符合法性: 12ad3就不对
溢出处理：1234567899999会溢出，负数的范围到-2^16, 正数的范围到2^16 -1，所以
说正数溢出和负数溢出不能简单的先判断符号再判断后面的正数是否溢出
函数原型的设计：如果是int atoi(const char* str), 返回什么值代表异常？？返
回负一，要是本来传的就是-1怎么办？？
标准的atoi实现大家可以看看更本没考虑这么多，字符非法就非法，直接拿ascII值来
算。溢出就溢出，所有错误返回-1, 不管你传得是不是"-1"
我的意思是版上很多人说什么像这样简单的题15分钟内需要想都不想写出简洁无bug的
答案。像这种考虑很多的题，更本不可能在20分钟或15分钟内完成，看起来简单，
实际上是吹毛求疵

【在 x*******7 的大作中提到】

: 能举出所有要考虑的东西吗？负数多一个需要特别处理？
:
: ,

w*x2011-11-04 07:11

9 楼

话是这么说没错，大体知道是这样，但是具体逻辑实现上可能没那么顺利，就是很
“绕”的感觉，就这么"绕"一下时间就过去了

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

: 这个不是qsort的基础吗，多写几遍qsort就行了。。

n*w2011-11-04 07:11

10 楼

google“dutch national flag problem”
个人一点体会。
做题得彻底理解，特别题目中最容易卡思路的地方以及薄弱的题型。不然过段时间碰到
了还是会卡同样的地方。
比如三分数组，最巧妙的地方就是3个指针。分别指向某部分的头或者尾。
感觉最容易卡住的地方就是中间那部分。得利用中间那部分每个数都相等，可以只swap
1次把整个中间部分后移一位。而且这样做本质上是unstable的。理解了这点应该就能
很快写出bug-free code。
atoi的话，先把exception定义在那里，最后去实现。

【在 x*******7 的大作中提到】

: 什么是3分数组?
:
: ,

w*x2011-11-04 07:11

11 楼

you
clear
how
说的很有道理，非常感谢

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

: 不要光求数量，
: 一道题目草草一过太浪费了，参考这篇文章：
: http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=
: Here's your first exercise: take any problem in the Practice Rooms that you
: haven't done. Fight through it, no matter how long it takes, and figure it
: out (use the editorial from the competition as a last resort). Get it to
: pass system tests, and then note how long you took to solve it. Next, clear
: your solution out, and try to type it in again (obviously cutting and
: pasting will ruin the effect). Again, get it to pass system tests. Note how
: long it took you to finish the second time. Then, clear it out and do the

x*72011-11-04 07:11

12 楼

确实考虑的挺多的，能贴下你的代码，怎么更好处理这么多cases.

【在 w****x 的大作中提到】

:
: you
: clear
: how
: 说的很有道理，非常感谢

w*x2011-11-04 07:11

13 楼

不知道有没有其他bug
int myatoi(const char* p)
{
assert(p);
int nFlg = 1;
if ('-' == *p)
nFlg = -1;
if ('-' == *p || '+' == *p)
p++;
if ('\0' == *p)
throw CException("Invalid expression");
int nRet = 0;
while('\0' != *p)
{
if (*p < '0' || *p > '9')
throw CException("Invalid character");
int nVal = *p - '0';
int nNew = nRet*10 + nFlg * nVal;
if (nRet != 0 && ((nNew & 0x80000000) != (nRet & 0x80000000)))
throw CException("Integer over flow");

nRet = nNew;
p++;
}
return nRet;
}

【在 x*******7 的大作中提到】

: 确实考虑的挺多的，能贴下你的代码，怎么更好处理这么多cases.

y*g2011-11-04 07:11

14 楼

找工作的过程不是和板上的id较劲，而是拿到offer
面试也不是给NASA敲命令来拯救15分钟内即将坠毁空间站，而是给面试官展现你能处
理问题，你能code

【在 w****x 的大作中提到】

:
: 不知道有没有其他bug
: int myatoi(const char* p)
: {
: assert(p);
: int nFlg = 1;
: if ('-' == *p)
: nFlg = -1;
: if ('-' == *p || '+' == *p)
: p++;

y*g2011-11-04 07:11

15 楼

我被问过这个问题，错误处理我当时问过我的面试官，他首先让我写正常的，
然后问了我标准的atoi怎么做的，有哪些不好，你应该怎么做，
我回答加一个参数
int myatoi(const char* p, int& out);
返回值是错误代码， atoi的结果在out里

【在 w****x 的大作中提到】

:
: 不知道有没有其他bug
: int myatoi(const char* p)
: {
: assert(p);
: int nFlg = 1;
: if ('-' == *p)
: nFlg = -1;
: if ('-' == *p || '+' == *p)
: p++;

x*72011-11-04 07:11

16 楼

那itoa也要考虑这么多合法性？
比如输入是-abc21，要检查是不是int?

【在 w****x 的大作中提到】

:
: 不知道有没有其他bug
: int myatoi(const char* p)
: {
: assert(p);
: int nFlg = 1;
: if ('-' == *p)
: nFlg = -1;
: if ('-' == *p || '+' == *p)
: p++;

B*12011-11-04 07:11

17 楼

你这个skip了开头的whitespace了吗？
The function first discards as many whitespace characters as necessary until
the first non-whitespace character is found. Then, starting from this
character, takes an optional initial plus or minus sign followed by as many
numerical digits as possible, and interprets them as a numerical value.

【在 w****x 的大作中提到】

:
: 不知道有没有其他bug
: int myatoi(const char* p)
: {
: assert(p);
: int nFlg = 1;
: if ('-' == *p)
: nFlg = -1;
: if ('-' == *p || '+' == *p)
: p++;

x*72011-11-04 07:11

18 楼

good point

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

: 找工作的过程不是和板上的id较劲，而是拿到offer
: 面试也不是给NASA敲命令来拯救15分钟内即将坠毁空间站，而是给面试官展现你能处
: 理问题，你能code

v*k2011-11-04 07:11

19 楼

所谓bug free是指没有明规则意义上的bug，潜规则的bug很多都不考虑的。当然碰到印
度人那就没办法了

w*r2011-11-04 07:11

20 楼

加油，总会有质变的那一天

,

【在 w****x 的大作中提到】

C*d2011-11-04 07:11

21 楼

bless

,

【在 w****x 的大作中提到】

S*02011-11-04 07:11

22 楼

正数和负数的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){
throw new Exception("expression is invalid");
}
}
int ret = 0;
while(index char c = expression.charAt(index);
if(c < '0' || c > '9') throw new Exception("expression is
invalid");
int value = c - '0';
if(sign > 0){
if(ret > Integer.MAX_VALUE / 10) throw new Exception("
Integer overflow");
}else{
if(ret < Integer.MIN_VALUE / 10) throw new Exception("
Integer overflow");
}
ret = ret*10;
if(sign > 0){
if(ret > Integer.MAX_VALUE - value) throw new Exception("
Integer overflow");
}else{
if(ret < Integer.MIN_VALUE + value ) throw new Exception("
Integer overflow");
}
ret += value * sign;
index++;
}
return ret;
}

【在 w****x 的大作中提到】

:
: 不知道有没有其他bug
: int myatoi(const char* p)
: {
: assert(p);
: int nFlg = 1;
: if ('-' == *p)
: nFlg = -1;
: if ('-' == *p || '+' == *p)
: p++;

d*l2011-11-04 07:11

23 楼

我现在觉得面试要考察的有知识的掌握，临场应变，交流沟通能力，背景的匹配程度等
多方面，解算法题只占一小部分。像楼主说的那些问题都是边界比较多的，快速写出来
全无bug非常困难，三分数组要是在平时我一定倾向于用两次典型的qsort的partition
来做到，这样不容易出错。atoi我也不会一上来就处理溢出。
我现在觉得算法水平在所有人中达到90%就不错了，再往上提高很不容易，还不如用来
准备design或者是别的问题。临场的时候能展现出真实水平我就很满意了。

k*n2011-11-04 07:11

24 楼

面试官其实未必需要你立马写出bugless的代码
更看重的是你的基本功，遇到问题时怎样分析，怎样和跟人讨论解决问题的能力
公司不会指望招进来的所有人都是ACM级别的
而是希望招进来的是能一起工作的
就像这道题，你说的这些问题都是你自己想到的吗？
如果在面试的时候，你能对基本的case迅速写出没有bug的代码
然后能针对这些异常情况分别作出分析，给出解决的办法——这部分没必要coding
我觉得就属于非常成功的解答了

【在 w****x 的大作中提到】

:
: 不知道有没有其他bug
: int myatoi(const char* p)
: {
: assert(p);
: int nFlg = 1;
: if ('-' == *p)
: nFlg = -1;
: if ('-' == *p || '+' == *p)
: p++;

k*n2011-11-04 07:11

25 楼

忍不住说一句
你这个程序能写在一个白板上吗？
面试的coding问题不会让你写超过20行代码的

【在 S*******0 的大作中提到】

: 正数和负数的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;

w*x2011-11-04 07:11

26 楼

谢谢大家关注, 只是随便问问, thanks

n*w2011-11-04 07:11

27 楼

那么多exception，有些还不简单。一般没那么多时间。
跟interviewer说说要处理哪些exception，然后定义着。主体写完了有时间可以完善。

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

: 忍不住说一句
: 你这个程序能写在一个白板上吗？
: 面试的coding问题不会让你写超过20行代码的

h*62011-11-04 07:11

28 楼

景仰400题的大牛。

r*t2011-11-04 07:11

29 楼

不是-1 是 0 吧，你这个“标准的atoi”哪儿看来的？

【在 w****x 的大作中提到】

: 谢谢大家关注, 只是随便问问, thanks

c*p2011-11-04 07:11

30 楼

个人觉得有些东西需要一些兴趣和平时的积累。
看到一些事情，想能不能用编程解决实现（有没有解），
能编的话数据结构和算法怎么组织，有哪些corner case需要考虑，
怎样确保程序的可扩展性，有没有适用于更深广的结论的可能；
看到比较犀利的代码没有为我所用的可能和适用场景……【在 wwwyhx (wwwyhx) 的大
作中提到: 】
,

g*82011-11-04 07:11

31 楼

同意，正解

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

g*y2011-11-04 07:11

32 楼

你又来开国际玩笑。

【在 h**6 的大作中提到】

: 景仰400题的大牛。

g*y2011-11-04 07:11

33 楼

赞无名！这篇是topcoder上的新文章？我漏过了。道理讲得很好。

you
clear
how

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

g*v2011-11-04 07:11

34 楼

mark

a*n2011-11-04 07:11

35 楼

真的需要这样准备啊，我总共可能才做１０道左右（不知道有没有）就跑去面世。在
TOP CODER做过一道题。。。看来我准备的很不好。。。惭愧。。。

q*x2011-11-04 07:11

36 楼

因人而异。我认识一个朋友，裸上也搞定了G和L，F差一点。

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

: 真的需要这样准备啊，我总共可能才做１０道左右（不知道有没有）就跑去面世。在
: TOP CODER做过一道题。。。看来我准备的很不好。。。惭愧。。。

r*t2011-11-04 07:11

37 楼

atoi 是不能 throw 的，除非自己的山寨版本。
明天该能试试三分数组了，顶这个经验贴。

swap

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

: google“dutch national flag problem”
: 个人一点体会。
: 做题得彻底理解，特别题目中最容易卡思路的地方以及薄弱的题型。不然过段时间碰到
: 了还是会卡同样的地方。
: 比如三分数组，最巧妙的地方就是3个指针。分别指向某部分的头或者尾。
: 感觉最容易卡住的地方就是中间那部分。得利用中间那部分每个数都相等，可以只swap
: 1次把整个中间部分后移一位。而且这样做本质上是unstable的。理解了这点应该就能
: 很快写出bug-free code。
: atoi的话，先把exception定义在那里，最后去实现。