久久久久亚洲精品中文字幕,国产日韩久久免费影院,久久久久亚洲精品天堂久久久久久

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

#面试�?/span>#�l�定数组A�Q�大��ؓn�Q�数�l�元素�ؓ1�?/span>n的数字，不过有的数字出现了多�ơ，有的数字没有出现。请�l�出��法和程序，�l�计哪些数字没有出现�Q�哪些数字出��C��多少�ơ。能够在O(n)的时间复杂度�Q?/span>O(1)的空间复杂度要求下完成么�Q?/span>

想了好久�Q�都没能惛_��来算法，我觉得是不是自己走进死胡同了�Q�决定再看一遍题目，�q�一遍果然让我发玎ͼ�原来自己真的理解错了题目的意思，我一开始以��输出多次出现的数字对应的数字�Q�所以一直都�l�不�q�来弯�?/span>

所以有时候面试过�E�中�Q�重新确认题目还是有必要的，有时候面试紧张会误解题目意思，当自己没有思�\的时候，可以��试��认题意�Q�以来可以缓解一下自��q��心情�Q�再者可能面试官会跟你有更多的互动，增加好感�?/span>

��定了题意，��Z��之前的思考，我的��法是这��L��遍历一遍数�l�，�?/span>-2,-1,0来表�C�没有出玎ͼ�出现一�ơ，出现多次�Q�如果当前节点大�?�Q�目标节点�ؓ它对应的��|��当前�|��ؓ-2�Q�若��于0�Q�加一但不要超�q?。算法需要一个递归函数�Q�用来递归处理目标节点一直大�?的情况，��x��处理�q�的�Q�和一个遍历的函数。最�l?即�ؓ多次出现�Q?1出现1�ơ的�Q?2没有出现。因为有2个前提这个算法才有效�Q?～n�Q�只要出现多�ơ和没出现的数字�Q�不需要次数�?/span>

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 }

源代�?/a>

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

可怜的��老鼠

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

#面试思考题#可怜的��老鼠�Q�有11瓉��Q�只有一瓶有毒。喝酒之后，三天会死�Q�只有三天时间。请问至��需要多��只老鼠�Q�可以找�?瓶没有毒的酒。关注微信公众�̎�?#8220;待字��Z��”�Q�了解和讨论参考分析�?br />
http://www.weibo.com/1915548291/A2QpWmhUH

分析�Q?br />

直觉上应该是4只鼠可以扑և�那瓶有毒的。如果要扑և�9瓶没有毒的，肯定不大�?嘛。这个大家能��x��白吗�Q�有人想看分析就回复哦�?P

最多需�?只就够了�Q?宫格。ABC �?ABC�Q�每只鼠负责一横一竖，�q�样每一瓉��臛_��?只喝�q�，除了对角�U�上�Q�如果是对角�U�上只会��M��只，其余都是2只，�?只就能定位到哪一瓶了。额。。不知道�q�有没有更少的，只需�?只或�?只就搞定的？

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

A需要喝的是1�Q?�Q?�Q?�Q?
B需要喝的是2�Q?�Q?�Q?�Q?
C需要喝的是3�Q?�Q?�Q?�Q?

现在可以通过��L��老鼠的情冉|��断出哪一瓶有问题了，对吧�?br />
更新�Q?br />多谢@geagle9�?/a>的提醒，��实存在问题�Q?�?都是A和B歅R��呜呜！�Q�之前的��法错误喽。�?br />
看�v来我�?宫格是走不通了�Q�不知道老罗是不是还走的下去�?br />
其实我一直有个不明白的是�Q�一�?1个瓶子，为啥只要扑և�9个没有毒的就可以了。答案是�?个一�l�，�?�l�，�q�样的话�Q�用3个老鼠能定位到每一�l�，�q�个时候肯定是有一�l�有问题的，但不��是哪一�l�，臛_��能有9瓶是好的。哎呀妈呀。终于弄出来了�?br />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 发表评论

�W�n杯水

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

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

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

面试题：熟悉的陌生�h

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

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

题目乍一看，感觉像是图连通的问题。细�l�品了下�Q�貌��g��是滴�?nbsp; 阅读全文

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

��法题：一个不能少

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

摘要: #面试�~�程�?一个不能少�Q�有k个有序的数组�Q�请扑ֈ�一个最��的数字范围。��得这k个有序数�l�中�Q�每个数�l�都臛_��有一个数字在该范围中。例如：1:{ 4, 10, 15, 24, 26 }�Q?: { 0, 9, 12, 20 }�Q?: { 5, 18, 22, 30 }。所得最��范围�ؓ[20,24]�Q�其中，20�?中，22�?中，24�?中�?nbsp; 阅读全文

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

杂谈 - 面试问算法题

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

前些天，看到很多大牛��?#8220;面试该不该问��法�?#8221;�q�行了大量的讨论和厮杀�Q�作为小�E�序员也��q��看的份。昨天在微博上看到有个网友对一个面试题做的评论�Q?#8220;如果一个�h看过�c�M��解法�Q�能回答出来�Q�一个�h没看�q�回�{�不出来�Q�就能说明回�{�不出来的能力就不如回答出来的吗�Q?#8221;�Ҏ��我表�C��同，��实不能说明回答不出的能力不如看�q�而回�{�出来的人�?/p>

