面试珠玑 微软面试题小汇

2024-01-05 11:48
文章标签 面试 面试题 微软 珠玑 小汇

本文主要是介绍面试珠玑 微软面试题小汇，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1、有一个整数数组，请求出两两之差绝对值最小的值，记住，只要得出最小值即可，不需要求出是哪两个数。

复制代码 
  1 using System;
  2 using System.Linq;
  3 using System.Collections.Generic;
  4 namespace ConsoleApplication1
  5 {
  6     class Program
  7     {
  8         static Random Rand = new Random();
  9 
 10         static void Main(string[] args)
 11         {
 12             int count = 10000;
 13             List<int> Input = new List<int>();
 14 //             for (int i = 0; i < count; i++)
 15 //             {
 16 //                 Input.Add(Rand.Next(int.MinValue, int.MaxValue));
 17 //             }
 18             Input.Add(1); Input.Add(2); Input.Add(3); Input.Add(4); Input.Add(5); Input.Add(19);
 19 
 20             ulong re = PigeonNest(Input, ulong.MaxValue);
 21             Console.WriteLine(re);
 22             Console.WriteLine(ulong.MaxValue);
 23             Console.WriteLine(Input.Min());
 24         }
 25 
 26         //鸽巢原理。
 27         static ulong PigeonNest(List<int> List, ulong MinResult)
 28         {
 29             switch (List.Count)
 30             {
 31                 case 0:
 32                 case 1:
 33                     return MinResult;
 34                 case 2:
 35                     return ABS(List[0], List[1]);
 36                 default:
 37                     break;
 38             }
 39             int min = List.Min();
 40             //确定桶的大小。
 41             int width = (int)Math.Ceiling((double)(List.Max() - min) / List.Count);
 42             //不可能比1还小了。
 43             if (width == 1) { return 1ul; }
 44             //把数据丢到桶里。
 45             Dictionary<int, NumbersInfo> EachNestNum = new Dictionary<int, NumbersInfo>();
 46             foreach (int n in List)
 47             {
 48                 int Key = Convert.ToInt32(Math.Ceiling((double)(n - min) / width));
 49                 if (!EachNestNum.ContainsKey(Key))
 50                 {
 51                     EachNestNum.Add(Key, new NumbersInfo(Key));
 52                 }
 53                 EachNestNum[Key].Add(n);
 54             }
 55             //找到所有桶里，和相邻两桶的最大最小值距离，三个数中最近的。
 56             foreach (int Key in EachNestNum.Keys)
 57             {
 58                 MinResult = Min(MinResult, EachNestNum[Key].minresult(EachNestNum, MinResult));
 59             }
 60             return MinResult;
 61         }
 62         class NumbersInfo
 63         {
 64             public NumbersInfo(int k)
 65             { key = k; }
 66             private List<int> List = new List<int>();
 67             private int key;
 68             public int max = int.MinValue;
 69             public int min = int.MaxValue;
 70             public int count { get { return List.Count; } }
 71             public ulong minresult(Dictionary<int, NumbersInfo> EachNestNum, ulong re)
 72             {
 73                 //在三个数中选最小的。  
 74                 //当命中数大于1的时候，递归这个过程。由于迅速收敛，故复杂度忽略不计。
 75                 if (List.Count > 1)
 76                 {
 77                     re = PigeonNest(List, re);
 78                 }
 79                 if (EachNestNum.ContainsKey(key - 1))
 80                 {
 81                     re = Min(ABS(EachNestNum[key].min, EachNestNum[key - 1].max), re);
 82                 }
 83                 if (EachNestNum.ContainsKey(key + 1))
 84                 {
 85                     re = Min(ABS(EachNestNum[key].max, EachNestNum[key + 1].min), re);
 86                 }
 87                 return re;
 88             }
 89             public void Add(int x)
 90             {
 91                 List.Add(x);
 92                 if (x > max) { max = x; }
 93                 if (x < min) { min = x; }
 94             }
 95         }
 96 
 97 
 98         static ulong ABS(int x, int y)
 99         {
100             //三分。
101             switch (x.CompareTo(y))
102             {
103                 case -1:
104                     return (ulong)y - (ulong)x;
105                 case 1:
106                     return (ulong)x - (ulong)y;
107             }
108             return 0ul;
109 
110         }
111 
112         static ulong Min(ulong x, ulong y)
113         {
114             if (x > y) { return y; }
115             return x;
116         }
117     }
118 }
复制代码

