面试地点在中关村搜狐大厦,面试的岗位是云计算Java开发 下午两点到了之后打电话,然后被带到一个工作区域的休息区,然后发了一张面试试卷,里面是三道算法题,三选二,然后大约是给了40分钟的时间,期间没有人管,然后我就用手机拍下来整张试卷。
第一道算法题是 给定一链表L,以及值x,对链表进行切分,使得切分后的左半部分全部小于x,右半部分全部大于或等于x,并保证左右部分维持原有部分不变。例如:链表L是1->4->3->2->5->2, x是3 return 1->2->2->4->3->5。左部分是 1->2->2全部小于3,另一部分是4->3->5,全部大于等于3。这道题相对比较简单,设置两个指针p,q,遍历整个链表,首先要确定两边大小的隔离node, 如果root.value >=x, q = root, 则隔离位置在root的前面位置,遍历链表p.next.value找到第一个比x小的节点,找到之后p.next.next = q, p.next = p.next.next, q = p.next,确定位置之后 n = p.next, p.next = p.next.next, n.next = q.next, q.next = n.反之亦然。第二道算法题是 找出未排序数组中出现次数超过三分之一的元素,要求方案的时间复杂度为O(n), 空间复杂度为O(1)。这道题当时没答出来。后来看到了网上的解答。
主要思想是超过三分之一元素最多有两个,设置两个变量计数a,b,在设置两个变量存值va,vb,遍历数组,如果计数变量a为0或者a=该元素,则va=该元素值, a++,如果a>0 b=0 且va !=该元素值, 或者 vb == 该元素, 则vb = 该元素值 b++, 否则 a-- b--.第三道算法题是写出LRU cache,至少包含get(key), set(key, value)。这道题考察的是java编程能力,比较简单笔试之后,就是面试,会问一下java的基本知识,包括集合类,GC机制,class loader等等.
...查看更多