logo
Redian新闻
>未名空间
>JobHunting - 待字闺中
>
一个小的startup，类似于snapchat的电面
avatar
一个小的startup，类似于snapchat的电面# JobHunting - 待字闺中
r*h
1 楼
其他题目都是Java相关，没有难度。有两道题说出来大家讨论一下。
1. 给一个数组，每个元素是2或者3或者5的k次方，k是非负数，这个数组是排好序的，
写一个函数返回第n个数
2. 实现下面的class包括给定的方法，要求线程安全：
public class CartAdder {
public void addItem(int userId, int productId, ConcurrentHashMapVector> shoppingCarts) {
}
}
avatar
j*3
2 楼
请站内我名字。。。
avatar
y*e
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) {
: }
: }
avatar
r*h
4 楼
1. 是的，我也是用暴力法产生，这个时间是O(nlogn)，followup只能说先搞一个数组
存起来，需要多次调用的时候直接返回对应的值。就是在想有没有可能O(n)
2. 打错了，应该是string

【在 y****e 的大作中提到】
: 1. 用三个迭代器（2， 3，5各一个）可以产生从1到n的每一个数。直接产生第n个数有
: 些难度。
: 2. 你确认userId是int不是String？
:
: String,
avatar
d*e
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
avatar
y*e
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
avatar
s*7
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
avatar
r*h
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);
: }
: }
avatar
r*h
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
avatar
n*n
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) {
: }
: }
avatar
n*n
11 楼
浮点误差怎么办？

【在 r*******h 的大作中提到】
: treemap是bst，一样O(lgn)的插入，所以还是O(nlogn)
: 我倒是想到了一点优化，因为n很大的时候算power会overflow，所以一个做法是取对数
: ，这样就变成了k*log2 vs. k*log3 vs. k*log5，因为log保持了单调递增，所以就好
: 处理多了。
avatar
s*7
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保持了单调递增，所以就好
: 处理多了。
avatar
r*h
13 楼
抱歉之前没看仔细，确实是好方法，赞！！

【在 s******7 的大作中提到】
: treemap从头到尾只有三个元素（3个篮子），是lg3常数，那里需要lgn的插入
avatar
e*i
14 楼
re[N]

【在 n******n 的大作中提到】
: 已经拍好序的数组，下标是N，直接取这个元素不就行了？
:
: shoppingCarts) {
avatar
d*g
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) {
: }
: }
相关阅读
跟一个组面试完之后，hr把offer递上去没有批大家觉得面经，CC150, leetcode这几个相对重要程度怎么排？真心求教两个offer选择！！请教offer怎么谈，煮熟的鸭子啊，职位是猎头推的H1b 批准后是不是悲剧了vt pp reg 收到退信Dept. of Labor 一般需要多久批准LCA?做了半天题，发现最难的是拿面试机会啊。。面试时 “永远不要说现在和以前公司的坏话” -- 是吗？求纽约周围能CPT的学校！最近面G的不少啊。。湾区求个entry level java的intern付费。。求帮忙托运车！！！（芝加哥到洛杉矶）String Match一定要用KMP吗？h1b被rfe, 到哪里找类似的小公司的类似的position去？H1B post- decision实在理解不了DP、图论等题，可以死记硬背么？$65/hr 相当于permanent job的多少年薪？还有比这个更折磨人的吗？
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章，不代表同意其说法或描述，仅为提供更多信息，也不构成任何建议。文章信息的合法性及真实性由其作者负责，与Redian.news及其运营公司无关。欢迎投稿，如发现稿件侵权，或作者不愿在本网发表文章，请版权拥有者通知本网处理。