May 2009 - May 2017 论坛八周年-你的足迹,我的骄傲


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

一亩三分地官方iOS手机应用下载
查看: 2744|回复: 20
收起左侧

面经求玉米大米红薯土豆

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

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

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

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

x
经历:第一次电面google drive坏了,interviewer让我找recruiter reschedule,第二次面,碰到同一个国人。

题目:给一个string="bcdaea",和一个int k=2,输出最小的排列,每个字母只能换到距离k以内的地方
举例. Waral 鍗氬鏈夋洿澶氭枃绔,
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"

. visit 1point3acres.com for more.
这种做法是O(KN)的时间复杂度,O(N)空间复杂度。我还想过用minHeap和deque之类的data structure,好像都不大行。. more info on 1point3acres.com
听面试官口气似乎可以不用extra space,O(N)的做法?求大家指教。. 1point 3acres 璁哄潧
最后写了code,这么简单的code中间还写错了,非常不好意思。. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷


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


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


评分

5

查看全部评分

fatalme 发表于 2015-11-6 17:18:21 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
  1. class charComparator implements Comparator<int[]> {
  2.   
  3.   int k = 0;
  4.   -google 1point3acres
  5.   public charComparator(int k){
  6.     this.k = k;
  7.   }

  8.   @Override
  9.   public int compare(int[] o1, int[] o2) {
  10.     if(o1[k] != o2[k]){
  11.       return o1[k] - o2[k];
  12.     }
  13.     return o1[1-k] - o2[1-k];. From 1point 3acres bbs
  14.   }
  15.   
  16. }

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

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

使用道具 举报

可爱的帕吉 发表于 2015-11-6 15:44:10 | 显示全部楼层
关注一亩三分地微博:
Warald
  1. #include <set>
  2. #include <stdio.h>
  3. #include <string.h>
  4. #include <utility>
  5. #include <algorithm>-google 1point3acres
  6. .鏈枃鍘熷垱鑷1point3acres璁哄潧
  7. using namespace std;

  8. const int MAXN = 10000;

  9. char a[MAXN + 1], c[MAXN + 1];
  10. bool b[MAXN]; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  11. set<pair<char, int> > s;
  12. int N, K;
  13. 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  14. int main() {
  15.   scanf("%s %d", a, &K);
  16.   N = strlen(a);
    . from: 1point3acres.com/bbs
  17.   memset(b, 0, sizeof(bool) * N);
  18.   for (int i = 0; i < min(K, N); ++i)
  19.     s.insert(make_pair(a[i], i));
  20.   for (int i = 0; i < N; ++i) {
  21.     if (i + K < N)
  22.       s.insert(make_pair(a[i + K], i + K));
  23.     if (i - K >= 0 && !b[i - K]) {. 1point3acres.com/bbs
  24.       c[i] = a[i - K]; . 1point 3acres 璁哄潧
  25.       b[i - K] = true;
  26.       s.erase(make_pair(a[i - K], i - K));
  27.     } else {. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  28.       c[i] = s.begin() -> first;
  29.       b[s.begin() -> second] = true;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  30.       s.erase(s.begin());
  31.     }   . 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  32.   }
  33.   c[N] = '\0';
  34.   printf("%s\n", c);
  35.   return 0;
  36. }
复制代码
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<>();.1point3acres缃
  4. .鐣欏璁哄潧-涓浜-涓夊垎鍦
  5.                 int i = 0;. 鍥磋鎴戜滑@1point 3 acres
  6.                 while(i<str.length() || pq.size()>0){
  7.                         if(i<str.length()){
  8.                                 pq.add(str.charAt(i));
  9.                         }
  10.                         if(i++<k) continue;
  11.                         res.add(pq.poll());. 1point3acres.com/bbs
  12.                 }
  13.                 return res;.鐣欏璁哄潧-涓浜-涓夊垎鍦
  14.         }
复制代码

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

使用道具 举报

宝贝忆彼岸 发表于 2015-11-6 10:09:40 | 显示全部楼层
marthew777 发表于 2015-11-6 09:52. visit 1point3acres.com for more.
补充内容 (2015-11-6 09:55):. visit 1point3acres.com for more.
空间用了 O(k); 时间用了 O(lgk * N)
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
你是不是看漏了一个条件---(每个字母只能换到距离k以内的地方)?
回复 支持 反对

使用道具 举报

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

忘记这个条件了。。.鏈枃鍘熷垱鑷1point3acres璁哄潧
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
用一个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. .1point3acres缃
  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;-google 1point3acres
  10.                                 if(word[i] < word[minIndex]){
  11.                                         minIndex = i;. Waral 鍗氬鏈夋洿澶氭枃绔,
  12.                                 }
  13.                         }
  14.                         used[minIndex] = true;.鏈枃鍘熷垱鑷1point3acres璁哄潧
  15.                         res.add(word[minIndex]);. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

  16.                         while(start<L && used[start]) start++;
  17.                         if(end<L-1) end++;                       
  18.                         if(end-start == 2*k+1) start++;                       
  19.                 }

  20.                 return res;.鏈枃鍘熷垱鑷1point3acres璁哄潧
  21.         }
