一个小的startup，类似于snapchat的电面 - 未名空间MITBBS历史存档

一个小的startup，类似于snapchat的电面# JobHunting - 待字闺中

r*h2015-04-10 07:04

1 楼

其他题目都是Java相关，没有难度。有两道题说出来大家讨论一下。
1. 给一个数组，每个元素是2或者3或者5的k次方，k是非负数，这个数组是排好序的，
写一个函数返回第n个数
2. 实现下面的class包括给定的方法，要求线程安全：
public class CartAdder {
public void addItem(int userId, int productId, ConcurrentHashMapVector> shoppingCarts) {
}
}

j*32015-04-10 07:04

2 楼

请站内我名字。。。

y*e2015-04-10 07:04

3 楼

1. 用三个迭代器（2， 3，5各一个）可以产生从1到n的每一个数。直接产生第n个数有
些难度。
2. 你确认userId是int不是String？

String,

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

: 其他题目都是Java相关，没有难度。有两道题说出来大家讨论一下。
: 1. 给一个数组，每个元素是2或者3或者5的k次方，k是非负数，这个数组是排好序的，
: 写一个函数返回第n个数
: 2. 实现下面的class包括给定的方法，要求线程安全：
: public class CartAdder {
: public void addItem(int userId, int productId, ConcurrentHashMap: Vector> shoppingCarts) {
: }
: }

r*h2015-04-10 07:04

4 楼

1. 是的，我也是用暴力法产生，这个时间是O(nlogn)，followup只能说先搞一个数组
存起来，需要多次调用的时候直接返回对应的值。就是在想有没有可能O(n)
2. 打错了，应该是string

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

: 1. 用三个迭代器（2， 3，5各一个）可以产生从1到n的每一个数。直接产生第n个数有
: 些难度。
: 2. 你确认userId是int不是String？
:
: String,

d*e2015-04-10 07:04

5 楼

这个题不要数组。
你用一个简单heap min queue like data structure. 里面加入三个 iterables的当前
纸和next function.
(value, iterables.next()), 写个pop函数，取最小，替换为next 的value. heapify.
然后主程序写个for loop.或者while loop pop. 丢掉前 n -1个。
返回 n-th value.

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

: 1. 是的，我也是用暴力法产生，这个时间是O(nlogn)，followup只能说先搞一个数组
: 存起来，需要多次调用的时候直接返回对应的值。就是在想有没有可能O(n)
: 2. 打错了，应该是string

y*e2015-04-10 07:04

6 楼

第二题：
public void addItem(String userId, int productId, ConcurrentHashMapVector> shoppingCarts) {
Vector cart = shoppingCarts.putIfAbsent(userId, new Vector<
Integer>());
synchronized(cart) {
cart.add(productId);
}
}

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

: 1. 是的，我也是用暴力法产生，这个时间是O(nlogn)，followup只能说先搞一个数组
: 存起来，需要多次调用的时候直接返回对应的值。就是在想有没有可能O(n)
: 2. 打错了，应该是string

s*72015-04-10 07:04

7 楼

O（n）, 差不多也是暴力法，三个篮子2，3，5，每次选最小的，再乘上篮子标号放回
去，搞n就可以了
三个选最小的，都不用什么heap, 直接排序就可以了
篮子实现用个treemap
SortedMap map = new TreeMap<>();
map.put(1,2); // 2^0=1
map.put(1,3); // 3^0=1
map.put(1,5); // 5^0=1
int minK = 0;
for(int i=0;iminK = map.firstKey();
int minV = map.get(minK);
map.remove(min);
map.put(min*minV,minV);
}
return minK;

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

: 1. 是的，我也是用暴力法产生，这个时间是O(nlogn)，followup只能说先搞一个数组
: 存起来，需要多次调用的时候直接返回对应的值。就是在想有没有可能O(n)
: 2. 打错了，应该是string

r*h2015-04-10 07:04

