《数据科学面试40+真题讲解》,K神本年度最后一次开课


一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推你去多家公司面试
Airbnb 数据科学职位
in analytics and inference
天天打游戏、照样领工资,
你要不要来?
把贵司招聘信息放这里
查看: 4068|回复: 10
收起左侧

Pocket Gems第一轮电面

[复制链接] |试试Instant~ |关注本帖
ryuichist 发表于 2015-4-18 07:56:35 | 显示全部楼层 |阅读模式

2015(4-6月) 码农类 本科 全职@PoketGem - 网上海投 - 技术电面 |Other在职跳槽

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?Sign Up 注册获取更多干货

x
老掉牙的两道题目了,STRSTR和Top kth repeating number,把代码贴出来给大家分享下,可以在coder pad上完美运行的
顺便求点大米搜索!又要不够大米了!!!谢谢. from: 1point3acres.com/bbs

记得要有如下的import
import java.util.AbstractMap.SimpleEntry;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
import java.util.Comparator;. From 1point 3acres bbs
import java.util.Hashtable;
import java.util.Iterator;
import java.util.Map.Entry;
import java.util.PriorityQueue;. from: 1point3acres.com/bbs
import java.util.Queue;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
import java.util.Set;
.1point3acres缃import java.util.List;
import java.util.ArrayList;

第一题,STRSTR,说白了就是String match,看一个String里面有没有一个小的sub string,如果有,返回index。
解法,直接暴力法,最坏情况O(mn),比如一个是"aaaaaaaaaaaaaaaaaaaaab",一个是"ab"
public static int solve(String s, String p){
  if(s == null || p == null || p.length() > s.length()){
    return -1;
  }

  if(p.isEmpty() || p.equals(s)){
    return 0;
  }

  int slength = s.length();
  int plength = p.length();
  int startindex = 0;
  while(startindex <= (slength-plength)){
    int i = startindex;. 鍥磋鎴戜滑@1point 3 acres
    for(int j = 0; j < plength; j++){
      char c1 = s.charAt(i);. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
      char c2 = p.charAt(j);
      if(c1 != c2){
        startindex++;
        break;
      }else{
        if(j == plength-1){
          return startindex;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
        }else{. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
          i++;
        }
      }
    }
. visit 1point3acres.com for more.
    }
      return -1;
  }
第二题,Top kth repeating number。
解法,hash table+PriorityQueue,时间复杂度是O(n*log k);
public static List<Integer> kth(int[] arr, int k){
  List<Integer> result = new ArrayList<Integer>();. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  if(arr == null || arr.length==0){. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
    System.out.println("invalid input");.鏈枃鍘熷垱鑷1point3acres璁哄潧
    return result;
  } 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  Hashtable<Integer, Integer> table = new Hashtable<Integer, Integer>();.1point3acres缃
  for(int e : arr){
    int temp = 0;
    if(!table.containsKey(e)){
      temp++;
    }else{
      temp = table.get(e)+1;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
    }. 鍥磋鎴戜滑@1point 3 acres
    table.put(e, temp);
  }
  if(k > table.size()){
    System.out.println("invalid input"); 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
    return result;.鏈枃鍘熷垱鑷1point3acres璁哄潧
  }. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

  Comparator<Entry<Integer, Integer>> cmp = new Comparator<Entry<Integer, Integer>>(){
    public int compare(Entry<Integer, Integer> e1, Entry<Integer, Integer> e2){-google 1point3acres
      return e2.getValue() - e1.getValue();
    }. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  };

  Queue<Entry<Integer, Integer>> q = new PriorityQueue<Entry<Integer, Integer>>(k, cmp);
  Set<Integer> ks = table.keySet();
  Iterator<Integer> it = ks.iterator();
  while(it.hasNext()){
    int key = it.next();
    int value = table.get(key);
    Entry<Integer, Integer> en = new SimpleEntry<Integer, Integer>(key, value);
    q.add(en);
  }
  while(k > 0){
    result.add(q.poll().getKey());
    k--; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  }
  return result;
}


评分

4

查看全部评分

frankrenyu 发表于 2015-5-20 01:18:11 | 显示全部楼层
感谢楼主,但感觉楼主第二题的时候,没有必要把所有的元素都放进heap里吧,其实只需要维护一个k size的heap就行了吧?
回复 支持 反对

使用道具 举报

 楼主| ryuichist 发表于 2015-5-20 03:19:19 | 显示全部楼层
frankrenyu 发表于 2015-5-20 01:18
感谢楼主,但感觉楼主第二题的时候,没有必要把所有的元素都放进heap里吧,其实只需要维护一个k size的heap ...

对的 写comparator的时候改下就是了 你是对的
回复 支持 反对

使用道具 举报

frankrenyu 发表于 2015-5-20 05:18:40 | 显示全部楼层
ryuichist 发表于 2015-5-20 03:19
对的 写comparator的时候改下就是了 你是对的

谢谢楼主回复, 祝楼主早日拿到大offer!
回复 支持 反对

使用道具 举报

 楼主| ryuichist 发表于 2015-5-20 05:23:38 | 显示全部楼层
frankrenyu 发表于 2015-5-20 05:18
谢谢楼主回复, 祝楼主早日拿到大offer!

ONSITE已经被三哥黑了,如果你不是女生的话,最好做好最坏的打算。
onsite面筋:http://www.1point3acres.com/bbs/thread-134318-1-1.html. 1point3acres.com/bbs
被黑内幕:http://www.1point3acres.com/bbs/thread-134633-1-1.html
回复 支持 反对

使用道具 举报

frankrenyu 发表于 2015-5-20 05:43:10 | 显示全部楼层
谢谢 看到帖子了,也看到了有人奇葩的回复,加油吧,找工作也是找个心理,估计这过程心里承受能力得非常强! 不过地里还是很多正能量的,至于结果也就无所谓了。
回复 支持 反对

使用道具 举报

 楼主| ryuichist 发表于 2015-5-20 06:10:19 | 显示全部楼层
frankrenyu 发表于 2015-5-20 05:43
谢谢 看到帖子了,也看到了有人奇葩的回复,加油吧,找工作也是找个心理,估计这过程心里承受能力得非常强 ...

嗯,做好自己这一份就是了。加油吧,好运
回复 支持 反对

使用道具 举报

xanadulord 发表于 2015-5-25 02:22:47 | 显示全部楼层
strstr不要求线性的方法吗?
回复 支持 反对

使用道具 举报

woridage1 发表于 2015-10-13 21:12:57 | 显示全部楼层
frankrenyu 发表于 2015-5-20 01:18
感谢楼主,但感觉楼主第二题的时候,没有必要把所有的元素都放进heap里吧,其实只需要维护一个k size的heap ...
. 鍥磋鎴戜滑@1point 3 acres
应该是维护k+1 size的heap吧
回复 支持 反对

使用道具 举报

Quinny 发表于 2015-10-14 22:46:33 | 显示全部楼层
请问楼主投了多久得到的电面呢?是内推还是海投?
回复 支持 反对

使用道具 举报

HML0622 发表于 2015-11-17 08:53:45 | 显示全部楼层
楼主加油啊~~~
回复 支持 反对

使用道具 举报

本版积分规则

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-11-24 15:47

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表