coding everyday

编程面试题 https://interview.codeplex.com

C++博客 首页 新随笔 联系 聚合 管理
  12 Posts :: 2 Stories :: 7 Comments :: 0 Trackbacks

2013年8月29日 #

#面试题#给定数组A,大小为n,数组元素为1n的数字,不过有的数字出现了多次,有的数字没有出现。请给出算法和程序,统计哪些数字没有出现,哪些数字出现了多少次。能够在O(n)的时间复杂度,O(1)的空间复杂度要求下完成么


想了好久,都没能想出来算法,我觉得是不是自己走进死胡同了,决定再看一遍题目,这一遍果然让我发现,原来自己真的理解错了题目的意思,我一开始以为要输出多次出现的数字对应的数字,所以一直都绕不过来弯。

所以有时候面试过程中,重新确认题目还是有必要的,有时候面试紧张会误解题目意思,当自己没有思路的时候,可以尝试确认题意,以来可以缓解一下自己的心情,再者可能面试官会跟你有更多的互动,增加好感。


确定了题意,基于之前的思考,我的算法是这样的遍历一遍数组,用-2,-1,0来表示没有出现,出现一次,出现多次,如果当前节点大于0,目标节点为它对应的值,当前置为-2,若小于0,加一但不要超过0。算法需要一个递归函数(用来递归处理目标节点一直大于0的情况,即未处理过的)和一个遍历的函数。最终0即为多次出现,-1出现1次的,-2没有出现。因为有2个前提这个算法才有效:1~n;只要出现多次和没出现的数字,不需要次数。

 

 1 #include <iostream>
 2 #include <array>
 3 using namespace std;
 4 
 5 template<int N>
 6 class array_stat {
 7 public:
 8     array_stat(const array<int, N>& arr) : m_arr(arr) {
 9     }
10 
11     void operator()() {
12         for (int i=1; i<=N; i++) {
13             process(i);
14         }
15 
16         for (int i=0; i<N; i++) {
17             if (m_arr[i] == 0)
18                 cout << i+1 << " exists more than once" << endl;
19             else if (m_arr[i] == -2)
20                 cout << i+1 << " doesnt exist" << endl;
21         }
22     }
23 private:
24     array<int, N> m_arr;
25 
26     void process(int i) {
27         if (m_arr[i-1> 0) {
28             int cur = m_arr[i-1];
29             m_arr[i-1= -2;
30             process(cur);
31         }
32         else {
33             m_arr[i-1]++;
34             if (m_arr[i-1> 0)
35                 m_arr[i-1= 0;
36         }
37     }
38 };
39 
40 int main() {
41     array<int10> arr = {2143565656};
42     array_stat<10> stat(arr);
43     stat();
44     return 0;
45 }

源代码
posted @ 2013-08-29 10:24 everyday 阅读(465) | 评论 (0)编辑 收藏

2013年8月2日 #

#面试思考题#可怜的小老鼠:有11瓶酒,只有一瓶有毒。喝酒之后,三天会死,只有三天时间。请问至少需要多少只老鼠,可以找出9瓶没有毒的酒。关注微信公众账号“待字闺中”,了解和讨论参考分析。

http://www.weibo.com/1915548291/A2QpWmhUH

分析:
直觉上应该是4只鼠可以找出那瓶有毒的。如果要找出9瓶没有毒的,肯定不大于4嘛。这个大家能想明白吗?有人想看分析就回复哦。:P

最多需要3只就够了,9宫格。ABC 和 ABC,每只鼠负责一横一竖,这样每一瓶都至少有2只喝过,除了对角线上,如果是对角线上只会死一只,其余都是2只,那2只就能定位到哪一瓶了。额。。不知道还有没有更少的,只需要2只或者1只就搞定的?

  A B C
A 1 2 3
B 4 5 6
C 7 8 9

A需要喝的是1,2,3,4,7
B需要喝的是2,4,5,6,8
C需要喝的是3,6,7,8,9

现在可以通过死掉老鼠的情况推断出哪一瓶有问题了,对吧。

更新:
多谢@geagle9。的提醒,确实存在问题,2和4都是A和B死。呜呜!!之前的算法错误喽。。

看起来我的9宫格是走不通了,不知道老罗是不是还走的下去。

其实我一直有个不明白的是,一共11个瓶子,为啥只要找出9个没有毒的就可以了。答案是要2个一组,分6组,这样的话,用3个老鼠能定位到每一组,这个时候肯定是有一组有问题的,但不管是哪一组,至少能有9瓶是好的。哎呀妈呀。终于弄出来了。
1,2 -> A
3,4 -> B
5,6 -> C
7,8 -> A+B
9,10 -> A+C
11 ->B+C
posted @ 2013-08-02 17:26 everyday 阅读(161) | 评论 (0)编辑 收藏

2013年8月1日 #

     摘要: 一座金字塔,从上到下,第一层有一个杯子、第二层有两个杯子,依次类推。每个杯子的容量为C升,从塔顶倒下L升水,当1号杯子满了之后,会等量溢出到2号和3号杯子。当2号和3号满了,2号溢出到4号和5号,3号溢出到5号和6号,注意5号接受来自两个杯子的水。依次类推。给定C和L,请问,第n杯里有多少水。   阅读全文
posted @ 2013-08-01 13:43 everyday 阅读(172) | 评论 (0)编辑 收藏

2013年7月19日 #

     摘要: #面试题#Facebook用户都是双向的好友,a是b的好友,那么b一定是a的。给定一个用户列表,有些用户是好友,有些不是,请判断,这些用户是否可以划分为两组,每组内的用户,互相都不是好友。如果能,请给出这个划分。比如用户:{1, 2, 3} 好友关系:1-2, 2-3 划分:{1,3} {2}。

题目乍一看,感觉像是图连通的问题。细细品了下,貌似不是滴。  阅读全文
posted @ 2013-07-19 09:52 everyday 阅读(317) | 评论 (0)编辑 收藏

2013年7月18日 #

     摘要: #面试编程题#一 个不能少:有k个有序的数组,请找到一个最小的数字范围。使得这k个有序数组中,每个数组都至少有一个数字在该范围中。例如:1:{ 4, 10, 15, 24, 26 };2: { 0, 9, 12, 20 };3: { 5, 18, 22, 30 }。所得最小范围为[20,24],其中,20在2中,22在3中,24在1中。  阅读全文
posted @ 2013-07-18 10:14 everyday 阅读(181) | 评论 (0)编辑 收藏

2013年7月17日 #

前些天,看到很多大牛就“面试该不该问算法题”进行了大量的讨论和厮杀,作为小程序员也就看看的份。昨天在微博上看到有个网友对一个面试题做的评论,“如果一个人看过类似解法,能回答出来,一个人没看过回答不出来,就能说明回答不出来的能力就不如回答出来的吗?”对此我表示赞同,确实不能说明回答不出的能力不如看过而回答出来的人。

 

但是如果我是面试官,我肯定会对回答出来的人更有好感。为什么?我没有理由不对回答出我问题的人欣赏,而对没有回答出来的人更欣赏嘛,我想这是人之常情吧。我刚才说我赞同,确实不能证明回答出来的人更有能力,假如他是看过的,但是我想至少能说明或许他更勤奋,为了面试做了准备,平时有这方面的兴趣等,难道不是吗?

 

退一步讲,作为面试官为什么要去证明回答不出的人更有实力呢?这不是应该应聘者的事吗?应聘者才需要证明自己更有能力胜任这个工作吧?

 

通常应聘者被问到一些自己回答不了的问题之后,会很紧张(更紧张),以至于影响发挥,完全体现不出自己的实力。其实我倒觉得可以正视自己回答不了的问题,这些只不过是所有面试问题中的一小部分,不如坦白的承认这方面自己相对较弱,然后引导面试官问一些自己比较擅长的问题,能体现自己的能力(分析问题解决问题,学习能力,编码能力)的方向。当面试官问你一些你不熟悉的问题,坦白说不会,“这个方面我不太熟,但是相关的,方面,我平时比较关注,也花了不少时间,有些”(前提是,说实话)这个时候如果面试官也了解这方面,可以深入的问你这方面的问题;即便面试官不了解这方面,也会对你有好感,改善对你的看法。

posted @ 2013-07-17 09:13 everyday 阅读(204) | 评论 (0)编辑 收藏

2013年7月13日 #

这个问题很简单,大学学数据结构的时候,讲堆栈一章的时候作为其中一个例子来说的。但是如果面试中被问到这个题,我想用堆栈来做应该不能被接受吧,理由是空间和时间的代价都挺高的。

有没有稍微好点的算法呢?介绍个时间O(n), 空间O(1)的算法。

既然我们只是要找出括号有没有匹配就行了,那我们用一种方式记下左括号和右括号的次数不就可以了,例如left_count, right_count。它们的差为0不就好了?只要不为0,肯定就不匹配了,对吧?更进一步,为啥非要用2个变量呢,一个就够了嘛。遇到左括号++,遇到右括号--,最后为0即匹配。
 1 bool is_brackets_match(char *const input) {
 2     if (input != nullptr) {
 3         char *p = input;
 4         int count = 0;
 5 
 6         while (*p != '\0') {
 7             if (*p == '(')
 8                 ++count;
 9             else if (*p == ')')
10                 --count;
11 
12             p++;
13         }
14 
15         if (count == 0)
16             return true;
17     }
18     return false;
19 }
posted @ 2013-07-13 17:20 everyday 阅读(478) | 评论 (1)编辑 收藏

2013年7月12日 #

#面试编程题#给定一个数组A,其中有一个位置被称为Magic Index,含义是:如果i是Magic Index,则A[i] = i。假设A中的元素递增有序、且不重复,请给出方法,找到这个Magic Index。当A中允许有重复的元素,该怎么办呢?

第一个,不重复,很简单,用二分查找就OK了。对吧

 1 int find_magic_index2(int *list, int count) {
 2     int low = 0, high = count - 1;
 3     while (high > low) {
 4         int idx = (high + low) / 2;
 5         if (idx == list[idx])
 6             return idx;
 7         else if (list[idx] > idx) {
 8             high = idx - 1;
 9         }
10         else 
11             low = idx + 1;
12     }
13 
14     return -1;
15 }

第二个,可重复的,该怎么办?从头到尾走一边,总归是可以的嘛。:)。我的想法是,如果a[i]等于i的话,找到了;如果大于i的话,让i=a[i],不然i++继续找。这样最差的情况才是O(n)
至于为什么可以让i=a[i],原因由于数列是递增的,所以数组元素在{i, a[i]}的区间中,肯定不可能存在magic index。这样看上去是不是跳跃着前进啊。:)
 1 int find_magic_index (int *list, int count) {
 2     int i=0;
 3     while (i<count) {
 4         if (list[i] == i)
 5             return i;
 6         else if (list[i] > i)
 7             i = list[i];
 8         else
 9             i++;
10     }
11     return -1;
12 }
posted @ 2013-07-12 14:25 everyday 阅读(167) | 评论 (1)编辑 收藏

单链表的快速排序
单链表的快速排序跟数组的排序原理上一致,有一个分区(区分)的函数在一个区间中针对某个标杆值进行区分,比它大的放它后面,比它小的放它前面,并返回它的地址,好对它前面的以及它后面的递归。

单链表的快速排序跟数组有个明显的区别,就是指示起始和终止的元素,在一轮之后它们在链表中的位子会发生改变,所以需要返回一个新的起始的位置(终止的位置)
我的算法中总是拿后一个的节点作为终止位置,所以它在链表中的位子其实是不改变的,所以我只修改了起始位置指向新的起始位置即可。

我的算法是,用2个链表,一个放比它大的一个放比它小的,最后接起来,它的位置就是mid,而其实位置就是当初起始的前一个节点在新链表中的next。有点拗口,就是说a->start->...->nullptr,这一轮传进来的是start,那么经过这轮的分区之后,start的位置肯定改变了,对吧?但是a->next的地址没有改变,即&(a->next),因为start之前的都会原封不动的放在那里。我觉得用指针的地址来处理是这里的关键之处吧。


这是一轮partition之前和之后的图示,之后就对于(begin, mid)和(mid->next, end)进行快速排序即可。

 1 // Problem: sort a singly link list by Quick Sort
 2 node *partition(list &l, node *&begin, node *end = nullptr) {
 3     // if end is the next node, that means it's only one node to sort
 4     if (begin == nullptr || end == begin->next) {
 5         return nullptr;
 6     }
 7 
 8     list small_list, big_list;
 9     node *current = l.root;
10     node *pivot = begin;
11     node **pbegin;          // points to the address of begin
12     node **s_current = &small_list.root, **b_current = &big_list.root;
13 
14     // move previous nodes before 'begin' to small list
15     while (current != begin) {
16         *s_current = current;
17         s_current = &(*s_current)->next;
18         current = current->next;
19     }
20 
21     // pbegin presents the location(address) of begin item, e.g. if (a->next == begin) then pbegin = &a->next;
22     pbegin = s_current;
23 
24     while (begin != end) {
25         if (begin->data < pivot->data) {
26             *s_current = begin;
27             s_current = &(*s_current)->next;
28         }
29         else {
30             *b_current = begin;
31             b_current = &(*b_current)->next;
32         }
33 
34         begin = begin->next;
35     }
36 
37     // pass begin back to quick_sort for next sort action
38     begin = *pbegin;
39 
40     *b_current= end;
41     *s_current = big_list.root;
42     l = small_list;
43     l.print();
44 
45     // current pivot would be the end node for smaller set sorting
46     return big_list.root;
47 }
48 
49 void quick_sort(list &l, node *begin, node *end = nullptr) {
50     if (begin == end) {
51         return;
52     }
53     // mid represents the pivot node which is the next node of the end of the small list
54     node *mid = partition(l, begin, end);
55 
56     if (mid != nullptr){
57         quick_sort(l, begin, mid);
58     }
59 
60     if (mid != nullptr &&
61         mid->next != nullptr) {        
62         quick_sort(l, mid->next, end);
63     }
64 }

代码
posted @ 2013-07-12 13:41 everyday 阅读(1177) | 评论 (0)编辑 收藏

2013年7月3日 #

yeah. 首先要恭喜下自己,昨天的算法蒙对了,请看@陈利人帖子。 【鼓掌】【鼓掌】:)

经典面试题:蓄水池抽样

要求从N个元素中随机的抽取k个元素,其中N无法确定。

这种应用的场景一般是数据流的情况下,由于数据只能被读取一次,而且数据量很大,并不能全部保存,因此数据量N是无法在抽样开始时确定的;但又要保持随机性,于是有了这个问题。所以搜索网站有时候会问这样的问题。

这里的核心问题就是“随机”,怎么才能是随机的抽取元素呢?我们设想,买彩票的时候,由于所有彩票的中奖概率都是一样的,所以我们才是“随机的”买彩票。那么要使抽取数据也随机,必须使每一个数据被抽样出来的概率都一样。


哎呀妈呀,这题目一天比一天难啊。目测搞不定啊。

在班车上简单分析了下,N的值要到最后才知道,从N个里面抽k个元素,要是概率知识没有都还给老师的话,每个元素被抽中的概率是CNk,对不?唔,既然在N知道之前,就要一样概率的抽取k个元素,那我能不能猜想最后的算法其实是跟N无关的呢?不管怎么样先挖个坑再说,目测这个坑不一定能填上。:D

posted @ 2013-07-03 09:29 everyday 阅读(323) | 评论 (1)编辑 收藏

仅列出标题  下一页