10月28,K神开讲数据科学:AB Test/实验设计


一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
天天打游戏、照样领工资、还办H1B
这份工作你要不要?
把贵司招聘信息放这里
查看: 2635|回复: 10
收起左侧

Google电面

[复制链接] |试试Instant~ |关注本帖
我是小马甲 发表于 2015-10-2 16:13:49 | 显示全部楼层 |阅读模式

2015(10-12月) 码农类 硕士 全职@Google - 猎头 - 技术电面 |Passfresh grad应届毕业生

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

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

x
谷歌第一轮电面,已过。
1. Longest substring without repeating letters. 原题,不说了
2. Longest consecutive numbers in a binary tree.

关于第二题,大致意思是这样,让在binary tree里挑出最长的连续(必须后面数=前面数+1)递增数列,数列顺序只能从parent到child,不可以反着来。比如:
. Waral 鍗氬鏈夋洿澶氭枃绔,
                 1
                    \
                      3
                    /    \
                  2      4
                           \
                             5
则返回[3, 4, 5]


再比如:
                 2
                    \
                      3
                    /    \
                  1      4
                 /          \
               2             5. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
              /
             3
            /
           4. visit 1point3acres.com for more.

则返回[1, 2, 3, 4].鐣欏璁哄潧-涓浜-涓夊垎鍦

我一开始想着一个recursive就好了,后来发现还得用dfs更新每一个节点,大致程序这样:. Waral 鍗氬鏈夋洿澶氭枃绔,

public List<Integer> longestConsecutiveSequence(TreeNode root) {
        List<Integer> max = new ArrayList<Integer>();
        longestListHelper(max, new ArrayList<Integer>(), root);  
        return max;
    }
   
   
private void longestListHelper(List<Integer> max, List<Integer> list, TreeNode node) {
        if (node == null) {
            return;
        }
        
        if (list.size() == 0) {. Waral 鍗氬鏈夋洿澶氭枃绔,
            list.add(node.val);
        } else if (list.size() > 0 && list.get(list.size() - 1) == node.val -1) {
            list.add(node.val);
        } else {
            list = new ArrayList<Integer>();
            list.add(node.val);. 鍥磋鎴戜滑@1point 3 acres
        }. 鍥磋鎴戜滑@1point 3 acres
        . From 1point 3acres bbs
        if (list.size() > max.size()) {
            max.clear();
            max.addAll(list);
        }
        longestListHelper(max, list, node.left);. from: 1point3acres.com/bbs
        longestListHelper(max, list, node.right);
        
    }




补充内容 (2015-10-2 16:16): 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
of course, second test case would pass if you return [2,3,4,5]

评分

1

查看全部评分

本帖被以下淘专辑推荐:

Wizmann 发表于 2015-10-2 22:00:45 | 显示全部楼层
  1. int ans = 0;
  2. void dfs(TreeNode* cur, int pre, int len) {
  3.     if (cur == nullptr) {
  4.         return; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  5.     }
  6.     int value = cur->value;
  7.     if (value == pre + 1) {
  8.         len++;
  9.     } else {
  10.         len = 1;
  11.     }. more info on 1point3acres.com
  12.     ans = max(ans, len);
    .鏈枃鍘熷垱鑷1point3acres璁哄潧
  13.     dfs(cur->left, value, len);
  14.     dfs(cur->right, value, len);
  15. } 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  16. . 1point 3acres 璁哄潧
  17. dfs(root, -INF, 0);
复制代码
回复 支持 1 反对 0

使用道具 举报

 楼主| 我是小马甲 发表于 2015-10-2 16:16:34 | 显示全部楼层
of course, second test case would pass if you return [2,3,4,5]
回复 支持 反对

使用道具 举报

zxy_snow 发表于 2015-10-2 21:06:08 | 显示全部楼层
  1. void findLongest(TreeNode *root, vector<pair<int, int> > &path, int &max_len, int &tail) {
  2.     if (root == NULL) {
  3.         return ;
  4.     }
  5.     if (path.empty() || root->val != path.back().first + 1) {
  6.         path.push_back(make_pair(root->val, 1));-google 1point3acres
  7.     } else {
  8.         path.push_back(make_pair(root->val, path.back().second + 1));
  9.         if (max_len < path.back().second) {
  10.             max_len = path.back().second;
  11.             tail = path.back().first;.鐣欏璁哄潧-涓浜-涓夊垎鍦
  12.         }
  13.     }
  14.     findLongest(root->left, path, max_len, tail);
  15.     findLongest(root->right, path, max_len, tail);
  16.     path.pop_back();
  17. }
