1、反转一个链表。循环算法。
List reverse(List l) {
if(!l) return l;
list cur = l.next;
list pre = l;
list tmp;
pre.next = null;
while ( cur ) {
tmp = cur;
cur = cur.next;
tmp.next = pre
pre = tmp;
}
return tmp;
}
2、反转一个链表。递归算法。
List resverse(list l) {
if(!l || !l.next) return l;
List n = reverse(l.next);
l.next.next = l;
l.next=null;
}
return n;
}
3、广度优先遍历二叉树。
void BST(Tree t) {
Queue q = new Queue();
q.enque(t);
Tree t = q.deque();
while(t) {
System.out.println(t.value);
q.enque(t.left);
q.enque(t.right);
t = q.deque();
}
}
class Node {
Tree t;
Node next;
}
class Queue {
Node head;
Node tail;
public void enque(Tree t){
Node n = new Node();
n.t = t;
if(!tail){
tail = head = n;
} else {
tail.next = n;
tail = n;
}
}
public Tree deque() {
if (!head) {
return null;
} else {
Node n = head;
head = head.next;
return n.t;
}
}
4、输出一个字符串所有排列。注意有重复字符。
char[] p;
void perm(char s[], int i, int n){
int j;
char temp;
for(j=0;j<n;++j){
if(j!=0 && s[j]==s[j-1]);
elseif(s[j]!='@'){
p[i]=s[j];
s[j]='@';
if(i==n-1){
p[n]='\0';
printf("%s", p);
}else{
perm(s,i+1,n);
}
s[j]=p[i];
}
}
}
void main() {
char s[N];
sort(s);
perm(s,0,strlen(s));
}
5、输入一个字符串,输出长型整数。
long atol(char *str){
char *p = str;
long l=1;m=0;
if (*p=='-') {
l=-1;
++p;
}
while(isDigit(*p)){
m = m*10 + p;
++p;
}
if(!p) return m*l;
else return error;
}
6、判断一个链表是否有循环。
int isLoop(List l) {
if ( ! l) return - 1 ;
List s = l.next;
while (s && s != l) {
s = s.next;
}
if ( ! s) return - 1 ;
else reutrn 1 ;
}
int isLoop(List l){
if(!l) return 0;
p=l.next;
wihle(p!=l&&p!=null) {
l.next=l;
l=p;p=p.next;
}
if(p=l) return 1;
return 0;
}
实际上,在我的面试过程中,还问到了不破坏结构的其他算法。
我的答案是从链表头开始遍历,如果节点next指针指向自身,则循环存在;否则将next指针指向自身,遍历下一个节点。直至next指针为空,此时链表无循环。
http://en.wikipedia.org/wiki/Floyd's_cycle-finding_algorithm
http://ostermiller.org/find_loop_singly_linked_list.html
http://www.cnblogs.com/wqguan/archive/2006/06/20/
不是随便两个步长不同的指针都会在循环链表上相遇。一个充分条件是,两个遍历指针步长相差1。最好是1,2这两个步长,这样就可以进而求出循环的位置和链表的大小。
7、反转一个字符串。
void reverse( char * str) {
char tmp;
int len;
len = strlen(str);
for ( int i = 0 ;i < len / 2 ; ++ i) {
tmp = char [i];
str[i] = str[len - i - 1 ];
str[len - i - 1 ] = tmp;
}
}
8、实现strstr函数。
int strstr(char[] str, char[] par){
int i=0;
int j=0;
while(str[i] && str[j]){
if(str[i]==par[j]){
++i;
++j;
}else{
i=i-j+1;
j=0;
}
}
if(!str[j]) return i-strlen(par);
else return -1;
}
9、实现strcmp函数。
int strcmp(char* str1, char* str2){
while(*str1 && *str2 && *str1==*str2){
++str1;
++str2;
}
return *str1-*str2;
}
10、求整形中二进制1的位数
求一个整形中1的位数。
int f( int x) {
int n = 0 ;
while (x) {
++ n;
x &= x - 1 ;
}
return n;
}
11、汉诺塔问题。
void tower(n,x,y,z){
if(n==1) move(x,z);
else {
tower(n-1, x,z,y);
move(x,z);
tower(n-1, y,x,z);
}
}
12、汉诺塔最小步数
三柱汉诺塔最小步数。
int f3(n) {
if (f3[n]) return f3[n];
else {
if (n == 1 ) {
f3[n] = 1 ;
return 1 ;
}
f3[n] = 2 * f3(n - 1 ) + 1 ;
return f3[n];
}
}
四柱汉诺塔最小步数。
int f4(n){
if(f4[n]==0){
if(n==1) {
f4[1]==1;
return 1;
}
min=2*f4(1)+f3(n-1);
for(int i=2;i<n;++i){
u=2*f4(i)+f3(n-i);
if(u<min) min=u;
}
f4[n]=min;
return min;
} else return f4[n];
}
13、在一个链表中删除另一个链表中的元素。
void delete(List m, List n) {
if(!m || !n) return;
List pre = new List();
pre.next=m;
List a=m, b=n,head=pre;
while(a && b){
if(a.value < b.value) {
a=a.next;
pre=pre.next;
}else if(a.value > b.value){
b=b.next;
}else{
a=a.next;
pre.next=a;
}
}
m=head.next;
}
14、一个数组,下标从0到n,元素为从0到n的整数。判断其中是否有重复元素。
int hasDuplicate(int[] a, int n){
for(int i=0;i<n;++i){
while(a[i]!=i && a[i]!=-1){
if(a[a[i]]==-1) return 1;
a[i]=a[a[i]];
a[a[i]]=-1;
}
if(a[i]==i) {a[i]=-1;}
}
return 0;
}
15、判断一颗二叉树是否平衡。
int isB(Tree t){
if(!t) return 0;
int left=isB(t.left);
int right=isB(t.right);
if( left >=0 && right >=0 && left - right <= 1 || left -right >=-1)
return (left<right)? (right +1) : (left + 1);
else return -1;
}
16、返回一颗二叉树的深度。
int depth(Tree t){
if(!t) return 0;
else {
int a=depth(t.right);
int b=depth(t.left);
return (a>b)?(a+1):(b+1);
}
}
17、两个链表,一升一降。合并为一个升序链表。
List merge(List a, List d) {
List a1 = reverse(d);
List p = q = new List();
while ( a && a1 ) {
if (a.value < a1.value) {
p.next = a;
a = a.next;
} else {
p.next = a1;
a1 = a1.next;
}
p = p.next;
}
if (a) p.next = a;
elseif(a1) p.next = a1;
return q.next;
}
链表逆序本来就是O(N),所以这道题再烂的做法也不会超过O(N)。我觉得先逆序再归并不会比设计一个个巧妙的方法一次组成目标链表慢多少的
18、将长型转换为字符串。
char* ltoa(long l){
char[N] str;
int i=1,n=1;
while(!(l/i<10)){i*=10;++n}
char* str=(char*)malloc(n*sizeof(char));
int j=0;
while(l){
str[j++]=l/i;
l=l%i;
i/=10;
}
return str;
}
19、用一个数据结构实现
if (x == 0) y = a;
else y = b;
j[] = {a,b};
y=j[x];
20、在双向链表中删除指定元素。
void del(List head, List node){
List pre=new List();
pre.next = head;
List cur = head;
while(cur && cur!=node){
cur=cur.next;
pre=pre.next;
}
if(!cur) return;
List post = cur.next;
pre.next=cur.next;
post.last=cur.last;
return;
}
21、不重复地输出升序数组中的元素。
void outputUnique( char [] str, int n) {
if (n <= 0 ) return ;
elseif(n == 1 ) putchar(str[ 0 ]);
else {
int i = 0 ,j = 1 ;
putchar(str[ 0 ]);
while (j < n) {
if (str[j] !== str[i]) {
putchar(str[j]);
i = j;
}
++ j;
}
}
}
22、面试过程中我还遇到了下面几题:
1、如何删除链表的倒数第m的元素?我的方法是先用pre指针从链表头开始步进m,新建pst节点next指针指向头节点,cur指针指向头节点,然后pre,cur,post三个指针一起步进,当pre指向链表结尾的时候cur指向倒数第m个元素,最后利用pst指针删除cur指向元素。
2、如何判断一个字符串是对称的?如a,aa,aba。设置头尾指针同时向中间比较靠齐直至相遇。
3、如何利用2函数找出一个字符串中的所有对称子串?以子串头指针和尾指针为循环变量设置两个嵌套的循环以找出所有子串,对每个子串应用2函数。
分享到:
相关推荐
微软面试100题(含参考答案)
微软以往的面试题,属于技术层次的问题,需要对编程有一定的了解。
微软2012年的面试解析与答案,很详细。
包括华为 微软 面试试题和C语言的基本知识,涉及面向对象的程序设计
C语言面试题大汇总之微软亚洲技术中心面试题,欢迎下载
程序员C/C++面试题汇总 Intel面试题 微软面试题 Cisco思科面试题 华为面试题C/C++笔试题 慧通面试题
1.进程和线程的差别。 线程是指进程内的一个执行单元,也是进程内的可调度实体. 与进程的区别: (1)调度:线程作为调度和分配的基本单位,进程作为拥有资源的基本单位 (2)并发性:不仅进程之间可以并发执行,同一个...
互联网行业面试笔试真题资料BAT谷歌微软等笔试面试真题复习资料合集200MB: 2015创新工场校招研发笔试题.pdf 2015小米校招技术类笔试题.pdf 360校园招聘2015届技术类笔试题.pdf 4399游戏2015校园招聘游戏开发类笔试题...
微软亚洲技术中心的面试题,希望对面试的同学有帮助,欢迎大家下载。
一些微软经典面试题及丛之中看到的思路,方法
一些微软编程技术的面试心得,内有一些编程题
微软面试题库 930题 leetcode 2020年6月29日 (上) 最新下载的题目列表,包含频率难度等关键信息
微软面试题库 930题 leetcode 2020年6月29日 (下) 最新题目,包含出现频率难度等关键信息
微软的技术支持工程师的笔试题目,一份是语言测试,一份是技术测试,都是英文的。
体会程序之美。 讲述微软的面试经历 例如 编一个程序控制cpu的利用率在百分之五十 很有意思的一些程序
6、C语言面试题大汇总之微软亚洲技术中心面试题.txt 7、c语言面试题及答案_1.txt 8、面试题.htm 9、求职笔试面试大全.htm 10、如何回答十个最棘手的面试问题.htm 11、英语面试常见问题.htm 12、英语面试问答.htm ...
微软亚洲技术支持中心面试题目、微创笔试题目(微创,微软在中国的合资公司)、Intel笔试面试题目、IBM笔试题目、阿尔卡特(中国)的面试题目、Google、 戴尔、Sony笔试题、华为笔试题、大唐电信、网通笔试题、中软...
总结的c++面试试题,非常全面,并且大部分都有解答,希望对找工作的朋友有用,或者小型企业人事主管等非计算机专业面试出题有用 英华达: 1.限制变量的作用域 ... 微软亚洲技术中心的面试题 慧通面试题
6、C语言面试题大汇总之微软亚洲技术中心面试题.txt 7、c语言面试题及答案_1.txt 8、面试题.htm 9、求职笔试面试大全.htm 10、如何回答十个最棘手的面试问题.htm 11、英语面试常见问题.htm 12、英语面试问答.htm 13...
包括了微软所以的技术题、智力题、以及微软面试过程