微软电话面

程序员文章站 2024-01-10 09:47:22

...

序：

这几天读了《羊皮卷》感触很大。
及时复盘，及时总结很重要。
这两道题都是刷面经碰到的，看来有时候刷面经要比刷题有用。
如果面试是电话面试，建议可以把通话录下来，这样你也可以知道自己在面试中表现如何了。面试时间是早上7点到8点。为了和美国调整时差。
工作时如何对待上级并非是最重要的，最重要的是提升自己的能力。不要局限于在某个公司。不要懒于思考。
做题切忌走马观花，要一道一道认真做，宁可窄也要深。

进入主题：

面试官是个温柔的小哥哥。7点就准时打来。刚开始就直奔主题出了一道题。(快下班了比较急？)
P：给定一个整数数组，数组长度不超过2000，元素范围为[0,1000]。求其中最大的一个不重复元素。(LeetCode没找到原题)

S1：用一个长度为1001的大数组(回答时说了1000和1001都可以，还反复解释了1000如何解决，完全忽视了面试官的提示，最后经面试官提示才反应过来，真是尴尬。平时做题一定要细心)，将元素作为索引值进行遍历。最后倒着遍历大数组，得到第一个值为1的值的索引即为结果。
过程中面试官反复问了边界值该如何处理、用例该怎么写，所以建议平时也可以自己写一下用例。

边界值：

关于数组长度，0和1要特殊处理。
关于边界值0和1000。要考虑到各个场景，比如都是重复元素，都是不重复元素。设计用例时尽量要包含0和1。具体用例见3、4、5。
都是重复元素时着重考虑一下几个用例：比如有2000个元素，全是0、全是1000、2个0剩余为1000、2个1000剩余为0、2个02个1000剩余为其他元素。
都不是重复元素，0到1000所有数都包含。
除了0其他都是重复元素、除了1000其他都是重复元素、只有0是重复元素、只有1000是重复元素

代码如下：

public int maxNoRepeatNum(int[] nums)
{
	int[] rate = new int[1001];
	for (int num : nums)
	{
		rate[num]++;
	}
	for (int i = 1000; i >= 0; i--)
	{
		if (rate[i] == 1)
		{
			return i;
		}
	}
	return -1;
}

测试用例如下：

int[] t1 = {};
int[] t2 = {0};
int[] t3 = {1000};
int[] t4 = {0, 0, 0, 0};
int[] t5 = {1000, 1000, 1000, 1000};
int[] t6 = {0, 1000, 1000, 1000};
int[] t7 = {1000, 0, 0, 0};
int[] t8 = {0, 1, 1};
int[] t9 = {1000, 2, 2};
int[] t10 = {0, 0, 3, 4};
int[] t11 = {1000, 1000, 6, 7};

运行结果如下：

S2：Hash表。
要能在脑海中做出来，因为面试官会问的很细。面试官几乎问了每一行代码该如何写。末了又问了result初始值为-1和Integer.MAX_VALUE时该如何处理。
代码如下：

public int maxNoRepeatNum(int[] nums)
{
	Map<Integer, Integer> rate = new HashMap<>();
	for (int num : nums)
	{
		rate.put(num, rate.getOrDefault(num, 0) + 1);
	}
	int result = -1;
	int tmp;
	for (int num : rate.keySet())
	{
		tmp = rate.get(num);
		if (tmp == 1)
		{
			result = num > result ? num : result;
		}
	}
	return result == -1 ? Integer.MAX_VALUE : result;
}

运行结果如下：

题目进阶

虽然小哥哥说不作为依据，但还是很慌。

P：数组元素值为[1,1000]，且重复出现次数为偶数，顶多存在一个非重复元素。(LeetCode原题：https://leetcode-cn.com/problems/find-the-duplicate-number/)

典型的异或算法。(途中多次把异或说成了位运算，尴尬，经面试官提示终于反应过来了，囧)
结束的时候面试官说他会向苏州那边反应一下面试情况。之后介绍了整个面试流程(觉得可能会面过的会详细介绍一下)，总共会有五面，英文占比不是太大。出现全英文面的可能性不是太大。并且说了到时候工作时邮件什么的都会是英文让我提前准备一下。之后问我有没有什么问题。我问的问题记录如下：
Q：项目主要是做什么的？
A：面试官详细介绍了一下。
Q：后面会有全英文面吗？
A：不排除，但可能性不是太大。
忘了问下一面大概什么时候开始，真是可惜。

微软电话面