但是如果我是面试官，我肯定会对回�{�出来的人更有好感。�ؓ什么？我没有理�׃��对回�{�出我问题的人欣赏，而对没有回答出来的�h更欣赏嘛�Q�我惌��是�h之常情吧。我刚才说我赞同�Q�确实不能证明回�{�出来的人更有能力，假如他是看过的，但是我想臛_��能说明或�总�更勤奋，��Z��面试做了准备�Q��^时有�q�方面的兴趣�{�，��N��不是吗？

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

通常应聘者被问到一些自己回�{�不了的问题之后�Q�会很紧张（更紧张）�Q�以至于影响发挥�Q�完全体��C��q��实力。其实我倒觉得可以正视自己回�{�不了的问题�Q�这些只不过是所有面试问题中的一��部分，不如坦白的承认这斚w��自己相对较弱�Q�然后引导面试官问一些自己比较擅长的问题�Q�能体现自己的能力（分析问题解决问题�Q�学习能力，�~�码能力…�Q�的方向。当面试官问你一些你不熟悉的问题�Q�坦白说不会�Q?#8220;�q�个斚w��我不太熟�Q�但是相关的�Q?/span>…斚w��Q�我�q�x��比较��x��Q�也�׃��不少旉��Q�有�?/span>…”�Q�前提是�Q�说实话�Q�这个时候如果面试官也了解这斚w��Q�可以深入的问你�q�方面的问题�Q�即侉K��试官不了解这斚w��Q�也会对你有好感�Q�改善对你的看法�?/span>

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

括号匚w��问题

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

�q�个问题很简单，大学学数据结构的时候，讲堆栈一章的时候作为其中一个例子来说的。但是如果面试中被问到这个题�Q�我想用堆栈来做应该不能被接受吧�Q�理由是�I�间和时间的代�h都挺高的�?br />
有没有稍微好点的��法呢？介绍个时间O(n), �I�间O(1)的算法�?br />
既然我们只是要找出括��h��没有匚w��p��了，那我们用一�U�方式记下左括号和右括号的次��C��可以了�Q�例如left_count, right_count。它们的差�ؓ0不就好了�Q�只要不�?�Q�肯定就不匹配了�Q�对吧？更进一步，为啥非要�?个变量呢�Q�一个就够了嘛。遇到左括号++�Q�遇到右括号--�Q�最后�ؓ0卛_��配�?br />

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

#面试�~�程�?�l�定一个数�l�A�Q�其中有一个位�|�被�U�CؓMagic Index�Q�含义是�Q�如果i是Magic Index�Q�则A[i] = i。假设A中的元素递增有序、且不重复，��L��出方法，扑ֈ��q�个Magic Index。当A中允许有重复的元素，该怎么办呢�Q?/div>
�W�一个，不重复，很简单，用二分查扑ְ�OK了。对�?br />

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 }

�W�二个，可重复的�Q�该怎么�?从头到尾��C��边，��d��是可以的嘛�?)。我的想法是�Q�如果a[i]�{�于i的话�Q�找��C��Q�如果大于i的话�Q�让i=a[i]�Q�不然i++�l�箋找。这��h��差的情况才是O(n)
至于��Z��么可以让i=a[i]�Q�原因由于数列是递增的，所以数�l�元素在{i, a[i]}的区间中�Q�肯定不可能存在magic index。这��L��上去是不是蟩跃着前进啊�?)

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

单链表的快速排�?br />单链表的快速排序跟数组的排序原理上一��_��有一个分区（区分�Q�的函数在一个区间中针对某个标杆��D��行区分，比它大的攑֮�后面�Q�比它小的放它前面，�q�返回它的地址�Q�好对它前面的以及它后面的递归�?br />
单链表的快速排序跟数组有个明显的区别，��是指示起始和终止的元素�Q�在一轮之后它们在链表中的位子会发生改变，所以需要返回一个新的�v始的位置�Q�终止的位置�Q?br />我的��法中��L��拿后一个的节点作�ؓ�l�止位置�Q�所以它在链表中的位子其实是不改变的�Q�所以我只修改了起始位置指向新的起始位置卛_��?br />
我的��法是，�?个链表，一个放比它大的一个放比它��的�Q�最后接��h��Q�它的位�|�就是mid�Q�而其实位�|�就是当初�v始的前一个节点在新链表中的next。有�Ҏ��口，��是说a->start->...->nullptr�Q�这一轮传�q�来的是start�Q�那么经�q�这轮的分区之后�Q�start的位�|�肯定改变了�Q�对吧？但是a->next的地址没有改变�Q�即&(a->next)�Q�因为start之前的都会原��不动的攑֜�那里。我觉得用指针的地址来处理是�q�里的关键之处吧�?br />

�q�是一轮partition之前和之后的囄��Q�之后就对于(begin, mid)和（mid->next, end)�q�行快速排序即可�?br />

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. 首先要恭喜下自己�Q�昨天的��法蒙对了，��L��@陈利�?/a> �?a >帖子�?【鼓掌】【鼓掌�?)

�l�典面试题：蓄水池抽�?/h1>

要求从N个元素中随机的抽取k个元素，其中N无法��定�?/p>

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

�q�里的核心问题就�?#8220;随机”�Q�怎么才能是随机的抽取元素呢？我们设想�Q�买彩票的时候，�׃��所有彩��的中奖概率都是一��L��Q�所以我们才�?#8220;随机�?#8221;买彩��。那么要使抽取数据也随机�Q�必��M��每一个数据被抽样出来的概率都一栗��?/p>

哎呀妈呀�Q�这题目一天比一天难啊。目��搞不定啊�?/p>

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

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