问个东西类似于sandisk ultra fit USB flash drive - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>PDA - 掌中宝

问个东西类似于sandisk ultra fit USB flash drive

问个东西类似于sandisk ultra fit USB flash drive# PDA - 掌中宝

M*g2016-11-20 08:11

1 楼

面试的是一个国人phd。
1.pow(double a, int b)没什么说的，注意overflow就行
2.实现2sum
interface TwoSum{
//存储用户输入的数
void store(int input){
}
//判断是否有两个数的和是val
boolean test(int val){
}
}
要求输入有重复，首先实现test的复杂度O(n) store的复杂度常数（用hashmap）
然后实现store的复杂度是o(n)，test的复杂度是常数（用hashset）
最后考虑并发问题，两个方法同是被调用的时候（互斥锁）
很好的面试题，考察的挺全面，实际中也会碰到这样的问题，给大家分享一下。因为多
线程编程不是很了解，估计已挂。面试的时候又紧张。

a92016-11-20 08:11

2 楼

水管稍微有点漏水，大概一分钟一滴的样子（两根铜管接头的地方），有没有简单的方
法修一下？

j*12016-11-20 08:11

3 楼

没有工作经验,totally fresh MSEE, power electronic 和 simulation 方向的
工作从去年八月份就开始找了，现在连实习都没有，接近放弃的边缘了
还想去湾区找找，大家给点意见吧，到底值得一拼吗？
如果值得，可不可以提供一些衣食住行的建议？
一个月得花多少钱？
一定要买车吗？
到底现在回国还是跑到湾区找？
现在真的好迷惑！！！

c*e2016-11-20 08:11

4 楼

小形状很像，但是里面可以插 SD card, amazon /eBay 都找不到了，哪位还记得？

n*n2016-11-20 08:11

5 楼

hash map和set不都是hash？test怎么可能是常数？存所有的和？那样存储平方。

【在 M**********g 的大作中提到】

