一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 2818|回复: 13
收起左侧

zillow onsite总结

[复制链接] |试试Instant~ |关注本帖
doudou23231 发表于 2016-3-8 07:21:31 | 显示全部楼层 |阅读模式

2016(1-3月) 码农类 硕士 全职@Zillow - 校园招聘会 - Onsite |Otherfresh grad应届毕业生

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
写点啥回馈地里吧~~从这里收益不少,虽然不知道onsite结果如何,估计挂了?因为只有三轮,但是其中两轮都妥妥的顺利通过无bug,剩下一轮有一题没搞清楚面试官的意思,是关于hash collision的。大家回去看看基本概念,关于啥是linear hashing,quatratic hashing啥的。这里是我搜集的之前地里面试总结,有些leetcode有原题,有些我自己根据要求写的代码。总之不太难,大家加油
有米捧个米场,哈哈

zillow
Median of Two sorted Arrays

Product of Array Except Self

Question: A solution consists of four balls from a set of four different colors. The user tries to guess the solution.
If they guess the right color for the right spot, record it as being in the correct 'Location'. If it's the right color, but the wrong spot, record it as a correct 'Color'. For example: if the solution is 'BGRR' and the user guesses 'RGYY' they have 1 'Location' and 1 'Color'. A correct solution would be 4 'Location' and 0 'Color'.
Bulls and Cows

How would you discover a memory leak in a software product that contains thousands of lines?

You are given an array of integers and a sum. Find all pairs of integers that equal that sum.
Two sum

Factorial Trailing Zeroes

Given a 2^31 x 2^31 tic tac toe board, describe how you would store the state of the game to check if there is a winner.

Maximum Subarray


Find all subsets of a set

Swap nodes in pairs in a linked list

Lowest Common Ancestor of a Binary Search Tree
Lowest Common Ancestor of a Binary Tree
Find the Least Common Ancestor given two nodes of a binary tree. The nodes each have a reference to their parent node and you do not have the root node of the tree
??????????????????????????????????
public Node LCA(node A, node B){
        if(height(A) > height(B)){
                return LCA(B, A);
        }
        node t1 = A;
        node t2 = B;
        while(t1 != t2){
                if(t2.parent == null){
                        if(t1.parent == null){
                                return null;
                        }else{
                                t1 = t1.parent;
                        }
                }else{
                        t2 = t2.parent;
                }
        }
        return t1;
}

private int height(node A){
        int count = 0;
        while(A.parent != null){
                count++;
                A = A.parent;
        }
        return count;
}
. Waral 鍗氬鏈夋洿澶氭枃绔,
class Node {
        int val;
        Node parent;
        Node(int x){
                val = x;
        }
}

Determine if two rectangular are overlapped
//check两个rectangle是否重叠
public class overlapRectangle {
        public static boolean check(Node topLeftA, Node topLeftB, Node bottomRightA, Node bottomRightB){
                //左右关系,用x
                if(bottomRightA.x <= topLeftB.x || bottomRightB.x <= topLeftA.x){
                        return false;
                }
                //上下关系,用y
                if(topLeftA.y <= bottomRightB.y || topLeftB.y <= bottomRightA.y){
                        return false;
                }
                return true;
        }
       
        public static class Node {
                double x;
                double y;
                public Node(double x, double y){
                        this.x = x;
                        this.y = y;
                }
        }
}

First non-repeat character in a given string

Triangle
Pascal's Triangle
Pascal's Triangle II

Implement Trie (Prefix Tree)

Implement a function for blackjack that returns the score of your hand
public int score(Hand hand){
        int score = 0;
        for(Card currentCard : hand){
                switch(currentCard.value){
                        case value.Two:
                                score += 2;
                                break;
                        case value.Three:
                                score += 3;
                                break;
                        case value.Four:
                                score += 4;
                                break;
                        case value.Five:
                                score += 5;
                                break;
                        case value.Six:
                                score += 6;
                                break;
                        case value.Seven:
                                score += 7;
                                break;
                        case value.Eight:
                                score += 8;
                                break;
                        case value.Nine:
                                score += 9;
                                break;
                        case value.Ten:
                        case value.Jack:
                        case value.Queen:
                        case value.King:
                                score += 10;
                                break;
                        case value.Ace:
                                score += 11;
                                break;

                }
        }

        // after evaluating with 11 for each ace, if score has busted,
        //then change each ace value from 11 to 1
        if(score > 21){
                for(Card currentAcecard : hand){
                        if(score < 21){
                                break;
                        }
                        if(currentAcecard.val == value.Ace){
                                score -= 10;
                        }
                }
        }
        return score;
}



Validate Binary Search Tree

Merge Two Sorted Lists
Merge k Sorted Lists

LRU Cache


给你一个graph每一个node都是一个facebook的user,然后找出这个user的两度关系以内所有和他last name一样的人的email address

