10月28,K神开课讲数据科学,你来吗?


一亩三分地论坛

 找回密码
 获取更多干活,快来注册
Babeltime游戏工作室招工程师、美术和策划
Tubi TV招安卓、前端和机器学习工程师
把贵司招聘信息放这里
查看: 1175|回复: 13
收起左侧

wish 全套面经

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

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

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

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

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缃
.鐣欏璁哄潧-涓浜-涓夊垎鍦
就是有n个人比赛,问你有多少种比赛结果排名,每个人可以独自一人一组,
也可以和其他人组成团体,
比如n= 2, 两个人A,B,
可能的结果有3种
A 第一,B 第二
B 第一,A 第二
A, B 团体第一

楼主是怎么处理的?. from: 1point3acres.com/bbs
多谢楼主。
回复 支持 反对

使用道具 举报

 楼主| 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轮:.1point3acres缃
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
-google 1point3acres请问能给一个例子吗?
回复 支持 反对

使用道具 举报

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. 1point 3acres 璁哄潧

想了半天也没想出关系式,楼主能具体说说是怎么做的吗?
多谢多谢。

另外,那道 String query 的题,是TF-IDF吗?还是看看哪10片文章里String query出现的次数最多?. 1point3acres.com/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,. visit 1point3acres.com for more.
given a list of logs with  ...

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

使用道具 举报

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

/*
就是有n个人, 比赛, 问你有多少种比赛结果排名, 每个人可以独自一人一组,
也可以和其他人组成团体,
比如n = 2, 两个人 A,B,
可能的结果有3种
A 第一, B 第二
B 第一, A 第二
A, B 团体第一
. 1point 3acres 璁哄潧
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;. 1point 3acres 璁哄潧
        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++){. 1point 3acres 璁哄潧
         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;. more info on 1point3acres.com
  int time;
  public Log(String id, int time){
    this.id = id;
    this.time = time;
  }. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
}. From 1point 3acres bbs
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){
. 鍥磋鎴戜滑@1point 3 acres      String id = log.id;
      int time = log.time;. 1point 3acres 璁哄潧
      if(set.contains(id)){.1point3acres缃
        continue;
      }
. 鍥磋鎴戜滑@1point 3 acres      if(!map.containsKey(id)){
        Queue<Integer> q = new LinkedList<>();
        q.add(time);
        map.put(id, q);. more info on 1point3acres.com
      }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: 1point3acres.com/bbs
就是有n个人, 比赛, 问你有多少种比赛结果排名, 每个人可以独自一人一组, . Waral 鍗氬鏈夋洿澶氭枃绔,
也可以和其他人组成团体, ...

谢谢楼主的回复。
看了半天才看懂,是一道排列组合的题目。.鏈枃鍘熷垱鑷1point3acres璁哄潧
楼主厉害了。
回复 支持 反对

使用道具 举报

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

使用道具 举报

endofunctor 发表于 2017-8-15 13:54:38 | 显示全部楼层
组队题:
  1. int count(int n) {. 1point 3acres 璁哄潧
  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) {
  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];.1point3acres缃
  11.     }
  12.   }
  13.   int res = 0;
  14.   for (int i = 1; i <= n; ++i) {
  15.     res += dp[n][i];
  16.   }. From 1point 3acres bbs
  17.   return res;
  18. }
复制代码
回复 支持 反对

使用道具 举报

EricZhang 发表于 6 天前 | 显示全部楼层
oio14644 发表于 2017-7-14 14:29
import java.util.*;
class Log{
  String id;

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

所以check每一行log之后都应该Update所有id的queue。. visit 1point3acres.com for more.

补充内容 (2017-9-14 23:54):. more info on 1point3acres.com
PS:如果每个timestamp只有一个bot id, lz这道题的解法没有问题。
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-9-20 04:59

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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