: 面试的是一个国人phd。
: 1.pow(double a, int b)没什么说的，注意overflow就行
: 2.实现2sum
: interface TwoSum{
: //存储用户输入的数
: void store(int input){
: }
: //判断是否有两个数的和是val
: boolean test(int val){
: }

l*h2016-11-20 08:11

6 楼

我家门口的进水管漏水，用大班子拧了拧就好了。

【在 a9 的大作中提到】

: 水管稍微有点漏水，大概一分钟一滴的样子（两根铜管接头的地方），有没有简单的方
: 法修一下？

f*d2016-11-20 08:11

7 楼

如果有tapeout经验应该稍微容易些. 最近也听说公司招人,不过都要有一定经验的.
去craiglist看看房子就大概知道什么价钱了,有几百刀住人家里那种.
也可以回学校读个Ph.D.,到经济好了再出来.

【在 j******1 的大作中提到】

: 没有工作经验,totally fresh MSEE, power electronic 和 simulation 方向的
: 工作从去年八月份就开始找了，现在连实习都没有，接近放弃的边缘了
: 还想去湾区找找，大家给点意见吧，到底值得一拼吗？
: 如果值得，可不可以提供一些衣食住行的建议？
: 一个月得花多少钱？
: 一定要买车吗？
: 到底现在回国还是跑到湾区找？
: 现在真的好迷惑！！！

c*e2016-11-20 08:11

8 楼

感觉你没问题的
写了３道题呢　最后一个小follow－up而已

a92016-11-20 08:11

9 楼

我漏水的地方不是螺纹的接头，是两根铜管拐弯的地方，焊起来的。

的方

【在 l**h 的大作中提到】

: 我家门口的进水管漏水，用大班子拧了拧就好了。

e*s2016-11-20 08:11

10 楼

龟

y*e2016-11-20 08:11

11 楼

谢谢lz分享，祝拿到onsite。
第一题power有什么trick吗？和leetcode应该是一样的（正负指数，奇偶指数），
overflow的话因为return type是double, 还需要特别考虑吗？
第二题多线程怎么答呢？用synchronized行吗？

【在 M**********g 的大作中提到】

J*S2016-11-20 08:11

12 楼

除了重新接，
我想可以补。。
我看到一个帖子，买房子。卖家修了水管，说没问题了。是STUCCO的，我想，就是外
面糊了一层水泥一样的东西吧。

【在 a9 的大作中提到】

: 水管稍微有点漏水，大概一分钟一滴的样子（两根铜管接头的地方），有没有简单的方
: 法修一下？

c*n2016-11-20 08:11

13 楼

作为店面难度正好

【在 M**********g 的大作中提到】

l*h2016-11-20 08:11

14 楼

再焊一下？
如果是排水管，也可以检查一下是不是有点堵。

【在 a9 的大作中提到】

: 我漏水的地方不是螺纹的接头，是两根铜管拐弯的地方，焊起来的。
:
: 的方

M*g2016-11-20 08:11

15 楼

答得时候磕磕绊绊，也想了不少时间

【在 c*******e 的大作中提到】

: 感觉你没问题的
: 写了３道题呢　最后一个小follow－up而已

a92016-11-20 08:11

16 楼

就是不会焊，看有没有东西抹一下，呵呵。
是进水，特别细的那种管
话说，去哪儿买那个气焊啊？

【在 l**h 的大作中提到】

: 再焊一下？
: 如果是排水管，也可以检查一下是不是有点堵。

M*g2016-11-20 08:11

17 楼

第一题就是负数变证书的时候overflow 因为最小负数变正后比最大正数大1
synchronized两个方法，然后用wait和notify()控制

【在 y*****e 的大作中提到】

: 谢谢lz分享，祝拿到onsite。
: 第一题power有什么trick吗？和leetcode应该是一样的（正负指数，奇偶指数），
: overflow的话因为return type是double, 还需要特别考虑吗？
: 第二题多线程怎么答呢？用synchronized行吗？

g*y2016-11-20 08:11

18 楼

要不上照片要不拍个照片去lowes
最简单的方式是把铜管两边cut掉，接一个sharkbite的管子

M*g2016-11-20 08:11

19 楼

maintain一个arraylist还有一个hashset
每次有input就先遍历arraylist，每个数和输入书求和，存到hashset里
再把数存到arraylist里

【在 n******n 的大作中提到】

: hash map和set不都是hash？test怎么可能是常数？存所有的和？那样存储平方。

u*q2016-11-20 08:11

20 楼

只能

M*g2016-11-20 08:11

21 楼

maintain一个arraylist和hashset
对于每个输入的数，遍历arraylist 每个数和输入算和，加到hashset里，最后把输入
的数加到arraylist里

【在 n******n 的大作中提到】

: hash map和set不都是hash？test怎么可能是常数？存所有的和？那样存储平方。

y*e2016-11-20 08:11

22 楼

好滴好滴明白了

【在 M**********g 的大作中提到】

: 第一题就是负数变证书的时候overflow 因为最小负数变正后比最大正数大1
: synchronized两个方法，然后用wait和notify()控制

y*e2016-11-20 08:11

23 楼

lz为啥你就一个面试官哪，我是两个耶。。。。估计有一个是shadow。。。

M*g2016-11-20 08:11

24 楼

是电面有两个么？
好奇怪啊，没碰到过两个的、、、、

【在 y*****e 的大作中提到】

: lz为啥你就一个面试官哪，我是两个耶。。。。估计有一个是shadow。。。

y*e2016-11-20 08:11

25 楼

对啊店面两个，一个人比较好啊，两个容易紧张。。。

【在 M**********g 的大作中提到】

: 是电面有两个么？
: 好奇怪啊，没碰到过两个的、、、、

c*n2016-11-20 08:11

26 楼

后面用read write lock 更容易些，你用notify 基本就是实现read lock 和write
lock

【在 M**********g 的大作中提到】

: 第一题就是负数变证书的时候overflow 因为最小负数变正后比最大正数大1
: synchronized两个方法，然后用wait和notify()控制

m*32016-11-20 08:11

27 楼

请问你怎么解决这个问题的最小负数变正后比最大正数大1，是内部用long type么？

【在 M**********g 的大作中提到】

: 第一题就是负数变证书的时候overflow 因为最小负数变正后比最大正数大1
: synchronized两个方法，然后用wait和notify()控制

a*52016-11-20 08:11

28 楼

一般只有一个的原因是：有一个临时放鸽子了，问第二个说你能自己HOLD住不？不能我
就找个人替我
第二个说：没问题，我自己来就行。
所以就只有一个了。

【在 y*****e 的大作中提到】

: 对啊店面两个，一个人比较好啊，两个容易紧张。。。

y*e2016-11-20 08:11

29 楼

哈哈太有画面感了。。。

【在 a********5 的大作中提到】

: 一般只有一个的原因是：有一个临时放鸽子了，问第二个说你能自己HOLD住不？不能我
: 就找个人替我
: 第二个说：没问题，我自己来就行。
: 所以就只有一个了。

s*m2016-11-20 08:11

30 楼

感谢分享。祝LZ好运！

j*l2016-11-20 08:11

31 楼

不太懂呀，麻烦写一个multi-threading 吧

【在 M**********g 的大作中提到】

: maintain一个arraylist和hashset
: 对于每个输入的数，遍历arraylist 每个数和输入算和，加到hashset里，最后把输入
: 的数加到arraylist里

x*u2016-11-20 08:11

32 楼

多线程不容易搞.

b*i2016-11-20 08:11

33 楼

谢了，这个overflow好难想到，感觉有点刁了
是不是所有这种code里面int要求负数的都要考虑overflow。。。

【在 M**********g 的大作中提到】

: 第一题就是负数变证书的时候overflow 因为最小负数变正后比最大正数大1
: synchronized两个方法，然后用wait和notify()控制

M*g2016-11-20 08:11

34 楼

就单独处理一下最小负数就行了，long也行

【在 m******3 的大作中提到】

: 请问你怎么解决这个问题的最小负数变正后比最大正数大1，是内部用long type么？

M*g2016-11-20 08:11

35 楼

其实再store的方法加个synchronized 就可以了，
每当有线程调用store方法的时候，这个对象就上锁了，其他线程就不能访问了。
下面是原题，和我写的实现
public interface TwoSum {
/**
* Stores @param input in an internal data structure.
*/
void store(int input);

/**
* Returns true if there is any pair of numbers in the internal data
structure which
* have sum @param val, and false otherwise.
* For example, if the numbers 1, -2, 3, and 6 had been stored,
* the method should return true for 4, -1, and 9, but false for 10, 5,
and 0
*/
boolean test(int val);
}
public class TwoSumCalculator implements TwoSum {
/**
* Stores @param input in an internal data structure.
*/
ArrayList inputs = new ArrayList();
HashTable sums = new HashTable();
synchronized void store(int input){
for(int i:inputs)
sums.add(i+input);
inputs.add(input);
}
/**
* Returns true if there is any pair of numbers in the internal data
structure which
* have sum @param val, and false otherwise.
* For example, if the numbers 1,0, -2,1, 3,2, and 6; 1 had been stored,
* the method should return true for 4, -1, and 9, but false for 10, 5,
and 0
*/
boolean test(int val){
return sums.contains(val);
}
}

【在 j********l 的大作中提到】

: 不太懂呀，麻烦写一个multi-threading 吧

M*g2016-11-20 08:11

36 楼

收到onsite邀请了，谢谢咯

【在 s***m 的大作中提到】

: 感谢分享。祝LZ好运！

M*g2016-11-20 08:11

37 楼

拿到onsite了，好幸运，你的面试怎么样了

【在 y*****e 的大作中提到】

M*g2016-11-20 08:11

38 楼

是啊其实你做leetcode就会有这样的test case，国人大哥应该也是做过，所以会问吧

【在 b******i 的大作中提到】

: 谢了，这个overflow好难想到，感觉有点刁了
: 是不是所有这种code里面int要求负数的都要考虑overflow。。。

M*g2016-11-20 08:11

39 楼

收到版主送来的20伪币，好开心啊，以后也有分享的动力了。
等onsite回来就分享onsite的题

y*e2016-11-20 08:11

40 楼

多谢分享lz，你这个版本是每加一个数进去，就把所有的sum都放到hashset里面，test
就是O(1),但store是o(n),你这么写是不是因为面试官说了test会被频繁调用之类的话
呢？
因为我觉得那个list不需要用啊，直接一个hashmap，key是进来的数字，val是出现的
次数。这样写的话test是o(n），store是o(1),所有可不可以说，如果store需要频
繁调用的话，就只用hashmap, test频繁调用的话，就得用list + hashset，每加入一
个数计算出所有可能的和？
下面这个是我写的只用hashmap的版本。。。还请lz指教。
public class twoo implements TwoSum {
private Map map;
public twoo(){
map = new HashMap();
}
public void store(int input){
if(map.containsKey(input)){
map.put(input, map.get(input) + 1);
}
else{
map.put(input, 1);
}
}
public boolean test(int val){
for(int key : map.keySet()){
int target = val - key;
if(val - key == target && map.get(key) > 1){
return true;
}
if(map.containsKey(target)){
return true;
}
}
return false;
}

【在 M**********g 的大作中提到】

: 其实再store的方法加个synchronized 就可以了，
: 每当有线程调用store方法的时候，这个对象就上锁了，其他线程就不能访问了。
: 下面是原题，和我写的实现
: public interface TwoSum {
: /**
: * Stores @param input in an internal data structure.
: */
: void store(int input);
:
: /**

y*e2016-11-20 08:11

41 楼

恭喜lz!!我还在店面的初级阶段那。。。lz是不是加州local的？

【在 M**********g 的大作中提到】

: 拿到onsite了，好幸运，你的面试怎么样了

b*52016-11-20 08:11

42 楼

我靠。。我被问到好几次multithreaded，从来不敢用synchronized， always trying
to be cute with ReentrantLock, or ConcurrentHashMap, or
ReentrantReadWriteLock...
然后写写写写，就觉得需要google来看那些class的javadoc。。。

【在 M**********g 的大作中提到】

G*m2016-11-20 08:11

43 楼

lz应该过了吧：）

【在 M**********g 的大作中提到】

M*g2016-11-20 08:11

44 楼

对啊，两个都写了，一个就是要经常调用test函数，所以保证test是constant 的
running time

test

【在 y*****e 的大作中提到】

: 多谢分享lz，你这个版本是每加一个数进去，就把所有的sum都放到hashset里面，test
: 就是O(1),但store是o(n),你这么写是不是因为面试官说了test会被频繁调用之类的话
: 呢？
: 因为我觉得那个list不需要用啊，直接一个hashmap，key是进来的数字，val是出现的
: 次数。这样写的话test是o(n），store是o(1),所有可不可以说，如果store需要频
: 繁调用的话，就只用hashmap, test频繁调用的话，就得用list + hashset，每加入一
: 个数计算出所有可能的和？
: 下面这个是我写的只用hashmap的版本。。。还请lz指教。
: public class twoo implements TwoSum {
: private Map map;

M*g2016-11-20 08:11

45 楼

hashmap的话就跟你写的一样

test

【在 y*****e 的大作中提到】

M*g2016-11-20 08:11

46 楼

是啊，人在三藩

【在 y*****e 的大作中提到】

: 恭喜lz!!我还在店面的初级阶段那。。。lz是不是加州local的？

M*g2016-11-20 08:11

47 楼

是啊，我也是刚开始看多线程，synchronized直接用在方法上，效率是挺低的，我那么
写的也不对了
我觉得学习多线程，多看几个经典实例比较好，明白了原理，就很容易理解那些类了

trying

【在 b**********5 的大作中提到】

: 我靠。。我被问到好几次multithreaded，从来不敢用synchronized， always trying
: to be cute with ReentrantLock, or ConcurrentHashMap, or
: ReentrantReadWriteLock...
: 然后写写写写，就觉得需要google来看那些class的javadoc。。。

h*02016-11-20 08:11

48 楼

楼主，为什么synchronized作用在方法上会效率低？正常的多线程用该用什么？

【在 M**********g 的大作中提到】

: 是啊，我也是刚开始看多线程，synchronized直接用在方法上，效率是挺低的，我那么
: 写的也不对了
: 我觉得学习多线程，多看几个经典实例比较好，明白了原理，就很容易理解那些类了
:
: trying

A*e2016-11-20 08:11

49 楼

结果是浮点数，怎么还会有最小比最大差1的问题？

【在 M**********g 的大作中提到】

: 第一题就是负数变证书的时候overflow 因为最小负数变正后比最大正数大1
: synchronized两个方法，然后用wait和notify()控制

o*n2016-11-20 08:11

50 楼

公司名字都没拼对。。。估计已挂

m*t2016-11-20 08:11

51 楼

int 负数不是问题。。。。负数直接除 2 就行了。。。
主要得考虑 double 的 overflow 和 underflow 这种问题，以及 NaN InF 还有 pow(0
, 0) 这种 exception
http://opensource.apple.com/source/Libm/Libm-315/Source/Intel/e

【在 b******i 的大作中提到】

: 谢了，这个overflow好难想到，感觉有点刁了
: 是不是所有这种code里面int要求负数的都要考虑overflow。。。

h*32016-11-20 08:11

52 楼

楼主overflow 怎么处理？返回0 吗？
如果n给的是 1<<31 ?

M*g2016-11-20 08:11

53 楼

if(n==Integer.MIN_VALUE)
return 1/(x*pow(x,Integer.MAX_VALUE));
原来是if（n<0）
return 1/pow(x,-n);

【在 h****3 的大作中提到】

: 楼主overflow 怎么处理？返回0 吗？
: 如果n给的是 1<<31 ?

M*g2016-11-20 08:11

54 楼

因为synchronized作用在方法上，就把这个对象锁定了，所有其他synchronized的方法
就不可以访问了，如果不同进程想同时调用test方法就要等待了

【在 h*******0 的大作中提到】

: 楼主，为什么synchronized作用在方法上会效率低？正常的多线程用该用什么？

M*g2016-11-20 08:11

55 楼

因为我写的是
pow(x,n){
if(n<0)
return 1/pow(x,-n);
}
所以他才问我这里的最小值溢出问题。。。。
整个函数确实是应该考虑double的溢出

(0

【在 m*********t 的大作中提到】

: int 负数不是问题。。。。负数直接除 2 就行了。。。
: 主要得考虑 double 的 overflow 和 underflow 这种问题，以及 NaN InF 还有 pow(0
: , 0) 这种 exception
: http://opensource.apple.com/source/Libm/Libm-315/Source/Intel/e