《数据科学面试40+真题讲解》,K神本年度最后一次开课


一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推你去多家公司面试
Airbnb 数据科学职位
in analytics and inference
天天打游戏、照样领工资,
你要不要来?
把贵司招聘信息放这里
查看: 1846|回复: 14
收起左侧

wish 全套面经

[复制链接] |试试Instant~ |关注本帖
oio14644 发表于 2017-6-18 01:34:10 | 显示全部楼层 |阅读模式

2017(4-6月) 码农类 硕士 全职@wish - 网上海投 - Onsite |Passfresh grad应届毕业生

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

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

x
电面
1.      给一个数, 如何判断是不是斐波那契数
2.      //Given a ODD number, print the diamond with *.
//  like
//  input 3
//  _X_
//  XXX
//  _X_
//  input 5
//    X  
//   XXX
//  XXXXX
//   XXX
要求最好是递归,但是迭代也可以
On site
1: mergetwo sorted arrays, merge n sorted DataStream, 最后一题
就是有n个人, 比赛, 问你有多少种比赛结果排名,每个人可以独自一人一组,
也可以和其他人组成团体,
比如n= 2, 两个人A,B,
可能的结果有3
A 第一,B 第二
B 第一,A 第二
A, B 团体第一
2: threesum, k sum, number of island
3: top klargest from an array, sort, heap, quick select 三种方法都让写一遍, 然后让证明quick select的平均复杂度是O(n)
4:
A bot is an id that visit the site m times in the last nseconds,
given a list of logs with id and time sorted by time, returnall the bots's id
这家很抠门,on site 旅途中吃饭不报销

评分

3

查看全部评分

larry514 发表于 2017-7-13 06:29:49 | 显示全部楼层
请问这道题
. 1point3acres.com/bbs
就是有n个人比赛,问你有多少种比赛结果排名,每个人可以独自一人一组,
也可以和其他人组成团体,. visit 1point3acres.com for more.
比如n= 2, 两个人A,B,. 1point3acres.com/bbs
可能的结果有3种
A 第一,B 第二
B 第一,A 第二
A, B 团体第一

楼主是怎么处理的?
多谢楼主。
回复 支持 反对

使用道具 举报

 楼主| oio14644 发表于 2017-7-13 14:14:34 | 显示全部楼层
larry514 发表于 2017-7-13 06:29
请问这道题-google 1point3acres

就是有n个人比赛,问你有多少种比赛结果排名,每个人可以独自一人一组,

dp 动态规划
回复 支持 反对

使用道具 举报

forteller 发表于 2017-7-13 15:08:29 | 显示全部楼层
第4轮:
A bot is an id that visit the site m times in the last nseconds,
given a list of logs with id and time sorted by time, returnall the bots's id
请问能给一个例子吗?
回复 支持 反对

使用道具 举报

larry514 发表于 2017-7-13 23:48:58 | 显示全部楼层

有三个人 A, B, C, 那么结果应该包括
ABC, ... , CBA -> 6
(AB)C, C(AB), ... , A(BC) -> 6
(ABC) -> 1

有两个人 A, B, 结果有
AB, BA -> 2
(AB) -> 1
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
想了半天也没想出关系式,楼主能具体说说是怎么做的吗?
多谢多谢。

另外,那道 String query 的题,是TF-IDF吗?还是看看哪10片文章里String query出现的次数最多?. From 1point 3acres bbs
谢谢楼主。

补充内容 (2017-7-14 00:14):
String query 那题看错了。不好意思。
回复 支持 反对

使用道具 举报

wangdi561 发表于 2017-7-14 02:58:21 | 显示全部楼层
多谢分享。楼主去这家了吗?
回复 支持 反对

使用道具 举报

 楼主| oio14644 发表于 2017-7-14 11:58:49 | 显示全部楼层
wangdi561 发表于 2017-7-14 02:58. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
多谢分享。楼主去这家了吗?

没去, 做的东西 不太喜欢
回复 支持 反对

使用道具 举报

 楼主| oio14644 发表于 2017-7-14 11:59:54 | 显示全部楼层
forteller 发表于 2017-7-13 15:08
第4轮:
A bot is an id that visit the site m times in the last nseconds,
given a list of logs with  ...

leetcode design hit 和 rate limiter的 综合
回复 支持 反对

使用道具 举报

 楼主| oio14644 发表于 2017-7-14 14:28:10 | 显示全部楼层
larry514 发表于 2017-7-13 23:48
. 1point 3acres 璁哄潧有三个人 A, B, C, 那么结果应该包括
ABC, ... , CBA -> 6
(AB)C, C(AB), ... , A(BC) -> 6

