查看: 3629|回复: 14
收起左侧

[高频题] 微软近期高频面试题分享 + 分析(七)

    |只看干货
本楼: 👍   100% (15)
 
 
0% (0)   👎
全局: 👍   99% (325)
 
 
0% (2)    👎

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

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
最近来巨硬面试的小朋友通过概率实在太低了,代码老是写不对,我们组已经十连拒了,不得不感叹,现在出的面试题越来越难了,我决定还是上来地里透透题,说点最近我们组面试常考高频题和解析(毕竟岗位机会也不能都让三锅霸占了对不)。招人艰难,看微软机会的小伙伴,也欢迎LinkedIn勾搭:
https://www.linkedin.com/in/andy-yongjian-deng-212977200/


注意打招呼的时候备注一下,方便识别友军,hhhh。

带娃有压力,尽量保持一周两更,大家海涵。


往期链接:

微软近期高频面试题分享 + 分析(一)

微软近期高频面试题分享 + 分析(二)

微软近期高频面试题分享 + 分析(三)

微软近期高频面试题分享 + 分析(四)

微软近期高频面试题分享 + 分析(五)

微软近期高频面试题分享 + 分析(六)

评分

参与人数 12大米 +16 收起 理由
满船清梦压星河 + 1 给你点个赞!
linlaw + 3 很有用的信息!
moveingsun + 1 很有用的信息!
turtle33333 + 1 谢谢分享!
cuteripperkk + 1 赞一个
jameszhan2019 + 1 赞一个
xzhang0980 + 1 赞一个
jessyyilin + 1 赞一个

查看全部评分


上一篇:Pramp Refer 链接 大家一起来Mock Interview吧
下一篇:求推荐一个家用的server,自己做项目用
 楼主| YankeeDoodle 2021-6-8 10:17:16 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   99% (325)
 
 
0% (2)    👎
字符串-兄弟字符串

如果两个字符串的字符一样,但是顺序不一样,被认为是兄弟字符串,问如何在迅速匹配兄弟字符串(如,bad和adb就是兄弟字符串)
回复

使用道具 举报

 楼主| YankeeDoodle 2021-6-9 10:25:46 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   99% (325)
 
 
0% (2)    👎
YankeeDoodle 发表于 2021-6-8 10:17
字符串-兄弟字符串

如果两个字符串的字符一样,但是顺序不一样,被认为是兄弟字符串,问如何在迅速匹配 ...

1、O(n*m)的轮询方法

判断string2中的字符是否在string1中: String 1: ABCDEFGHLMNOPQRS String 2: DCGSRQPO

判断一个字符串是否在另一个字符串中,最直观也是最简单的思路是,针对第二个字符串string2中每一个字符,与第一个字符串string1中每个字符依次轮询比较,看它是否在第一个字符串string1中。
回复

使用道具 举报

 楼主| YankeeDoodle 2021-6-10 10:31:46 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   99% (325)
 
 
0% (2)    👎
YankeeDoodle 发表于 2021-6-8 10:17
字符串-兄弟字符串

如果两个字符串的字符一样,但是顺序不一样,被认为是兄弟字符串,问如何在迅速匹配 ...

2、 O(mlogm)+O(nlogn)+O(m+n)的排序方法

一个稍微好一点的方案是先对这两个字符串的字母进行排序,然后同时对两个字串依次轮询。两个字串的排序需要(常规情况)O(mlogm) + O(nlogn)次操作,之后的线性扫描需要O(m+n)次操作。

步骤如下: 1、判断两个字符串的长度是否一样,如果不一样则退出。 2、每个字符串按字符排序,如acb排序之后是abc,如果是兄弟字符串的话,排序之后是一样的。
回复

使用道具 举报

wm389751584x 2021-6-11 08:13:22 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   0% (0)
 
 
0% (0)    👎
好人一生平安
回复

使用道具 举报

