一亩三分地论坛

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

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

面经求玉米大米红薯土豆

[复制链接] |试试Instant~ |关注本帖
eeyyabc 发表于 2015-11-6 08:49:40 | 显示全部楼层 |阅读模式

2015(10-12月) 码农类 博士 全职@Google - 内推 - 技术电面 |Pass在职跳槽

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

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

x
经历:第一次电面google drive坏了,interviewer让我找recruiter reschedule,第二次面,碰到同一个国人。.鏈枃鍘熷垱鑷1point3acres璁哄潧

题目:给一个string="bcdaea",和一个int k=2,输出最小的排列,每个字母只能换到距离k以内的地方. 1point3acres.com/bbs
举例. from: 1point3acres.com/bbs
bcdaea, k=2,
i=0 [bcd]aea 最小的是b,输出"b",记录 index 0 已经用过. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
i=1 [bcda]ea 最小的是a,输出"ba",记录 index 0, 3 已经用过
.鐣欏璁哄潧-涓浜-涓夊垎鍦i=2 [bcdae]a 最小的是c,输出"bac"...
i=3 b[cdaea] 最小的是a,输出"baca"
i=4 bc[daea] 最小的是d,输出"bacad"
i=5 bcd[aea] 最小的是e,输出"bacade"

. 鍥磋鎴戜滑@1point 3 acres
这种做法是O(KN)的时间复杂度,O(N)空间复杂度。我还想过用minHeap和deque之类的data structure,好像都不大行。. Waral 鍗氬鏈夋洿澶氭枃绔,
听面试官口气似乎可以不用extra space,O(N)的做法?求大家指教。
最后写了code,这么简单的code中间还写错了,非常不好意思。
. From 1point 3acres bbs

总之算法没想出来好的,code中间还写错了,国人面试官手下留情,多谢了。


新人第一次发帖,看在这么辛苦码字的份上,求大米玉米还是什么的,现在好多帖子看不到很着急。。。谢谢. Waral 鍗氬鏈夋洿澶氭枃绔,


评分

5

查看全部评分

fatalme 发表于 2015-11-6 17:18:21 | 显示全部楼层
  1. class charComparator implements Comparator<int[]> {
  2.   
  3.   int k = 0;
  4.   . visit 1point3acres.com for more.
  5.   public charComparator(int k){
  6.     this.k = k;
  7.   }
  8. .鐣欏璁哄潧-涓浜-涓夊垎鍦
  9.   @Override
  10.   public int compare(int[] o1, int[] o2) {
  11.     if(o1[k] != o2[k]){
  12.       return o1[k] - o2[k];
  13.     }
  14.     return o1[1-k] - o2[1-k];. from: 1point3acres.com/bbs
  15.   }
  16.   
  17. }. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

  18. public class Solution {
  19.   
  20.   public String smallest(String s, int k){
  21.     StringBuffer sb = new StringBuffer();
  22.     PriorityQueue<int[]> pqc = new PriorityQueue<>(k, new charComparator(0));.鏈枃鍘熷垱鑷1point3acres璁哄潧
  23.     PriorityQueue<int[]> pqi = new PriorityQueue<>(k, new charComparator(1));
  24.     int i = 0;
  25.     for(i = 0; i < Math.min(s.length(), k); ++i){
    . 鍥磋鎴戜滑@1point 3 acres
  26.       int[] a = new int[]{(int)s.charAt(i), i};
  27.       pqc.add(a);
  28.       pqi.add(a);
  29.     }
  30.     for(int j = i; j < i + s.length(); ++j){
  31.       if(j < s.length()){
  32.         int[] a = new int[]{(int)s.charAt(j), j};. 鍥磋鎴戜滑@1point 3 acres
  33.         pqc.add(a);
  34.         pqi.add(a);
  35.       }
  36.       if(pqi.peek()[1] + k == j - i){
  37.         sb.append(s.charAt(pqi.peek()[1]));
  38.         pqc.remove(pqi.poll());
  39.       }else{
    .鐣欏璁哄潧-涓浜-涓夊垎鍦
  40.         sb.append((char)pqc.peek()[0]);. From 1point 3acres bbs
  41.         pqi.remove(pqc.poll());
  42.       }
  43.     }
  44.     return sb.toString();
  45.   }
  46. }
复制代码
一亩三分地严打"顶""好贴""收藏了"之类的垃圾回复帖!被警告三次,系统会自动封杀ID!

想支持楼主,请点击帖子下方的"好苗""分享""收藏"键,酌情给楼主加大米(系统不扣你自己的分)。. 1point 3acres 璁哄潧
积分不够看不了帖子,请参考论坛导航里的"帮助","新手提纲"里有攒积分指南
回复 支持 2 反对 0