/*.鏈枃鍘熷垱鑷1point3acres璁哄潧
就是有n个人, 比赛, 问你有多少种比赛结果排名, 每个人可以独自一人一组,
也可以和其他人组成团体,
比如n = 2, 两个人 A,B,
可能的结果有3种
A 第一, B 第二
B 第一, A 第二
A, B 团体第一
. 鍥磋鎴戜滑@1point 3 acres
n = 3, 有 13 种可能
dp[0] = 1;
dp[1] = 1;
dp count with i persons
*/
class Solution {. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
    public static int findTotalCount(int n){
        int[] dp = new int[n + 1];
        if(n <= 1){
          return n;
        }
        dp[0] = 1;
        dp[1] = 1;
        for(int i = 2; i <= n; i++){
          for(int k = 0; k < i; k++){
            dp += helper(i, i - k) * dp[k];
          }
        }
        return dp[n];
    }
    public static int helper(int n, int k){
      int res = 1;
      for(int i = n - k + 1; i <= n; i++){. Waral 鍗氬鏈夋洿澶氭枃绔,
         res *= i;
      }
      for(int i = 1; i <= k; i++){
         res /= i;
      }
      return res;
    }
  public static void main(String[] args){
    int n = 3;
   
    System.out.println(findTotalCount(n) + "\n");
    for(int i = 0; i <= n; i++){
        System.out.println(helper(n, i));
    }
  }
}
回复 支持 反对

使用道具 举报

 楼主| oio14644 发表于 2017-7-14 14:29:13 | 显示全部楼层
forteller 发表于 2017-7-13 15:08
第4轮: 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
A bot is an id that visit the site m times in the last nseconds,
given a list of logs with  ...

import java.util.*;
class Log{
  String id;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  int time;. 1point3acres.com/bbs
  public Log(String id, int time){. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
    this.id = id;-google 1point3acres
    this.time = time;
  }
}
class Solution{
  public static HashSet<String> getBots(List<Log> logs, int n, int m){
    HashMap<String, Queue<Integer>> map = new HashMap<>();
    HashSet<String> set = new HashSet<>();
    for(Log log : logs){
      String id = log.id;
      int time = log.time;
      if(set.contains(id)){
. From 1point 3acres bbs        continue;. more info on 1point3acres.com
      }
      if(!map.containsKey(id)){
        Queue<Integer> q = new LinkedList<>();
        q.add(time);
        map.put(id, q);
      }else{
        while(!map.get(id).isEmpty() && time - map.get(id).peek() > n){
          map.get(id).remove();
        }
        map.get(id).add(time);
      }
      if(map.get(id).size() >= m){
          set.add(id);.鐣欏璁哄潧-涓浜-涓夊垎鍦
      }
    }
    return set;
  }
回复 支持 反对

使用道具 举报

larry514 发表于 2017-7-25 01:44:01 | 显示全部楼层
oio14644 发表于 2017-7-14 14:28. From 1point 3acres bbs
/*
就是有n个人, 比赛, 问你有多少种比赛结果排名, 每个人可以独自一人一组,
也可以和其他人组成团体, ...
. Waral 鍗氬鏈夋洿澶氭枃绔,
谢谢楼主的回复。
看了半天才看懂,是一道排列组合的题目。
楼主厉害了。
回复 支持 反对

使用道具 举报

LeetCodeOJ 发表于 2017-8-9 05:45:34 | 显示全部楼层
兄弟面的题目很难啊
回复 支持 反对

使用道具 举报

endofunctor 发表于 2017-8-15 13:54:38 | 显示全部楼层
组队题:
  1. int count(int n) {
  2.   if (n == 0)
  3.     return 0;
  4.   vector<vector<int> > dp(n + 1, vector<int>(n + 1, 0));
  5.   dp[1][1] = 1;
  6.   // ith person, j teams                                                                                                                     
  7.   for (int i = 2; i <= n; ++i) {-google 1point3acres
  8.     for (int j = i - 1; j >= 1; --j) {
  9.       dp[i][j + 1] += (j + 1) * dp[i - 1][j];
  10.       dp[i][j] += j * dp[i - 1][j];
  11.     }
  12.   }
  13.   int res = 0;
  14.   for (int i = 1; i <= n; ++i) {
  15.     res += dp[n][i];
  16.   }
  17.   return res;. Waral 鍗氬鏈夋洿澶氭枃绔,
  18. }
复制代码
回复 支持 反对

使用道具 举报

EricZhang 发表于 2017-9-14 23:46:54 | 显示全部楼层
oio14644 发表于 2017-7-14 14:29
import java.util.*;
class Log{. From 1point 3acres bbs
  String id;

. more info on 1point3acres.com这道题lz的做法有点问题吧。lz每次只update 了当前id的time queue。对于HashSet中其他的id,可能它们的queue.peek() 已经not in the last n seconds,lz并没有update。

所以check每一行log之后都应该Update所有id的queue。

补充内容 (2017-9-14 23:54):.鏈枃鍘熷垱鑷1point3acres璁哄潧
PS:如果每个timestamp只有一个bot id, lz这道题的解法没有问题。
回复 支持 反对

使用道具 举报

zws1818918 发表于 2017-10-7 07:17:58 | 显示全部楼层
请问楼主,diamond这题,如果input是5
是不是应该是
   x. 1point 3acres 璁哄潧
  xxx
xxxxxx
  xxx. from: 1point3acres.com/bbs
   x
楼主漏掉了最后一行?
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-11-21 07:23

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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