西拉免费代理IP

你当前的位置:西拉免费代理IP   >   新闻中心   >   一道微软面试题

一道微软面试题

来源: 西拉IP   作者: 张祁无   2018年12月14日 14:59

面试题目是这样子的:

两个单词如果包含相同的字母,次序不同,则称为字母易位词(anagram)。例如,“silent”和“listen”是字母易位词,而“apple”和“aplee”不是易位词。请定义函数检查两个单词是否是字母易位词。可以假设两个单词字母均为小写。要求算法复杂度尽量低。

看到这个题目,你的思路是什么?

思路一

首先,最基本的思路,便是检测字符串s1中的字符是否都出现在s2中(在s1和s2长度一样的前提下)。为了解决“apple”和“aplee”不是易位词的这种情况,不能仅仅判断出现在s2中就可以了,还需要做个标记。这里可以考虑将字符串转换为list,对于比较过的便设置为None。算法代码设计如下:

一道微软面试题

让我们考虑一下算法复杂度。可以从字符串s2来考虑,对于s2中的每个元素,s1都会从头开始进行遍历一次,所以算法的复杂度为:

一道微软面试题

即算法的复杂度为O(n^2)。

有没有算法复杂度更低的思路呢?思考一下。

思路二

通过题目,我们可以想到,字母易位词即为各个字母的数目相同,而顺序不一致。因而,如果对字符串按照字母顺序排序后,那么两个字符串应该完全一致。这样算法复杂度是否更低?

先看一下代码实现如下:

一道微软面试题

这样算法复杂度是否是O(n)了呢?因为仅仅进行了n次比较啊。当然不是,为什么呢?因为事先先对两个字符串进行了排序,而排序的复杂度并未计入。所以,此种算法的复杂度即为O(n*logn+n),为O(n*logn)。复杂度比思路一的复杂度降低了。

有没有复杂度更低的算法呢?

思路三

思路二利用了字母易位词即为各个字母的数目相同,而顺序不一致。我们从另外一个角度思考,字母一共有多少个?很明显,只有26个(只考虑小写字母)。那么,我们可以为字符串s1和s2分别设置26个计数器,然后判断这对应位置的计数是否相等,如果对应计数完全相等,则为字母易位词。算法代码实现如下:

一道微软面试题

算法的复杂度为O(n + n + 26) ,即为O(n),为线性复杂度的算法。

前几天,一直在跟同事讨论怎么面试考察思维反应能力,这个题目给出了答案,能够一步步深入下去的,必定需要一定的思维反应能力。

阅读 510   

相关推荐

服务器消息块协议(SMB协议) 服务器消息块协议(SMB协议)
服务器消息块协议(SMB协议)

服务器消息块协议(SMB协议)是一种客户端 - 服务器通信协议,用于共享对网络上的文件,打印机,串行端口和其他资源的访问。它还可以携带用于进程间通信的事务协议。 由IBM于20世纪80年 . . .

2018年12月15日
Microsoft SSIS(SQL Server集成服务) Microsoft SSIS(SQL Server集成服务)
Microsoft SSIS(SQL Server集成服务)

Microsoft SSIS(SQL Server Integration Services)是Microsoft SQL Server数据库中内置的企业数据集成,数据转换和数据迁移工具。它可 . . .

2018年12月15日
应用程序接口(API) 应用程序接口(API)
应用程序接口(API)

应用程序接口(API)是   允许两个软件程序彼此通信的代码。 API定义了开发人员编写从操作系统(OS)或其他应用程序请求服务的程序的正确方法。API  由动词和名词组成的函数调用实 . . .

2018年12月14日
Netscape Server应用程序编程接口(NSAPI)

NSAPI(Netscape服务器应用程序编程接口)是一个( 应用程序接口 ),随Netscape Web服务器一起提供,通过扩展服务器功能,帮助开发人员构建更快,更复杂 . . .

2018年12月14日
Adaptive Server Enterprise(ASE)

Adaptive Server Enterprise(ASE)是关系数据库管理系统(RDBMS),可在Linux和其他基于Unix的操作系统,Windows NT和Windows 2000以及Ma . . .

2018年12月14日
webshell你不知道的那些事 webshell你不知道的那些事
webshell你不知道的那些事

1.利用md5绕过waf的一句话 本体: 本质 利用方式 MD5("3fion0hj596569 . . .

2018年12月14日
设计模式之简单工厂模式 设计模式之简单工厂模式
设计模式之简单工厂模式

工厂,顾名思义,能够生产产品的一个地方。产品,在面向对象中,就是类的实例。所以,“工厂”就是一个能够产生其它类型的对象的类。工厂类设计模式主要有三种,即简单工厂模式,工厂模式,抽象工厂模式三种 . . .

2018年12月13日
谷歌搜索重返中国按下暂停键,CEO 皮查伊“对决”美国国会 谷歌搜索重返中国按下暂停键,CEO 皮查伊“对决”美国国会
谷歌搜索重返中国按下暂停键,CEO 皮查伊“对决”美国国会

在经历了今年 “Project Maven”项目和“蜻蜓”计划的道德滑坡的声讨过后,Google 公司仍旧“流年不顺”。 先是 Google Cloud 的三位女 . . .

2018年12月13日
如履薄冰:Redis 懒惰删除的巨大牺牲 如履薄冰:Redis 懒惰删除的巨大牺牲
如履薄冰:Redis 懒惰删除的巨大牺牲

大家都知道 Redis 是单线程的,但是 Redis 4.0 增加了懒惰删除功能,懒惰删除需要使用异步线程对已删除的节点进行内存回收,这意味着 Redis 底层其实并不是单线程,它内部还有 . . .

2018年12月13日
45K!刚面完 AI 岗,这几点分享给你! 45K!刚面完 AI 岗,这几点分享给你!
45K!刚面完 AI 岗,这几点分享给你!

互联网虽然寒冬,但人工智能热度不减,成果不断。今年所有的互联网公司,都在ALL in AI。百度、腾讯、阿里巴巴、京东等互联网巨头甚至都在美国硅谷大肆高薪挖掘人工智能人才。 . . .

2018年12月13日

新闻中心 代理分享 | 蜘蛛地图

全网最大的免费网页代理ip平台,提供大量免费http代理服务器免费ip代理地址

© 2016 - 2021. 西拉免费代理ip, All rights reserved. 鄂ICP备18017015号-4

在线客服