本篇收录了本人亲身经历的各大公司最新Data Structures and Algorithm面试笔试题及解题思路,持续更新,欢迎补充。
1. 给定一个单词a,如果通过交换单词中字母的顺序可以得到另外的单词b,那么定义b是a的兄弟单词,例如单词army和mary互为兄弟单词。现在给定一个字典,用户输入一个单词,如何根据字典找出这个单词有哪些兄弟单词?要求时间和空间效率尽可能的高。【2012年百度实习生招聘笔试题】
思路一:使用trie树。
在字典树的前缀中再存储一个vector结构的容器:
struct word
{
vector<string> brother; // 用于保存每个单词的兄弟单词
word *next[26]; // 字典树中每个节点代表一个字符,并指向下一个字符
};
如上述数据结构所示,字典树的建立是在预处理阶段完成的,首先根据字典中的单词来建立字典树,建立的时候,需要稍微特殊处理一下,就是比如pots、stop和tops互为兄弟单词,那么在字典中按照首字母顺序的话,应该先遇到pots单词,那么我首先对其进行排序,结果是opts,那么字典树中就分别建立4个节点,分别为o->p->t->s,当然这个是不同层次的,在节点s处的vector容器brother中添加单词pots,遇到stop的时候,同样的方法,排序是opts,此时发现这4个节点已经建立了,那么只需要在第四个节点s处的vector容器brother中添加单词stop,tops单词的处理方法是同样的。
这样建立完字典树后,查询兄弟单词的效率就会很高了,比哈希的效率还要高;查到tops的兄弟的单词的时候,首先排序,那么就是opts,然后在字典树中查找opts,在s处将其vector容器brother中的的单词输出就是tops的所有兄弟单词。
思路二:使用hash_map和链表。
首先定义一个key,使得兄弟单词有相同的key,不是兄弟的单词有不同的key。例如,将单词按字母从小到大重新排序后作为其key,比如bad的key为abd,good的key为dgoo。
使用链表将所有兄弟单词串在一起,hash_map的key为单词的key,value为链表的起始地址。
开始时,先遍历字典,将每个单词都按照key加入到对应的链表当中。当需要找兄弟单词时,只需求取这个单词的key,然后到hash_map中找到对应的链表即可。
这样创建hash_map时时间复杂度为O(n),查找兄弟单词时时间复杂度是O(1)。
思路三:同样使用hash_map和链表。
将每一个字母对应一个质数,然后让对应的质数相乘,将得到的值进行hash,这样兄弟单词的值就是一样的了,并且不同单词的质数相乘积肯定不同。
使用链表将所有兄弟单词串在一起,hash_map的key为单词的质数相乘积,value为链表的起始地址。
对于用户输入的单词进行计算,然后查找hash,将链表遍历输出就得到所有兄弟单词。
这样创建hash_map时时间复杂度为O(n),查找兄弟单词时时间复杂度是O(1)。
2. 数组al[0,mid-1]和al[mid,num-1]是各自有序的,对数组al[0,num-1]的两个子有序段进行merge,得到al[0,num-1]整体有序。要求空间复杂度为O(1)。注:al[i]元素是支持'<'运算符的。【2012年百度实习生招聘笔试题】
本题如果没有空间复杂度为O(1)的限制,则比较简单,以下代码就可以搞定:
//两个有序数组的合并函数
public static int[] MergeList(int a[],int b[])
{
int result[];
result = new int[a.length+b.length];
int i=0,j=0,k=0; //i:用于标示a数组 j:用来标示b数组 k:用来标示传入的数组
while(i<a.length && j<b.length)
if(a[i] <= b[j]) {
result[k++] = a[i++];
}else{
result[k++] = b[j++];
}
return result;
}
}
但是有了空间复杂度为O(1)的限制后,就不能新建result数组了。
方案:
1、两个有序段位A和B,A在前,B紧接在A后面,找到A的第一个大于B[0]的数A[i], A[0...i-1]相当于merge后的有效段,在B中找到第一个大于A[i]的数B[j],对数组A[i...j-1]循环右移j-k位,使A[i...j-1]数组的前面部分有序。
2、如此循环merge。
3、循环右移通过先子段反转再整体反转的方式进行,复杂度是O(L), L是需要循环移动的子段的长度。
// 将有序数组a[begin...mid] 和 a[mid+1...end] 进行归并排序
void Merge(int *a , int begin , int end )
{
int i , j , k;
i = begin;
j = 1 + ((begin + end)>>1); //位运算的优先级比较低,外面需要加一个括号,刚开始忘记添加括号,导致错了很多次
while(i <= end && j <= end && i<j)
{
while(i <= end && a[i] < a[j])
i++;
k = j; //暂时保存指针j的位置
while(j <= end && a[j] < a[i])
j++;
if(j > k)
RotateRight(a , i , j-1 , j-k); //数组a[i...j-1]循环右移j-k次
i += (j-k+1); //第一个指针往后移动,因为循环右移后,数组a[i....i+j-k]是有序的
}
}
void Reverse(int *a , int begin , int end ) //反转
{
for(; begin < end; begin++ , end--)
swap(a[begin] , a[end]);
}
void RotateRight(int *a , int begin , int end , int k) //循环右移
{
int len = end - begin + 1; //数组的长度
k %= len;
Reverse(a , begin , end - k);
Reverse(a , end - k + 1 , end);
Reverse(a , begin , end);
}
3. 设计数据结构与算法,要求统计一篇英文文章中的所有单词出现的次数,按照这些单词出现的顺序依次打印它们以及各自出现的次数。【2012年阿里巴巴校招pretest】
思路:先将文章中的所有单词依次读入一个链表中,建立一个hash_map,然后从头遍历链表,若单词不存在于map中,则将该单词作为key,1(出现次数)为value插入map中;若该单词已存在于map中,则只需将其对应的value加1。
最终再遍历一次链表,以每个单词为key在map中找到对应的value,即单词的出现次数,打印输出。
分享到:
相关推荐
【标题】Unity面试笔试集锦,收录了丰富的面试题,涵盖了Unity引擎的使用、数据结构与算法、C#编程语言以及Lua脚本等关键领域的知识。这个资源是为那些准备在游戏开发领域深入发展的专业人士而设计的,尤其适合正在...
本压缩包文件"各软件公司笔试面试题整理"收录了多家知名企业的笔试题目,为准备应聘者提供了宝贵的参考资料。以下是基于这个主题的详细知识点讲解: 1. **Java基础**: - 数据类型:Java有八种基本数据类型,包括...
本文档收录了 21 道 IT 软件开发笔试面试题,涵盖了字符串处理、算法设计、数据结构等多方面的知识点。下面是对每道题目的详细解释和知识点总结: 1. 字符串排列:该题目要求输入一个字符串,输出该字符串中所有...
资料中包含的面试题覆盖了广泛的IT技术和算法知识,例如数据结构、算法设计、编程语言特性等。每一题均附有详细的解答过程,这不仅可以帮助求职者掌握解题技巧,还能促进他们深入理解背后的逻辑和原理。例如,资料中...
本书第1章至第6章分别阐述字符串、数组、树、查找、动态规划、海量数据处理等相关的编程面试题和算法,第7章介绍机器学习的两个算法—K近邻和SVM。 此外,《编程之法:面试和算法心得》每一章都有“举一反三”和...
Java和.NET都是广泛使用的开发平台,其面试题通常会涵盖语法、数据结构、算法、设计模式、框架、并发编程等多个方面,对于求职者来说,熟悉这些题目有助于提升面试成功率。 压缩包内的文件名称列表包括“笔试题答案...
【软件开发笔试收录】这个资料集合包含了众多与软件开发相关的笔试题目,主要涵盖了数据结构、C语言、面试技巧、链表操作、C/C++编程语言、C++面试问题以及网络协议等多个方面,是软件开发者和求职者提升技能、准备...
- 技术面试:准备常见的算法题、设计模式等。 - 行为面试:STAR法则的应用。 3. **常见问题解答** - 为什么选择Java? - 介绍一个你解决过的复杂问题。 通过上述知识点的学习与实践,读者可以系统地提升自己的...
本资源精心收录了多家知名企业(包括奇安信、贝壳找房、小米、游卡、vivo、阿里巴巴、爱奇艺、百度、猿辅导、中兴等)的C++方向笔试题,覆盖从2020年至2022年的秋招和校招题目。这些题目不仅考察了C++的基础知识,如...
- **数据结构**:涉及数组、链表、树等数据结构的应用题。 - **系统设计**:可能考查操作系统、数据库等方面的知识。 #### 四、华为面试经验 本章节收集了求职者分享的华为面试经历,旨在帮助后来者更好地准备面试...
4. **通用知识点**:除了公司特定的题目,IT行业的笔试还可能包含常见的数据结构(如链表、树、图)、算法(排序、搜索)以及计算机网络、操作系统等基础知识。此外,问题解决能力和项目经验也是考核的重点。 5. **...
### 腾讯笔试题合集知识点解析 #### 标题与描述概述 - **标题**:“腾讯笔试题合集” - **描述**:“腾讯历年...此外,熟悉常见的算法和数据结构实现方法,掌握C++语言的高级特性,对于通过腾讯的招聘考试至关重要。
java笔试题算法 , , , , . 如果你发现自己陷入各种新技术、工具包围中,而纠结于该选择...数据结构与算法/leetcode/lintcode题解 - 借助开源项目,学习软件开发 - 前端工作面试问题 - 前端工作面试题解答 - 深入Java
这份资料包含了大量的Java源代码示例,覆盖了各种类型的应用场景,如数据结构实现、网络编程等,对于提高编程能力和解决实际问题有很大帮助。 #### 十八、经典Java编程100例 该资料精选了100个经典编程案例,每个...