Browsed by
标签: 面试

Leetcode 编程训练

Leetcode 编程训练

LeetCodeLogo (1)Leetcode这个网站上的题都是一些经典的公司用来面试应聘者的面试题,很多人通过刷这些题来应聘一些喜欢面试算法的公司,比如:Google、微软、Facebook、Amazon之类的这些公司,基本上是应试教育的功利主义。

我做这些题目的不是为了要去应聘这些公司,而是为了锻炼一下自己的算法和编程能力。因为我开始工作的时候基本没有这样的训练算法和编程的网站,除了大学里的“算法和数据结构”里的好些最基础最基础的知识,基本上没有什么训练。所以,当我看到有人在做这些题的时候,我也蠢蠢欲动地想去刷一下。

于是,我花了3-4个月的业余时间,我把Leetcode的154道题全部做完了。(这也是最近我没有太多的时间来写博客的原因,你可以看到我之前做的那个活动中有几个算法题来自于Leetcode)有人说我时间太多了,这里声明一下,我基本上都是利用了晚上10点以后的时间来做这些题的。

LeetCode的题大致分成两类:

1)基础算法的知识。这些题里面有大量的算法题,解这些题都是有套路的,不是用递归(深度优先DFS,广度优先BFS),就是要用动态规划(Dynamic Programming),或是拆半查找(Binary Search),或是回溯(Back tracing),或是分治法(Divide and Conquer),还有大量的对树,数组、链表、字符串和hash表的操作。通过做这些题能让你对这些最基础的算法的思路有非常扎实的了解和训练。对我而言,Dynamic Programming 是我的短板,尤其是一些比较复杂的问题,在推导递推公式上总是有思维的缺陷(数学是我的硬伤),通过做了这些题后,我能感到我在DP的思路上有了很大的收获。

2)编程题。比如:atoi,strstr,add two num,括号匹配,字符串乘法,通配符匹配,文件路径简化,Text Justification,反转单词等等,这些题的Edge Case, Corner Case有很多。这些题需要你想清楚了再干,只要你稍有疏忽,就会有几个case让你痛不欲生,而且一不小心就会让你的代码会写得又臭又长,无法阅读。通过做这些题,可以非常好的训练你对各种情况的考虑,以及你对程序代码组织的掌控(其实就是其中的状态变量)。还记得我在《函数式编程》中说的,程序中的状态是你程序变得复杂难维护的直接原因。

我觉得每个程序员都应该花时间和精力做这些题,因为你会从这些题中得到很大的收益。做完这些题后你一定会明白下面几个道理:

阅读全文 Read More

好烂啊有点差凑合看看还不错很精彩 (110 人打了分,平均分: 4.46 )
Loading...
C++面试中string类的一种正确写法

C++面试中string类的一种正确写法

(感谢网友 @bnu_chenshuo 投稿)

C++ 的一个常见面试题是让你实现一个 String 类,限于时间,不可能要求具备 std::string 的功能,但至少要求能正确管理资源。具体来说:

  1. 能像 int 类型那样定义变量,并且支持赋值、复制。
  2. 能用作函数的参数类型及返回类型。
  3. 能用作标准库容器的元素类型,即 vector/list/deque 的 value_type。(用作 std::map 的 key_type 是更进一步的要求,本文从略)。

换言之,你的 String 能让以下代码编译运行通过,并且没有内存方面的错误。

void foo(String x)
{
}

void bar(const String& x)
{
}

String baz()
{
  String ret("world");
  return ret;
}

int main()
{
  String s0;
  String s1("hello");
  String s2(s0);
  String s3 = s1;
  s2 = s1;

  foo(s1);
  bar(s1);
  foo("temporary");
  bar("temporary");
  String s4 = baz();

  std::vector<String> svec;
  svec.push_back(s0);
  svec.push_back(s1);
  svec.push_back(baz());
  svec.push_back("good job");
}

阅读全文 Read More

好烂啊有点差凑合看看还不错很精彩 (38 人打了分,平均分: 3.71 )
Loading...
为什么我反对纯算法面试题

为什么我反对纯算法面试题

