自我介绍
毕业院校、项目经历、实习工作经历,简单介绍掌握的技能。
算法题
-
实现一个前缀树,包括三种操作,插入单词、查询单词、查询前缀,自定义数据结构和方法,其中插入单词只包含小写字母,可以定义一个树结构,度为26
struct Node { char c; vector<Node*> next(26); };
q1: 照着这个思路写下去,面试官发现了问题,插入
apple
作为一个单词,同时插入app
这个单词,这apple
的路径包含了app
的路径,按照我的思路写下去,是否存在单词是根据叶子节点是否全部为空判断的,所以查询app
这个单词时会查询不到,面试官让我思考思考。a1: 暴力方法,使用
map
单独存一份单词,查询单词操作时直接从map中查找,但是会造成很大的时间复杂度。面试官给出建议修改数据结构:
struct Node { char c; vector<Node*> next(26); bool isEnd; };
通过设置一个标志位来判断单词是否存在。
-
无重复数字的全排列
回溯解决,简单
注意事项
pdd的算法题是在他们公司自己的OJ平台上做的,有些题是需要写输入输出的,面试官也会设置测试用例去运行,所以在写代码时一定要注意正确性,平时多用leetcode核心模式刷题的同学,最好还是要掌握一种语言的I/O方法。