Wepay OA面经及讨论

一直拖到现在把wepay oa做完了，POWER number这道题5个test case超时了所以我个人不抱有什么希望

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

rity queue的快。

1. class Main {
   
2.     public static void main(String[] args) {
   
3.         System.out.println(getPowerNumber(1000));
   
4.     }
   
5.    
   
6.     static long getPowerNumber(long index) {
   
7.         if(index <0){
   
8.             return -1;
   
9.         }
   
10.         
    
11.         HashMap<Long, Long> map = new HashMap<>();
    
12.         index += 1;
    
13.         long max = (long)Math.sqrt(Long.MAX_VALUE);
    
14.         for(long i = 2 ; i <= max; i++){
    
15.             if(map.containsKey(i)){
    
16.                 long root = map.get(i);
    
17.                 if(i * root < Long.MAX_VALUE){
    
18.                     map.put(i * root, root);
    
19.                 }
    
20.                 index--;
    
21.                 if(index == 0){
    
22.                     return i;
    
23.                 }
    
24.                 map.remove(i);
    
25.             }
    
26.             else{
    
27. map.put(i * i, i);
    
28.             }
    
29.         }
    
30.         
    
31.         return -1;
    
32.     }
    
33. }

复制代码

用堆排序，Java的话就用PriorityQueue。用一个Set判断每次向queue中添加的数字是否重复，不重复则添加。
两层for循环求power number，底数i从2增加到index+3，指数j从2增加到20几应该就够了。
再把queue poll到第index个元素。希望有帮助

llzy1178 发表于 2017-9-3 07:32
请问怎么优化的呢，我也刚做完，最后两个case不过。用的是PQ+hashset去重，PQ用了reverseOrder(),还是过 ...

可以根据给出来的index找一个最小的上界，最终答案只会小于等于这个上界。跑循环的时候，计算出来的power number大于这个上界就换个base再计算，至于上界怎么找就需要自己稍微思考一下了：）
另外的就跟帖子里另一个兄弟一样保持固定大小的pq。

nagisafight 发表于 2017-9-2 15:11
可以提供一下思路吗？谢谢

思路就是super ugly number 那题优化
一个PQ, 建一个数据结构  O(1)空间 O(nlogn).  具体代码我拿到电面贴给你们

test超时是指有test没过么？

我用的ugly number的方法做，超时最后两个test case，不知道是不是test case更新了，要不就是我太笨了

请问你们是怎么投的呀？官网上没看到专门New Grad的职位耶。。谢谢喔！！

test case最后5个我没有过，感觉他oa的题目要求有改，我朋友做的时候还是返回int，我做的时候已经变成返回long了

mrhhsmr 发表于 2017-9-1 02:41
test case最后5个我没有过，感觉他oa的题目要求有改，我朋友做的时候还是返回int，我做的时候已经变成返回l ...

这题我朋友今天做的时候也是long了  以前是int..   他也是最后几个test case过不去 应该是算法效率还是太低了 估计需要一个top down的写法 有没有什么好思路？

可以用PriorityQueue, 做best first search

没事了 我改了代码以后全过了   NlogN....   好爽 哈哈哈哈

求代码 求思路啊！！

jy02535954 发表于 2017-9-2 12:50
没事了 我改了代码以后全过了   NlogN....   好爽 哈哈哈哈

可以提供一下思路吗？谢谢