- 浏览: 741445 次
- 性别:
- 来自: 北京
文章分类
最新评论
-
u011487470:
感觉就是知识采集一样,博主能不能整理一下
基于Web的IM简介 -
whxtbest:
whxtbest 写道2里面:如果T本身就是重复的话 比如 ...
关于后缀树的一些理解 -
whxtbest:
2里面:如果T本身就是重复的话 比如S是aaab,T是aa ...
关于后缀树的一些理解 -
刘亮love小雪:
谢谢啦
Java 2D高级绘图 -
bluky999:
收集的资料挺多的 哈哈
基于Web的IM简介
1. 时针分针重合几次
表面上有60个小格,每小格代表一分钟,
时针每分钟走1/12小格,分针每分钟走1小格,从第一次重合到第二次重合分针比时针多走一圈即60小格,所以
60/(1-1/12)=720/11
每隔720/11分才重合一次(而并不是每小时重合一次)
1440里有22个720/11,如果说算上0点和24点,那也是重合23次而已,但我觉得0点应该算到前一天的24点头上,所以每一天循环下来重合22次啊
2. 找出字符串的最长不重复子串,输出长度
建一个256个单元的数组,每一个单元代表一个字符,数组中保存上次该字符上次出现的位置;
依次读入字符串,同时维护数组的值;
如果遇到冲突了,就返回冲突字符中保存的位置,继续第二步。也可以用hashmap保存已经出现的字符和字符的位置
3. 说是有一个文本文件,大约有一万行,每行一个词,要求统计出其中最频繁出
现的前十个词。
先用哈希,统计每个词出现的次数,然后在用在N个数中找出前K大个数的方法找出出现
次数最多的前10个词。
4. 如题3,但是车次文件特别大,没有办法一次读入内存。
1) 直接排序,写文件时,同时写入字符串及其出现
次数。
2) 可以用哈希,比如先根据字符串的第一个字符将字符串换分为多个区域,每个区域的字符串写到一个文件内,然后再用哈希+堆统计每个区域内前10个频率最高的字符串,最后求出所有字符串中前10个频率最高的字符串。
5. 有一个整数n,将n分解成若干个整数之和,问如何分解能使这些数的乘积最大,输出这个乘积m。例如:n=12
(1)分解为1+1+1+…+1,12个1, m=1*1*1……*1=1
(2)分解为2+2+…+2,6个2, m=64
(3)分解为3+3+3+3,4个3, m=81
(4)大于等于4时分解时只能分解为2和3,且2最多两个
f(n) = 3*f(n-3) n>4
f(4) = 2*2
f(3) = 3
f(2) = 2分解为4+4+4,3个4, m=64
6. 求数组n中出现次数超过一半的数
把数组分成[n/2]组,则至少有一组包含重复的数,因为如果无重复数,则最多只有出现次数等于一半的数。算法如下:
k<-n;
while k>3 do
把数组分成[k/2]组;
for i=1 to [k/2] do
if 组内2个数相同,则任取一个数留下;
else 2个数同时扔掉;
k<-剩下的数
if k=3
then 任取2个数进行比较;
if 两个数不同,则2个数都扔掉
else 任取一个数
if k=2 or 1 then 任取一数
7. A文件中最多有n个正整数,而且每个数均小于n,n <=10的七次方。不会出现重复的数。
要求对A文件中的数进行排序,可用内存为1M,磁盘可用空间足够。
不要把任何问题都往很复杂的算法上靠,最直接最简单的解决问题才是工程师应有的素质,
题目给的很有分寸:n个数,都小于n,两两不同,1M=10^6byte=10^7bit的内存,n <10^7
思路:
把1M内存看作是一个长度为10^7的位数组,每一位都初始化为0
从头扫描n个数,如果碰到i,就把位数组的第i个位置置为1,
这样扫描一遍就排好序了
时间复杂度为O(n)
8. 有10亿个杂乱无章的数,怎样最快地求出其中前1000大的数。
1) 建一个1000个数的堆,复杂度为N*(log1000)=10N
2) 1.用每一个BIT标识一个整数的存在与否,这样一个字节可以标识8个整数的存在与否,对于所有32位的整数,需要512Mb,所以开辟一个512Mb的字符数组A,初始全0
2.依次读取每个数n,将A[n>>3]设置为A[n>>3]|(1<<n%8),相当于将每个数的对应位设置为1
3.在A中,从大到小读取1000个值为1的数,就是最大的1000个数了。
这样读文件就只需要1遍,在不考虑内存开销的情况下,应该是速度最快的方法了。
9. 一棵树节点1, 2, 3, ... , n. 怎样实现:
先进行O(n)预处理,然后任给两个节点,用O(1)判断它们的父子关系
dfs一遍,记录每个结点的开始访问时间Si和结束访问时间Ei
对于两个节点i,j,若区间[Si,Ei]包含[Sj,Ej],则i是j的祖先。给每个节点哈夫曼编码也行,但只适合一般的二叉树,而实际问题未必是Binary的,所以编码有局限性
10. 给定一个二叉树,求其中N(N>=2)个节点的最近公共祖先节点。每个节点只有左右孩
子指
针,没有父指针。
后序递归给每个节点打分,每个节点的分数=左分数+右分数+k,如果某孩子是给定节点则+1
最深的得分为N的节点就是所求吧,细节上应该不用递归结束就可以得到这个节点
11. 如何打印如下的螺旋队列:
21 22 。。。。
20 7 8 9 10
19 6 1 2 11
18 5 4 3 12
17 16 15 14 13
#include <stdio.h>
#define max(a,b) ((a)<(b)?(b):(a))
#define abs(a) ((a)>0?(a):-(a))
int foo(int x, int y)
{
int t = max(abs(x), abs(y));
int u = t + t;
int v = u - 1;
v = v * v + u;
if (x == -t)
v += u + t - y;
else if (y == -t)
v += 3 * u + x - t;
else if (y == t )
v += t - x;
else
v += y - t;
return v;
}
int main()
{
int x, y;
for (y=-2;y<=2;y++)
{
for (x=-2;x<=2;x++)
printf("%5d", foo(x, y));
printf("\n");
}
return 0;
}
第 0 层规定为中间的那个 1,第 1 层为 2 到 9,第 2 层为 10 到 25,……好像看出一点名堂来了?注意到 1、9、25、……不就是平方数吗?而且是连续奇数(1、3、5、……)的平方数。这些数还跟层数相关,推算一下就可以知道第 t 层之内一共有 (2t-1)^2 个数,因而第 t 层会从 [(2t-1)^2] + 1 开始继续往外螺旋。给定坐标 (x,y),如何知道该点处于第几层?so easy,层数 t = max(|x|,|y|)。
知道了层数,接下来就好办多了,这时我们就知道所求的那点一定在第 t 层这个圈上,顺着往下数就是了。要注意的就是螺旋队列数值增长方向和坐标轴正方向并不一定相同。我们可以分成四种情况——上、下、左、右——或者——东、南、西、北,分别处于四条边上来分析。
东|右:x == t,队列增长方向和 y 轴一致,正东方向(y = 0)数值为 (2t-1)^2 + t,所以 v = (2t-1)^2 + t + y
南|下:y == t,队列增长方向和 x 轴相反,正南方向(x = 0)数值为 (2t-1)^2 + 3t,所以 v = (2t-1)^2 + 3t - x
西|左:x == -t,队列增长方向和 y 轴相反,正西方向(y = 0)数值为 (2t-1)^2 + 5t,所以 v = (2t-1)^2 + 5t - y
北|上:y == -t,队列增长方向和 x 轴一致,正北方向(x = 0)数值为 (2t-1)^2 + 7t,所以 v = (2t-1)^2 + 7t + x
12. 一个整数,知道位数,如何判断它是否能被3整除,不可以使用除法和模运算
首先 3|2^n+1 仅当 n 为奇数才可能 因为2^n = 3x + (-1)^n;所以该问题就转化为了
找到最后一个为1的位a,看看向前的一个1(b)和这个位的距离,如果为偶数的距离则不能整除,如果是奇数,去除b之后的位继续判断
13. seq=[a,b,...,z,aa,ab,...,az,ba,bb...,bz,...za,zb,...,zz,aaa...],求[a-z]+(从a到z任意字符组成的字符串)s在seq的位置,即排在第几
本质就是26进制。
表面上有60个小格,每小格代表一分钟,
时针每分钟走1/12小格,分针每分钟走1小格,从第一次重合到第二次重合分针比时针多走一圈即60小格,所以
60/(1-1/12)=720/11
每隔720/11分才重合一次(而并不是每小时重合一次)
1440里有22个720/11,如果说算上0点和24点,那也是重合23次而已,但我觉得0点应该算到前一天的24点头上,所以每一天循环下来重合22次啊
2. 找出字符串的最长不重复子串,输出长度
建一个256个单元的数组,每一个单元代表一个字符,数组中保存上次该字符上次出现的位置;
依次读入字符串,同时维护数组的值;
如果遇到冲突了,就返回冲突字符中保存的位置,继续第二步。也可以用hashmap保存已经出现的字符和字符的位置
3. 说是有一个文本文件,大约有一万行,每行一个词,要求统计出其中最频繁出
现的前十个词。
先用哈希,统计每个词出现的次数,然后在用在N个数中找出前K大个数的方法找出出现
次数最多的前10个词。
4. 如题3,但是车次文件特别大,没有办法一次读入内存。
1) 直接排序,写文件时,同时写入字符串及其出现
次数。
2) 可以用哈希,比如先根据字符串的第一个字符将字符串换分为多个区域,每个区域的字符串写到一个文件内,然后再用哈希+堆统计每个区域内前10个频率最高的字符串,最后求出所有字符串中前10个频率最高的字符串。
5. 有一个整数n,将n分解成若干个整数之和,问如何分解能使这些数的乘积最大,输出这个乘积m。例如:n=12
(1)分解为1+1+1+…+1,12个1, m=1*1*1……*1=1
(2)分解为2+2+…+2,6个2, m=64
(3)分解为3+3+3+3,4个3, m=81
(4)大于等于4时分解时只能分解为2和3,且2最多两个
f(n) = 3*f(n-3) n>4
f(4) = 2*2
f(3) = 3
f(2) = 2分解为4+4+4,3个4, m=64
6. 求数组n中出现次数超过一半的数
把数组分成[n/2]组,则至少有一组包含重复的数,因为如果无重复数,则最多只有出现次数等于一半的数。算法如下:
k<-n;
while k>3 do
把数组分成[k/2]组;
for i=1 to [k/2] do
if 组内2个数相同,则任取一个数留下;
else 2个数同时扔掉;
k<-剩下的数
if k=3
then 任取2个数进行比较;
if 两个数不同,则2个数都扔掉
else 任取一个数
if k=2 or 1 then 任取一数
7. A文件中最多有n个正整数,而且每个数均小于n,n <=10的七次方。不会出现重复的数。
要求对A文件中的数进行排序,可用内存为1M,磁盘可用空间足够。
不要把任何问题都往很复杂的算法上靠,最直接最简单的解决问题才是工程师应有的素质,
题目给的很有分寸:n个数,都小于n,两两不同,1M=10^6byte=10^7bit的内存,n <10^7
思路:
把1M内存看作是一个长度为10^7的位数组,每一位都初始化为0
从头扫描n个数,如果碰到i,就把位数组的第i个位置置为1,
这样扫描一遍就排好序了
时间复杂度为O(n)
8. 有10亿个杂乱无章的数,怎样最快地求出其中前1000大的数。
1) 建一个1000个数的堆,复杂度为N*(log1000)=10N
2) 1.用每一个BIT标识一个整数的存在与否,这样一个字节可以标识8个整数的存在与否,对于所有32位的整数,需要512Mb,所以开辟一个512Mb的字符数组A,初始全0
2.依次读取每个数n,将A[n>>3]设置为A[n>>3]|(1<<n%8),相当于将每个数的对应位设置为1
3.在A中,从大到小读取1000个值为1的数,就是最大的1000个数了。
这样读文件就只需要1遍,在不考虑内存开销的情况下,应该是速度最快的方法了。
9. 一棵树节点1, 2, 3, ... , n. 怎样实现:
先进行O(n)预处理,然后任给两个节点,用O(1)判断它们的父子关系
dfs一遍,记录每个结点的开始访问时间Si和结束访问时间Ei
对于两个节点i,j,若区间[Si,Ei]包含[Sj,Ej],则i是j的祖先。给每个节点哈夫曼编码也行,但只适合一般的二叉树,而实际问题未必是Binary的,所以编码有局限性
10. 给定一个二叉树,求其中N(N>=2)个节点的最近公共祖先节点。每个节点只有左右孩
子指
针,没有父指针。
后序递归给每个节点打分,每个节点的分数=左分数+右分数+k,如果某孩子是给定节点则+1
最深的得分为N的节点就是所求吧,细节上应该不用递归结束就可以得到这个节点
11. 如何打印如下的螺旋队列:
21 22 。。。。
20 7 8 9 10
19 6 1 2 11
18 5 4 3 12
17 16 15 14 13
#include <stdio.h>
#define max(a,b) ((a)<(b)?(b):(a))
#define abs(a) ((a)>0?(a):-(a))
int foo(int x, int y)
{
int t = max(abs(x), abs(y));
int u = t + t;
int v = u - 1;
v = v * v + u;
if (x == -t)
v += u + t - y;
else if (y == -t)
v += 3 * u + x - t;
else if (y == t )
v += t - x;
else
v += y - t;
return v;
}
int main()
{
int x, y;
for (y=-2;y<=2;y++)
{
for (x=-2;x<=2;x++)
printf("%5d", foo(x, y));
printf("\n");
}
return 0;
}
第 0 层规定为中间的那个 1,第 1 层为 2 到 9,第 2 层为 10 到 25,……好像看出一点名堂来了?注意到 1、9、25、……不就是平方数吗?而且是连续奇数(1、3、5、……)的平方数。这些数还跟层数相关,推算一下就可以知道第 t 层之内一共有 (2t-1)^2 个数,因而第 t 层会从 [(2t-1)^2] + 1 开始继续往外螺旋。给定坐标 (x,y),如何知道该点处于第几层?so easy,层数 t = max(|x|,|y|)。
知道了层数,接下来就好办多了,这时我们就知道所求的那点一定在第 t 层这个圈上,顺着往下数就是了。要注意的就是螺旋队列数值增长方向和坐标轴正方向并不一定相同。我们可以分成四种情况——上、下、左、右——或者——东、南、西、北,分别处于四条边上来分析。
东|右:x == t,队列增长方向和 y 轴一致,正东方向(y = 0)数值为 (2t-1)^2 + t,所以 v = (2t-1)^2 + t + y
南|下:y == t,队列增长方向和 x 轴相反,正南方向(x = 0)数值为 (2t-1)^2 + 3t,所以 v = (2t-1)^2 + 3t - x
西|左:x == -t,队列增长方向和 y 轴相反,正西方向(y = 0)数值为 (2t-1)^2 + 5t,所以 v = (2t-1)^2 + 5t - y
北|上:y == -t,队列增长方向和 x 轴一致,正北方向(x = 0)数值为 (2t-1)^2 + 7t,所以 v = (2t-1)^2 + 7t + x
12. 一个整数,知道位数,如何判断它是否能被3整除,不可以使用除法和模运算
首先 3|2^n+1 仅当 n 为奇数才可能 因为2^n = 3x + (-1)^n;所以该问题就转化为了
找到最后一个为1的位a,看看向前的一个1(b)和这个位的距离,如果为偶数的距离则不能整除,如果是奇数,去除b之后的位继续判断
13. seq=[a,b,...,z,aa,ab,...,az,ba,bb...,bz,...za,zb,...,zz,aaa...],求[a-z]+(从a到z任意字符组成的字符串)s在seq的位置,即排在第几
本质就是26进制。
发表评论
-
求交集和并集的线性算法
2011-10-24 23:00 5304对于给定的两个集合,使用哈希表可以在线性时间复杂度内得到他们的 ... -
关于后缀树的一些理解
2008-10-01 21:07 9010要理解suffix tree就首先 ... -
词频统计的C++实现
2008-03-10 16:01 3746#include <map> # ... -
Google面试题(九)
2008-02-20 00:13 275325匹马赛跑,5个跑道,怎么以最少的比赛次数来决出最快的3匹, ... -
数据结构面试大全
2008-02-19 12:50 44731.判断链表是否存在环 ... -
Google面试题(七)
2008-02-14 03:35 3037很多Google考生出来,也 ... -
Google面试题(六)
2008-02-14 03:03 6006题目:对现在的Stack(栈)数据结构进行改进,加一个min( ... -
Google面试题(五)
2008-02-14 02:30 2663几星期前,一个朋友接 ... -
Google面试题(四)
2008-02-13 22:07 226126个英文字母从新排序(未知的顺序alphabet),然后用这 ... -
google面试题(三)
2008-02-13 06:22 2499算法题一:Given 1 GB memory, input a ... -
google面试题(二)
2008-02-11 01:43 3484平面上N个点,求一条直线,穿过的点数最多 思路:2点确定一条 ... -
google面试题(一)
2008-02-11 01:27 2484有一个random number generator,是生成真 ... -
数据结构和算法中容易忽略的要点总结[未完待续]
2008-02-10 23:44 14391。递归需要有个递归出口,否则会是infinite的递归 -
矩阵求逆的快速算法
2008-02-10 20:40 3895算法介绍 矩阵求逆在3D ... -
约瑟夫问题
2008-02-10 09:57 1994有n个人围成一圈,顺序编号。从第一个人开始报数,凡报到m的人退 ... -
hash函数学习总结,以及与hashcode()、hashMap的关系
2008-02-10 06:21 7435以前一直觉得hash函数很 ... -
突然发现没真正领悟哈希表
2008-02-10 05:11 2554在一个字符串中找到第 ... -
[微软面试题]请把一个整形数组中重复的数字去掉
2008-02-10 04:08 4353请把一个整形数组a中重复的数字去掉 方法一: for i ... -
Java版堆排序
2008-02-09 23:41 1150/** * author Akalius Kung 2008 ... -
Java版插入排序
2008-02-09 04:40 1471/** * author Akalius Kung 2008 ...
相关推荐
Java面试题集锦6:华为面试题 管理资料.pdfJava面试题集锦6:华为面试题 管理资料.pdfJava面试题集锦6:华为面试题 管理资料.pdfJava面试题集锦6:华为面试题 管理资料.pdfJava面试题集锦6:华为面试题 管理资料.pdf...
吐血总结!50道Python面试题集锦(附答案)
ASP.NET整理过的面试题集锦 ASP.NET整理过的面试题集锦 16个经典面试问题回答思路.txt ASP代码题.doc ASP问答题.doc c#选择题.txt C#面试题.doc Interview.doc SQL面试题.doc 博彦考题.doc 外 企 面 试 技 巧.doc ...
2023 前端二面高频 vue 面试题集锦2023 前端二面高频 vue 面试题集锦2023 前端二面高频 vue 面试题集锦2023 前端二面高频 vue 面试题集锦2023 前端二面高频 vue 面试题集锦2023 前端二面高频 vue 面试题集锦2023 ...
2023 前端二面高频 vue 面试题集锦.docx2023 前端二面高频 vue 面试题集锦.docx2023 前端二面高频 vue 面试题集锦.docx2023 前端二面高频 vue 面试题集锦.docx2023 前端二面高频 vue 面试题集锦.docx2023 前端二面...
spring 面试题集锦spring 面试题集锦spring 面试题集锦spring 面试题集锦spring 面试题集锦spring 面试题集锦
java面试题集锦
J2EE面试题集锦J2EE面试题集锦J2EE面试题集锦J2EE面试题集锦J2EE面试题集锦
Java面试题集锦 Java面试题集锦
全国软件公司面试题集锦 面试题 全国软件公司面试题集锦 面试题
java面试题集锦.rarjava面试题集锦.rarjava面试题集锦.rarjava面试题集锦.rarjava面试题集锦.rarjava面试题集锦.rarjava面试题集锦.rarjava面试题集锦.rarjava面试题集锦.rarjava面试题集锦.rarjava面试题集锦.rar
各大公司常考的嵌入式面试题,史上最全附带答案。
模电数电题面试题集锦模电数电题面试题集锦模电数电题面试题集锦
Oracle企业面试题集锦
java web 笔试面试题集锦 java web 笔试面试题集锦
面试题集锦
面试题集锦,网上摘抄到一些,自己整理一部分,形成文档。看完面试基本能通过一半。
php mysql 面试题集锦
需要面试k8s相关岗位的小朋友来取,增加面试过关率
面试题集锦,java面试题大全,找工作请看