Yahoo Phone Interview
1.Product of Array Exclude itself
public class Solution {
public int[] productExceptSelf(int[] nums) {
if(nums==null||nums.length==0) return new int[0];
int len = nums.length;
int[] rst = new int[len];
int pdt = 1;
for(int i=0;i<len;i++){
rst[i] = pdt;
pdt *= nums[i];
}
pdt = 1;
for(int i=len-1;i>=0;i--){
rst[i] *= pdt;
pdt *= nums[i];
}
return rst;
}
}
2.然后写了linkedList Loop 那道简单题
public class Solution {
public ListNode detectCycle(ListNode head) {
if(head==null||head.next==null) return null;
ListNode slow = head, fast=head;
while(fast!=null&&fast.next!=null){
slow = slow.next;
fast = fast.next.next;
if(slow==fast) break;
}
if(slow!=fast) return null;
slow = head;
while(slow!=fast){
slow = slow.next;
fast = fast.next;
}
return slow;
}
}
写完之后 又有一道braintesar 的题，给你10个 stone, one is heavior than any other. how to do to use a balance with fewest steps to get this one.
3.如何写quicksort
public class QuickSort{
public void quicksort(int[] nums){
quicksort(nums,0,nums.length-1);
}
public void quicksort(int[] nums, int L, int R){
int idx = partition(nums,L,R);
if(L<idx-1) quicksort(nums,L,idx-1);
if(idx<R) quicksort(nums,idx,R);
}
public int partition(int[] nums, int L, int R){
int mid = nums[L+((R-L)>>1)];
while(L<=R){
while(mid<nums[R]) R--;
while(mid>nums[L]) L++;
if(L<=R) swap(nums,L++,R--);
}
return L;
}
public void swap(int[] nums, int L, int R){
int tmp = nums[L];
nums[L] = nums[R];
nums[R] = tmp;
}
}
4.Fianance Team: symmetric tree Follow up: 不用递归完成
public class SymmetricTree{
//recursive method
public boolean isSymmetric(TreeNode root){
return root == null || isSymmetric(root.left,root.right);
}
public boolean isSymmetric(TreeNode left, TreeNode right){
if(left==null||right==null) return left==right;
return left.val==right.val && isSymmetric(left.left,right.right) && isSymmetric(left.right,right.left);
}
//iterative method
public boolean isSymmetric(TreeNode root) {
if(root==null) return true;
Stack<TreeNode> stk1 = new Stack<>();
Stack<TreeNode> stk2 = new Stack<>();
stk1.push(root);
stk2.push(root);
while(!stk1.empty() && !stk2.empty()){
TreeNode crt1 = stk1.pop();
TreeNode crt2 = stk2.pop();
if(crt1.val!= crt2.val) return false;
if(crt1.left!=null&&crt2.right!=null){
stk1.push(crt1.left);
stk2.push(crt2.right);
}else if((crt1.left==null)^(crt2.right==null)){
return false;
}
if(crt1.right!=null&&crt2.left!=null){
stk1.push(crt1.right);
stk2.push(crt2.left);
}else if((crt1.right==null)^(crt2.left==null)){
return false;
}
}
return true;
}
}
5.Ads Team: top k frequent elements Follow up : 讨论了其他几种数据结构实现的方法。 正好我之前用三种方法做过这道题，所以很顺利。 链接给大家参考 时间剩的比较多就加了一道简单dp： Unique Binary Search Tree
//Unique BST
public class Solution {
public int numTrees(int n) {
int[] DP = new int[n+1];
DP[0] = 1;
for(int i=1;i<=n;i++){
int sum = 0;
for(int j=0;j<=i-1;j++){
sum += DP[j]*DP[i-j-1];
}
DP[i] = sum;
}
return DP[n];
}
}
//Top k frequent elements
//hashmap+heap
public List<Integer> topKFrequent(int[] nums, int k) {
List<Integer> rst = new ArrayList<>();
if(nums.length==0||k<1) return rst;
Map<Integer,Integer> map = new HashMap<>();
for(int num : nums) map.put(num, map.getOrDefault(num,0)+1);
PriorityQueue<Integer> heap = new PriorityQueue<>(k, new Comparator<Integer>(){
public int compare(Integer a, Integer b){
return map.get(a) - map.get(b);
}
});
for(Integer num : map.keySet()){
if(heap.size()<k) heap.offer(num);
else if(map.get(num)>map.get(heap.peek())){
heap.poll();
heap.offer(num);
}
}
while(!heap.isEmpty()) rst.add(heap.poll());
return rst;
}
//hashmap + bucket
public List<Integer> topKFrequent(int[] nums, int k) {
Map<Integer, Integer> map = new HashMap<>();
for(int n: nums){
map.put(n, map.getOrDefault(n,0)+1);
}
// corner case: if there is only one number in nums, we need the bucket has index 1.
List<Integer>[] bucket = new List[nums.length+1];
for(int n:map.keySet()){
int freq = map.get(n);
if(bucket[freq]==null)
bucket[freq] = new LinkedList<>();
bucket[freq].add(n);
}
List<Integer> res = new LinkedList<>();
for(int i=bucket.length-1; i>0 && k>0; --i){
if(bucket[i]!=null){
List<Integer> list = bucket[i];
res.addAll(list);
k-= list.size();
}
}
return res;
}
}
6.上来他先介绍了自己，然后让我也介绍，简单说了一下background，以及介绍了做过的project和internship，然后他逐个问问题，比如project里database怎么连接，Spring的框架模式之类，因为是backend engineer，问了实习中关于java programming的经历，大概10多分钟。
然后半小时开始狂轰滥炸问java基础知识。
- 说说hashmap.
- 说说concurrent hashmap。这个以前没接触过，回答说用hashtable线程安全，他说对，但是concurrent hashmap性能更好，问我如何实现。。。我扯了set不知道对不对，懵逼了都没google一下，蠢得要死
- 说说interface和abstract，以及jre 8的interface跟之前版本的区别，区别你大爷啊
- 说说GC
- 简单说一下final，对象，方法和类.
- Singleton
这时候已经过去40多分钟了，终于开始coding 第一题lc原题，在一个大多数出现过两次的array里找只出现过一次的数字：eg ｛4，5，4，5，3，7，7｝返回3。刚拿到题目兴奋啊，脱口而出easy，用哈希表或者位运算＝ ＝结果可能太兴奋没有演一演，可能被他怀疑做到过Orz。。。。。说好的实(yan)力(ji)呢(hashset,XOR) 第二题，只用加法实现减法乘法以及除法，还简单
7.一个特别客气的国人小哥。 因为面的是安卓组，所以先问了些安卓的知识。 然后笑着说来道简单题吧 Two Sum 我就泪如泉涌。
但接下来follow up 让我确实惊叹了。 int[] 里有重复出现的数字 【1,2,2】sum target = 3 输出【1,2】【1,2】
蒙了好久，又问了好久才终于领悟到
这是个非常奇特的变体，每选一个pair，要消耗其中一个数字的次数。然后输出最多pair。
需要用HashMap统计每个数字出现的次数.
然后遍历int[].
每次pair出现时，要选其中出现次数较大的，使其次数-1.
Two Sum 真是博大精深.
8.感觉十天之前的题都还很难啊，听人说是因为很多人在刷题准备跳槽，这个理由微微无法信服…….
今天中午刚面的，就是问了很多概念，之前的帖子里基本涵盖了，有一些超出的，我也忘了，因人而异也，就是看你描述的时候触发了哪一个关键字…….
然后一道coding，好像之前说的都是String to integer，所以在他敲出Node的时候我以为是一个略难的题，树什么的，结果就是一个链表判断有没有环。
9.面试的题目都很简单，但是范围还挺广的。 一上来先问了数据结构的问题，list和set的区别，从list取元素的时间复杂度，还有就是快排平均和最坏的时间复杂度等等这些基本的数据结构问题。 然后开始问编程语言，我选的java，问了final，继承，代码共享的两种方式，hashmap在java里是如何实现的（这个有点懵）等等。 第三部分是网络知识，先是在浏览器里输入yahoo会发生什么，然后tcp的特点，服务器是如何响应用户请求的，浏览器是如何解析网站response的等等. 终于到了算法部分，很简单的string to interge, 给他说了一大堆corner case，他说先不用考虑这个，写完他问我如果输入中有非法的字符是应该忽略还是报错。 最后是一道智力题，10块石头，一个天平，有一块石头比其他的重，问最少秤几次可以找到这个石头。
10.给一个array，都是正整数，没有重复，问是否存在一个subsequence其和等于target.例如：{1,2,5,6,10,12,17}, target=15. 应该返回true， 因为有{1,2,12}或{5，10}. 应该是跪了,实在没想出什么好的解
11. 一面： 1.给一个BST，按inorder顺序返回一个linkedlist。linkedlist的node的结构要自己写出来。 2.leetcode 316. Remove Duplicate Letters（最后没完全做出来，只是大致说了一些思路吧）
public class Solution {
public String removeDuplicateLetters(String s) {
int[] map = new int[128];
char[] ipt = s.toCharArray();
for(char c : ipt) map[c]++;
Stack<Character> stk = new Stack<>();
for(char c : ipt){
if(stk.search(c)!=-1){
map[c]--;
continue;
}
while(!stk.empty()&&stk.peek()>c&&map[stk.peek()]>0) stk.pop();
stk.push(c);
map[c]--;
}
StringBuilder rst = new StringBuilder();
while(!stk.empty()) rst.append(stk.pop());
return rst.reverse().toString();
}
}
二面： 1.给一个String s="{ name:a, children:[{name:aa, children:[{children:[{name:aaaa}], name:aaa}, {name:aab}]}, {name:ab}]}"; 返回下面这样的树状结构：
a
/ \
aa ab
/ \
aaa aab
/
aaaa
2.输入一个int r, 让你print出来所有满足“x*x + y*y + z*z =r, x,y,z are all positive interger, x>=y>=z”这个条件的x, y, z.
加上三面面经： 1. word breakII 实施代码
public class Solution {
private List<String> rst = new ArrayList<>();
private StringBuilder crt = new StringBuilder();
private boolean[] DP;
public List<String> wordBreak(String s, Set<String> wordDict) {
int len = s.length();
DP = new boolean[len+1];
DP[len] = true;
for(int i=len-1;i>=0;i--){
for(int j=i+1;j<=len;j++){
if(DP[j]&&wordDict.contains(s.substring(i,j))){
DP[i] = true;
break;
}
}
}
backTracking(s,0,wordDict);
return rst;
}
private void backTracking(String s, int idx, Set<String> dict){
if(idx==s.length()){
crt.deleteCharAt(crt.length()-1);
rst.add(crt.toString());
return;
}
for(int i=idx;i<s.length();i++){
String t = s.substring(idx,i+1);
if(DP[i+1]&&dict.contains(t)){
int len = crt.length();
crt.append(t+' ');
backTracking(s,i+1,dict);
crt.setLength(len);
}
}
}
}
2.Given an array of n elements, where each element is at most k away from its target position, devise an algorithm that sorts in O(n log n) time. 简述你用什么方法做。时间复杂度讲讲(keep a 2k heap) 3. LRU思路和他说说
public class LRUCache {
private LinkedNode head,tail;
private int capacity,cnt;
private Map<Integer,LinkedNode> map;
public LRUCache(int capacity) {
this.capacity = capacity;
this.cnt = 0;
head = new LinkedNode(0,0);
tail = new LinkedNode(0,0);
head.next = tail;
tail.prev = head;
map = new HashMap<>();
}
public int get(int key) {
if(!map.containsKey(key)) return -1;
delete(key);
insert(key);
return map.get(key).val;
}
public void set(int key, int value) {
if(map.containsKey(key)){
map.get(key).val = value;
delete(key);
insert(key);
}else{
if(cnt==capacity){
int tobeDeleted = tail.prev.key;
delete(tobeDeleted);
map.remove(tobeDeleted);
cnt--;
}
map.put(key, new LinkedNode(key,value));
insert(key);
cnt++;
}
}
public void insert(int key){
LinkedNode crt = map.get(key);
crt.next = head.next;
crt.next.prev = crt;
head.next = crt;
crt.prev = head;
}
public void delete(int key){
LinkedNode crt = map.get(key);
crt.prev.next = crt.next;
crt.next.prev = crt.prev;
crt.next = null;
crt.prev = null;
}
public class LinkedNode {
int key,val;
LinkedNode prev,next;
public LinkedNode(int key, int val){
this.key = key;
this.val = val;
}
}
}
祝大家都拿到满意的offer！加油！
12.刚刚结束的yahoo电面，趁记得过来给大家通报下： 面试官本来是个中国人，后来有事换了个阿三哥，人很nice，上来介绍下自己的情况，project经历和从中学到什么，估计扯这些时间太长了，没有问更多的基础知识直接code， allen->112-223-444 bryan->232-444-999 ... ... Zach->123-345-789
name->number 有一个无法直接查询的phonebook
public class phonebook{
static Record getReord(int index){
return record;
}
public class Record(){
Static String Name;
Static String Number;
String getName(){
return this.Name;
}
String getNumber(){
return this.Number
}
}
String checkNumber(String name){
//return name's phone number
}
}
大体就是上面的结构，具体一些细节既不太清楚，让你implement最后的checkNumber函数；就是考你java很基本的编程 问了一下时间复杂度，然后问如何提高，我说利用首字母排序过后可以利用binarysearch来进行名字定位，然后他又问这种办法什么时候会出问题(all the people have same inital character)，出问题怎么办，然后继续implement，最后时间到了，code到一半他让直接把思路一说，觉得可行就没让继续了。 最后问了点问题，说hr回来之后会给消息。
题很简单，但是自己前面太紧张，感觉思维卡壳了，基本悬了。。。 唉
13.刚面了yahoo, 三哥英语听的好辛苦；开头问了7分钟的简历上面的project
1.singleton pattern,
改进 a. lazy loading b. multiple threading如何最有效率的synchronized (两层if, 表示想不出来)
https://gist.github.com/brother-fu/fc701b8d0d6980ad914f
public class Singleton {
private static final Object obj;
public static Object getInstance() {
if (obj == null) { //只是创建的时候要synchronized;
synchronized(obj) {
if (obj == null)
obj = new Object();
}
}
}
return obj;
}
2.word break;
3.factory pattern, 解释java encapsulation vs abstraction vs interface
http://www.tutorialspoint.com/java/java_encapsulation.htm
14.之前在linkedin上海投的。9月的Yahoo sunnyvale on-campus： 先聊了简历，由于面试官就是做楼主的方向的东西，对project比较熟悉，因此要求楼主在白板上实现这个project里其中的两个methods。
然后是算法，第一题是LC 384原题 random shuffle 一个array，楼主很快讲完思路，然后写完。
public class Solution {
private int[] nums;
private int[] rst;
private Random rdm;
public Solution(int[] nums) {
this.nums = nums;
this.rst = Arrays.copyOf(nums,nums.length);
this.rdm = new Random();
}
/** Resets the array to its original configuration and return it. */
public int[] reset() {
return rst = Arrays.copyOf(nums,nums.length);
}
/** Returns a random shuffling of the array. */
public int[] shuffle() {
int len = rst.length;
for(int i=0;i<len;i++){
int id = rdm.nextInt(len-i);
int tmp = rst[i];
rst[i] = rst[i+id];
rst[i+id] = tmp;
}
return rst;
}
}
/**
* Your Solution object will be instantiated and called as such:
* Solution obj = new Solution(nums);
* int[] param_1 = obj.reset();
* int[] param_2 = obj.shuffle();
*/
第二题是给定一个Class Line, 里面是{int len, int value}, 代表的是这个object的长度还有这个object的value,
public class Line {
int len;
int value;
}
现在给定一个长度N和一个List<Line> lines, 要求从lines里选出一些line，使得他们的长度之和<=N,同时要求他们的value之和最大，返回选出的line。(Backtracking)
15.网上申请，过了两周通知第一轮电面，是个很nice的中国（？）小哥。开始就是小哥自我介绍，然后过一遍简历，由于楼主有iOS方向的经验，面的组也是iOS组，所以问了一些iOS的东西， 比如MVC，networking用啥API做的，delegation，notification center, cocoa pod，weak vs strong, etc. 然后问了一道算法题，实现一个能O(1)找max值的stack， 用collabedit写。最后问了小哥几个问题就结束了，花了一个小时左右。这轮小哥比较nice，比较想跟人聊天，代码写完会自己写test case然后跟你说每步执行结果啥样， 之前问iOS的问题有个没答上来，还自己写了段代码跟我讲为啥是这样的原理是啥。 一周以后面了第二轮， 也是个亚洲小哥。对比起来没有第一轮那么nice， 但总体还不错， 也是iOS组的小哥。没有自我介绍，就直接对着简历问项目，然后还是一些iOS问题和Objective-C的问题。问完就开始写算法题。跟小哥说了写好了，他就直接问我说还有没有其他问题，问了他一个问题就结束了第二轮，大概一共花了半个小时，好惶恐。。。
// input: 2 integer arrays, A[] B[]
// output: boolean, true if A[] and B[] have eaxctly the same elements
// example" A = [12, 24, 33, 22], B=[33, 22, 24, 12] = > true
(hashmap to recorde element and its frequency)/(Bit manipulation XOR)
16.之前在地里看到有哥们提供自助式内推服务，我就自己试了一下。 上周HR电话问了一些基本情况，约的今天电面。电面的是一个Sr.manager，烙印。
1.对什么工作感兴趣，why yahoo？
2.What is virtual memory, how it works？ Is there any limitation for the size of virtual memory?
3.现在有一些数据，该用什么data structure来存和query，ID+Address, ID是Integer，Address是String,要求data是按照ID sorted。两个methods，一个是getAddress(int ID), 一个是get all IDs. Time complexity
4.现在有一个file，要求返回 last N lines。Assume有一个API read the line one by one.要求是只读文件一遍。
第四题，我说这个好办啊，就像是linked list那样，用两个pointers相隔N，然后返回。他说这样的话，就算读两遍了。后来他提示可以用extra memory。。。好吧，用一个stack or linkedList,都存进去，然后返回前面N个。他说good。
整个是面试没有coding啊，约的是45min，其实就20min结束了。感觉要被黑了。。
17.这次是第二次发帖， 内容是有关yahoo的电面：
在介绍电面内容之前，想补充一下UP主自己上一次电面的follow up。
今天想在此补充一个follow up的问题。UP主在上个帖子中提到过引申的第三点。 其实面试官的follow up问的就是第三点：如何在不用call get function的情况下来去除内存中expired的内容。 因为这是一个follow up的问题，所以只要我说思路就可以了。 我的回答是： 我们可以利用LRU cache的思想来解决这个问题。 我们可以将内存中先加入的
其实这次电面的问题一点都不难，但是问的很详细。 首先上来的是一系列有关Java基础的问题，UP主努力回忆，所问问题如下(都是在Java中)：
1.List 和 set的区别
2.ArrayList 和 LinkedList 的区别
3.How hashmap works？
4.什么是Hash function
5.hashmap 的 contains() 和 put()的时间复杂度
6.如果hashcode相同的视乎如何处理
HashMap的工作原理 HashMap基于hashing原理，我们通过put()和get()方法储存和获取对象。当我们将键值对传递给put()方法时，它调用键对象的hashCode()方法来计算hashcode，让后找到bucket位置来储存值对象。当获取对象时，通过键对象的equals()方法找到正确的键值对，然后返回值对象。HashMap使用链表来解决碰撞问题，当发生碰撞了，对象将会储存在链表的下一个节点中。 HashMap在每个链表节点中储存键值对对象。
当两个不同的键对象的hashcode相同时会发生什么？ 它们会储存在同一个bucket位置的链表中。键对象的equals()方法用来找到键值对
7.Class 和 interface 的区别
8.inheritance 的特点
9.final， finally， finalize 的用法和区别
10.多线程有关的问题，例：如什么是thread， how do u make threads, 如何避免 collision，how do u make lock
equals and hashcode override problem: 再说一遍，在每个改写了equals()方法的类中，必须要改写hashCode()方法。如果不这样做，就会违反Object.hashCode的通用约定，从而导致该类无法与所有基于hash的集合类结合在一起正常运作，这样的集合类包括HashMap、HashSet和HashTable。
在Java的集合中，判断两个对象是否相等的规则是：
1)判断两个对象的hashCode是否相等
如果不相等，认为两个对象也不相等，完毕
如果相等，转入2)
（这一点只是为了提高存储效率而要求的，其实理论上没有也可以，但如果没有，实际使用时效率会大大降低，所以我们这里将其做为必需的。后面会重点讲到这个问题。）
2)判断两个对象用equals运算是否相等
如果不相等，认为两个对象也不相等
如果相等，认为两个对象相等（equals()是判断两个对象是否相等的关键）
public class Book {
private String name;
private String author;
public Book(String name, String author) {
this.name = name;
this.author = author;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Book book = (Book) o;
if (author != null ? !author.equals(book.author) : book.author != null) return false;
if (name != null ? !name.equals(book.name) : book.name != null) return false;
return true;
}
@Override
public int hashCode() {
int result = name != null ? name.hashCode() : 0;
result = 31 * result + (author != null ? author.hashCode() : 0);
return result;
}
}
其实UP主都大概了解，但是由于面试官问的太细，所以很多没答上来。 估计由于前面回答的不够好，所以免得算法题也很简单：题目如下
实现一个convert string to int的function。 那么UP主当时写的如下.
和面试官交流得出来的结论是：只有正整数，木有负数
public int stringToInt(String s) {
//Coner case
if ( s == null || s.length() == 0 ) return -1；
int size = s.length();
int result = 0;
for ( int i = size - 1; i >= 0; i--) {
result += result *10 + s.charAt(i) - '0';
}
return result;
}
算法应该没写错，后面面试官接着问，那你这数字最多能表示多少啊？ UP回答2^31 - 1; 估计是对前面UP主回答的基本问题很不满意，面试官又问：那你为什么不用long来表示，那样范围不是很大嘛。。。。。。。UP主实在无言以对，只能以我面试很紧张为由来推脱。。。。。
后来UP回忆这两次面试，得出感悟如下： 大公司的电面貌似都不是很难，但是他们对于基本的算法考的都很灵活。 像UP第一篇帖子中提到的改写hashmap，还有这次的convert string to number， 本身的算法并不难，但是主要考察的是你对数据结构的理解。 如果理解到位，应该很快可以写出。 所以小伙伴们在刷leetcode的时候，也不能疏忽Java基础知识。 尤其是对于EE转CS的同学，本身的基本功是比不上CS科班出身的，所以在刷题之余更要加强对于Java基础知识的掌握。 提前预告一下， UP主在10月6号有triplebyte的onsite。 到时候和大家再来分享题目。。。。
望大家多多支持UP主，给UP点个赞。。。。。 也在此祝大家招工组顺利
18.刚过结束，新鲜面经，DPS组
小哥上来介绍他们组，然后问简历，因为有java/Spring Framework/Maven的经历，详细问了这个 基础知识：
- hashmap和hashtable.
- java里面的GC.
- 操作系统，有log file记录的登录User和登录时间timestamp，找出J.Smith的登录频率，大致说一下怎么做，不用写 code：
- 很nice的warmup，小哥说让我熟悉collabedit。reverse string
- 找出数组里的largest distance，找最大最小值减一下
- 找一个String里最长的不含重复字符的子字符串，原题，问了HashSet和array的优缺点
最后问问题结束。 题目简单感觉还不错，求过求onsite。。。.
19.不得不说的是我觉得雅虎的HR是说话最舒服的。 虽然不景气，但是说话很诚恳，说说公司近况和未来打算什么的。
Yahoo 第一面 一共45min 面试官说话很糊，听不清楚。 刚开始聊简历和自我介绍什么的大概10分钟左右。 然后问了一些技术概念什么的。 coding是要求实现一个event emitter， 实现publish和subscribe两个function。
等结果攒人品ing
20.昨天面了一通领英今天转战雅虎。中午十二点面完，傍晚就收到了现场面试的邀请，看来是真缺人啊。贴面经之前实在忍不住唠嗑一下，虽然很多人已经不再考虑雅虎了，我也只是抱着试一试的态度让一位朋友内推一下，但心里还是多少有点敬佩和惋惜这位昔日的巨头。对于科技公司，20岁往往等价于传统公司的60岁，时代的变化是很多人都无法阻挡的，科技的日新月异很快就会让一大批一时愣神没跟上的公司淡出历史的舞台。记得几年前还在学校的时候，老教授们很感慨雅虎的处境，说它做了很多amazing work，但都没盈利，还有就是Sun公司。Anyway，说正经事了。 正规传统的45分钟面试。面试官是个三姐，是个manager。因为平时听三哥英语习惯了，没啥大的压力。
首先是各种非技术问题，谈项目经验，针对她感兴趣的问题提问，老实说就好。10多分钟结束。
然后是算法题，很经典的问题：给一个英语单词list，将拥有相同字母组合的单词归为一类，然后将最后的分类结果返回。比如：stop, post, eat, tea, tops, apple，结果是三类：stop, post, tops; eat, tea; apple.（；是类别分隔符）。用hashmap就好。key的话我一开始是排序单词来做。follow up是有没有更快的生成key方法：hash算法，26进制或者Java的那个hash算法都行。17分钟时间。
最后又是机器学习问题。情景是这样：假设一个email account肯能被黑了，如何设计出feature set来判断出一个email account是否被黑。16分钟时间。
剩下的是扯问题。问了她的组干啥的。
21.2轮电面 贡献下面经， 没问啥基础知识。。 1轮 ：Caculator, LC 315
public class Solution {
public int calculate(String s) {
int sign = 1;
int num = 0;
int sum = 0;
Stack<Integer> stk = new Stack<>();
for(int i=0;i<s.length();i++){
char c = s.charAt(i);
if(Character.isDigit(c)){
num = num*10 +(int) (c-'0');
}else if(c=='+'||c=='-'){
sum += sign*num;
num = 0;
sign = c=='+' ? 1 : -1;
}else if(c=='('){
stk.push(sum);
stk.push(sign);
sign = 1;
sum = 0;
}else if(c==')'){
sum += sign*num;
sum *= stk.pop();
sum += stk.pop();
sign = 1;
num = 0;
}
}
sum += sign*num;
return sum;
}
}
public class Solution {
public int calculate(String s) {
Stack<Integer> stk = new Stack<>();
char sign = '+';
int num = 0;
for(int i=0;i<s.length();i++){
char c = s.charAt(i);
if(Character.isDigit(c)) num = num*10 + (int)(c -'0');
if(c=='+'||c=='-'||c=='*'||c=='/'||i==s.length()-1){
if(sign=='+') stk.push(num);
if(sign=='-') stk.push(-num);
if(sign=='*') stk.push(stk.pop()*num);
if(sign=='/') stk.push(stk.pop()/num);
sign = c;
num=0;
}
}
num=0;
while(!stk.empty()) num += stk.pop();
return num;
}
}
Key point is sorting copy array, then using hashmap to store their index, then from original order to get their index and insert. When meeting duplicate elements, as using hashmap, they will be on the same index, the last position this element appear, when insert, they are on the same index.
public class Solution {
public List<Integer> countSmaller(int[] nums) {
if(nums==null||nums.length==0) return new ArrayList<>();
int len = nums.length;
int[] sortedNums = Arrays.copyOf(nums,len);
Arrays.sort(sortedNums);
Map<Integer,Integer> map = new HashMap<>();
for(int i=0;i<len;i++) map.put(sortedNums[i],i);
int[] BIT = new int[len+1];
List<Integer> rst = new ArrayList<>();
for(int i=len-1;i>=0;i--){
rst.add(query(BIT,map.get(nums[i])-1));
insert(BIT,map.get(nums[i]),1);
}
Collections.reverse(rst);
return rst;
}
public void insert(int[] BIT, int idx, int val){
idx++;
while(idx<BIT.length){
BIT[idx] += val;
idx += (idx & -idx);
}
}
public int query(int[] BIT, int idx){
idx++;
int sum=0;
while(idx>0){
sum += BIT[idx];
idx -= (idx & -idx);
}
return sum;
}
}
2轮 ：Isomophic, Wildcard matching
public class Solution {
public boolean isIsomorphic(String s, String t) {
Map<Character,Character> map = new HashMap<>();
Set<Character> set = new HashSet<>();
for(int i=0;i<s.length();i++){
char s_c = s.charAt(i);
char t_c = t.charAt(i);
if(!map.containsKey(s_c)){
map.put(s_c,t_c);
if(!set.add(t_c)) return false;
}else{
if(map.get(s_c)!=t_c) return false;
}
}
return true;
}
}
public class Solution {
public boolean isMatch(String s, String p) {
int len_s = s.length();
int len_p = p.length();
boolean[][] DP = new boolean[len_s+1][len_p+1];
DP[0][0] = true;
for(int i=0;i<len_p;i++){
if(p.charAt(i)=='*') DP[0][i+1] = DP[0][i];
}
for(int i=0;i<len_s;i++){
for(int j=0;j<len_p;j++){
char c_s = s.charAt(i);
char c_p = p.charAt(j);
if(c_s==c_p||c_p=='?'){
DP[i+1][j+1] = DP[i][j];
}else if(c_p=='*'){
DP[i+1][j+1] = DP[i+1][j]||DP[i][j]||DP[i][j+1];
}
}
}
return DP[len_s][len_p];
}
}
public class Solution {
public boolean isMatch(String s, String p) {
int sidx=0,pidx=0;
int star=-1,match=-1;
while(sidx<s.length()){
if(pidx<p.length()&&(p.charAt(pidx)=='?'||p.charAt(pidx)==s.charAt(sidx))){
pidx++;
sidx++;
}else if(pidx<p.length()&&p.charAt(pidx)=='*'){
star = pidx;
match = sidx;
pidx++;
}else if(star!=-1){
pidx = star+1;
sidx = match+1;
match = sidx;
}else{
return false;
}
}
while(pidx<p.length()){
if(p.charAt(pidx++)!='*') return false;
}
return true;
}
}
下周 onsite， 希望RP好点。。
22.1面是个和蔼的国人叔叔，上来先让自我介绍和简历内容，然后问了SVM的principle 是什么 什么是support vector，abstract和interface区别，default的package是什么类，AWS EMR跟普通的Hadoop里的有什么区别（懵逼） 你的project里的hadoop是几分钟一次的?(二次懵逼)，最后代码是 写一个singleton class和 leetcode 216。写singleton时问了是不是必须static。。static是在comile time还是runtime里的。。写backtrackking时还问了跟exaustive method有什么区别。。为什么要new一个放进去。。. 2面也是先自我介绍，问了HMM和一般markov的区别。。让楼主介绍项目。。还没介绍完就打断了说来不及写代码了。。然后出了一道leetcode hard非面经题。。leetcode321。。后来又跟了一道follow up是给你两组数如果全部都用该怎么实现。
public class Solution {
public int[] maxNumber(int[] nums1, int[] nums2, int k) {
int len1 = nums1.length;
int len2 = nums2.length;
int[] rst = new int[k];
for(int i=Math.max(0,k-len2);i<=Math.min(len1,k);i++){
int[] crt1 = findMaxK(nums1,i);
int[] crt2 = findMaxK(nums2,k-i);
int idx1=0, idx2=0,idx=0;
int[] crt = new int[k];
while(idx1<crt1.length||idx2<crt2.length){
crt[idx++] = greater(crt1,crt2,idx1,idx2) ? crt1[idx1++] : crt2[idx2++];
}
if(greater(crt,rst,0,0)) rst = crt;
}
return rst;
}
private int[] findMaxK(int[] nums, int k){
if(k==0) return new int[0];
int[] rst = new int[k];
int len = nums.length;
int idx = 0;
for(int i=0;i<len;i++){
while(idx!=0&&len-i>k-idx&&rst[idx-1]<nums[i]) idx--;
if(idx<k) rst[idx++] = nums[i];
}
return rst;
}
private boolean greater(int[] nums1, int[] nums2, int idx1, int idx2){
while(idx1<nums1.length||idx2<nums2.length){
if(idx1>=nums1.length) return false;
if(idx2>=nums2.length) return true;
if(nums1[idx1]==nums2[idx2]){
idx1++;
idx2++;
continue;
}else{
return nums1[idx1]>nums2[idx2];
}
}
return false;
}
}
最后求大米啊求积分啊。。楼主积分很低好多帖子看不了T T
23.看了地里好多面经，来发一个Yahoo的电面攒攒人品。Yahoo in Sunnyvale。楼主在职跳槽，电面已过，45分钟，问了好多问题。。。每题请按照1.2.3 -> a.b.c -> i, ii, iii 查看。
希望大家好运。
Virtual memory:
What is virtual memory?
What is the limitation of the virtual memory size?
First of all, forget the idea that virtual memory is limited by the size of pointers on your machine.
Virtual memory limits are not the same as addressing space. You can address more virtual memory than is available in your pointer-based address space using paging.
- Virtual memory upper limits are set by the OS: for example, on 32-bit Windows the limit is 16TB, and on 64-bit Windows the limit is 256TB.
- Virtual memory is also physically limited by the available disc space.
Why is 32 bits system memory space limited to 4G?
Why should people use 64 bit system if 32 bit memory space is good enough?
How to write 60G data to 64G memory on 32 bit system with 4G memory space?
If a single process cannot do it, shall I use multiple process?
How shall I know which process I shall turn to when I read/write?
Thread:
What is thread and process? What is the difference? Why is thread called a lightweight process? Where is it lightweight? Why we shall use multi-thread or multi-process? In what case is multi-process better than multi-thread?
TreeMap:
There is an address book with names and address, what is the data structure you shall use if I want to output all names in order? What is the time complexity for a search? What is the worst case?(all the tree node in the same side, like left side, so the complexity goes to O(n)) What is a balanced BST, what is the cost to keep it balanced when insertion?
Save the kth element:
Given a big file, how to read back the kth last line by only reading the file once. Two pointer is equivalent to read it twice. What if I want to save the time for enqueue and dequeue.
Just use a cyclic array, and it shall be fine.
Yahoo Messenger system:
How to implement a Yahoo Messenger system? What shall be used to store values? What shall be stored? How is client talk to the server? Is it directly talk to a data base? How to know if a person is online or not? *
What if push and pull model take too much resource? How to speed up checking if lookup database take too much time? How to avoid update too frequent. How about store it in the memory?
What if your friend is in Europe and you are in Asia?
Are all you guys data on the same server? * If not same server, how to coordinate? If not same server, how to get your friend list and talk to each other?
Design a general BST without Java Generics *
What type should be stored in the BST node? How to compare it? What will happen when you inherit functions from a parent class?
24.周五面的Yahoo Finance 1) reverse string in place 2) Combination sum.只需要输出最终有多少种组合. 相同数字不同顺序视为一样。 另外想请问下大神第二题如果用DP应该怎么写。。。
public class Solution {
public int combinationSum4(int[] nums, int target) {
int[] DP = new int[target+1];
DP[0] = 1;
for(int i=1;i<=target;i++){
for(int num : nums){
if(i-num<0) continue;
DP[i] += DP[i-num];
}
}
return DP[target];
}
}
//same digit different version
public class Solution{
public int comb(int[] nums, int tar){
int[] DP = new int[tar+1];
DP[0] = 1;
Arrays.sort(nums)
for(int num : nums){
for(int i=num;i<=tar;i++){
DP[i] += DP[i-num];
}
}
return DP[tar];
}
}
25.第一次： 国人姐姐：问了简历上面most challenge的project。题目分别是：rotate array find minimum. follow up是有duplicate的情况。 第二道题是：有一个很大的文件，每一行是一个数，怎么排序。我说分成很多小文件，分别排序，然后merge. 然后她就让我写merge k sorted array. 然后问了些时间复杂度。 第二次： 不知为何，有好几个面试官，3个以上，一人问了我一道题，还有人在旁边听。。估计是为了培训面试官吧。 第一道题目很简单，但是题意很复杂，解释半天题目我才明白。就是input是一个字母组，表示树的指向（A->B,A->B->C,…）。返回一个map，分别是每个字母在树中的层次。其实就是每个字母在subarray中的最大index了，遍历一下就好。 input: [,,] output: map:{ A:1 B:2 C:3 E:1 } ———— C | B |\ E A ————————————————————– 注意：如果加一个F input: [,,,] output: map:{ F:1 A:1 1（此处A的index仍为1，不会变成2.。。一开始我绕进去了= =） B:2 3 C:3 4 E:1 2 } ———— C | B |\ E A | F ——————————————————————————- 第二道题就是coin change.
26.邮件后端组 面试1: Java 语法问题: final finally finalize, StringBuffer, StringBuilder. HashMap, LinkedHashMap. Exceptions. First non-duplicate char in a string, with one pass scan.(store the frequency and its first appear position) 面试2: validate 二叉搜索树(in order traverse or divide and conquer), give two unsorted arrays a and b. each entry is sum of a + b. Find the first K sums in ascending order 面试3: 2SUM, OOD咖啡机, 数据库如果query很慢,大概原因, 网路知识. 面试4: OOD 档案系统. OOP概念,多型. 面试5: LRU Cache.
27.9/14收到邮件安排电面，安排到了第二天。9/15面完，9/16号收到onsite通知。但不知道batch onsite是个什么。 面试的题目都很简单，但是范围还挺广的。 一上来先问了数据结构的问题，list和set的区别，从list取元素的时间复杂度，还有就是快排平均和最坏的时间复杂度等等这些基本的数据结构问题。 然后开始问编程语言，我选的java，问了final，继承，代码共享的两种方式，hashmap在java里是如何实现的（这个有点懵）等等。 第三部分是网络知识，先是在浏览器里输入yahoo会发生什么，然后tcp的特点，服务器是如何响应用户请求的，浏览器是如何解析网站response的等等。 终于到了算法部分，很简单的string to interge, 给他说了一大堆corner case，他说先不用考虑这个，写完他问我如果输入中有非法的字符是应该忽略还是报错。 最后是一道智力题，10块石头，一个天平，有一块石头比其他的重，问最少秤几次可以找到这个石头。 总之很简单，希望大家好运，顺便求大米，多谢。
28.没有概念题，两道 Coding： 1、 返回范围 ：输入 int nums, 输出 List() 2.1、gas station 输入：gas station 位置 条件：car 加一次油最多能跑 100，要求停最少次数到终点 (Xn) 输出：停车加油的位置 ArrayList() 2.2、follow up 每个station 有 cost 求使得 cost 最小，返回停车加油次数
29.数字1~16. print出来所有组合：相邻的两个数相加是perfect square Example: 1 3 6 10 15 1,8 2,7,9,16 后来面试官提示规律：根据以下规律建图 1->3, 8, 15 2->7, 14 3->1, 6, 13 4->5, 12 6->3,10 7->2, 9 8->1 9->7, 16 10->15, 6
30.1）一个string set，求anagram，案组输出 2）一个msg stream，每个msg有一个处理好的topic，如何求得过去一个小时的最多的k个topic followup 是大量message如何处理