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


一亩三分地论坛

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

Microsoft on-campus interview30分钟

[复制链接] |试试Instant~ |关注本帖
graininear 发表于 2016-10-14 03:22:38 | 显示全部楼层 |阅读模式

2016(10-12月) 码农类 本科 实习@Microsoft - 校园招聘会 - 校园招聘会 |Other其他

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

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

x
30分钟前面了Microsoft的 OnCampus Interview。behavioral question就是遇到最大困难,讲讲project之类,没有问很,
然后白板做题: String Compression : aaabbbaaa -> a3b3a3,inplace.
本来看面经以为会问的比较简单,但这个题至少对我来说并不简单,时间也很紧,不敢光想太久不说话,反正还是经验欠缺吧。  
满脑子里想的都是leetcode的array 去重,但发现比那个难, 告诉了面试官用two pointer, 但具体while loop里面的东西没有想得很清楚, 卡了半天,以为面试官会提示,但他也不鸟我。
最后写完code也没让我分析也没让我test直接让我问他问题, 应该是没写出对的结果。
哎,应该是没onsite了, 光leetcode还是不行啊, 实力经验还是不够。   继续去投其他公司了。. 1point3acres.com/bbs
最后求一波大米。。穷的连面经都搜索不了了。


补充内容 (2016-10-19 04:17):
哎被拒了。看来跟微软无缘了,只能继续加油了

评分

6

查看全部评分

本帖被以下淘专辑推荐:

JohnDoe 发表于 2016-10-19 13:48:31 | 显示全部楼层
zjhsyfz 发表于 2016-10-19 11:19. From 1point 3acres bbs
好吧,你问了需要考虑这些情况吗?。。。说不定他们之前没想到这,纯属坑你

写了个Java版本的,变量名比较乱不好意思。
基本思路就是first pass先压缩出现多于1的字母,计算出现只有1的字母数目
second pass倒着来遇到出现只有1的字母添加1后再拷,其他直接拷。.鐣欏璁哄潧-涓浜-涓夊垎鍦
大伙帮忙测试下,main里面的输出是a1b1c1d6e15f1g1。
. From 1point 3acres bbs
public class CompressString {
    public int compress(char[] s){
        int start = 0, offset = 0, single = 0;
        for(int end = 1;end<=s.length; end++){
            if(end==s.length||s[end]!=s[start]){
                int cnt = end-start;
                if(cnt==1){.鐣欏璁哄潧-涓浜-涓夊垎鍦
                    s[offset++]=s[start];
                    single++;
. visit 1point3acres.com for more.                }else offset = copy(s, offset, s[start], cnt);. from: 1point3acres.com/bbs
                start=end;
            }
        }
        int end = offset-1+single;
        int j = end;
        for(int i = offset-1;i>=0;i--){. 1point3acres.com/bbs
            if(Character.isLetter(s)&&(i+1==offset||Character.isLetter(s[i+1]))){
                s[j--]='1';
            }
            s[j--]=s;
        }
        return end;
    }

    private int copy(char[] s, int offset, char c, int cnt){. visit 1point3acres.com for more.
        int curr = offset;
        s[curr++]=c;
        int mask = 1;
        while(cnt/10/mask>0) mask*=10;
        while(cnt>0){. visit 1point3acres.com for more.
            s[curr++]=(char)((cnt/mask)+'0');-google 1point3acres
            cnt%=mask;
            mask/=10;
        }
        return curr;
    }

    public static void main(String[] args) {.1point3acres缃
        CompressString test = new CompressString();. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
        char[] s = "abcddddddeeeeeeeeeeeeeeefg".toCharArray();
        int end = test.compress(s);
        System.out.println(new String(s,0,end+1));. more info on 1point3acres.com
    }
}

评分

2

查看全部评分

回复 支持 3 反对 0

使用道具 举报

