M**********g
发帖数: 59 | 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）
最后考虑并发问题，两个方法同是被调用的时候（互斥锁）
很好的面试题，考察的挺全面，实际中也会碰到这样的问题，给大家分享一下。因为多
线程编程不是很了解，估计已挂。面试的时候又紧张。 |
n******n
发帖数: 12088 | 2 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){
: }
|
c*******e
发帖数: 621 | 3 感觉你没问题的
写了３道题呢 最后一个小follow－up而已 |
y*****e
发帖数: 712 | 4 谢谢lz分享，祝拿到onsite。
第一题power有什么trick吗？和leetcode应该是一样的（正负指数，奇偶指数），
overflow的话因为return type是double, 还需要特别考虑吗？
第二题多线程怎么答呢？用synchronized行吗？
【在 M**********g 的大作中提到】
: 面试的是一个 国人phd。
: 1.pow(double a, int b)没什么说的，注意overflow就行
: 2.实现2sum
: interface TwoSum{
: //存储用户输入的数
: void store(int input){
: }
: //判断是否有两个数的和是val
: boolean test(int val){
: }
|
c******n
发帖数: 4965 | 5 作为店面 难度正好
【在 M**********g 的大作中提到】
: 面试的是一个 国人phd。
: 1.pow(double a, int b)没什么说的，注意overflow就行
: 2.实现2sum
: interface TwoSum{
: //存储用户输入的数
: void store(int input){
: }
: //判断是否有两个数的和是val
: boolean test(int val){
: }
|
M**********g
发帖数: 59 | 6 答得时候磕磕绊绊，也想了不少时间
【在 c*******e 的大作中提到】
: 感觉你没问题的
: 写了３道题呢 最后一个小follow－up而已
|
M**********g
发帖数: 59 | 7 第一题就是 负数变证书的时候overflow 因为最小负数变正后比最大正数大1
synchronized两个方法，然后用wait和notify()控制
【在 y*****e 的大作中提到】
: 谢谢lz分享，祝拿到onsite。
: 第一题power有什么trick吗？和leetcode应该是一样的（正负指数，奇偶指数），
: overflow的话因为return type是double, 还需要特别考虑吗？
: 第二题多线程怎么答呢？用synchronized行吗？
|
M**********g
发帖数: 59 | 8 maintain一个arraylist还有一个hashset
每次有input就先遍历arraylist，每个数和输入书求和，存到hashset里
再把数存到arraylist里
【在 n******n 的大作中提到】
: hash map和set不都是hash？test怎么可能是常数？存所有的和？那样存储平方。
|
M**********g
发帖数: 59 | 9 maintain一个arraylist和hashset
对于每个输入的数，遍历arraylist 每个数和输入算和，加到hashset里，最后把输入
的数加到arraylist里
【在 n******n 的大作中提到】
: hash map和set不都是hash？test怎么可能是常数？存所有的和？那样存储平方。
|
y*****e
发帖数: 712 | 10 好滴好滴明白了
【在 M**********g 的大作中提到】
: 第一题就是 负数变证书的时候overflow 因为最小负数变正后比最大正数大1
: synchronized两个方法，然后用wait和notify()控制
|
|
|
y*****e
发帖数: 712 | 11 lz为啥你就一个面试官哪，我是两个耶。。。。估计有一个是shadow。。。 |
M**********g
发帖数: 59 | 12 是电面有两个么？
好奇怪啊，没碰到过两个的、、、、
【在 y*****e 的大作中提到】
: lz为啥你就一个面试官哪，我是两个耶。。。。估计有一个是shadow。。。
|
y*****e
发帖数: 712 | 13 对啊店面两个，一个人比较好啊，两个容易紧张。。。
【在 M**********g 的大作中提到】
: 是电面有两个么？
: 好奇怪啊，没碰到过两个的、、、、
|
c******n
发帖数: 4965 | 14 后面用read write lock 更容易些， 你用notify 基本就是实现read lock 和write
lock
【在 M**********g 的大作中提到】
: 第一题就是 负数变证书的时候overflow 因为最小负数变正后比最大正数大1
: synchronized两个方法，然后用wait和notify()控制
|
m******3
发帖数: 346 | 15 请问你怎么解决这个问题的最小负数变正后比最大正数大1，是内部用long type么？
【在 M**********g 的大作中提到】
: 第一题就是 负数变证书的时候overflow 因为最小负数变正后比最大正数大1
: synchronized两个方法，然后用wait和notify()控制
|
a********5
发帖数: 1631 | 16 一般只有一个的原因是：有一个临时放鸽子了，问第二个说你能自己HOLD住不？不能我
就找个人替我
第二个说：没问题，我自己来就行。
所以就只有一个了。
【在 y*****e 的大作中提到】
: 对啊店面两个，一个人比较好啊，两个容易紧张。。。
|
y*****e
发帖数: 712 | 17 哈哈太有画面感了。。。
【在 a********5 的大作中提到】
: 一般只有一个的原因是：有一个临时放鸽子了，问第二个说你能自己HOLD住不？不能我
: 就找个人替我
: 第二个说：没问题，我自己来就行。
: 所以就只有一个了。
|
s***m
发帖数: 336 | |
j********l
发帖数: 325 | 19 不太懂呀，麻烦写一个multi-threading 吧
【在 M**********g 的大作中提到】
: maintain一个arraylist和hashset
: 对于每个输入的数，遍历arraylist 每个数和输入算和，加到hashset里，最后把输入
: 的数加到arraylist里
|
x********u
发帖数: 1150 | |
|
|
b******i
发帖数: 914 | 21 谢了，这个overflow好难想到，感觉有点刁了
是不是所有这种code里面int要求负数的都要考虑overflow。。。
【在 M**********g 的大作中提到】
: 第一题就是 负数变证书的时候overflow 因为最小负数变正后比最大正数大1
: synchronized两个方法，然后用wait和notify()控制
|
M**********g
发帖数: 59 | 22 就单独处理一下最小负数就行了，long也行
【在 m******3 的大作中提到】
: 请问你怎么解决这个问题的最小负数变正后比最大正数大1，是内部用long type么？
|
M**********g
发帖数: 59 | 23 其实再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**********g
发帖数: 59 | 24 收到onsite邀请了，谢谢咯
【在 s***m 的大作中提到】
: 感谢分享。祝LZ好运！
|
M**********g
发帖数: 59 | 25 拿到onsite了，好幸运，你的面试怎么样了
【在 y*****e 的大作中提到】
: 谢谢lz分享，祝拿到onsite。
: 第一题power有什么trick吗？和leetcode应该是一样的（正负指数，奇偶指数），
: overflow的话因为return type是double, 还需要特别考虑吗？
: 第二题多线程怎么答呢？用synchronized行吗？
|
M**********g
发帖数: 59 | 26 是啊 其实你做leetcode就会有这样的test case，国人大哥应该也是做过，所以会问吧
【在 b******i 的大作中提到】
: 谢了，这个overflow好难想到，感觉有点刁了
: 是不是所有这种code里面int要求负数的都要考虑overflow。。。
|
M**********g
发帖数: 59 | 27 收到版主送来的20伪币，好开心啊，以后也有分享的动力了。
等onsite回来就分享onsite的题 |
y*****e
发帖数: 712 | 28 多谢分享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*****e
发帖数: 712 | 29 恭喜lz!!我还在店面的初级阶段那。。。lz是不是加州local的？
【在 M**********g 的大作中提到】
: 拿到onsite了，好幸运，你的面试怎么样了
|
b**********5
发帖数: 7881 | 30 我靠。。我被问到好几次multithreaded， 从来不敢用synchronized， always trying
to be cute with ReentrantLock, or ConcurrentHashMap, or
ReentrantReadWriteLock...
然后写写写写， 就觉得需要google来看那些class的javadoc。。。
【在 M**********g 的大作中提到】
: 其实再store的方法加个synchronized 就可以了，
: 每当有线程调用store方法的时候，这个对象就上锁了，其他线程就不能访问了。
: 下面是原题，和我写的实现
: public interface TwoSum {
: /**
: * Stores @param input in an internal data structure.
: */
: void store(int input);
:
: /**
|
|
|
G*****m
发帖数: 5395 | 31 lz应该过了吧：）
【在 M**********g 的大作中提到】
: 面试的是一个 国人phd。
: 1.pow(double a, int b)没什么说的，注意overflow就行
: 2.实现2sum
: interface TwoSum{
: //存储用户输入的数
: void store(int input){
: }
: //判断是否有两个数的和是val
: boolean test(int val){
: }
|
M**********g
发帖数: 59 | 32 对啊，两个都写了，一个就是要经常调用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**********g
发帖数: 59 | 33 hashmap的话就跟你写的一样
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**********g
发帖数: 59 | 34 是啊，人在三藩
【在 y*****e 的大作中提到】
: 恭喜lz!!我还在店面的初级阶段那。。。lz是不是加州local的？
|
M**********g
发帖数: 59 | 35 是啊，我也是刚开始看多线程，synchronized直接用在方法上，效率是挺低的，我那么
写的也不对了
我觉得学习多线程，多看几个经典实例比较好，明白了原理，就很容易理解那些类了
trying
【在 b**********5 的大作中提到】
: 我靠。。我被问到好几次multithreaded， 从来不敢用synchronized， always trying
: to be cute with ReentrantLock, or ConcurrentHashMap, or
: ReentrantReadWriteLock...
: 然后写写写写， 就觉得需要google来看那些class的javadoc。。。
|
h*******0
发帖数: 270 | 36 楼主，为什么synchronized作用在方法上会效率低？ 正常的多线程用该用什么？
【在 M**********g 的大作中提到】
: 是啊，我也是刚开始看多线程，synchronized直接用在方法上，效率是挺低的，我那么
: 写的也不对了
: 我觉得学习多线程，多看几个经典实例比较好，明白了原理，就很容易理解那些类了
:
: trying
|
A*******e
发帖数: 2419 | 37 结果是浮点数，怎么还会有最小比最大差1的问题？
【在 M**********g 的大作中提到】
: 第一题就是 负数变证书的时候overflow 因为最小负数变正后比最大正数大1
: synchronized两个方法，然后用wait和notify()控制
|
o****n
发帖数: 937 | |
m*********t
发帖数: 527 | 39 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****3
发帖数: 89 | 40 楼主overflow 怎么处理？返回0 吗？
如果n给的是 1<<31 ? |
|
|
M**********g
发帖数: 59 | 41 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**********g
发帖数: 59 | 42 因为synchronized作用在方法上，就把这个对象锁定了，所有其他synchronized的方法
就不可以访问了，如果不同进程想同时调用test方法就要等待了
【在 h*******0 的大作中提到】
: 楼主，为什么synchronized作用在方法上会效率低？ 正常的多线程用该用什么？
|
M**********g
发帖数: 59 | 43 因为我写的是
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
|