2、平面上N个点，没两个点都确定一条直线，求出斜率最大的那条直线所通过的两个点

平面上N个点，没两个点都确定一条直线，求出斜率最大的那条直线所通过的两个点（斜率不存在的情况不考虑）。时间效率越高越好。
先把N个点按x排序。
斜率k最大值为max(斜率(point[i],point[i+1]))    0 <=i <n-2。
复杂度Nlog(N)。
以3个点为例,按照x排序后为ABC,假如3点共线,则斜率一样,假如不共线,则可以证明AB或BC中,一定有一个点的斜率大于AC,一个点的斜率小于AC。

3、写一个函数，检查字符是否是整数，如果是，返回其整数值。（或者：怎样只用4行代码编写出一个从字符串到长整型的函数）

复制代码 
1 long strtoint(char *str,int length){
2     if(length > 1) {
3         return str[0]=='-' ? strtoint(str, length-1)*10-(str[length-1]-'0') : strtoint(str, length-1)*10+str[length-1]-'0';
4     } else {
5         return str[0]=='-' ? -1/10 : str[0]-'0';
6     }
7 }
复制代码

4、怎样编写一个程序，把一个有序整数数组放到二叉树中？

复制代码 
 1 #include <iostream>
 2 
 3 using namespace std;
 4 
 5 typedef struct Node
 6 {
 7     int v;
 8     struct Node *lchild;
 9     struct Node *rchild;
10 }Node;
11 
12 void Insert(Node *&n, int v) {
13     if (NULL == n)
14     {
15         n = (Node*)malloc(sizeof(Node));
16         n->v = v; n->lchild = n->rchild = NULL;
17         return;
18     }
19     if (v < n->v)
20     {
21         Insert(n->lchild, v);
22     }
23     else
24     {
25         Insert(n->rchild, v);
26     }
27 }
28 
29 void Print(Node *r)
30 {
31     if (NULL == r)
32     {
33         return;
34     }
35     Print(r->lchild);
36     cout << r->v << endl;
37     Print(r->rchild);
38 }
39 
40 Node *root = NULL;
41 
42 void Print1(int a[], int low, int high)
43 {
44     if (low > high)    return;
45     int mid = (low+high)/2;
46     Insert(root, mid);
47     Print1(a, low, mid-1);
48     Print1(a, mid+1, high);
49 }
50 
51 int main()
52 {
53 //     Node *root = NULL;
54 //     for (int i = 0; i < 3; i++)
55 //     {
56 //         Insert(root, i);
57 //     }
58 
59     int a[6];
60     for (int i = 0; i < 6; i++)
61     {
62         a[i] = i;
63     }
64 
65     Print1(a, 0, 5);
66 
67     // Êä³ö²éÕÒ¶þ²æÊ÷
68     Print(root);
69 
70     return 0;
71 }
复制代码

5、怎样从顶部开始逐层打印二叉树结点数据？请编程。

复制代码 
 1 void Print2(Node *root)
 2 {
 3     queue<Node*> q;
 4     q.push(root);
 5 
 6     while(!q.empty())
 7     {
 8         Node *t = q.front();
 9         q.pop();
10         cout << t->v;
11         if (t->lchild) q.push(t->lchild);
12         if (t->rchild) q.push(t->rchild);
13     }
14     cout << endl;
15 }
复制代码

6、编程实现两个正整数的除法

复制代码 
 1 #include <iostream>
 2 
 3 using namespace std;
 4 
 5 int div1(const int x, const int y) {
 6     int left_num = x;
 7     int result = 0;
 8     while (left_num >= y) {
 9         int multi = 1;
10         while (y * multi <= (left_num>>1)) {
11             multi = multi << 1;
12         }
13         result += multi;
14         left_num -= y * multi;
15     }
16     return result;
17 }
18 
19 int main()
20 {
21     cout << div1(11, 3) << endl;
22     return 0;
23 }
复制代码