复制代码
有点像dp吧,pair first是结尾k,second为结尾为k最大长度

补充内容 (2015-10-2 21:07):
max_len是存的最大长度,tail是最大长度的结尾。输出直接输出tail-max_len + 1 ~ tail即可。

补充内容 (2015-10-2 21:18):
啊,也可以不用pair,只用int,记录当前节点的长度,前驱节点用一个参数传进去就行了。。
回复 支持 反对

使用道具 举报

又见紫风铃 发表于 2015-10-2 23:02:18 | 显示全部楼层
写了个iterative的
  1. class TreeNode:
  2.     def __init__(self, x):
  3.         self.val = x
  4.         self.left = None
  5.         self.right = None. more info on 1point3acres.com

  6. class Solution:.鏈枃鍘熷垱鑷1point3acres璁哄潧
  7.     def longestConsecutiveNumsinBT(self, root):
  8.         if not root: return []
  9.         stack = [(root, [root.val])]
  10.         res = []
  11.         while stack:
  12.             node, path = stack.pop()
    . visit 1point3acres.com for more.
  13.             if not node.left and not node.right:
  14.                 res.append(path)
  15.                 continue
  16.             if node.left:
  17.                 if node.left.val == node.val + 1:
  18.                     stack.append((node.left, path + [node.left.val]))
  19.                 else:
  20.                     stack.append((node.left, [node.left.val]))
  21.             if node.right:
  22.                 if node.right.val == node.val + 1:.鏈枃鍘熷垱鑷1point3acres璁哄潧
  23.                     stack.append((node.right, path + [node.right.val]))
  24.                 else:
  25.                     stack.append((node.right, [node.right.val])). 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

  26.         longest = res[0]
  27.         for i in range(1, len(res)):
  28.             if len(res[i]) > len(longest):
  29.                 longest = res[i]
  30.         return longest
复制代码
回复 支持 反对

使用道具 举报

LifeGoesOn 发表于 2015-10-4 05:16:59 | 显示全部楼层
Actually your code may not work for this case. you should reset list to the origin state when it's passed in before you call longestListHelper(max, list, node.left); and  longestListHelper(max, list, node.right);

your code will give [1, 2, 3, 4, 5, 6] given the following test case. while [1,2,3,4] is the right answer.
Anyway. Congs!
  1.         /*
  2.          *   1
  3.          *    \. from: 1point3acres.com/bbs
  4.          *     2.鐣欏璁哄潧-涓浜-涓夊垎鍦
  5.          *    / \
  6.          *   3   5
  7.          *  /     \
  8.          * 4       6
  9.          *       . 1point3acres.com/bbs
  10.          */
复制代码
回复 支持 反对

使用道具 举报

tangvictor 发表于 2015-10-19 09:01:16 | 显示全部楼层
我用的是dfs做的,贴下我的代码以供大家参考。
  1. class TreeNode: 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  2.         def __init__(self, val):. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  3.                 self.val = val
  4.                 self.left = None
  5.                 self.right = None

  6. def longestConsecutiveNumbers(root):
  7.         res = [[]]
  8.         helper(root, [], res, True)
  9.         helper(root, [], res, False)
  10.         return res[0]
  11. . visit 1point3acres.com for more.
  12. def helper(root, line, res, isIncreased):
  13.         if root == None:
  14.                 return

  15.         if len(line) == 0 or (isIncreased and root.val == line[-1] + 1) or (not isIncreased and root.val == line[-1] - 1):
  16.                 if len(list(line) + [root.val]) > len(res[0]):
  17.                         res[0] = list(line) + [root.val]
  18.                 helper(root.left, line + [root.val], res, isIncreased)
  19.                 helper(root.right, line + [root.val], res, isIncreased)
  20.         else:. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  21.                 helper(root.left, [root.val], res, True)
  22.                 helper(root.left, [root.val], res, False)
  23.                 helper(root.right, [root.val], res, True)
  24.                 helper(root.right, [root.val], res, False)
