深信服java日常实习面经

我在学校里面过、工位上面过、会议室面过、酒店面过、家里面过，甚至厕所里也面过。面试时间约的是下午两点，我提前约了会议室。但是巧的是那天正好肚子不舒服，于是只好带着电脑冲进厕所。结果这次厕所直接上了半小时，蹲的我腿都麻了，站都站不起来。厕所还能听到别人的声音，不过当时我带着耳机，没仔细听。就是不知道别人会不会感到奇怪，怎么这个坑位还有人一直说话。不过，这次经历也给了我一个教训：还是要提前准备好。不论是面试题、身体状况还是环境，还得都考虑到位。

约面的时候先是hr打过来一个电话聊了下，说是一轮技术面一轮hr面，得实习到毕业拿到毕业证才能转正，然后一般工作时间9点上班20点下班吧（研发肯定要晚一些）问了下实习为什么离职之类的手撕：不含重复字符的最长子串做的最有挑战或是最难的事情是什么？感觉更看态度吧，不怎么难，毕竟是实习转正......

比较经典的题目,如果之前没写过的可能需要想一番,首先实现缓存最先想到的就是hashmap,O1级别的查找速度很适合做缓存,然后就是要实现lru,参考redis的zset底层实现,zset也是使用了两个数据结构跳表+hashmap,使用跳表实现排序,我们这里也是使用双向链表实现lru功能,每次查询对应数据的时候就将数据移除重新加到头部,也就是更新使用频率,附上代码如下比较经典的题目,如果之前没写过的可能需要想一番,首先实现缓存最先想到的就是hashmap,O1级别的查找速度很适合做缓存,然后就是要实现lru,参考redis的zset底层实现,zset也是使用了两个数据结构跳表+hashmap,使用跳表实现排序,我们这里也是使用双向链表实现lru功能,每次查询对应数据的时候就将数据移除重新加到头部,也就是更新使用频率//通过自定义节点,hashmap,哨兵节点//删除时通过pre和next指针快速删除节点//添加时只操作头尾,通过哨兵节点快速添加节点class LRUCache {private class Node{//保留key,不然在删除尾结点的时候不能返回key让map也删除//而map又不知道尾结点是哪个int key,value;Node pre,next;Node(int key,int value){this.key=key;this.value=value;}Node(int key,int value,Node pre,Node next){this.key=key;this.value=value;this.pre=pre;this.next=next;}}private int capacity;//通过哨兵节点可以快速找到头结点和尾节点private Node dummy;//通过hashmap快速找到节点,通过节点pre指针和next指针快速实现删除private Map<Integer,Node> map=new HashMap();public LRUCache(int capacity) {this.capacity=capacity;//不能dummy=new Node(-1,-1,dummy,dummy)//这样会导致dummy的pre和next为nulldummy=new Node(-1,-1);dummy.pre=dummy;dummy.next=dummy;}public int get(int key) {if(!map.containsKey(key)) return -1;//如果存在,更新使用频率(加到头部)Node node=map.get(key);remove(node);addFirst(node);return node.value;}public void put(int key, int value) {Node node;if(!map.containsKey(key)){while(map.size()>=capacity){int removeKey=removeLast();map.remove(removeKey);}node=new Node(key,value);addFirst(node);}else{//否则更新数值重新加入node=map.get(key);node.value=value;remove(node);addFirst(node);}map.put(key,node);}public void remove(Node node){Node pre=node.pre;Node next=node.next;pre.next=next;next.pre=pre;}public int removeLast(){Node tail=dummy.pre;remove(tail);return tail.key;}public void addFirst(Node node){//通过哨兵结点快速找到头结点Node head=dummy.next;head.pre=node;node.next=head;dummy.next=node;node.pre=dummy;}}

题目1：无序数组找第K大数