public List<String> getEmail(Node node){
        List<String> result = new ArrayList<String>();
        Queue<Node> queue = new Queue<Node>();
        queue.add(node);
        int count = 2;
        while(!queue.isEmpty()){
               
                Node curr = queue.poll();
                for(Node neighbor : neighbors){
                        if(neighbor.user.lastname.equals(curr.lastname)){
                                result.add(neighbor.email);
                        }
                        queue.add(neighbor);
                }
                count--;
                if(count == 0){
                        break;
                }
        }
        return result;
}

class Node {
        User user;
        String email;
        List<Node> neighbors;
        public Node (User user, String email){
                this.user = user;
                this.email = email;
        }
}
.鏈枃鍘熷垱鑷1point3acres璁哄潧
class User {
        String firstname;
        String lastname;
        public User(String first, String last){
                fisrtname = first;
                lastname = last;
        }
}

给你一个log file,每一行都有一条记录,包括三个数据:访问时间,user id,访问的page id。然后让你找出访问次数最多的10组3个连续访问page。就是如果user A访问了page 1 2 3,这样 1 2 3 就算被访问了一次。不用考虑时间间隔所以我昨天访问1,今天2,后天3,也能算作连续访问page。我的做法是先用map统计了所有用户的按时间顺序排列好的访问page,然后三个三个加到另一个map里面去count(我用最土的办法 id1_id2_id3 下划线连接),最后用minHeap找出前10个
public int[] maxFrequencyPage(List<Log> logFile){
        int len = logFile.size();
        //userId 对应一个list,每个list是个hashmap<pageId_list : 个数>
        //Map<Integer, List<HasshMap<List<Integer>, Integer>>> user_page = new HashMap<>();

        //Map<Integer, List<List<Integer>>> user_page = new HashMap<>();
        Map<Integer, List<Integer>> user_page = new HashMap<>();
        Map<List<Integer>, Integer> count_map = new HashMap<>();
        //List<PQNode> count_map = new ArrayList<PQNode>();
        //Deque<Integer> deque = new LinkedList<Integer>();
        for(Log info : logFile){
                if(!user_page.containsKey(info.userId)){
                        Deque<Integer> deque = new LinkedList<Integer>();
                        user_page.add(info.userId, deque);
                }

                deque = user_page.get(info.userId);
                if(deque.size() == 3){
                       
                        if(!count_map.containsKey(deque)){
                                count_map.put(new LinkedList<Integer>(deque), 1);
                        }else{
                                count_map.put(new LinkedList<Integer>(deque), count_map.get(deque) + 1);
                        }
                        deque.removeFrist();
                        deque.addLast(info.pageId);
                }else{
                        deque.addLast(info.pageId);
                }
        }


        Collections.sort(count_map, new Comparator<Map.Entry<List<Integer>, Integer>>{
                public int compare(Map.Entry<List<Integer>, Integer> a, Map.Entry<List<Integer>, Integer> b){
                        return (b.getValue()).compareTo(a.getValue);
                }
        });

        int i = 0;
        List<Integer>[] result = new ArrayList<Integer>[10];
        for(Map.Entry<List<Integer>, Integer> entry : count_map){
                        result[i++] = entry.getKey();
                        if(i == 10){
                                break;
                        }
                }
        }
        return result;
}

class Log{
        date time;
        int userId;
        int pageId;
        public Log (date time, int userId, int pageId){
                this.time = time;
                this.userId = userId;
                this.pageId = pageId;
        }
}
.鐣欏璁哄潧-涓浜-涓夊垎鍦
.鐣欏璁哄潧-涓浜-涓夊垎鍦
fibonacci implementation
求那个斐波那契数列, 刚开始就写了简单的递归,然后他说给个index,是让返回这个数列所有斐波那契数的和。 只好在写个函数,把每个斐波那契数算出来,加入到一个arraylist里面,再去扫一遍arraylist加到一起。然后问怎么优化,就把算斐波那契数的函数里面改用DP做

判断一个node 是否是另一个 node 的 child 很简单一个 DFS 搞定
?????????????????????????????

Reverse Integer, 像这样:int reverse(1234), 返回4321

if (ret >= (Integer.MAX_VALUE - num % 10) / 10 && isPositive ||
    ret >= (Integer.MAX_VALUE - num % 10 + 1) / 10 && !isPositive) {
    throws new Exception;
}
I miss the edge case where you should check for max integer input, basically if input is larger then Max integer, the function should throws NumberFormatException

评分

6

查看全部评分

houqingniao 发表于 2016-3-8 09:10:08 | 显示全部楼层
赞lz。预祝offer!!!
回复 支持 反对

使用道具 举报

ningchris 发表于 2016-3-8 09:45:21 | 显示全部楼层
见到CTO就有机会过. from: 1point3acres.com/bbs
没见到就是必挂
当然也有像我这种的 见了CTO依然挂
回复 支持 反对

使用道具 举报

