1.
n支队伍比赛，分别编号为0，1，2。。。。n-1，已知它们之间的实力对比关系，存储在一个二维数组w[n][n] 中，w[i][j]
的值代表编号为i，j的队伍中更强的一支 所以w[i][j]=i 或者j，现在给出它们的出场顺序，并存储在数组order[n]中，
比如order[n] = {4,3,5,8,1......}，那么第一轮比赛就是 4对3， 5对8。。。。。。
胜者晋级，败者淘汰，同一轮淘汰的所有队伍排名不再细分，即可以随便排，
下一轮由上一轮的胜者按照顺序，再依次两两比，比如可能是4对5,直至出现第一名
编程实现，给出二维数组w，一维数组order 和 用于输出比赛名次的数组result[n]，求出result
2.题目说的比较花哨，根据我的理解，本质上就是有n个长为m+1的字符串，如果某个字符串的最后m个字符与某个字符串的前m个字符匹配，则两个字符串可以联接，问这n个字符串最多可以连成一个多长的字符串，如果出现循环，则返回错误
百度面试：
3.
用天平（只能比较，不能称重）从一堆小球中找出其中唯一一个较轻的，使用x次天平 最多可以从y个小球中找出较轻的那个，求y与x的关系式
4.有一个很大很大的输入流，大到没有存储器可以将其存储下来，而且只输入一次，如何从这个输入流中随机取得m个记录
5.大量的URL字符串，如何从中去除重复的，优化时间空间复杂度
网易有道笔试：
6. 求一个二叉树中任意两个节点间的最大距离，两个节点的距离的定义是
这两个节点间边的个数，比如某个孩子节点和父节点间的距离是1，和相邻兄弟节点间的距离是2，优化时间空间复杂度
7.求一个有向连通图的割点，割点的定义是，如果除去此节点和与其相关的边，有向图不再连通，描述算法
discussion can be found @:
http://topic.csdn.net/u/20100930/13/9f10c56c-9545-488e-9b53-edffc9b6761d.html
==========
GOOGLE今天晚上的笔试题，刚参加回来.
第一题比较简单，检测同一个平面上的两个矩形是否重合
第二题是，给定一个随机函数，对一个数组进行随机排列，保证所有可能的排列出现的概率相等，也就是n!分之一
第三题就是约瑟夫问题的最优解法~Knuth具体数学上有，不过我忘记了，自己没推导出来，就写了个模拟
discussion can be found @:
http://topic.csdn.net/u/20101018/23/75b6dc53-610f-401e-b8ae-5aebee5cabe8.html
==========
雅虎：
1.对于一个整数矩阵，存在一种运算，对矩阵中任意元素加一时，需要其相邻（上下左右）某一个元素也加一，现给出一正数矩阵，判断其是否能够由一个全零矩阵经过上述运算得到。
2.一个整数数组，长度为n，将其分为m份，使各份的和相等，求m的最大值
比如{3，2，4，3，6} 可以分成{3，2，4，3，6} m=1;
{3,6}{2,4,3} m=2
{3,3}{2,4}{6} m=3 所以m的最大值为3
搜狐：
3.四对括号可以有多少种匹配排列方式？比如两对括号可以有两种：（）（）和（（））
创新工场：
4.求一个数组的最长递减子序列 比如{9，4，3，2，5，4，3，2}的最长递减子序列为{9，5，4，3，2}
微软：
5.一个数组是由一个递减数列左移若干位形成的，比如{4，3，2，1，6，5}是由{6，5，4，3，2，1}左移两位形成的，在这种数组中查找某一个数。
discussion can be found @:
http://topic.csdn.net/u/20101021/14/7fdbcd52-3ee6-42ce-b48e-8fb56c4418da.html
==========
雅虎：
1.对于一个整数矩阵，存在一种运算，对矩阵中任意元素加一时，需要其相邻（上下左右）某一个元素也加一，现给出一正数矩阵，判断其是否能够由一个全零矩阵经过上述运算得到。
2.一个整数数组，长度为n，将其分为m份，使各份的和相等，求m的最大值
比如{3，2，4，3，6} 可以分成{3，2，4，3，6} m=1;
{3,6}{2,4,3} m=2
{3,3}{2,4}{6} m=3 所以m的最大值为3
搜狐：
3.四对括号可以有多少种匹配排列方式？比如两对括号可以有两种：（）（）和（（））
创新工场：
4.求一个数组的最长递减子序列 比如{9，4，3，2，5，4，3，2}的最长递减子序列为{9，5，4，3，2}
微软：
5.一个数组是由一个递减数列左移若干位形成的，比如{4，3，2，1，6，5}是由{6，5，4，3，2，1}左移两位形成的，在这种数组中查找某一个数。
discussion can be found @:
http://topic.csdn.net/u/20101021/14/7fdbcd52-3ee6-42ce-b48e-8fb56c4418da.html
No comments:
Post a Comment