xiaozhuxiaozhu 发表于 2016-10-16 14:46:52 | 显示全部楼层
这题去去年google实习面经。 刷完leetcode, 足够应付了。
  1. public class microsoft_practice_string_compression {
  2.         . 1point3acres.com/bbs
  3.        
  4.         public static String compression(char[] ch)
  5.         {
  6.                 if(ch==null) return ""; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  7.                 if(ch.length<2) return "";. 鍥磋鎴戜滑@1point 3 acres
  8.                 StringBuilder sb = new StringBuilder();
  9.                 char start = ch[0];. Waral 鍗氬鏈夋洿澶氭枃绔,
  10.                 int counter =1;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  11. . From 1point 3acres bbs
  12.                 for(int i =1;i < ch.length;i++). 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  13.                 {
  14.                         if(ch[i]==start)
  15.                         {
  16.                                 counter++;. 1point3acres.com/bbs
  17.                         }. from: 1point3acres.com/bbs
  18.                         else
  19.                         {
  20.                                 sb.append(start);
  21.                                 sb.append(counter);
  22.                                 start = ch[i];
  23.                                 counter=1;.鐣欏璁哄潧-涓浜-涓夊垎鍦
  24.                         }
  25.                 }
  26.                 sb.append(start);
  27.                 sb.append(counter);
  28.                 return sb.toString();
  29.         }
  30.         public static void main(String[] args)
  31.         {
  32.                 String str = "aaabbbccc";
  33.                 char [] test = str.toCharArray();
  34.                 String str1 = "abc";
  35.                 char[] test1 = str1.toCharArray();
  36.                 String str2 = "abbb";
  37.                 char[] test2 = str2.toCharArray();
  38.                 System.out.println(compression(test));
  39.                 System.out.println(compression(test1));. 1point 3acres 璁哄潧
  40.                 System.out.println(compression(test2));
  41.         }
  42. }
复制代码
. from: 1point3acres.com/bbs
补充内容 (2016-10-16 14:50):
length < 2  ;直接return str, 打错了
回复 支持 1 反对 1

使用道具 举报

xiaozhuxiaozhu 发表于 2016-10-17 06:43:48 | 显示全部楼层
609064231 发表于 2016-10-17 05:58
你这只考虑了counter是个位数啊
counter大于等于10呢

你自己不能加几行代码?
  1. public class microsoft_practice_string_compression {. Waral 鍗氬鏈夋洿澶氭枃绔,
  2.        
  3.        
  4.         public static void compression(char[] ch)
  5.         {
  6.                 int counter =1;. From 1point 3acres bbs
  7.                 int j =0;

  8.                 for(int i =0;i < ch.length;i++). 鍥磋鎴戜滑@1point 3 acres
  9.                 {
  10.                                 while((i+1<ch.length) && ch[i]==ch[i+1])
  11.                                 {. 1point3acres.com/bbs
  12.                                         counter++;
  13.                                         i++;
  14.                                 }
  15.                                 ch[j++] = ch[i];
  16.                                 if(counter<10)
  17.                                 {
  18.                                         ch[j++] = (char) (counter+'0');

  19.                                 }
  20.                                 else
  21.                                 {
  22.                                         int temp =0;. visit 1point3acres.com for more.
  23.                                         int start = j;. visit 1point3acres.com for more.
  24.                                         while(counter>0)
  25.                                         {
  26.                                                 temp = counter%10;
  27.                                                 ch[j++] =(char) (temp+'0');
  28.                                                 counter= counter/10;
  29.                                         }
  30.                                         int end = j-1; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  31.                                         while(start < end)
  32.                                         {
  33.                                                 char tempChar = ch[start];
  34.                                                 ch[start] = ch[end];
  35.                                                 ch[end] = tempChar;
  36.                                                 start++;
  37.                                                 end--;
  38.                                         }
  39.                                 }
  40.                                 counter=1;
  41. . more info on 1point3acres.com
  42.                 }
  43.                 while(j!=ch.length)
  44.                 {. more info on 1point3acres.com
  45.                         ch[j++] ='\0';. from: 1point3acres.com/bbs
  46.                 }
  47.                 for(char c: ch)
  48.                 {
  49.                         System.out.println(c);. From 1point 3acres bbs
  50.                 }. Waral 鍗氬鏈夋洿澶氭枃绔,
  51.         }
  52.         public static void main(String[] args). 1point 3acres 璁哄潧
  53.         {
  54.                 String str = "aaabbbccc";
  55.                 char [] test = str.toCharArray();
  56.                 String str1 = "aaaaab";
  57.                 char[] test1 = str1.toCharArray();
  58.                 String str2 = "aaaaba";
  59.                 char[] test2 = str2.toCharArray();
  60.                 String str3 = "aa";
  61.                 char[] test3 = str3.toCharArray();
  62.                 String str4 = "aabb";. Waral 鍗氬鏈夋洿澶氭枃绔,
  63.                 char[] test4 = str4.toCharArray();
  64.                 String str5 = "aaaaaabbbbbbbbbbbbbbbbbbbbbcccccccccccccc";
  65.                 char[] test5 = str5.toCharArray();
  66.                 String str6 = "hhhhhhhhhhhhhhhh";
  67.                 char[] test6 = str6.toCharArray();
  68.                 System.out.println("test");
  69.                 compression(test);
  70.                 System.out.println("test1");. 1point 3acres 璁哄潧
  71.                 compression(test1);
  72.                 System.out.println("test2");-google 1point3acres
  73.                 compression(test2);
  74.                 System.out.println("test3");
  75.                 compression(test3);.鏈枃鍘熷垱鑷1point3acres璁哄潧
  76.                 System.out.println("test4");.鏈枃鍘熷垱鑷1point3acres璁哄潧
  77.                 compression(test4);
  78.                 System.out.println("test5");-google 1point3acres
  79.                 compression(test5);
  80.                 System.out.println("test6");
  81.                 compression(test6);. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  82.         }. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  83. }
