一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 2231|回复: 16
收起左侧

新出炉的狗家电二面

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

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

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

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

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

姐姐还给我好多个提示。
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
我用的是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.. 1point 3acres 璁哄潧
2就会有2/15次的机会成为Output
.鏈枃鍘熷垱鑷1point3acres璁哄潧
只能用ran() method->returns a number in [0,1). e.g. 0.2345
不可以用random.randint哦~~~~
. 1point3acres.com/bbs
最后写出来个最简单的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会要什么才对啊。???求告知~~~. 1point3acres.com/bbs
[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),看落在哪里行不行. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
. from: 1point3acres.com/bbs
补充内容 (2016-10-7 01:02):
。。并不需要排序
回复 支持 反对

使用道具 举报

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

//*******************************************************************. visit 1point3acres.com for more.

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. 鍥磋鎴戜滑@1point 3 acres
  public static void main(String[] args)-google 1point3acres
  {
    int[] ns={1,2,3};. Waral 鍗氬鏈夋洿澶氭枃绔,
    OtherClass o=new OtherClass(ns);
    for(int i=0;i<6;i++){
      System.out.println(o.get());
  }.鐣欏璁哄潧-涓浜-涓夊垎鍦
  }. 1point 3acres 璁哄潧
}

// you can add other public classes to this editor in any order
public class OtherClass
{
  int[] buffer;
  int sum;. Waral 鍗氬鏈夋洿澶氭枃绔,
  Random rand;
  public OtherClass(int[] numbers){
    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;
      if(randInt>=sum-tempSum)
        return n;
     
-google 1point3acres                  }
    return 0;
  }
}
回复 支持 反对

使用道具 举报

rabbithui 发表于 2016-10-7 01:17:56 | 显示全部楼层
import java.lang.Math; // headers MUST be above the first class. visit 1point3acres.com for more.
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)
  {
    OtherClass o=new OtherClass();.1point3acres缃
    for(int i=1;i<10;i++){
      System.out.println(o.generateMagicString(i));
  }
  }
}. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

// you can add other public classes to this editor in any order
public class OtherClass
{. 1point3acres.com/bbs
  public String generateMagicString(int len){.鐣欏璁哄潧-涓浜-涓夊垎鍦
    String result="1";
    int currentCount=0;
    int countingPosition=0;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
    while(result.length()<len){. 鍥磋鎴戜滑@1point 3 acres
      char count=result.charAt(currentCount);. 1point 3acres 璁哄潧
      char countingChar=result.charAt(countingPosition);
      if(count=='1'){
              if(countingChar=='1')
          result+='2';. 1point 3acres 璁哄潧
        else
          result+='1';
        countingPosition++;
      }
      else{
        result+=countingChar;. from: 1point3acres.com/bbs
        if(countingChar=='1')
          result+='2';
        else
          result+='1';. 1point 3acres 璁哄潧
        countingPosition+=2;
      }. visit 1point3acres.com for more.
      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 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
存partial sums, 可以做到logn

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

使用道具 举报

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

使用道具 举报

yhatl 发表于 2016-10-9 03:02:51 | 显示全部楼层
int tmp=0;. From 1point 3acres bbs
vector<int> sum(nums.size(),0);
for(int i=0;i<nums.size();i++){. Waral 鍗氬鏈夋洿澶氭枃绔,
    sum[i]+=tmp+nums[i];. visit 1point3acres.com for more.
    tmp=sum[i];. visit 1point3acres.com for more.
}
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;. From 1point 3acres bbs
  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) {
  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)吧?
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

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

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-9 18:31

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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