7、在排序数组中，找出给定数字的出现次数。比如 [1, 2, 2, 2, 3] 中2的出现次数是3次。

复制代码 
 1 #include <iostream>
 2 
 3 using namespace std;
 4 
 5 void equal_range1(int a[], int len, int x)
 6 {
 7     int low=0, high=len-1;
 8     int mid;
 9     while (low<=high)
10     {
11         mid=(low+high)/2;
12         if (x==a[mid]) {cout << mid << endl; break;}
13         else if (x<mid) high=mid-1;
14         else low=mid+1;
15     }
16     if (low>high)
17     {
18         cout << "ûÓÐÕÒµ½" << x << endl;
19     }
20     else
21     {
22         int k=mid-1;
23         while (k>=0&&a[k]==x)
24         {
25             cout << k-- << endl;
26         }
27         k=mid+1;
28         while (k<=len-1&&a[k]==x)
29         {
30             cout << k++ << endl;
31         }
32     }
33 }
34 
35 int main()
36 {
37     int a[] = {1,2,2,2,2,3,4};
38     equal_range1(a, 7, 2);
39     return 0;
40 }
复制代码

8、一个整数数列，元素取值可能是0~65535中的任意一个数，相同数值不会重复出现。0是例外，可以反复出现。
请设计一个算法，当你从该数列中随意选取5个数值，判断这5个数值是否连续相邻。
注意：
- 5个数值允许是乱序的。比如： 8 7 5 0 6
- 0可以通配任意数值。比如：8 7 5 0 6 中的0可以通配成9或者4
- 0可以多次出现。
- 复杂度如果是O(n2)则不得分。

插入排序-》最大值-最小值<=4

9、一棵排序二叉树，令 f=(最大值+最小值)/2，设计一个算法，找出距离f值最近、大于f值的结点。复杂度如果是O(n2)则不得分。

复制代码 
 1 void find1(Node *h, int value1, Node *&r)
 2 {
 3     if (NULL==h)
 4     {
 5         return;
 6     }
 7     if (value1 >= h->v)
 8     {
 9         find1(h->rchild, value1, r);
10     }
11     else
12     {
13         r=h;
14         find1(h->lchild, value1, r);
15     }
16 }
复制代码

这篇关于面试珠玑 微软面试题小汇的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/572765。

相关文章

字节面试 | 如何测试RocketMQ、RocketMQ？

字节面试 | 如何测试RocketMQ、RocketMQ？

字节面试：RocketMQ是怎么测试的呢？ 答： 首先保证消息的消费正确、设计逆向用例，在验证消息内容为空等情况时的消费正确性； 推送大批量MQ，通过Admin控制台查看MQ消费的情况，是否出现消费假死、TPS是否正常等等问题。（上述都是临场发挥，但是RocketMQ真正的测试点，还真的需要探讨） 01 先了解RocketMQ 作为测试也是要简单了解RocketMQ。简单来说，就是一个分
阅读更多...
秋招最新大模型算法面试，熬夜都要肝完它

秋招最新大模型算法面试，熬夜都要肝完它

💥大家在面试大模型LLM这个板块的时候，不知道面试完会不会复盘、总结，做笔记的习惯，这份大模型算法岗面试八股笔记也帮助不少人拿到过offer ✨对于面试大模型算法工程师会有一定的帮助，都附有完整答案，熬夜也要看完，祝大家一臂之力 这份《大模型算法工程师面试题》已经上传CSDN，还有完整版的大模型 AI 学习资料，朋友们如果需要可以微信扫描下方CSDN官方认证二维码免费领取【保证100%免费
阅读更多...
荣耀嵌入式面试题及参考答案

荣耀嵌入式面试题及参考答案

在项目中是否有使用过实时操作系统？ 在我参与的项目中，有使用过实时操作系统。实时操作系统（RTOS）在对时间要求严格的应用场景中具有重要作用。我曾参与的一个工业自动化控制项目就采用了实时操作系统。在这个项目中，需要对多个传感器的数据进行实时采集和处理，并根据采集到的数据及时控制执行机构的动作。实时操作系统能够提供确定性的响应时间，确保关键任务在规定的时间内完成。 使用实时操作系统的
阅读更多...
一些其他面试题

