一亩三分地论坛

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

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

Microsoft on-campus interview30分钟

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

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

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

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

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 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
zjhsyfz 发表于 2016-10-19 11:19
好吧,你问了需要考虑这些情况吗?。。。说不定他们之前没想到这,纯属坑你

写了个Java版本的,变量名比较乱不好意思。
基本思路就是first pass先压缩出现多于1的字母,计算出现只有1的字母数目
second pass倒着来遇到出现只有1的字母添加1后再拷,其他直接拷。
大伙帮忙测试下,main里面的输出是a1b1c1d6e15f1g1。

public class CompressString {
    public int compress(char[] s){
        int start = 0, offset = 0, single = 0;. 1point3acres.com/bbs
        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++;
                }else offset = copy(s, offset, s[start], cnt);
                start=end;
            }. Waral 鍗氬鏈夋洿澶氭枃绔,
        }
        int end = offset-1+single;
        int j = end;
        for(int i = offset-1;i>=0;i--){
            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){
        int curr = offset;
        s[curr++]=c;
        int mask = 1;
        while(cnt/10/mask>0) mask*=10;
        while(cnt>0){
            s[curr++]=(char)((cnt/mask)+'0');
            cnt%=mask;
            mask/=10;
        }
        return curr;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
    }

    public static void main(String[] args) {
        CompressString test = new CompressString();. 1point3acres.com/bbs
        char[] s = "abcddddddeeeeeeeeeeeeeeefg".toCharArray();
        int end = test.compress(s);
        System.out.println(new String(s,0,end+1));-google 1point3acres
    }
}

评分

2

查看全部评分

回复 支持 3 反对 0

使用道具 举报

xiaozhuxiaozhu 发表于 2016-10-16 14:46:52 | 显示全部楼层
关注一亩三分地微博:
Warald
这题去去年google实习面经。 刷完leetcode, 足够应付了。
  1. public class microsoft_practice_string_compression {
  2.        
  3.        
  4.         public static String compression(char[] ch). 1point3acres.com/bbs
  5.         {-google 1point3acres
  6.                 if(ch==null) return "";
  7.                 if(ch.length<2) return "";
  8.                 StringBuilder sb = new StringBuilder();
  9.                 char start = ch[0];
  10.                 int counter =1;

  11.                 for(int i =1;i < ch.length;i++)
  12.                 {
  13.                         if(ch[i]==start)
  14.                         {
  15.                                 counter++;
  16.                         }. Waral 鍗氬鏈夋洿澶氭枃绔,
  17.                         else
  18.                         {
  19.                                 sb.append(start);
  20.                                 sb.append(counter);
  21.                                 start = ch[i];. from: 1point3acres.com/bbs
  22.                                 counter=1;-google 1point3acres
  23.                         }
  24.                 }
  25.                 sb.append(start);.鐣欏璁哄潧-涓浜-涓夊垎鍦
  26.                 sb.append(counter);
  27.                 return sb.toString();
  28.         }
  29.         public static void main(String[] args)
  30.         {
  31.                 String str = "aaabbbccc"; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  32.                 char [] test = str.toCharArray();
  33.                 String str1 = "abc";
  34.                 char[] test1 = str1.toCharArray();
  35.                 String str2 = "abbb";
  36.                 char[] test2 = str2.toCharArray();
  37.                 System.out.println(compression(test));
  38.                 System.out.println(compression(test1));
  39.                 System.out.println(compression(test2));
  40.         }
    .鐣欏璁哄潧-涓浜-涓夊垎鍦
  41. }
复制代码

补充内容 (2016-10-16 14:50):
length < 2  ;直接return str, 打错了
回复 支持 1 反对 1

使用道具 举报

xiaozhuxiaozhu 发表于 2016-10-17 06:43:48 | 显示全部楼层
609064231 发表于 2016-10-17 05:58. 鍥磋鎴戜滑@1point 3 acres
你这只考虑了counter是个位数啊.鏈枃鍘熷垱鑷1point3acres璁哄潧
counter大于等于10呢