飞翔的小狐狸 2021-6-11 09:11:51 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   98% (464)
 
 
1% (5)    👎
wow楼主好人一生平安啊~
回复

使用道具 举报

 楼主| YankeeDoodle 2021-6-11 10:01:22 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   99% (325)
 
 
0% (2)    👎
YankeeDoodle 发表于 2021-6-8 10:17
字符串-兄弟字符串

如果两个字符串的字符一样,但是顺序不一样,被认为是兄弟字符串,问如何在迅速匹配 ...

3、Hashmap
建两个hash数组,分别记录两个字符串,然后比较两个数组的每一项是否相同,有不同的说明不是兄弟字符串
  1. #include<iostream>
  2. #include<stdio.h>
  3. #include<stdlib.h>
  4. #include<string.h>
  5. using namespace std;  

  6. int main()
  7. {
  8.         int hash1[256],hash2[256],i,len1,len2;
  9.         char str1[100],str2[100];
  10.        
  11.         printf("请输入2个字符串:(0结束)\n");
  12.         while(1)
  13.         {
  14.                 //输入
  15.                 scanf("%s",str1);
  16.                 if(!strcmp(str1,"0")) break;
  17.                 scanf("%s",str2);
  18.                
  19.                 //比较长度
  20.                 len1=strlen(str1);
  21.                 len2=strlen(str2);
  22.                 if(len1!=len2)
  23.                 {
  24.                         printf("%s,%s,二者不是兄弟字符串\n",str1,str2);
  25.                         continue;
  26.                 }
  27.                  
  28.                 //字符是否相同
  29.                 memset(hash1,0,sizeof(hash1));
  30.                 memset(hash2,0,sizeof(hash2));
  31.                 for(i=0;i<len1;i++)
  32.                 {
  33.                         hash1[str1[i]]++;
  34.                         hash2[str2[i]]++;
  35.                 }
  36.                 for(i=0;i<255;i++)
  37.                 {
  38.                         if(hash1[i]!=hash2[i])//不同
  39.                                 break;
  40.                 }
  41.                 if(i==255)
  42.                         printf("%s,%s,二者是兄弟字符串\n",str1,str2);
  43.                 else
  44.                         printf("%s,%s,二者不是兄弟字符串\n",str1,str2);
  45.         }
  46. }
  47. /*
  48. bad abd
  49. abcd abc
  50. aabbccdd abcdabcd
  51. abcdabc aabbccc
  52. aaa bbb
  53. ababa babab
  54. ababa aabba
  55. 0
  56. */
复制代码
回复

使用道具 举报

 楼主| YankeeDoodle 2021-6-12 10:17:06 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   99% (325)
 
 
0% (2)    👎
4、 O(n)到 O(n+m)的素数方法
你可能会这么想:O(n+m)是你能得到的最好的结果了,至少要对每个字母至少访问一次才能完成这项操作,而上一节最后的俩个方案是刚好是对每个字母只访问一次。

给26个字符依次赋予质数。质数是比较特殊的一堆数字,它们只能被1和本身整除。以给a赋值2、给b赋值3、给c赋值5、给d赋值7、给e赋值11、给f赋值13。

加法:两个字符串中的所有字符都赋值了,接着让它们各自相加,如果两个字符串得出的结果是一样的,那它们是兄弟字符串。但是,b+f=3+13=16;c+e=5+11=16,所以有误;

乘法:两个字符串中的所有字符让它们各自相乘,方法是对的,但是会溢出,所以要大整数处理了;用平方和或者立方和:考虑平方和会不会解决加法有误,乘法溢出:b*b+f*f=3*3+13*13=178;c*c+e*e=5*5+11*11=146

然后——轮询第二个字符串,用每个字母除它。如果除的结果有余数,这说明有不匹配的字母。如果整个过程中没有余数,你应该知道它是第一个字串恰好的子集了。