算法面试可能是微软搞出来的面试方法,现在很多公司都在效仿,而且我们的程序员也乐于解算法题,我个人以为,这是应试教育的毒瘤!我在《再谈“我是怎么招程序员”》中比较保守地说过,“问难的算法题并没有错,错的很多面试官只是在肤浅甚至错误地理解着面试算法题的目的。”,今天,我想加强一下这个观点——我反对纯算法题面试!(注意,我说的是纯算法题)

图片源Wikipedia(点击图片查看词条)

我再次引用我以前的一个观点——

能解算法题并不意味着这个人就有能力就能在工作中解决问题,你可以想想,小学奥数题可能比这些题更难,但并不意味着那些奥数能手就能解决实际问题。

好了,让我们来看一个示例(这个示例是昨天在微博上的一个讨论),这个题是——“找出无序数组中第2大的数”,几乎所有的人都用了O(n)的算法,我相信对于我们这些应试教育出来的人来说,不用排序用O(n)算法是很正常的事,连我都不由自主地认为O(n)算法是这个题的标准答案。我们太习惯于标准答案了,这是我国教育最悲哀的地方。(广义的洗脑就是让你的意识依赖于某个标准答案,然后通过给你标准答案让你不会思考而控制你)

功能性需求分析

试想,如果我们在实际工作中得到这样一个题 我们会怎么做?我一定会分析这个需求,因为我害怕需求未来会改变,今天你叫我找一个第2大的数,明天你找我找一个第4大的数,后天叫我找一个第100大的数,我不搞死了。需求变化是很正常的事。分析完这个需求后,我会很自然地去写找第K大数的算法——难度一下子就增大了。

阅读全文 Read More

好烂啊有点差凑合看看还不错很精彩 (55 人打了分,平均分: 4.44 )
Loading...
一个fork的面试题

一个fork的面试题

前两天有人问了个关于Unix的fork()系统调用的面试题,这个题正好是我大约十年前找工作时某公司问我的一个题,我觉得比较有趣,写篇文章与大家分享一下。这个题是这样的:

题目:请问下面的程序一共输出多少个“-”?

#include <stdio.h>
#include <sys/types.h>
#include <unistd.h>

int main(void)
{
   int i;
   for(i=0; i<2; i++){
      fork();
      printf("-");
   }

   wait(NULL);
   wait(NULL);

   return 0;
}

如果你对fork()的机制比较熟悉的话,这个题并不难,输出应该是6个“-”,但是,实际上这个程序会很tricky地输出8个“-”。

要讲清这个题,我们首先需要知道fork()系统调用的特性,

阅读全文 Read More

好烂啊有点差凑合看看还不错很精彩 (72 人打了分,平均分: 4.67 )
Loading...
给程序员新手的一些建议

给程序员新手的一些建议

前段时间因为实习生计划花了很多时间做了实习生招聘的工作,产生的一些想法,写在这里。

这次招聘过程中,我发现我们在校的学生有下面的这些特点:

1)NB的项目。当说到自己做过的项目时, 我发现他们做的事都是很NB。要么是研究Linux的底层内核,要么是图像识别处理,要么是推荐算法,要么做高性能计算,要么做数据挖掘,要么是移动方面的协议,还有一些很高深的课题我听不太懂的项目。这让我想起当年我在学校里的实习,对比起我用Java Applet 和 HTML做操作系统的教学课件,或是在公司里用Delphi/PowerBuilder做的那些MIS系统。让我觉得有些汗颜。

2)OK的解决问题能力。当问到算法题时,我发现他们的问题解决能力还OK。我一般问1到2个中低难度的算法题和1个基本的面向对象设计的题,都不难。我相信只要在学校里好好学习的人都应该答得出来。无非就是一些基本的算法和基本数据结构操作的问题,和比较基础的面向对象设计的题,说白了就是作业题。可惜的是,只有5%不到的同学能够在不给提示的情况下答出来,70%的人可以在给一定的提示下答出来,15%左右的同学需要提示到几乎给出答案才能答出来,还有10%的同学怎么给提示都答不出来。

