链表问题总结

九月 16th, 2011 by klose | No Comments | Filed in 求职技术

链表是否有环的解决方案: 链表在面试中出现的频率很高,有的比较正常,考链表的常规操作,主要看基本功是否扎实,有些就比较难,难在思维的改变和是否能够想到对应的点。这里出现的是其中一个题目,我称之为有环链表问题。也就是从判断一个单链表是否存在循环而扩展衍生的问题。下面来看问题如何解决。 首先来看最基本的这个问题:如何判断一个单链表是否存在循环,链表数目未知。算法不能破坏链表。 这里我们可以想到有三种解决的方法。 第一种方法,将所有的遍历过的节点用某个结构存储起来,然后每遍历一个节点,都在这个结构中查找是否遍历过,如果找到有重复,则说明该链表存在循环;如果直到遍历结束,则说明链表不存在循环。 这个结构我们可以使用hash来做,hash中存储的值为节点的内存地址,这样查找的操作所需时间为O(1),遍历操作需要O(

面试智力题(不断更新,鼠标选中即可查看答案)

九月 9th, 2011 by klose | No Comments | Filed in 求职技术

这部分的内容取自  http://blog.sina.com.cn/s/blog_604d011e0100ws85.html 1、考虑一个双人游戏。游戏在一个圆桌上进行。每个游戏者都有足够多的硬币。他们需要在桌子上轮流放置硬币,每次必需且只能放置一枚硬币,要求硬币完全置 于桌面内(不能有一部分悬在桌子外面),并且不能与原来放过的硬币重叠。谁没有地方放置新的硬币,谁就输了。游戏的先行者还是后行者有必胜策略?这种策略 是什么? 答案:先行者在桌子中心放置一枚硬币,以后的硬币总是放在与后行者刚才放的地方相对称的位置。这样,只要后行者能放,先行者一定也有地方放。先行者必胜。   2、一个矩形蛋糕,蛋糕内部有一块矩形的空洞。只用一刀,如何将蛋糕切成大小相等的两块? 答案:注意到平分矩形面积的线都经过矩形的中心。过大矩形和空心矩形各自的中心画一条线,这条线

智力题其实是数学题(不断更新,欢迎网友分享)

九月 2nd, 2011 by klose | No Comments | Filed in 求职技术

1、卡塔兰数 卡塔兰数是组合数学中一个常在各种计数问题中出现的数列。由以比利时的数学家欧仁·查理·卡塔兰 (1814–1894)命名。 卡塔兰数的一般项公式为 前几项为 (OEIS中的数列A000108): 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452, … 性质 Cn的另一个表达形式为 所以,Cn是一个自然数;这一点在先前的通项公式中并不显而易见。这个表达形式也是André对前一公式证明的基础。(见下文的第二个证明。) 卡塔兰数满足以下递推关系 它也满足 这提供了一个更快速的方法来计算卡塔兰数。 卡塔兰数的渐近增长为 它的含义是左式除以右式的商趋向于1当

Java并发编程总结—Hadoop核心源码实例解读

五月 26th, 2011 by klose | No Comments | Filed in mapreduce, 互联网应用, 求职技术, 编程点滴

程序设计需要同步(synchronization),原因: 1)复杂的功能要求的需要使用多线程编程,线程之间存在读写共享变量。 2)读写共享变量(shared mutual variable),JVM的内存模型(Memory model: decide when and how changes made by one thread become visuble to others)受到其它因素干扰。 3)对共享变量的操作非原子性。例如 i++;就不是原子操作,它分为两部分,(1) 读i (2) i+1写入内存。如果i是线程A和线程B共享的变量,线程A在操作(1)之后,线程调度器调度调度线程B执行i++,因此两个线程在变量i产生了不一致。注意,volatile修饰符是线程操作之前更新数据,但是,上面的问题显然不是更新数据就能解决的。 4)增加互斥区(mutual exclusion)会降低执行效率,但是这是实现数据安全、功能强大的多线程编程最为重要的部分。 5)线程之间需要

Tags: , , ,

数组top K的数

五月 25th, 2011 by klose | No Comments | Filed in 求职技术, 编程点滴

给定数组,求top K的数。 算法思路: 使用快排插入排序的做法,在每次迭代求得数组第一个元素需要插入的位置m, 1)如果m恰好为k或者k-1,则停止迭代,当前数组的前k个位置的数即是前K大的数。 2)如果m < k-1, 那么只需继续对于(m+1,length)进行迭代即可。 3)如果m > k, 继续(l, m-1)迭代。 代码献上: #include <stdio.h> #include <stdlib.h> #include <unistd.h> void getRand(int* data, int length) { int i; srand((unsigned int) getpid()); //generate the array using rand() for (i = 0; i < length; i++) { data[i] = rand() % 1000; } //print the array printf(“generate the array using rand:\n”); for (i = 0; i < length; i++) { printf(“%d “, data[i]); } } int length;

JobHunting — 随机排序算法求第k大的数O(n)

五月 18th, 2011 by klose | No Comments | Filed in 求职技术

基于快速排序思想的随机排列的数组中找第k小的数 在一组随机排列的数组中找出第k小的,这个元素称为k-th Order Statistic。 能想到的最直观的算法肯定是先把这些数排序然后取第k个,时间复杂度和排序算法相同,可以是Θ(nlgn)。 但它也有平均情况下时间复杂度是Θ(n)的算法,基于快速排序思想。算法: 01  02 int partition(int start, int end) 03 { 04     int i, j, pivot=a[start], temp; 05     i = start; 06     j = end; 07  08     while (i < j) 09     { 10         while (a[i] <= pivot && i < end) i++; 11         while (a[j] >= pivot && j > start) j–; 12         if (i < j) 13    

JobHunting — 二分查找

五月 18th, 2011 by klose | No Comments | Filed in 求职技术, 编程点滴

算法不多说了,相信如果有人读过Jon Bentley 的《Programming Pearls》,就会十分重视这个算法了。记得上大学的时候,写的第一个程序也是这个,:-)。 #include <stdio.h> #include <stdlib.h> typedef int DataType; int length = 10; int data[] = {1, 3, 5, 23, 45, 231, 234, 754, 5632, 12345}; int bS(DataType * d, int length, DataType target) { int left = 0, right = length-1, mid; if    (length <= 0) { return -1; } while (left <= right) { mid = (right + left) >> 1; if (d[mid] > target) { right = mid – 1; } else if (d[mid] == target) { return mid; } else { left = mid + 1; } } return -1; } int main (int argc, char* argv[]) { if (argc != 2) { printf(“Usage:binarySear

Tags: ,