如果是加法,那么使用一个类似于set的数据结构来记录字符串中字母出现的频次即可,但是空间开销会比素数更大(素数法要求分配素数也是需要空间的,虽然是常数级)。代码如下:
  1. /*
  2. 如果两个字符串的字符一样,但是顺序不一样,被认为是兄弟字符串,
  3. 问如何在迅速匹配兄弟字符串(如,bad和adb就是兄弟字符串)。
  4. */
  5. #include <iostream>
  6. using namespace std;

  7. int isBroStr(char *str1, char *str2)
  8. {
  9.     int a[26 * 2] = {0};
  10.     int i, strLen;
  11.    
  12.     if (!str1 && !str2)
  13.         return 1;
  14.     else if (!str1 || !str2)
  15.         return 0;
  16.     else
  17.     {
  18.         if(strlen(str1) != strlen(str2))
  19.             return 0;
  20.         strLen = strlen(str1);
  21.         for(i = 0; i < strLen; i++)
  22.         {
  23.             ++a[str1[i] - 'A'];
  24.             --a[str2[i] - 'A'];
  25.         }
  26.         for(i = 0; i < 26 * 2; i++)
  27.             if (a[i])
  28.                 return 0;
  29.         return 1;
  30.     }        
  31. }

  32. int main()
  33. {
  34.     char *str1 = "asdfaabAAB";
  35.     char *str2 = "asdfAABaab";
  36.     if (isBroStr(str1, str2))
  37.         cout << " String 1 and String 2 are brothers!" << endl;
  38.     else
  39.         cout << " String 1 and String 2 are not brothers!" << endl;
  40.     system("PAUSE");
  41.     return 0;
  42. }
复制代码
回复

使用道具 举报

grain0217 2021-6-13 22:38:43 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   0% (0)
 
 
0% (0)    👎
攒👍🏻
回复

使用道具 举报

 楼主| YankeeDoodle 2021-6-18 09:56:25 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   99% (325)
 
 
0% (2)    👎
橘子问题

厨房里总共有 n 个橘子,你决定每一天选择如下方式之一吃这些橘子:

吃掉一个橘子。
如果剩余橘子数 n 能被 2 整除,那么你可以吃掉 n/2 个橘子。
如果剩余橘子数 n 能被 3 整除,那么你可以吃掉 2*(n/3) 个橘子。 每天你只能从以上 3 种方案中选择一种方案。
请你返回吃掉所有 n 个橘子的最少天数。
  1. 示例 1:
  2. 输入:n = 10
  3. 输出:4
  4. 解释:你总共有 10 个橘子。
  5. 第 1 天:吃 1 个橘子,剩余橘子数 10 - 1 = 9。
  6. 第 2 天:吃 6 个橘子,剩余橘子数 9 - 2*(9/3) = 9 - 6 = 3。(9 可以被 3 整除)
  7. 第 3 天:吃 2 个橘子,剩余橘子数 3 - 2*(3/3) = 3 - 2 = 1。
  8. 第 4 天:吃掉最后 1 个橘子,剩余橘子数 1 - 1 = 0。
  9. 你需要至少 4 天吃掉 10 个橘子。

  10. 示例 2:
  11. 输入:n = 6
  12. 输出:3
  13. 解释:你总共有 6 个橘子。
  14. 第 1 天:吃 3 个橘子,剩余橘子数 6 - 6/2 = 6 - 3 = 3。(6 可以被 2 整除)
  15. 第 2 天:吃 2 个橘子,剩余橘子数 3 - 2*(3/3) = 3 - 2 = 1。(3 可以被 3 整除)
  16. 第 3 天:吃掉剩余 1 个橘子,剩余橘子数 1 - 1 = 0。
  17. 你至少需要 3 天吃掉 6 个橘子。

  18. 示例 3:
  19. 输入:n = 1
  20. 输出:1

  21. 示例 4:
  22. 输入:n = 56
  23. 输出:6
复制代码
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

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