复制代码
回复 支持 1 反对 0

使用道具 举报

609064231 发表于 2016-10-17 05:58:30 | 显示全部楼层
xiaozhuxiaozhu 发表于 2016-10-17 04:42
你意思是这个? 鏉ユ簮涓浜.涓夊垎鍦拌鍧.

补充内容 (2016-10-17 04:43):

你这只考虑了counter是个位数啊
counter大于等于10呢
回复 支持 1 反对 0

使用道具 举报

小飞侠 发表于 2016-10-17 03:06:02 | 显示全部楼层
xiaozhuxiaozhu 发表于 2016-10-16 14:46. from: 1point3acres.com/bbs
这题去去年google实习面经。 刷完leetcode, 足够应付了。
.鐣欏璁哄潧-涓浜-涓夊垎鍦
题目说了是in place, Java不能用stringbuilder或者stringbuffer,也就是说函数是这样,public void compress(char []array),没有返回值,直接在array上面改。还有就是题目不会给invalid的input,比如abc,要求输出a1b1c1,这样输出的char超过了给的数组的长度,这样input就是invalid,所以不会有这样的input。
回复 支持 1 反对 0

使用道具 举报

wtcupup 发表于 2016-10-14 03:26:03 | 显示全部楼层
这道题如果用java的话得用stringbuilder,无法in-place啊
回复 支持 反对

使用道具 举报

ben_viv 发表于 2016-10-14 03:32:27 | 显示全部楼层
同样是今早面的,同一道behaviour question~~
回复 支持 反对

使用道具 举报

haveto 发表于 2016-10-14 03:33:39 | 显示全部楼层
inplace 的意思是直接在aaabbbaaa上面改?所以是第二个a替换成3 第三个a替换成b 最后多余的截掉 这种??
回复 支持 反对

使用道具 举报

genius1wjc 发表于 2016-10-14 03:34:55 | 显示全部楼层
ben_viv 发表于 2016-10-14 03:32
同样是今早面的,同一道behaviour question~~
. Waral 鍗氬鏈夋洿澶氭枃绔,
下周面on campus, 能不能说一下technical面的是啥...谢谢
回复 支持 反对

使用道具 举报

 楼主| graininear 发表于 2016-10-14 03:36:42 | 显示全部楼层
wtcupup 发表于 2016-10-14 03:26
这道题如果用java的话得用stringbuilder,无法in-place啊

career cup好像有,刚搜了一下,哎,感觉把情况写全不简单
回复 支持 反对

使用道具 举报

say543 发表于 2016-10-14 12:11:44 | 显示全部楼层
楼主能贴个carrer link吗 私心觉得 in place 就算 c++也无法解 abc 如果要变成a1b1c1 感觉就无法in place?
回复 支持 反对

使用道具 举报

 楼主| graininear 发表于 2016-10-14 13:08:41 | 显示全部楼层
我没说清楚。。输入是char array, 只是我只在careercup看到了这道题,叫String Compression, 所以就直接用这个名字了。
回复 支持 反对

使用道具 举报

 楼主| graininear 发表于 2016-10-14 13:09:16 | 显示全部楼层
say543 发表于 2016-10-14 12:11
楼主能贴个carrer link吗 私心觉得 in place 就算 c++也无法解 abc 如果要变成a1b1c1 感觉就无法in place?


我没说清楚。。输入是char array, 只是我只在careercup看到了这道题,叫String Compression, 所以就直接用这个名字了。
回复 支持 反对

使用道具 举报

小飞侠 发表于 2016-10-15 04:26:52 | 显示全部楼层
想问一下,你说输入是 char array,那要写的函数是不是这个形式啊: public void compression(char []array)?然后in place要求在char []array上,而不是返回一个string?有时间上的要求么?感觉O(n)的char array in place写不出来啊,career cup上面给的输入是string?谢谢
回复 支持 反对

使用道具 举报

 楼主| graininear 发表于 2016-10-16 01:11:32 | 显示全部楼层
小飞侠 发表于 2016-10-15 04:26
想问一下,你说输入是 char array,那要写的函数是不是这个形式啊: public void compression(char []array) ...

对void函数, 我反正觉得不太好写。。用i,j两个pointer,然后用insertindex = 0,慢慢加上去,感觉应该能出来吧, careercup的确实不好,不清楚,还经常有bug,我也没找到这道题特别好的solution
回复 支持 反对

使用道具 举报

