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


一亩三分地论坛

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

新出炉的狗家电二面

[复制链接] |试试Instant~ |关注本帖
claireyangyang 发表于 2016-10-6 07:26:59 | 显示全部楼层 |阅读模式

2016(7-9月) 码农类 本科 全职@Google - 网上海投 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
听起来像是一个中国姐姐(口音)给我出的题也很简单啊。
只不过我脑子死的很。。。想半天想不出来。。。。

姐姐还给我好多个提示。. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

我用的是python. 鍥磋鎴戜滑@1point 3 acres

题:
given an array=[1,2,3,4,5], so the sum will be 15 in total.
return random number from the array based on the probability.
e.g. 1->1/15
       2->2/15
所以每次run random(array) output will be different.
2就会有2/15次的机会成为Output

只能用ran() method->returns a number in [0,1). e.g. 0.2345
不可以用random.randint哦~~~~-google 1point3acres

最后写出来个最简单的O(N^2)的方法。我是不是很蠢。。。。。
然后问我test case 有哪些。drawback 有哪些
Test cases (unit):
  • [1,2,3,4,5]  | want: return a number from the array.
  • big array, length > 1m | want: no timeout

Drawbacks:
  • Time complexity: O(n^2) too large
  • When array is big, then the “list” will consume all the memory

[size=13.3333px]


[size=13.3333px]
.鐣欏璁哄潧-涓浜-涓夊垎鍦

[size=13.3333px]感觉自己基础不是很好啊:PPPPP。大神看了能不能告知一般test case会要什么才对啊。???求告知~~~
[size=13.3333px]就这样,祝各位好运。我也要振作起来了!!!!!

评分

1

查看全部评分

本帖被以下淘专辑推荐:

木易wen 发表于 2016-10-19 23:44:23 | 显示全部楼层
partial sum 然后二分找区间?
回复 支持 1 反对 0

使用道具 举报

WhatsFLAG 发表于 2016-10-6 07:47:01 | 显示全部楼层
楼主你是女性程序员吧?
回复 支持 反对

使用道具 举报

steveguang 发表于 2016-10-6 22:58:20 | 显示全部楼层
楼主怎么做的?
回复 支持 反对

使用道具 举报

xihaokai1 发表于 2016-10-7 00:22:21 | 显示全部楼层
存partial sums, 可以做到logn
回复 支持 反对

使用道具 举报

TheBlackMamba 发表于 2016-10-7 00:57:07 | 显示全部楼层
是我没理解题意吗。。。。先排序,把一样的值数出来分别多少个,然后一个vector保留累积的sum(长度是 不同的值的个数,但是sum要算每个值的所有个数),然后每次求rand(0,1),看落在哪里行不行
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
补充内容 (2016-10-7 01:02):
。。并不需要排序
回复 支持 反对

使用道具 举报

rabbithui 发表于 2016-10-7 00:59:09 | 显示全部楼层
Java Code:

//*******************************************************************. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

import java.lang.Math; // headers MUST be above the first class
import java.util.*;

// one class needs to have a main() method
public class HelloWorld
{
  // arguments are passed using the text field below this editor. more info on 1point3acres.com
  public static void main(String[] args)
-google 1point3acres  {
    int[] ns={1,2,3};
    OtherClass o=new OtherClass(ns);
    for(int i=0;i<6;i++){
      System.out.println(o.get());
  }
  }
}. From 1point 3acres bbs

// you can add other public classes to this editor in any order. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
public class OtherClass
{
  int[] buffer;
  int sum;
  Random rand;-google 1point3acres
  public OtherClass(int[] numbers){
. from: 1point3acres.com/bbs     buffer=numbers;
    sum=0;
    for(int n:numbers)
              sum+=n;
    rand=new Random();
  }
  
  public int get(){
    int tempSum=0;
    int randInt=rand.nextInt(sum);
    for(int n:buffer){
      tempSum+=n;. Waral 鍗氬鏈夋洿澶氭枃绔,
      if(randInt>=sum-tempSum)
        return n;
     . visit 1point3acres.com for more.
                  }
    return 0;
  }
}
回复 支持 反对

使用道具 举报

rabbithui 发表于 2016-10-7 01:17:56 | 显示全部楼层
import java.lang.Math; // headers MUST be above the first class
import java.util.*;

