河池学院：《数据结构》课程电子教案（PPT教学课件）第1章 绪论 1.1 什么是数据结构 1.2算法及其描述

教材： 《数据结构教程》（用Java描述）李春葆等 清华大学出版社 2020 《数据结构教程学习与实验指导》李春葆等 清华大学出版社 2020 参考书： 《算法》（第4版） R.Sedgewick等 人民邮电出版社 2012（普林 斯顿大学教材）

谷歌二月电面Pass及流程 第一轮 国人姐。就一题。问给一堆单词，找所有词里符合某种条件的， 哪个最多。如果没记错是类似说 给一个n, 那么在有n size相同的prefix里， 哪个之后能写出最多的单词。 我真的可能记错了，但没错的话给个例子：词条是-abcd,abef,abfg, xya, xyb 那先把这些词处理一下，然后n=2 就是说在有2个相同开头字母的 词里，谁最多可能性，答案是 "ab". 这一题一开始没有具体的内容除了一堆单词，全程嘴讲，把整个class写 出来，model问题以及每一个method. 中间讨论很多细节问题，哪些逻辑加在 data pre-process 还是怎么的，所以一道题写完就米有了。我全程 很干净， 有条理的写，也基本 bug free 除有个 syntax 后来发现写错了（Queue 给 写出了.pop() 这种智障玩意），问问题时间都很匆忙，只记得之一，我问刚 去谷歌的时候最喜欢啥，她秒答天天免费吃，顿了一下，情不自禁的开始甜美 的笑了起来

第二轮 烙印。一开始穷紧张。结果哥们发音挺标准就不紧张了。他 问了一道超级简单的题。二叉树的最长路径。但我说思路的期间，他一直 嫌弃。所以没急着写 code 跟他讨论了每种做，这道题虽简单，但有点时 间没写过，所以一开始就说 用一个 global variable 记录，很简单的 递归并更新。他就很嫌弃且鄙视的说 global 肯定是不行的， blah blah 一堆废话理由。 讨论一下我说可以自己装一个 data struct, pass reference value (java). 他又说这也是肯定不行的，blah blah，并且带着不耐 烦的口音。我说那就试着从下面往上返回的时候每个节点自己维护暂时的 最大值吧，听他好像深呼一口气，然后我自己画个图整理好思路才写。很 简单的题却花十五分钟聊天和写好 bug free

Follow up只是换成 n-ary tree，自己model. 一样简单但又开始鸡蛋 里挑骨头，吵很久怎么 model 好，各种 structure 的取舍。主要子节点的信 息，我用 Set 但他一直想叫我用 List。明白他意思有点晚，放弃自己观点会 闲得很愚蠢。他强调 worst case 所以只好辩驳avg case，我说除非有信息 或资料显示这 hash 有相当的 collision 可能性，不然用秒探索孩子存在的 能力 换取一个名义上更好地 Big O 而且孩子之间也没有任何本质上的顺序关 系 并不是 n-ary tree 更好的表现形式，最后甚至说出了 “你想我用 list 吗，你想我就换”，他居然让步了。 诸如此类，边写code变斗嘴也挺累人。最后他还来了一招“嗯你这答案里 有问题，自己看看吧” 浪费 十分钟检查。我说看不出来你讲吧。具体记不清 反正他误解/看错了，跟他解释一顿他明白了，还道个歉（突然觉得自己是否说 话口气有点重）当时以为这交流有点悬。 但根据最后一周之内收到 pass 的结果来看，没跟我计较

Facebook Onsite + addtion电面 1. coding：flatten linked list: a listNode has a next pointer, and data；data could be either a normal data such as int val, or a pointer point to another linked list node 2. coding：implement circular buffer with read & write functions 3. coding：两个整数相除， 不能用除法和取模: 给了一个常用解法，就 是每次double除数，然后用被除数减新的除数，除数大于被除数之后变回最 开始的除数，。；follow up问有没有更优的解法，小哥一直耐心提示， 不过当时有点累了，没有完全答出来；

4. behavior＋project＋coding：coding 题目很简单，validate bst。 5. system design：设计一个memcache，实现读、写和删除操作；用什么 样的data structure，eviction rule是什么，怎样最大程度避免 segmentation，如何handle concurrency。都是基于一个server的情况考虑， 没有问distributed 的infrastructure如何设计。 感觉除了第三轮没有答得太好，其它都还可以，觉得就算需要加面的话应 该也是加面一轮coding；没想到等了两周多之后告之需要加面一轮系统设计来 考察distributed infrastructure相关的能力。 外加额外system design 店面. 并没有问distributed infrastructure相关的问题； 问了用什么样的数据结构存 social graph相关的信息； 然后花了很长时间问了如何在一个server上面处理大量的读写并发，读的 量大于写

Amazon intern 电面 第一题：找missing number，leetcode变形题，从x到y的范围找 missing的数，要求用logn的时间复杂度。之前leetcode刷题tag里都没有提 示这个做法，就没想，面试官要求logn我才想到用binary search，根据中 间点与预期中间点的大小判断在左边还是右边。 第二题：kth smallest element in BST，leetcode原题， 我用迭代 做的，维护了一个stack。 面试官觉得我写的有点快时间还有好多，又问了 递归的方法，我就说了一下思路。然后问了第一个方法的时间复杂度。 还剩十多分钟面试官介绍了自己的工作，又扯了一会儿结束

第1章绪论 1.1什么是数据结构 1.2算法及其描述 提纲 1.3算法分析 CONTENTS 1.4 数据结构的目标 作业 上机实验题

CONTENTS 提纲

用计算机解决一个具体问题的步骤 （1）分析问题，确定数据模型。 （2）设计相应的算法。 （3）编写程序，运行并调试程序直至得到正确的结果

需要从数据入手来分析并得到解决问题的方法 数据是描述客观事物的数、字符以及所有能输入到计算机中并被计算机 程序处理的符号的集合。 数据元素是数据的基本单位（例如，A班中的每个学生记录都是一个数据 元素），也就是说数据元素是组成数据的、有一定意义的基本单位，在计 算机中通常作为整体处理 数据项是具有独立含义的数据最小单位，也称为域或域（例如，A班中每 个数据元素即学生记录是由学号、姓名、性别和班号等数据项组成）。 结构化数据