使用道具 举报

可爱的帕吉 发表于 2015-11-6 15:44:10 | 显示全部楼层
  1. #include <set>
  2. #include <stdio.h>. Waral 鍗氬鏈夋洿澶氭枃绔,
  3. #include <string.h>
  4. #include <utility>
  5. #include <algorithm>

  6. using namespace std;

  7. const int MAXN = 10000;

  8. char a[MAXN + 1], c[MAXN + 1];
    .1point3acres缃
  9. bool b[MAXN];. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  10. set<pair<char, int> > s;
  11. int N, K;.鐣欏璁哄潧-涓浜-涓夊垎鍦

  12. int main() {. 1point3acres.com/bbs
  13.   scanf("%s %d", a, &K);. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  14.   N = strlen(a);
  15.   memset(b, 0, sizeof(bool) * N);
  16.   for (int i = 0; i < min(K, N); ++i)
  17.     s.insert(make_pair(a[i], i));. 1point 3acres 璁哄潧
  18.   for (int i = 0; i < N; ++i) {
  19.     if (i + K < N)
  20.       s.insert(make_pair(a[i + K], i + K));
  21.     if (i - K >= 0 && !b[i - K]) {
  22.       c[i] = a[i - K];
  23.       b[i - K] = true;
  24.       s.erase(make_pair(a[i - K], i - K));. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  25.     } else {
  26.       c[i] = s.begin() -> first;
  27.       b[s.begin() -> second] = true;
  28.       s.erase(s.begin());
  29.     }   
  30.   }
  31.   c[N] = '\0';
  32.   printf("%s\n", c);
  33.   return 0;
  34. }
复制代码
C++的set是个平衡二叉树,在里面放入pair, pair对应的是character及其在原数组中的index。关键在于观察到character相同的时候优先取index较小的。算法复杂度是O(N * logK).
回复 支持 1 反对 0

使用道具 举报

marthew777 发表于 2015-11-6 09:52:21 | 显示全部楼层
  1.         public List<Character> windowmin(String str, int k){
  2.                 List<Character> res = new ArrayList<>();

  3.                 PriorityQueue<Character> pq = new PriorityQueue<>();. 鍥磋鎴戜滑@1point 3 acres

  4.                 int i = 0;. 1point 3acres 璁哄潧
  5.                 while(i<str.length() || pq.size()>0){
  6.                         if(i<str.length()){
  7.                                 pq.add(str.charAt(i));.鏈枃鍘熷垱鑷1point3acres璁哄潧
  8.                         }
  9.                         if(i++<k) continue;. from: 1point3acres.com/bbs
  10.                         res.add(pq.poll());
  11.                 }
  12.                 return res;. Waral 鍗氬鏈夋洿澶氭枃绔,
  13.         }
复制代码

补充内容 (2015-11-6 09:55):
空间用了 O(k); 时间用了 O(lgk * N)
回复 支持 反对

使用道具 举报

宝贝忆彼岸 发表于 2015-11-6 10:09:40 | 显示全部楼层
marthew777 发表于 2015-11-6 09:52
补充内容 (2015-11-6 09:55):
空间用了 O(k); 时间用了 O(lgk * N)

你是不是看漏了一个条件---(每个字母只能换到距离k以内的地方)?
回复 支持 反对

使用道具 举报

marthew777 发表于 2015-11-6 10:58:19 | 显示全部楼层
宝贝忆彼岸 发表于 2015-11-6 10:09
你是不是看漏了一个条件---(每个字母只能换到距离k以内的地方)?

忘记这个条件了。。. Waral 鍗氬鏈夋洿澶氭枃绔,

用一个set记录当前可以使用就是在范围内的点, 比如most left 的点的index是 left的话,每个iteration,检查left, 只要left+k < i-k, 就循环remove left指向的点;同时维护一个 与这个set 相同size 的 min queue (augmented queue with min value), 每次add/remove element from set,更新 minQueue;

补充内容 (2015-11-6 11:00):
空间使用, O(k)的set 和 minQueue, 时间复杂度是O(kN)
回复 支持 反对

使用道具 举报