3)WTF的编码能力。老实说,对于解算法题,我还是比较可以接受的,因为80%左右的同学在给予提示后都能描述出解题的算法,于是,我让他们把这个算法用他们最熟悉的语言写出来。但结果让我出乎意料,一段在解法很清楚的情况下只需要不到30行代码的小算法题,只有一个人能在10分钟几写完,其它的人基本所有的需要30分钟左右(甚至40分钟),有2、3个人居然写不出来。有一个比较极端的case是——有个同学花了十分钟都写不出从一个整型数组中找到最小的正数的代码。这个事让我觉得很惊讶,难道大家在做项目的时候不编程吗?

对于这种情况,我想给大家以下后一些建议:

阅读全文 Read More

好烂啊有点差凑合看看还不错很精彩 (63 人打了分,平均分: 4.43 )
Loading...
再谈“我是怎么招聘程序员的”(上)

再谈“我是怎么招聘程序员的”(上)

我以前写过一篇“我是怎么招聘程序员的”的文章(在CSDN那里有很多人进行了回复)。今天,我想再谈谈关于招聘和面试这方面的东西,主要是以下这些原因:

所以,我很想把自己的这些新的想法再次写下来的。还是和以前一样,这篇文章同样是献给面试官的。我认为,面试的好坏完全在面试官而不是面试的人。下面是我对“我是怎么招聘程序员的”一文中的一些加强性的观点。(关于一些点评,请参看本文下篇

为了让我的文章有连续性,请允许我重申一下前文的几个重要观点。

  • 只有应聘者真实和自然的表现,才能了解到最真实的东西
  • 重要的不是知识,重要的是其查找知识的能力
  • 重要的不是那个解题的答案,而是解题的思路和方法

操作,知识,经验,能力

我们有很多的面试官似乎分不清,什么是操作能力,什么是知识,什么是经验,什么是能力,这导致了我们的面试官经常错误地对面试者下结论,我认为分不清这些事的人是没有资格做面试官的。所以,我有必要在这里把这个问题先讲清楚。

阅读全文 Read More

好烂啊有点差凑合看看还不错很精彩 (44 人打了分,平均分: 4.41 )
Loading...
再谈“我是怎么招聘程序员的”(下)

再谈“我是怎么招聘程序员的”(下)

<<<再谈“我是怎么招聘程序员的”(上)

在上篇中,我们说到了一些认识人的方法(操作,知识,经验,能力),还有一些面试的方法(算法题,实际生产活动中的挑战),下面我们来说说,面试的风格,还有一些点评。

把应聘者当成你的同事

有些公司的面试官,在面试过程中问你一个算法题,然后等着你解答了,如果你给出一个答案,然后就会问你有没有更好的答案,如果你给出了正确的答案,他们就会问你一个更难的问题,如此循环下去。他们基本上很少给你提示,甚至不停地质问你,挑战你,搞得应聘者很紧张。

另外,有很多问题是没有标准答案的,或者说是,同一个答案的描述方法有多种,很多面试官会觉得你没有回答到他想要的答案,因此表现得有对你不屑,并表现出你不行的样子,并觉得你的能力有问题。真是可笑了。比如我一个朋友在回答什么是异步的问题时,举例说明了异步调用就是不能处理完就返回,并且需要传递一个回调函数给调用方以便完成后回调通知结果。这样的回答并没有错,但是这并不符合面试官心里想要的答案,面试官对此并不满意,进而认为我这个朋友还需要去多读读书。

我相信大多数面试官都会这样干的。我想问问这样的面试官,你们有没有用面试的方式对过你的同事?在你的工作场景中,你会不会用面试的风格和你的同事进行交流和说话?不妨让我们来问我们自己下面几个问题:

  • 你在工作当中遇到难题时你是怎么解决的?你会和人讨论吗?你只用15分钟就能得出最优解吗?
  • 你在工作当中解决难题时是否会有一个人在旁边质问你并给你压力吗?
  • 你在工作当中会为难你的同事吗?会让你的同事紧张吗?你觉得在紧张的状态下能做好工作吗?
  • 你在工作中觉得同事的回答并不是你想要的答案,不是符合你的答案,你会认为你的同事不行吗?
  • 你的成长过程是什么样的?在是压力和天天被人质问的情况下成长的吗?
  • 大家都知道学校里应试教育的弊端,你觉得你的面试是不是一种应试呢?
    (看看这么多的应聘者们都在做各种各样的算法题,这不就是一种应试吗?)

想一想你的日常工作,问自己一下上面这些问题,想一想你自己的成长过程,想一想你和你的同事是怎么相处的,想一想你的日常工作中是什么样的,相信你自己也能得出结论的。

如果你把应聘者当成自己未来的同事,那么你的面试会有下面的收获:

阅读全文 Read More

好烂啊有点差凑合看看还不错很精彩 (29 人打了分,平均分: 4.38 )
Loading...
面试题:火车运煤问题

面试题:火车运煤问题

这个可能是一个比较经典的智力题了,和以前的那个《赛马问题》很相似,其题目如下:

你是山西的一个煤老板,你在矿区开采了有3000吨煤需要运送到市场上去卖,从你的矿区到市场有1000公里,你手里有一列烧煤的火车,这个火车最多只能装1000吨煤,且其能耗比较大——每一公里需要耗一吨煤。请问,作为一个懂编程的煤老板的你,你会怎么运送才能运最多的煤到集市?

这道题一开始看上去好像是无解的,因为你的火车每一公里就要消耗一吨煤,而到目的地有1000公里,而火车最多只能装1000吨媒。如果你的火车可以全部装下,到目的地也会被全部烧光,一丁点也不剩。所以,很多人的第一反应都是觉得这个不太可能。

如果你一开始就觉得不太可能的话,这是很正常的。不过我不知道你还会不会继续思考下去,如果你不想思考下去了,那么我很为你担忧,因为你可能并不是一个不善于思考的人,而是一个畏难的人,还有可能是一个容易放弃的人。这对于你做好 一个需要大量思考的工作的程序员来说可能并不适合。

我一开始也觉得不可能,后来想了一想,想到一个解法可以最多运送500吨煤到市场,方法如下:(希望你先自己想一想再查看这个答案

阅读全文 Read More

好烂啊有点差凑合看看还不错很精彩 (51 人打了分,平均分: 4.45 )
Loading...
又一个有趣的面试题

又一个有趣的面试题

大家还记得前些天的那个火柴棍式的面试题吗?很有趣吧。下面是我今天在StackExchange上看到的一个有趣的面试题。大家不妨一起来思考一下。问题如下——

有两个相同功能代码如下,请在在A,B,C是什么的情况下,请给出三个原因case 1比case 2快,还有三个原因case 2会比case 1要执行的快。(不考虑编译器优化)

for (i=0; i<N; ++i){
    A;
    B;
    C;
}
for (i=0; i<N; ++i){
    A;
}
for (i=0; i<N; ++i){
    B;
}
for (i=0; i<N; ++i){
    C;
}

我的第一个反应是——

阅读全文 Read More

好烂啊有点差凑合看看还不错很精彩 (17 人打了分,平均分: 3.82 )
Loading...
“火柴棍式”程序员面试题

“火柴棍式”程序员面试题

有时候,有些面试题是很是无厘头,这不,又有一个,还记得小时候玩的的“火柴棍游戏”吗,就是移动一根火柴棍改变一个图或字的游戏。程序面试居然也可以这么玩,看看下面这个火柴棍式的程序面试题吧。

下面是一个C程序,其想要输出20个减号,不过,粗心的程序员把代码写错了,你需要把下面的代码修改正确,不过,你只能增加或是修改其中的一个字符,请你给出三种答案。

int n = 20;

for(int i = 0; i < n; i--){
    printf("-");
}

不要以为这题不是很难,我相信你并不那么容易能找到3种方法。我觉得,如果你能在10分钟内找出这三种方法,说明你真的很聪明,而且反应很快。当然,15分钟内也不赖。不过,你要是30分钟内找不到三种方法,当然,不说明你笨了,最多就是你的反应还不够快。嘿嘿。就当是玩玩吧。

下面是我的答案:

//第一种解法:在for循环中给n加一个负号
for(int i = 0; i < -n; i--)

//第二种解法:把 n 初始化成 -20
int n = -20;

//第三种解法:把for循环中的 i 初始化成40
for(int i = 40; i < n; i--)

不过,我要告诉你,以上这些答案都不对(我就知道你会偷看答案的),不过,顺着这些思路走很接近了。呵呵。

下面是正确答案——

阅读全文 Read More

好烂啊有点差凑合看看还不错很精彩 (54 人打了分,平均分: 4.59 )
Loading...