一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 2385|回复: 10
收起左侧

Pocket Gems第一轮电面

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

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

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

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

x
老掉牙的两道题目了,STRSTR和Top kth repeating number,把代码贴出来给大家分享下,可以在coder pad上完美运行的
顺便求点大米搜索!又要不够大米了!!!谢谢
.鐣欏璁哄潧-涓浜-涓夊垎鍦
记得要有如下的import
import java.util.AbstractMap.SimpleEntry;
import java.util.Comparator;
import java.util.Hashtable;
import java.util.Iterator;
import java.util.Map.Entry;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Set;
import java.util.List;. 1point 3acres 璁哄潧
import java.util.ArrayList;
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
第一题,STRSTR,说白了就是String match,看一个String里面有没有一个小的sub string,如果有,返回index。.鐣欏璁哄潧-涓浜-涓夊垎鍦
解法,直接暴力法,最坏情况O(mn),比如一个是"aaaaaaaaaaaaaaaaaaaaab",一个是"ab"
. more info on 1point3acres.compublic 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)){.1point3acres缃
    int i = startindex;
    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++;
        }
      }
    }. Waral 鍗氬鏈夋洿澶氭枃绔,

    }
      return -1;-google 1point3acres
  }
第二题,Top kth repeating number。
解法,hash table+PriorityQueue,时间复杂度是O(n*log k);
public static List<Integer> kth(int[] arr, int k){
. 鍥磋鎴戜滑@1point 3 acres  List<Integer> result = new ArrayList<Integer>();. 鍥磋鎴戜滑@1point 3 acres
  if(arr == null || arr.length==0){
    System.out.println("invalid input");.1point3acres缃
    return result;
  }
  Hashtable<Integer, Integer> table = new Hashtable<Integer, Integer>();
  for(int e : arr){. 1point3acres.com/bbs
    int temp = 0;
    if(!table.containsKey(e)){
      temp++;. Waral 鍗氬鏈夋洿澶氭枃绔,
    }else{
      temp = table.get(e)+1;
    }. from: 1point3acres.com/bbs
    table.put(e, temp);
  }
  if(k > table.size()){
    System.out.println("invalid input");
    return result;
  }

  Comparator<Entry<Integer, Integer>> cmp = new Comparator<Entry<Integer, Integer>>(){
    public int compare(Entry<Integer, Integer> e1, Entry<Integer, Integer> e2){
      return e2.getValue() - e1.getValue();
    }. From 1point 3acres bbs
  };

  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);
  }. Waral 鍗氬鏈夋洿澶氭枃绔,
  while(k > 0){
    result.add(q.poll().getKey());
    k--;. visit 1point3acres.com for more.
  }
  return result;
}

. Waral 鍗氬鏈夋洿澶氭枃绔,

评分

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. Waral 鍗氬鏈夋洿澶氭枃绔,
谢谢楼主回复, 祝楼主早日拿到大offer!

ONSITE已经被三哥黑了,如果你不是女生的话,最好做好最坏的打算。
onsite面筋:http://www.1point3acres.com/bbs/thread-134318-1-1.html
被黑内幕: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.鏈枃鍘熷垱鑷1point3acres璁哄潧
谢谢 看到帖子了,也看到了有人奇葩的回复,加油吧,找工作也是找个心理,估计这过程心里承受能力得非常强 ...

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

使用道具 举报

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 ...

应该是维护k+1 size的heap吧
回复 支持 反对

使用道具 举报

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

使用道具 举报

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

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

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

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-9 06:18

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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