小编Edw*_*ard的帖子

在最近的Java电话采访中我被问到这个问题:

您将获得具有以下属性的NxN二进制(0-1)矩阵:

• 每行都排序(序列为0,后跟1的序列)
• 每行代表一个无符号整数(通过读取位)
• 每行都是独一无二的

例:

0 1 1
1 1 1
0 0 1

每行中的位值被排序,行表示整数3,7和1.

找到表示最小整数的行.在上面的示例中,答案是第3行,它表示整数1.

我从二次复杂的蛮力开始.采访者回答说我没有利用排序的财产.

在思考了很多之后,我在每一行都使用了二元搜索,然后它来到了O(nlogn).他问我是否可以进一步改进.我想了很多但没有改进.

如果有人能提出任何关于改进它的指示,我将不胜感激.

另一个例子:

0 1 1 1
0 0 0 1
0 0 0 0
1 1 1 1

答案是第3行,代表整数0.

这是在微软的现场采访中提出的.

计算数组中给定键的出现次数.

我回答了线性搜索,因为元素可能散布在数组中.说密钥在开头和结尾都有.所以我们需要扫描整个阵列.

接下来他询问阵列是否排序？

想了一会儿说我会再次使用线性搜索.因为密钥的重复(如果存在)可以在阵列中的任何位置.作为优化,我还说如果第一个和最后一个数组元素相同,你可以将数组长度作为答案.

在这两种情况下,我的分析是否正确？

例:

Input = [0 0 1 1 1 2 2 3 3], key = 1, Answer = 3
Input = [0 0 2 2 3 3],       key = 1, Answer = 0

这是我在电话采访中被问到的另一个问题:

给定字典和填字游戏(2d字符矩阵),找到可以在填字游戏中找到的所有字典单词.

我能想到的只是对字典进行哈希,找到填字游戏中的每个可能的单词并搜索哈希.我无法优化它.

必须承认微软的面试问题很难:(

请给我一些思考的方法.