复制代码
回复 支持 反对

使用道具 举报

becky12 发表于 2015-10-19 10:08:58 | 显示全部楼层
我的代码:
void helper(TreeNode* root, int pre, int len, int& ans, int& val) {
    if (!root) {
        return;
    }
    int value = root->val;
    len = value==pre+1? len+1 : 1;
    . 1point 3acres 璁哄潧
    if(len>ans){
        ans = len;
        val = value;
-google 1point3acres    }
.鐣欏璁哄潧-涓浜-涓夊垎鍦
    helper(root->left, value, len, ans, val);
    helper(root->right, value, len, ans, val);.1point3acres缃
}
vector<int> longest(TreeNode *root) {
    int ans =0, val = 0;
    helper(root, INT_MIN, 0, ans, val);
    vector<int> v;. from: 1point3acres.com/bbs
    for(int i = ans-1;i>=0; --i){.鏈枃鍘熷垱鑷1point3acres璁哄潧
      v.push_back(val-i);
    }
    return v;
}
回复 支持 反对

使用道具 举报

孤笑客 发表于 2015-10-20 02:15:10 | 显示全部楼层
这个应该邀请onsite了吧?MTV吗?
回复 支持 反对

使用道具 举报

肖邦的眼泪 发表于 2015-10-20 05:00:20 | 显示全部楼层
LifeGoesOn 发表于 2015-10-4 05:16
Actually your code may not work for this case. you should reset list to the origin state when it's p ...

Very correct points!

instead of longestListHelper(max, list, node.right), it should be longestListHelper(max, new ArrayList<Integer>(list), node.right)
回复 支持 反对

使用道具 举报

杰西Jesse 发表于 2015-10-20 12:45:13 | 显示全部楼层
用string保存,dfs
  1. import java.util.*;
  2. class TreeNode {
  3.   int val;
  4.   TreeNode left;
  5.   TreeNode right;
  6.   TreeNode(int x) { val = x; }.1point3acres缃
  7. }
  8. public class FindSequenceTree {
  9.         int max =0;
  10.         String longest = "";
  11.         public List<Integer> findSeq(TreeNode root){. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  12.                 helper(root,"");
  13.                 List<Integer> ret= new ArrayList<Integer>();
  14.                 for(int i =0 ; i < longest.length();i++){.鏈枃鍘熷垱鑷1point3acres璁哄潧
  15.                         ret.add(longest.charAt(i)-'0');
  16.                 }               
  17.                 return ret;
  18.         }
  19.         public void helper(TreeNode root,String str){
  20.                 String result = str+String.valueOf(root.val);
  21.                 if(result.length()>max){. 鍥磋鎴戜滑@1point 3 acres
  22.                         max=result.length();
  23.                         longest=result;
  24.                 }
  25.                 if(root.left==null && root.right==null) return;
  26.                 if(root.right!=null){
  27.                         if(root.right.val==root.val+1) helper(root.right,result);
  28.                         helper(root.right,"");
  29.                 }
  30.                 if(root.left!=null){
  31.                         if(root.left.val==root.val+1) helper(root.left,result);
  32.                         helper(root.left,"");
  33.                 }
  34.         }
  35.         public static void main(String args[]) {
  36.                 FindSequenceTree cmt = new FindSequenceTree();
  37.                 TreeNode root=new TreeNode(4);
  38.                 TreeNode t1=new TreeNode(1);. visit 1point3acres.com for more.
  39.                 TreeNode t2=new TreeNode(2);. from: 1point3acres.com/bbs
  40.                 TreeNode t3=new TreeNode(3);
  41.                 TreeNode t5=new TreeNode(5);
  42.                 TreeNode t6=new TreeNode(6);
  43.                 TreeNode t7=new TreeNode(7);. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  44.                 TreeNode t8=new TreeNode(8);
  45.                 root.left=t1;
  46.                 t1.left=t2;
  47.                 t1.right=t3;
  48.                 root.right=t6;
  49.                 t6.right=t7;
  50.                 t7.left=t8;
  51.                 System.out.println(cmt.findSeq(root));
  52.         }
  53. }
复制代码
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-10-21 07:07

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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