你自己不能加几行代码?
  1. public class microsoft_practice_string_compression {. 1point 3acres 璁哄潧
  2.         . visit 1point3acres.com for more.
  3.        
  4.         public static void compression(char[] ch)
  5.         {
  6.                 int counter =1;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  7.                 int j =0;. more info on 1point3acres.com
  8. . visit 1point3acres.com for more.
  9.                 for(int i =0;i < ch.length;i++)
  10.                 {
  11.                                 while((i+1<ch.length) && ch[i]==ch[i+1]). 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  12.                                 {
  13.                                         counter++;
  14.                                         i++;
  15.                                 }
  16.                                 ch[j++] = ch[i];
  17.                                 if(counter<10)
  18.                                 {
  19.                                         ch[j++] = (char) (counter+'0');

  20.                                 }
  21.                                 else
  22.                                 {
  23.                                         int temp =0;
  24.                                         int start = j;
  25.                                         while(counter>0).1point3acres缃
  26.                                         {
  27.                                                 temp = counter%10;
  28.                                                 ch[j++] =(char) (temp+'0');
  29.                                                 counter= counter/10;
  30.                                         }
  31.                                         int end = j-1;
  32.                                         while(start < end)
    . From 1point 3acres bbs
  33.                                         {
  34.                                                 char tempChar = ch[start];. 1point3acres.com/bbs
  35.                                                 ch[start] = ch[end];
  36.                                                 ch[end] = tempChar;
  37.                                                 start++;
    . Waral 鍗氬鏈夋洿澶氭枃绔,
  38.                                                 end--; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  39.                                         }. 鍥磋鎴戜滑@1point 3 acres
  40.                                 }
  41.                                 counter=1;

  42.                 }
  43.                 while(j!=ch.length)
  44.                 {
  45.                         ch[j++] ='\0';
  46.                 }
  47.                 for(char c: ch)
  48.                 {
  49.                         System.out.println(c);
  50.                 }
  51.         }. 1point3acres.com/bbs
  52.         public static void main(String[] args)
  53.         {
  54.                 String str = "aaabbbccc";
  55.                 char [] test = str.toCharArray();
  56.                 String str1 = "aaaaab";
  57.                 char[] test1 = str1.toCharArray();.1point3acres缃
  58.                 String str2 = "aaaaba";
  59.                 char[] test2 = str2.toCharArray();. From 1point 3acres bbs
  60.                 String str3 = "aa";
  61.                 char[] test3 = str3.toCharArray();.1point3acres缃
  62.                 String str4 = "aabb";. visit 1point3acres.com for more.
  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");
  71.                 compression(test1);
  72.                 System.out.println("test2");
  73.                 compression(test2);-google 1point3acres
  74.                 System.out.println("test3");
  75.                 compression(test3);
  76.                 System.out.println("test4");
  77.                 compression(test4);
  78.                 System.out.println("test5");
  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呢
求职神器indeed - 在全球最大的求职网站找找适合你的工作?
回复 支持 1 反对 0

使用道具 举报

小飞侠 发表于 2016-10-17 03:06:02 | 显示全部楼层
xiaozhuxiaozhu 发表于 2016-10-16 14:46
这题去去年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~~

下周面on campus, 能不能说一下technical面的是啥...谢谢
回复 支持 反对

使用道具 举报

 楼主| graininear 发表于 2016-10-14 03:36:42 | 显示全部楼层
wtcupup 发表于 2016-10-14 03:26
这道题如果用java的话得用stringbuilder,无法in-place啊
.鏈枃鍘熷垱鑷1point3acres璁哄潧
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面的是啥...谢谢

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])
  11.                                 {
  12.                                         counter++;
  13.                                         i++;
  14.                                 }
    . Waral 鍗氬鏈夋洿澶氭枃绔,
  15.                                 ch[j++] = ch[i];
  16.                                 ch[j++] = (char) (counter+'0');. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  17.                                 if(counter!=1) {
  18.                                         counter=1;
  19.                                 }
  20.                 }
  21.                 while(j!=ch.length)
  22.                 {
  23.                         ch[j++] ='\0';
  24.                 }
  25.                 for(char c: ch)
  26.                 {.鐣欏璁哄潧-涓浜-涓夊垎鍦
  27.                         System.out.println(c);
  28.                 }
  29.         }.鏈枃鍘熷垱鑷1point3acres璁哄潧
  30.         public static void main(String[] args)
  31.         {. 1point3acres.com/bbs
  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");. more info on 1point3acres.com
  51.                 compression(test4);. 1point 3acres 璁哄潧
  52.         }
  53. }
复制代码

补充内容 (2016-10-17 04:43):. From 1point 3acres bbs
如果所有输入都是有效,这个代码应该可以。 如果需要检查输入是否有效,可以加几行代码。
回复 支持 反对

使用道具 举报

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

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

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2017-3-29 11:55

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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