izacuckoo 发表于 2016-3-8 10:37:30 | 显示全部楼层
lz辛苦了 贫农捧个人场
回复 支持 反对

使用道具 举报

brooks 发表于 2016-3-8 11:00:47 | 显示全部楼层
ningchris 发表于 2016-3-8 09:45
见到CTO就有机会过
没见到就是必挂
当然也有像我这种的 见了CTO依然挂

额,我就是没见到CTO过了的
回复 支持 反对

使用道具 举报

brooks 发表于 2016-3-8 11:04:00 | 显示全部楼层
ningchris 发表于 2016-3-8 09:45
见到CTO就有机会过
没见到就是必挂
当然也有像我这种的 见了CTO依然挂

. 1point3acres.com/bbs好像他家bar比较奇怪,就当攒人品好了,其他一切加油
回复 支持 反对

使用道具 举报

zsimath 发表于 2016-3-8 11:09:56 | 显示全部楼层
不一定是四场。 我是三场面试 没见CTO 然后过的。  祝lz好运气。
回复 支持 反对

使用道具 举报

ningchris 发表于 2016-3-8 11:22:30 | 显示全部楼层
brooks 发表于 2016-3-8 11:00
额,我就是没见到CTO过了的
.1point3acres缃
当时还是我的dream company啊
你现在是在那里工作吗?
回复 支持 反对

使用道具 举报

brooks 发表于 2016-3-9 03:21:05 | 显示全部楼层
ningchris 发表于 2016-3-8 11:22
当时还是我的dream company啊
你现在是在那里工作吗?

今年暑假入职。
回复 支持 反对

使用道具 举报

zhangyijun166 发表于 2016-3-21 10:44:57 | 显示全部楼层
brooks 发表于 2016-3-9 03:21
今年暑假入职。

Hello, 你也是summer入职嘛 可以加我微信 zhangyijun166, 加zillow2016群
回复 支持 反对

使用道具 举报

diyutianshi 发表于 2016-3-22 02:24:22 | 显示全部楼层
                感谢分享~~~~~~
回复 支持 反对

使用道具 举报

dou.bupt 发表于 2016-5-3 06:36:11 | 显示全部楼层
log file 的题,最后sort比较奇怪,hashmap sort之后,也不能保证顺序吧。还是用最小堆吧。

user friends 应该用类似tree level order traverse的方法吧

public List<String> getEmail(Node node){
        List<String> result = new ArrayList<String>();
        Queue<Node> queue = new Queue<Node>();
        queue.add(node);
        int count = 2;
        while(!queue.isEmpty()){
               // 每一层
             int size = queue.size();
             for(int i = 0; i< size; i++){. from: 1point3acres.com/bbs
                Node curr = queue.poll();.1point3acres缃
                for(Node neighbor : neighbors){ 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
                        if(neighbor.user.lastname.equals(curr.lastname)){. Waral 鍗氬鏈夋洿澶氭枃绔,
                                result.add(neighbor.email);
                        }. from: 1point3acres.com/bbs
                        queue.add(neighbor);
                }
          }.鏈枃鍘熷垱鑷1point3acres璁哄潧
                count--;
                if(count == 0){
                        break;. 1point3acres.com/bbs
                }
        }-google 1point3acres
        return result;
}

求交流
回复 支持 反对

使用道具 举报

happychenlei 发表于 2016-5-31 00:48:47 | 显示全部楼层
Find the first Common Parent, 感觉下面这方法会更好,原答案一些edge case没有很好地cover:
node* LCA(node* nd1, node* nd2){
.鏈枃鍘熷垱鑷1point3acres璁哄潧
node* cur1 = nd1; . Waral 鍗氬鏈夋洿澶氭枃绔,
node* cur2 = nd2;

// calculate nd1 height
int nd1_height = 0;
while(cur1->parent!=NULL){
nd1_height++;
cur1 = cur1->parent; . from: 1point3acres.com/bbs
} . 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
. 1point3acres.com/bbs
// calculate nd2 height
int nd2_height = 0;
while(cur2->parent!=NULL){
nd2_height++;
cur2 = cur2->parent;
} .鏈枃鍘熷垱鑷1point3acres璁哄潧

int diff = nd1_height - nd2_height;

cur1 = nd1;
cur2 = nd2;

if(diff>0){
while(diff--){
cur1 = cur1->parent;
}
.鐣欏璁哄潧-涓浜-涓夊垎鍦} else{
diff = -diff;
while(diff--){
cur2 = cur2->parent;
}
} .鏈枃鍘熷垱鑷1point3acres璁哄潧

while(1){ . Waral 鍗氬鏈夋洿澶氭枃绔,
if(cur1==NULL || cur2==NULL) break;
if(cur1 == cur2)
return cur1;
cur1 = cur1->parent; . 1point 3acres 璁哄潧
cur2 = cur2->parent;
}
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
return NULL; . 1point3acres.com/bbs
}
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-5 09:01

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表