一些其他面试题

阿里二面：那你来说说定时任务？单机、分布式、调度框架下的定时任务实现是怎么完成的？懵了。。_哔哩哔哩_bilibili 1.定时算法 累加，第二层每一个格子是第一层的总时间400 ms= 20 * 20ms 2.MQ消息丢失 阿里二面：高并发场景下引进消息队列有什么问题？如何保证消息只被消费一次？真是捏了一把汗。。_哔哩哔哩_bilibili 发送消息失败
阅读更多...
zookeeper相关面试题

zookeeper相关面试题

zk的数据同步原理？zk的集群会出现脑裂的问题吗？zk的watch机制实现原理？zk是如何保证一致性的？zk的快速选举leader原理？zk的典型应用场景zk中一个客户端修改了数据之后，其他客户端能够马上获取到最新的数据吗？zk对事物的支持？ 1. zk的数据同步原理？ zk的数据同步过程中，通过以下三个参数来选择对应的数据同步方式 peerLastZxid：Learner服务器（Follo
阅读更多...
java常用面试题-基础知识分享

java常用面试题-基础知识分享

什么是Java？ Java是一种高级编程语言，旨在提供跨平台的解决方案。它是一种面向对象的语言，具有简单、结构化、可移植、可靠、安全等特点。 Java的主要特点是什么？ Java的主要特点包括： 简单性：Java的语法相对简单，易于学习和使用。面向对象：Java是一种完全面向对象的语言，支持封装、继承和多态。跨平台性：Java的程序可以在不同的操作系统上运行，称为"Write once,
阅读更多...
java面试常见问题之Hibernate总结

java面试常见问题之Hibernate总结

1  Hibernate的检索方式 Ø  导航对象图检索（根据已经加载的对象，导航到其他对象。） Ø  OID检索（按照对象的OID来检索对象。） Ø  HQL检索（使用面向对象的HQL查询语言。） Ø  QBC检索（使用QBC(Qurey By Criteria)API来检索对象。 QBC/QBE离线/在线） Ø  本地SQL检索（使用本地数据库的SQL查询语句。） 包括Hibern
阅读更多...
微软正式推出 Spartan 斯巴达浏览器

微软正式推出 Spartan 斯巴达浏览器

作为用于替代 IE 浏览器的下一代继任者，微软的 Project Spartan 斯巴达浏览器可算是吊足了玩家们的胃口！如今，在最新的 Windows 10 Build 10049 版本起，它终于正式登场了。 斯巴达浏览器搭载了全新的渲染引擎、新的用户界面并集成了 Cortana 语音助手。功能上新增了稍后阅读列表、阅读视图、F12开发者工具、支持网页注释 (手写涂鸦)，可以保存到 O
阅读更多...
贝壳面试：什么是回表？什么是索引下推？

贝壳面试：什么是回表？什么是索引下推？

尼恩说在前面 在40岁老架构师 尼恩的读者交流群(50+)中，最近有小伙伴拿到了一线互联网企业如得物、阿里、滴滴、极兔、有赞、希音、百度、网易、美团的面试资格，遇到很多很重要的面试题： 1.谈谈你对MySQL 索引下推 的认识？ 2.在MySQL中，索引下推 是如何实现的？请简述其工作原理。 3、说说什么是 回表，什么是 索引下推 ？ 最近有小伙伴在面试 贝壳、soul，又遇到了相关的
阅读更多...
【Kubernetes】常见面试题汇总（三）

【Kubernetes】常见面试题汇总（三）

目录 9.简述 Kubernetes 的缺点或当前的不足之处？ 10.简述 Kubernetes 相关基础概念？ 9.简述 Kubernetes 的缺点或当前的不足之处？ Kubernetes 当前存在的缺点（不足）如下： ① 安装过程和配置相对困难复杂； ② 管理服务相对繁琐； ③ 运行和编译需要很多时间； ④ 它比其他替代品更昂贵； ⑤ 对于简单的应用程序来说，可能不
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2