// one class needs to have a main() method
public class HelloWorld
{
  // arguments are passed using the text field below this editor
  public static void main(String[] args). 鍥磋鎴戜滑@1point 3 acres
  {
    OtherClass o=new OtherClass();. more info on 1point3acres.com
    for(int i=1;i<10;i++){.1point3acres缃
      System.out.println(o.generateMagicString(i));
  }
  } 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
}. 鍥磋鎴戜滑@1point 3 acres

// you can add other public classes to this editor in any order
public class OtherClass
{
  public String generateMagicString(int len){
    String result="1";. Waral 鍗氬鏈夋洿澶氭枃绔,
    int currentCount=0;
    int countingPosition=0;
    while(result.length()<len){ 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
      char count=result.charAt(currentCount);-google 1point3acres
      char countingChar=result.charAt(countingPosition);
      if(count=='1'){
              if(countingChar=='1')
          result+='2';
        else. 1point 3acres 璁哄潧
          result+='1';
        countingPosition++;
      }. visit 1point3acres.com for more.
      else{
        result+=countingChar;-google 1point3acres
        if(countingChar=='1')
          result+='2';
        else
          result+='1';
        countingPosition+=2;
      }
      currentCount++; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
      
    }
    return result;
  }
}
回复 支持 反对

使用道具 举报

yezhangpost 发表于 2016-10-7 03:31:10 | 显示全部楼层
Reservoir Sampling
回复 支持 反对

使用道具 举报

Romeobaby 发表于 2016-10-7 04:25:54 | 显示全部楼层
xihaokai1 发表于 2016-10-7 00:22-google 1point3acres
存partial sums, 可以做到logn

言简意赅,点到关键…
回复 支持 反对

使用道具 举报

 楼主| claireyangyang 发表于 2016-10-8 17:36:39 | 显示全部楼层
对了,后面有说, 不管Time。space如何改进?。
回复 支持 反对

使用道具 举报

yhatl 发表于 2016-10-9 03:02:51 | 显示全部楼层
int tmp=0;
vector<int> sum(nums.size(),0);
for(int i=0;i<nums.size();i++){
    sum[i]+=tmp+nums[i];
    tmp=sum[i];
}
return nums[upper_bound(sum.begin(),sum.end(),rand()%sum[sum.size()])-sum.begin()];
回复 支持 反对

使用道具 举报

syjohnson 发表于 2016-10-31 09:44:20 | 显示全部楼层
xihaokai1 发表于 2016-10-7 00:22
存partial sums, 可以做到logn

求问详细思路,存完prefix sum之后如何logN查找呢
回复 支持 反对

使用道具 举报

warriorbrant 发表于 2016-11-3 10:18:43 | 显示全部楼层
  1. public static int find(int[] array){
  2.                 int[] sum=new int[array.length];
  3.                 sum[0]=array[0];
  4.                 for(int i=1;i<array.length;i++)sum[i]=array[i]+sum[i-1];
  5.                 int start=0;
  6.                 int end=sum.length-1;
  7.                 int location=-1;. 1point 3acres 璁哄潧
  8.                 int target=(int)(Math.random()*(sum[array.length-1]-sum[0]+1))+sum[0];
  9.                 while(start<end){
  10.                         int mid=start+(end-start)/2;
  11.                         if(sum[mid]==target){
  12.                                 location=mid;
  13.                                 break;
  14.                         }else if(sum[mid]<target) {
  15.                                 start=mid+1;
  16.                         }else{
  17.                                 end=mid;
  18.                         }
  19.                 }
  20.                 if(location==-1)location=start;
  21.                 if(location==0)return sum[0];
  22.                 else return sum[location]-sum[location-1];
  23.                 .鏈枃鍘熷垱鑷1point3acres璁哄潧
  24.         }
复制代码
回复 支持 反对

使用道具 举报

笑眯眯的白云 发表于 2016-11-4 10:11:19 | 显示全部楼层
想问一下 楼主, google 电话面试的话, 需不需要 在网上跑 (RUN)你的代码?
回复 支持 反对

使用道具 举报

huai10 发表于 2016-11-6 08:20:41 | 显示全部楼层
看来google还是喜欢考tree,特别各种BST
回复 支持 反对

使用道具 举报

Sorrow雨 发表于 2016-11-9 10:45:34 | 显示全部楼层
这题要求和怎么也得O(N)吧?
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-11-18 23:50

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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