复制代码
一亩三分地严打"顶""好贴""收藏了"之类的垃圾回复帖!被警告三次,系统会自动封杀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方法做了。。就这样简单的代码 ...

不错了。。。
我一轮电面就搞了这么一道,还是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 ,
http://www.geeksforgeeks.org/nearly-sorted-algorithm/
回复 支持 反对

使用道具 举报

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

想支持楼主,请点 ...
. 1point 3acres 璁哄潧
学习了!第一次看到的pq和comparator这样用法,给大神跪了。
回复 支持 反对

使用道具 举报

guoqinlong 发表于 2015-11-6 23:27:07 | 显示全部楼层
fatalme 发表于 2015-11-6 17:18
一亩三分地严打"顶""好贴""收藏了"之类的垃圾回复帖!被警告三次,系统会自动封杀ID!. from: 1point3acres.com/bbs
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
想支持楼主,请点 ...

好厉害的算法,学习了!. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
另外问一下,38行,pqi.peek()[1]是不是应该是pqi.peek()[0]?因为数组0元素代表的是字符,1代表的是下标
回复 支持 反对

使用道具 举报

matieee 发表于 2015-11-7 00:19:05 | 显示全部楼层
public String minPermutation(int k, String s){
        if(s == null || s.length() < k || k == 0 ) return "";
            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. more info on 1point3acres.com
一亩三分地严打"顶""好贴""收藏了"之类的垃圾回复帖!被警告三次,系统会自动封杀ID!

想支持楼主,请点 ...

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

使用道具 举报

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: 1point3acres.com/bbs
. 1point 3acres 璁哄潧
test case = "fdcbaabcdefadbcdaea", k = 2. visit 1point3acres.com for more.

正确:[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!. 鍥磋鎴戜滑@1point 3 acres

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

使用道具 举报

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

  2. .鏈枃鍘熷垱鑷1point3acres璁哄潧
  3.     public static void main(String[] args){. 鍥磋鎴戜滑@1point 3 acres
  4.         String s = "bcdaea";
  5.         int k = 2;
  6.         System.out.println(new Solution().smallest(s, k));
  7.     }


  8.     public String smallest(String s, int k){
  9.         StringBuffer sb = new StringBuffer();
  10.         PriorityQueue<Element> pq = new PriorityQueue<Element>(k, new Comparator<Element>() {
  11.             @Override
  12.             public int compare(Element o1, Element o2) {
  13.                 if(o1.c != o2.c){
  14.                     return o1.c - o2.c;
  15.                 }
  16.                 return o1.index - o2.index;
  17.             }
  18.         });
  19.         boolean[] visited = new boolean[s.length()];
  20.         HashMap<Integer, Element> hm = new HashMap<Integer, Element>();
  21.         int i = 0;
  22.         for(i = 0; i < Math.min(s.length(), k); ++i){
  23.             Element e = new Element(s.charAt(i), i);
  24.             hm.put(i, e);
  25.             pq.add(e);
  26.         }
  27.         for(int j = i; j < i + s.length(); ++j){
  28.             if(j < s.length()){-google 1point3acres
  29.                 Element e = new Element(s.charAt(j), j);
  30.                 hm.put(j, e);
  31.                 pq.add(e);
  32.             }
  33.             if(j - i - k >= 0 && !visited[j-i-k]){
  34.                 sb.append(hm.get(j-i-k).c);
  35.                 pq.remove(hm.get(j-i-k));-google 1point3acres
  36.                 visited[j-i-k] = true;. more info on 1point3acres.com
  37.             }else{
  38.                 Element e = pq.poll();
  39.                 visited[e.index] = true;.1point3acres缃
  40.                 sb.append(e.c);
  41.             }
  42.         }
  43.         return sb.toString();
  44.     }

  45.     static class Element{. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  46.         char c;
  47.         int index;
  48.         public Element(char c, int index){
  49.             this.c = c;
  50.             this.index = index;
  51.         }
  52.     }
  53. }
复制代码
回复 支持 反对

使用道具 举报

matieee 发表于 2015-11-7 12:46:12 | 显示全部楼层
marthew777 发表于 2015-11-7 01:31
你这里的代码和我在 “沙发” 的代码是一样的,犯了一个致命错误,看漏了那个条件, "每个字母只能换到距 ...
. 鍥磋鎴戜滑@1point 3 acres
的确:) 学习了。
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-5-25 13:21

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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