面试珠玑 微软面试题小汇

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。

相关文章

Java面试八股之怎么通过Java程序判断JVM是32位还是64位

Java面试八股之怎么通过Java程序判断JVM是32位还是64位

怎么通过Java程序判断JVM是32位还是64位 可以通过Java程序内部检查系统属性来判断当前运行的JVM是32位还是64位。以下是一个简单的方法： public class JvmBitCheck {public static void main(String[] args) {String arch = System.getProperty("os.arch");String dataM
阅读更多...
Java面试题：通过实例说明内连接、左外连接和右外连接的区别

Java面试题：通过实例说明内连接、左外连接和右外连接的区别

在 SQL 中，连接（JOIN）用于在多个表之间组合行。最常用的连接类型是内连接（INNER JOIN）、左外连接（LEFT OUTER JOIN）和右外连接（RIGHT OUTER JOIN）。它们的主要区别在于它们如何处理表之间的匹配和不匹配行。下面是每种连接的详细说明和示例。 表示例 假设有两个表：Customers 和 Orders。 Customers CustomerIDCus
阅读更多...
C++面试八股文：std::deque用过吗？

C++面试八股文：std::deque用过吗？

100编程书屋_孔夫子旧书网 某日二师兄参加XXX科技公司的C++工程师开发岗位第26面： 面试官：deque用过吗？ 二师兄：说实话，很少用，基本没用过。 面试官：为什么？ 二师兄：因为使用它的场景很少，大部分需要性能、且需要自动扩容的时候使用vector，需要随机插入和删除的时候可以使用list。 面试官：那你知道STL中的stack是如何实现的吗？ 二师兄：默认情况下，stack使
阅读更多...
Java面试八股之JVM参数-XX:+UseCompressedOops的作用

Java面试八股之JVM参数-XX:+UseCompressedOops的作用

JVM参数-XX:+UseCompressedOops的作用 JVM参数-XX:+UseCompressedOops的作用是启用对象指针压缩（Ordinary Object Pointers compression）。这一特性主要应用于64位的Java虚拟机中，目的是为了减少内存使用。在传统的64位系统中，对象引用（即指针）通常占用8字节（64位），而大部分应用程序实际上并不需要如此大的地址空间
阅读更多...
AI赋能天气：微软研究院发布首个大规模大气基础模型Aurora

AI赋能天气：微软研究院发布首个大规模大气基础模型Aurora

编者按：气候变化日益加剧，高温、洪水、干旱，频率和强度不断增加的全球极端天气给整个人类社会都带来了难以估计的影响。这给现有的天气预测模型提出了更高的要求——这些模型要更准确地预测极端天气变化，为政府、企业和公众提供更可靠的信息，以便做出及时的准备和响应。为了应对这一挑战，微软研究院开发了首个大规模大气基础模型 Aurora，其超高的预测准确率、效率及计算速度，实现了目前最先进天气预测系统性能的显著
阅读更多...
华为某员工爆料：偷偷跑出去面试，被面试官鄙视了。第一句话就问：华为淘汰的吧，35岁了，这个年龄在华为能混得下去吗？身体没啥毛病吧

华为某员工爆料：偷偷跑出去面试，被面试官鄙视了。第一句话就问：华为淘汰的吧，35岁了，这个年龄在华为能混得下去吗？身体没啥毛病吧

“你都35岁了，难不成是被华为淘汰的？在华为混不下去了吧？身体没啥毛病吧，我们这体检可是很严的。” 近日，一位华为员工在朋友圈爆料，自己在面试时遭到了面试官的无理取闹和人身攻击，原因仅仅是因为他35岁了，曾经在华为工作过。 这番话，充满了傲慢与偏见，让人听了义愤填膺。这位面试官的言行，不仅是对求职者的不尊重，更是对职场规则的践踏。 面试本应是双向选择的过程，企业和求职者在相互了解的基
阅读更多...
【SparkStreaming】面试题

【SparkStreaming】面试题

Spark Streaming 是 Apache Spark 提供的一个扩展模块，用于处理实时数据流。它使得可以使用 Spark 强大的批处理能力来处理连续的实时数据流。Spark Streaming 提供了高级别的抽象，如 DStream（Discretized Stream），它代表了连续的数据流，并且可以通过应用在其上的高阶操作来进行处理，类似于对静态数据集的操作（如 map、reduce、
阅读更多...
算法与数据结构面试宝典——回溯算法详解（C#，C++）

算法与数据结构面试宝典——回溯算法详解（C#，C++）

文章目录 1. 回溯算法的定义及应用场景2. 回溯算法的基本思想3. 递推关系式与回溯算法的建立4. 状态转移方法5. 边界条件与结束条件6. 算法的具体实现过程7. 回溯算法在C#，C++中的实际应用案例C#示例C++示例 8. 总结回溯算法的主要特点与应用价值 回溯算法是一种通过尝试各种可能的组合来找到所有解的算法。这种算法通常用于解决组合问题，如排列、组合、棋盘游
阅读更多...
Java线程面试题（50）

Java线程面试题（50）

不管你是新程序员还是老手，你一定在面试中遇到过有关线程的问题。Java语言一个重要的特点就是内置了对并发的支持，让Java大受企业和程序员的欢迎。大多数待遇丰厚的Java开发职位都要求开发者精通多线程技术并且有丰富的Java程序开发、调试、优化经验，所以线程相关的问题在面试中经常会被提到。 在典型的Java面试中， 面试官会从线程的基本概念问起, 如：为什么你需要使用线程，
阅读更多...
【面试干货】Java中的四种引用类型：强引用、软引用、弱引用和虚引用

【面试干货】Java中的四种引用类型：强引用、软引用、弱引用和虚引用

【面试干货】Java中的四种引用类型：强引用、软引用、弱引用和虚引用 1、强引用（Strong Reference）2、软引用（Soft Reference）3、弱引用（Weak Reference）4、虚引用（Phantom Reference）5、总结 💖The Begin💖点点关注，收藏不迷路💖 在Java中，除了我们常见的强引用（Strong Refer
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2