marthew777 发表于 2015-11-6 14:40:48 | 显示全部楼层
  1.         public List<Character> windowmin(char[] word, int k){
  2.                 List<Character> res = new ArrayList<>();
  3. . more info on 1point3acres.com
  4.                 int L = word.length;
  5.                 boolean[] used = new boolean[L];

  6.                 for(int start=0, end=k;start<L;){
  7.                         int minIndex = start;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  8.                         for(int i=start;i<=end;i++){
  9.                                 if(used[i]) continue;
  10.                                 if(word[i] < word[minIndex]){. visit 1point3acres.com for more.
  11.                                         minIndex = i;
  12.                                 }. 1point3acres.com/bbs
  13.                         }. more info on 1point3acres.com
  14.                         used[minIndex] = true;.1point3acres缃
  15.                         res.add(word[minIndex]);
  16. . 鍥磋鎴戜滑@1point 3 acres
  17.                         while(start<L && used[start]) start++;
  18.                         if(end<L-1) end++;                        -google 1point3acres
  19.                         if(end-start == 2*k+1) start++;                       
  20.                 }

  21.                 return res;
  22.         }
复制代码
一亩三分地严打"顶""好贴""收藏了"之类的垃圾回复帖!被警告三次,系统会自动封杀ID!

想支持楼主,请点击帖子下方的"好苗""分享""收藏"键,酌情给楼主加大米(系统不扣你自己的分)。
积分不够看不了帖子,请参考论坛导航里的"帮助","新手提纲"里有攒积分指南
回复 支持 反对

使用道具 举报

marthew777 发表于 2015-11-6 14:43:27 | 显示全部楼层
fancy的方法试了一圈下来都不行。。只好乖乖的按照LZ的brute force方法做了。。就这样简单的代码也能写错了debug了好几次,再次被自己的蠢哭了。。
回复 支持 反对

使用道具 举报

 楼主| eeyyabc 发表于 2015-11-6 15:26:10 | 显示全部楼层
marthew777 发表于 2015-11-6 14:43
fancy的方法试了一圈下来都不行。。只好乖乖的按照LZ的brute force方法做了。。就这样简单的代码 ...

不错了。。。. more info on 1point3acres.com
我一轮电面就搞了这么一道,还是brute force。。。最开始还没理解题意一直跟人家讲next permutation,面试的时候都无地自容要被自己蠢哭了。讲思路讲到最后,面试官说,现在实在没时间了,你写code 吧。。。心里流血啊。。。

总觉得这题可以用minHeap或者dequeue或者BST做,有点像输出maximum number with moving window(deque),或者moving average,或者找median的题,或者contain duplicate III,但是又都不是,真是纠结。。。
回复 支持 反对

使用道具 举报

可爱的帕吉 发表于 2015-11-6 15:48:02 | 显示全部楼层
这题就是考察编程语言内置的基本数据结构,知道就会,不知道就不会。
回复 支持 反对

使用道具 举报

fatalme 发表于 2015-11-6 15:52:59 | 显示全部楼层
用两个heap就好了,一个存value,一个存index。
回复 支持 反对

使用道具 举报

matieee 发表于 2015-11-6 16:40:02 | 显示全部楼层
用k+1的min heap怎么样?
像Sort a nearly sorted (or K sorted) array ,. From 1point 3acres bbs
http://www.geeksforgeeks.org/nearly-sorted-algorithm/
回复 支持 反对

使用道具 举报

marthew777 发表于 2015-11-6 22:53:25 | 显示全部楼层
fatalme 发表于 2015-11-6 17:18
一亩三分地严打"顶""好贴""收藏了"之类的垃圾回复帖!被警告三次,系统会自动封杀ID!

想支持楼主,请点 ...
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
学习了!第一次看到的pq和comparator这样用法,给大神跪了。
回复 支持 反对

使用道具 举报

guoqinlong 发表于 2015-11-6 23:27:07 | 显示全部楼层
fatalme 发表于 2015-11-6 17:18
一亩三分地严打"顶""好贴""收藏了"之类的垃圾回复帖!被警告三次,系统会自动封杀ID!

想支持楼主,请点 ...
. more info on 1point3acres.com
好厉害的算法,学习了!
另外问一下,38行,pqi.peek()[1]是不是应该是pqi.peek()[0]?因为数组0元素代表的是字符,1代表的是下标
回复 支持 反对

使用道具 举报

matieee 发表于 2015-11-7 00:19:05 | 显示全部楼层
public String minPermutation(int k, String s){. From 1point 3acres bbs
        if(s == null || s.length() < k || k == 0 ) return "";.1point3acres缃
            char[] str = s.toCharArray();
            PriorityQueue<Character> minHeap = new PriorityQueue<Character>(k+1);
            int index = 0;
            for(int i = 0; i<s.length();i++){
                if(minHeap.size()<k+1){
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷                    minHeap.add(str[i]);
                }
                if(minHeap.size() == k+1){
                    str[index++] = minHeap.remove();
                }
            }
            while(index < s.length()){
                str[index++] = minHeap.remove();
            }
            return new String(str);
    }
