C++博客-coding everyday

统计数组中未出现和多次出现的值

everyday — Thu, 29 Aug 2013 02:24:00 GMT

#面试题#给定数组A，大小为n，数组元素为1到n的数字，不过有的数字出现了多次，有的数字没有出现。请给出算法和程序，统计哪些数字没有出现，哪些数字出现了多少次。能够在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<int, 10> arr = {2, 1, 4, 3, 5, 6, 5, 6, 5, 6};
42     array_stat<10> stat(arr);
43     stat();
44     return 0;
45 }

源代码

everyday 2013-08-29 10:24 发表评论

可怜的小老鼠

everyday — Fri, 02 Aug 2013 09:26:00 GMT

#面试思考题#可怜的小老鼠：有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

everyday 2013-08-02 17:26 发表评论

第n杯水

everyday — Thu, 01 Aug 2013 05:43:00 GMT

摘要: 一座金字塔，从上到下，第一层有一个杯子、第二层有两个杯子，依次类推。每个杯子的容量为C升，从塔顶倒下L升水，当1号杯子满了之后，会等量溢出到2号和3号杯子。当2号和3号满了，2号溢出到4号和5号，3号溢出到5号和6号，注意5号接受来自两个杯子的水。依次类推。给定C和L，请问，第n杯里有多少水。阅读全文

everyday 2013-08-01 13:43 发表评论

面试题：熟悉的陌生人

everyday — Fri, 19 Jul 2013 01:52:00 GMT

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

题目乍一看，感觉像是图连通的问题。细细品了下，貌似不是滴。阅读全文

everyday 2013-07-19 09:52 发表评论

算法题：一个不能少

everyday — Thu, 18 Jul 2013 02:14:00 GMT

摘要: #面试编程题#一个不能少：有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中。阅读全文

everyday 2013-07-18 10:14 发表评论

杂谈 - 面试问算法题

everyday — Wed, 17 Jul 2013 01:13:00 GMT

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

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

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

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

everyday 2013-07-17 09:13 发表评论

括号匹配问题

everyday — Sat, 13 Jul 2013 09:20:00 GMT

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

有没有稍微好点的算法呢？介绍个时间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 }

everyday 2013-07-13 17:20 发表评论

Magic Index

everyday — Fri, 12 Jul 2013 06:25:00 GMT

#面试编程题#给定一个数组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 }

everyday 2013-07-12 14:25 发表评论

单链表的快速排序

everyday — Fri, 12 Jul 2013 05:41:00 GMT

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

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

我的算法是，用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 }

代码

everyday 2013-07-12 13:41 发表评论

蓄水池抽样

everyday — Wed, 03 Jul 2013 01:29:00 GMT

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

经典面试题：蓄水池抽样

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

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

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

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

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

everyday 2013-07-03 09:29 发表评论