8 楼

我觉得奇怪的是什么情况一下一个用户的shopping cart会产生并发操作呢？

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

: 第二题：
: public void addItem(String userId, int productId, ConcurrentHashMap: Vector> shoppingCarts) {
: Vector cart = shoppingCarts.putIfAbsent(userId, new Vector<
: Integer>());
: synchronized(cart) {
: cart.add(productId);
: }
: }

r*h2015-04-10 07:04

9 楼

treemap是bst，一样O(lgn)的插入，所以还是O(nlogn)
我倒是想到了一点优化，因为n很大的时候算power会overflow，所以一个做法是取对数
，这样就变成了k*log2 vs. k*log3 vs. k*log5，因为log保持了单调递增，所以就好
处理多了。

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

: O（n）, 差不多也是暴力法，三个篮子2，3，5，每次选最小的，再乘上篮子标号放回
: 去，搞n就可以了
: 三个选最小的，都不用什么heap, 直接排序就可以了
: 篮子实现用个treemap
: SortedMap map = new TreeMap<>();
: map.put(1,2); // 2^0=1
: map.put(1,3); // 3^0=1
: map.put(1,5); // 5^0=1
: int minK = 0;
: for(int i=0;i

n*n2015-04-10 07:04

10 楼

已经拍好序的数组，下标是N，直接取这个元素不就行了？

shoppingCarts) {

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

: 其他题目都是Java相关，没有难度。有两道题说出来大家讨论一下。
: 1. 给一个数组，每个元素是2或者3或者5的k次方，k是非负数，这个数组是排好序的，
: 写一个函数返回第n个数
: 2. 实现下面的class包括给定的方法，要求线程安全：
: public class CartAdder {
: public void addItem(int userId, int productId, ConcurrentHashMap: Vector> shoppingCarts) {
: }
: }

n*n2015-04-10 07:04

11 楼

浮点误差怎么办？

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

: treemap是bst，一样O(lgn)的插入，所以还是O(nlogn)
: 我倒是想到了一点优化，因为n很大的时候算power会overflow，所以一个做法是取对数
: ，这样就变成了k*log2 vs. k*log3 vs. k*log5，因为log保持了单调递增，所以就好
: 处理多了。

s*72015-04-10 07:04

12 楼

treemap从头到尾只有三个元素（3个篮子），是lg3常数，那里需要lgn的插入

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

: treemap是bst，一样O(lgn)的插入，所以还是O(nlogn)
: 我倒是想到了一点优化，因为n很大的时候算power会overflow，所以一个做法是取对数
: ，这样就变成了k*log2 vs. k*log3 vs. k*log5，因为log保持了单调递增，所以就好
: 处理多了。

r*h2015-04-10 07:04

13 楼

抱歉之前没看仔细，确实是好方法，赞！！

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

: treemap从头到尾只有三个元素（3个篮子），是lg3常数，那里需要lgn的插入

e*i2015-04-10 07:04

14 楼

re[N]

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

: 已经拍好序的数组，下标是N，直接取这个元素不就行了？
:
: shoppingCarts) {

d*g2015-04-10 07:04

15 楼

二分查找 log(n)
维护三个index x,y,z, 分别代表2,3,5的x,y,z次方
刚开始z的范围是0-n
每一步z=z/2,估算x和y，使得2^x ~= 3^y ~= 5^z
如果x+y+z>n,则递归找前一半
otherwise，则递归找后一半

String,

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

: 其他题目都是Java相关，没有难度。有两道题说出来大家讨论一下。
: 1. 给一个数组，每个元素是2或者3或者5的k次方，k是非负数，这个数组是排好序的，
: 写一个函数返回第n个数
: 2. 实现下面的class包括给定的方法，要求线程安全：
: public class CartAdder {
: public void addItem(int userId, int productId, ConcurrentHashMap: Vector> shoppingCarts) {
: }
: }