拼多多服务端研发工程师秋招一面

2024-11-05

自我介绍

毕业院校、项目经历、实习工作经历,简单介绍掌握的技能。

算法题

  1. 实现一个前缀树,包括三种操作,插入单词、查询单词、查询前缀,自定义数据结构和方法,其中插入单词只包含小写字母,可以定义一个树结构,度为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;
    };
    

    通过设置一个标志位来判断单词是否存在。

  2. 无重复数字的全排列

    回溯解决,简单

注意事项

pdd的算法题是在他们公司自己的OJ平台上做的,有些题是需要写输入输出的,面试官也会设置测试用例去运行,所以在写代码时一定要注意正确性,平时多用leetcode核心模式刷题的同学,最好还是要掌握一种语言的I/O方法。