r*******h
发帖数: 315 | 1 其他题目都是Java相关，没有难度。有两道题说出来大家讨论一下。
1. 给一个数组，每个元素是2或者3或者5的k次方，k是非负数，这个数组是排好序的，
写一个函数返回第n个数
2. 实现下面的class包括给定的方法，要求线程安全：
public class CartAdder {
public void addItem(int userId, int productId, ConcurrentHashMap
Vector> shoppingCarts) {
}
} |
j**********3
发帖数: 3211 | |
y****e
发帖数: 25 | 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*******h
发帖数: 315 | 4 1. 是的，我也是用暴力法产生，这个时间是O(nlogn)，followup只能说先搞一个数组
存起来，需要多次调用的时候直接返回对应的值。就是在想有没有可能O(n)
2. 打错了，应该是string
【在 y****e 的大作中提到】
: 1. 用三个迭代器（2， 3，5各一个）可以产生从1到n的每一个数。直接产生第n个数有
: 些难度。
: 2. 你确认userId是int不是String？
:
: String,
|
d******e
发帖数: 2265 | 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****e
发帖数: 25 | 6 第二题：
public void addItem(String userId, int productId, ConcurrentHashMap
Vector> 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******7
发帖数: 1758 | 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
minK = 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*******h
发帖数: 315 | 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*******h
发帖数: 315 | 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******n
发帖数: 12088 | 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******n
发帖数: 12088 | 11 浮点误差怎么办？
【在 r*******h 的大作中提到】
: treemap是bst，一样O(lgn)的插入，所以还是O(nlogn)
: 我倒是想到了一点优化，因为n很大的时候算power会overflow，所以一个做法是取对数
: ，这样就变成了k*log2 vs. k*log3 vs. k*log5，因为log保持了单调递增，所以就好
: 处理多了。
|
s******7
发帖数: 1758 | 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*******h
发帖数: 315 | 13 抱歉之前没看仔细，确实是好方法，赞！！
【在 s******7 的大作中提到】
: treemap从头到尾只有三个元素（3个篮子），是lg3常数，那里需要lgn的插入
|
e***i
发帖数: 231 | 14 re[N]
【在 n******n 的大作中提到】
: 已经拍好序的数组，下标是N，直接取这个元素不就行了？
:
: shoppingCarts) {
|
d****g
发帖数: 153 | 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) {
: }
: }
|