回复 支持 反对

使用道具 举报

宝贝忆彼岸 发表于 2015-11-7 00:56:22 | 显示全部楼层
fatalme 发表于 2015-11-6 17:18
一亩三分地严打"顶""好贴""收藏了"之类的垃圾回复帖!被警告三次,系统会自动封杀ID!. from: 1point3acres.com/bbs

想支持楼主,请点 ...

感谢分享思路!!
回复 支持 反对

使用道具 举报

marthew777 发表于 2015-11-7 01:31:42 | 显示全部楼层
matieee 发表于 2015-11-7 00:19
public String minPermutation(int k, String s){
        if(s == null || s.length() < k || k == 0 ) r ...

你这里的代码和我在 “沙发” 的代码是一样的,犯了一个致命错误,看漏了那个条件, "每个字母只能换到距离k以内的地方".. 你可以试试
. From 1point 3acres bbs
test case = "fdcbaabcdefadbcdaea", k = 2
. 鍥磋鎴戜滑@1point 3 acres
正确:[c, b, a, a, b, c, d, e, f, a, d, b, c, d, a, e, a]
错误:[c, b, a, a, b, c, d, d, e, a, d, b, c, d, a, e, a, f, f]

第一个f应该被检查到out of range之后就扔掉的
回复 支持 反对

使用道具 举报

RagingSword 发表于 2015-11-7 01:47:31 | 显示全部楼层
一亩三分地严打"顶""好贴""收藏了"之类的垃圾回复帖!被警告三次,系统会自动封杀ID!
. Waral 鍗氬鏈夋洿澶氭枃绔,
想支持楼主,请点击帖子下方的"好苗""分享""收藏"键,酌情给楼主加大米(系统不扣你自己的分)。
积分不够看不了帖子,请参考论坛导航里的"帮助","新手提纲"里有攒积分指南
回复 支持 反对

使用道具 举报

RagingSword 发表于 2015-11-7 01:48:14 | 显示全部楼层
我也上一个算法
  1. public class Solution {

  2.     public static void main(String[] args){
  3.         String s = "bcdaea";
  4.         int k = 2;
  5.         System.out.println(new Solution().smallest(s, k));
  6.     }


  7.     public String smallest(String s, int k){
  8.         StringBuffer sb = new StringBuffer();
  9.         PriorityQueue<Element> pq = new PriorityQueue<Element>(k, new Comparator<Element>() { 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  10.             @Override
  11.             public int compare(Element o1, Element o2) {
  12.                 if(o1.c != o2.c){
  13.                     return o1.c - o2.c;
  14.                 }.鏈枃鍘熷垱鑷1point3acres璁哄潧
  15.                 return o1.index - o2.index;. 鍥磋鎴戜滑@1point 3 acres
  16.             }
  17.         });-google 1point3acres
  18.         boolean[] visited = new boolean[s.length()];. 1point 3acres 璁哄潧
  19.         HashMap<Integer, Element> hm = new HashMap<Integer, Element>();
  20.         int i = 0;
  21.         for(i = 0; i < Math.min(s.length(), k); ++i){
  22.             Element e = new Element(s.charAt(i), i);
  23.             hm.put(i, e);
  24.             pq.add(e);
  25.         }
  26.         for(int j = i; j < i + s.length(); ++j){
  27.             if(j < s.length()){
  28.                 Element e = new Element(s.charAt(j), j);
  29.                 hm.put(j, e);
  30.                 pq.add(e);
  31.             }. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  32.             if(j - i - k >= 0 && !visited[j-i-k]){
  33.                 sb.append(hm.get(j-i-k).c);
  34.                 pq.remove(hm.get(j-i-k));
  35.                 visited[j-i-k] = true; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  36.             }else{
  37.                 Element e = pq.poll(); 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  38.                 visited[e.index] = true;
  39.                 sb.append(e.c);
  40.             }
  41.         }
  42.         return sb.toString();
  43.     }

  44.     static class Element{
  45.         char c;. 1point3acres.com/bbs
  46.         int index;
  47.         public Element(char c, int index){
  48.             this.c = c;
  49.             this.index = index;. 1point3acres.com/bbs
  50.         }
  51.     }
  52. }
复制代码
回复 支持 反对

使用道具 举报

matieee 发表于 2015-11-7 12:46:12 | 显示全部楼层
marthew777 发表于 2015-11-7 01:31
你这里的代码和我在 “沙发” 的代码是一样的,犯了一个致命错误,看漏了那个条件, "每个字母只能换到距 ...

的确:) 学习了。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-8 12:14

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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