推荐:数据科学课程和书籍清单以及培训讲座


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

一亩三分地官方iOS手机应用下载
查看: 3320|回复: 16
收起左侧

新出炉的狗家电二面

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

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

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

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

x
听起来像是一个中国姐姐(口音)给我出的题也很简单啊。
只不过我脑子死的很。。。想半天想不出来。。。。.1point3acres缃
. visit 1point3acres.com for more.
姐姐还给我好多个提示。

我用的是python

题:
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哦~~~~

最后写出来个最简单的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]. 1point3acres.com/bbs

. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
[size=13.3333px]

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

评分

1

查看全部评分

本帖被以下淘专辑推荐:

木易wen 发表于 2016-10-19 23:44:23 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
partial sum 然后二分找区间?
回复 支持 1 反对 0

使用道具 举报

WhatsFLAG 发表于 2016-10-6 07:47:01 | 显示全部楼层
关注一亩三分地微博:
Warald
楼主你是女性程序员吧?
回复 支持 反对

使用道具 举报

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),看落在哪里行不行. 1point 3acres 璁哄潧

补充内容 (2016-10-7 01:02):. 1point 3acres 璁哄潧
。。并不需要排序
回复 支持 反对

使用道具 举报

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.1point3acres缃
  public static void main(String[] args)
  {
    int[] ns={1,2,3};
    OtherClass o=new OtherClass(ns);
    for(int i=0;i<6;i++){
      System.out.println(o.get());
  }
  }
}. Waral 鍗氬鏈夋洿澶氭枃绔,

// you can add other public classes to this editor in any order
public class OtherClass
{
  int[] buffer;
  int sum;
  Random rand;
  public OtherClass(int[] numbers){.1point3acres缃
    buffer=numbers;
    sum=0;
    for(int n:numbers)
              sum+=n;
    rand=new Random();
  }
  . 1point 3acres 璁哄潧
  public int get(){
    int tempSum=0;
    int randInt=rand.nextInt(sum);
    for(int n:buffer){
      tempSum+=n;
      if(randInt>=sum-tempSum)
        return n;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
     . From 1point 3acres bbs
                  }
    return 0;
  }
}
回复 支持 反对

使用道具 举报

rabbithui 发表于 2016-10-7 01:17:56 | 显示全部楼层
import java.lang.Math; // headers MUST be above the first class
import java.util.*;
.1point3acres缃
// 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)
  {
    OtherClass o=new OtherClass();
    for(int i=1;i<10;i++){
      System.out.println(o.generateMagicString(i));
  }
  }
}
. more info on 1point3acres.com
// you can add other public classes to this editor in any order
public class OtherClass
{. visit 1point3acres.com for more.
  public String generateMagicString(int len){
    String result="1";
    int currentCount=0;
    int countingPosition=0;
    while(result.length()<len){
      char count=result.charAt(currentCount);
      char countingChar=result.charAt(countingPosition);
      if(count=='1'){
              if(countingChar=='1')
          result+='2';
        else
          result+='1';. 1point3acres.com/bbs
        countingPosition++;
      }. 1point 3acres 璁哄潧
      else{
        result+=countingChar;
        if(countingChar=='1')
          result+='2';
        else
          result+='1';-google 1point3acres
        countingPosition+=2;
      }
      currentCount++;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
      
    }
    return result;. 1point3acres.com/bbs
  }
}
回复 支持 反对

使用道具 举报

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

使用道具 举报

Romeobaby 发表于 2016-10-7 04:25:54 | 显示全部楼层
xihaokai1 发表于 2016-10-7 00:22
存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
. From 1point 3acres bbs
求问详细思路,存完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;
  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) {.鏈枃鍘熷垱鑷1point3acres璁哄潧
  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.                
  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-7-26 21:10

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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