ben_viv 发表于 2016-10-16 02:52:21 | 显示全部楼层
genius1wjc 发表于 2016-10-14 03:34
下周面on campus, 能不能说一下technical面的是啥...谢谢
. from: 1point3acres.com/bbs
http://www.1point3acres.com/bbs/thread-205799-1-1.html
回复 支持 反对

使用道具 举报

say543 发表于 2016-10-16 14:24:42 | 显示全部楼层
graininear 发表于 2016-10-16 01:11
对void函数, 我反正觉得不太好写。。用i,j两个pointer,然后用insertindex = 0,慢慢加上去,感觉应该 ...


inplace 还是觉得c++ 无法解...
回复 支持 反对

使用道具 举报

609064231 发表于 2016-10-16 22:54:13 | 显示全部楼层
say543 发表于 2016-10-14 12:11
楼主能贴个carrer link吗 私心觉得 in place 就算 c++也无法解 abc 如果要变成a1b1c1 感觉就无法in place?

我觉得如果是abc那么输出应该还是abc吧 如果输出a1b1c1那么反而达到跟compression相反的目的了
回复 支持 反对

使用道具 举报

 楼主| graininear 发表于 2016-10-17 03:15:24 | 显示全部楼层
xiaozhuxiaozhu 发表于 2016-10-16 14:46
这题去去年google实习面经。 刷完leetcode, 足够应付了。

面试官说inplace,应该不能用stringbuilder,要原来char array上直接修改,比如:[a,a,a,b,b,b] ->[a,3,b,3, null,null]。 请问你知道这种情况的话应该怎么写么?
回复 支持 反对

使用道具 举报

xiaozhuxiaozhu 发表于 2016-10-17 04:42:51 | 显示全部楼层
graininear 发表于 2016-10-17 03:15
面试官说inplace,应该不能用stringbuilder,要原来char array上直接修改,比如:[a,a,a,b,b,b] ->[a,3,b ...

你意思是这个?
  1. public class microsoft_practice_string_compression {
  2.        
  3.        
  4.         public static void compression(char[] ch)
  5.         {
  6.                 int counter =1;
  7.                 int j =0;

  8.                 for(int i =0;i < ch.length;i++)
  9.                 {
  10.                                 while((i+1<ch.length) && ch[i]==ch[i+1]). 1point 3acres 璁哄潧
  11.                                 {
  12.                                         counter++;
  13.                                         i++;
  14.                                 } 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  15.                                 ch[j++] = ch[i];
  16.                                 ch[j++] = (char) (counter+'0');. more info on 1point3acres.com
  17.                                 if(counter!=1) {
  18.                                         counter=1;
  19.                                 }. From 1point 3acres bbs
  20.                 }. 1point3acres.com/bbs
  21.                 while(j!=ch.length)
  22.                 {
  23.                         ch[j++] ='\0';. from: 1point3acres.com/bbs
  24.                 }
  25.                 for(char c: ch)
  26.                 {
  27.                         System.out.println(c);
  28.                 }. more info on 1point3acres.com
  29.         }. from: 1point3acres.com/bbs
  30.         public static void main(String[] args)
  31.         {
  32.                 String str = "aaabbbccc";
  33.                 char [] test = str.toCharArray();
  34.                 String str1 = "aaaaab";
  35.                 char[] test1 = str1.toCharArray();
  36.                 String str2 = "aaaaba";
  37.                 char[] test2 = str2.toCharArray();
  38.                 String str3 = "aa";
  39.                 char[] test3 = str3.toCharArray();
  40.                 String str4 = "aabb";
  41.                 char[] test4 = str4.toCharArray();
  42.                 System.out.println("test");
  43.                 compression(test);
  44.                 System.out.println("test1");.鐣欏璁哄潧-涓浜-涓夊垎鍦
  45.                 compression(test1);
  46.                 System.out.println("test2");
  47.                 compression(test2);
  48.                 System.out.println("test3");
  49.                 compression(test3);
  50.                 System.out.println("test4");
  51.                 compression(test4);
  52.         }
  53. }
复制代码

补充内容 (2016-10-17 04:43):.鐣欏璁哄潧-涓浜-涓夊垎鍦
如果所有输入都是有效,这个代码应该可以。 如果需要检查输入是否有效,可以加几行代码。
回复 支持 反对

使用道具 举报

xiaozhuxiaozhu 发表于 2016-10-17 04:44:55 | 显示全部楼层
小飞侠 发表于 2016-10-17 03:06. 1point 3acres 璁哄潧
题目说了是in place, Java不能用stringbuilder或者stringbuffer,也就是说函数是这样,public void comp ...

返回值是void 是char[] 和是不是in place没有关系,好么。
我可以inplace 原array, 最后返回array啊。
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-11-24 19:20

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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