这周四上午去交大闵行校区参加美团移动开发面试,一面就被虐成狗,看来自己的计算机基础知识不扎实,还需要多刷图书馆啊。分享美团移动开发的面试题,自己也总结下答案。
一.算法:数字转字符串
string my_itoa(int num)
{
if (num == 0) {
return "0";
}
string result = "";
bool positive = true;
if(num < 0)
{
positive = false;
num = -num;
}
vector<int> str;
while (num > 0) {
str.push_back(num % 10);
num = num / 10;
}
for (int i = str.size() - 1; i >= 0; i--) {
result += str[i] + '0';
}
return positive ? result : "-" + result;
}
这道题需要注意:
- 数字小于等于0的情况处理
- 单个数字转换成char的方法
二.算法:快排的原理,时间和空间复杂度,用快排的思想求第k大的数。这个就不写了,基础的排序算法。
三.算法:求文件中第k大的数,文件比内存大,不能全部放入内存中。
关于这个题目,推荐一篇文章:十道海量数据处理面试题与十个方法大总结
四.数据库:事务的定义,事务的ACID特性,事务的实现原理
事务的定义:事务是数据库管理系统执行过程中的一个逻辑单位,由一个有限的数据库操作序列构成。
事务的ACID特性:
- 原子性(Atomicity):事务作为一个整体被执行,包含在其中的对数据库的操作要么全部被执行,要么都不执行
- 一致性(Consistency):事务应确保数据库的状态从一个一致状态转变为另一个一致状态。一致状态的含义是数据库中的数据应满足完整性约束。
- 隔离性(Isolation):多个事务并发执行时,一个事务的执行不应影响其它事务的执行。
- 持久性(Durability):已被提交的事务对数据库的修改应该永久保存在数据库中。
事务的定义和ACID特性参考维基百科:数据库事务
- 事务的实现原理
事务的(ACID)特性是由关系数据库管理系统(RDBMS,数据库系统)来实现的。数据库管理系统采用日志来保证事务的原子性、一致性和持久性。日志记录了事务对数据库所做的更新,如果某个事务在执行过程中发生错误,就可以根据日志,撤销事务对数据库已做的更新,使数据库退回到执行事务前的初始状态。
数据库管理系统采用锁机制来实现事务的隔离性。当多个事务同时更新数据库中相同的数据时,只允许持有锁的事务能更新该数据,其他事务必须等待,直到前一个事务释放了锁,其他事务才有机会更新该数据。
事务的实现原理参考:谈谈数据库的ACID
五.数据库:索引的定义,索引的实现原理
索引的定义:索引时数据库表中一列或多列的值进行排序的一种结构,使用索引可快速访问数据库表中的特定信息。
索引的实现原理:B-Tree或者B+Tree,具体详细解析:数据库进阶系列之一:漫谈数据库索引
六.网络:HTTP包有哪几部分构成,HTTP包头部的关键字
HTTP请求包(GET、POST等请求方法)由三个部分构成,分别是:方法-URI-协议/版本,请求头,请求正文。下面是一个HTTP请求包(GET)的例子:
GET /index.jsp HTTP/1.1
Accept-Language:zh-cn
Connection:Keep-Alive
Host:192.168.0.106
Content-Length:37
userName=test&password=test
GET就是请求方法,HTTP 1.1支持七种请求方法:GET、POST、HEAD、OPTIONS、PUT、DELETE和TRACE等,常用的请求方法为GET和POST
和HTTP请求包相似,由三个部分构成,分别是:协议-状态代码-描述,应答头,应答正文。下面是一个HTTP应答的例子:
HTTP/1.1 200 OK
Server:Microsoft-IIS/4.0
Date:Sun, 17 Oct 2015 14:50:00 GMT
Content-Type:text/html
Last-Modified:Thu, 15 Oct 2015 09:00:00 GMT
Content-Length:90
<html>
<head>
<title>已被虐惨</title>
</head>
<body>
<h1>再接再厉</h1>
</body>
</html>
HTTP头部常用的关键字:
- Cache-Control:指定请求和响应遵循的缓存机制
- Date:表示消息发送的时间
- Pragma:用来包含实现特定的指令,最常用的是Pragma:no-cache
- Host:指定请求资源的Internet主机和端口号
- User-Agent:包含发出请求的用户信息
- Server:包含处理请求的原始服务器的软件信息
- Content-Type:用于向接收方指示实体的介质类型
- Last-modified:指定服务器上保存内容的最后修订时间
- Set-Cookie:设置和页面关联的Cookie
- Refresh:表示浏览器应该在多少时间之内刷新文档
完整的HTTP头部字段列表:List of HTTP header fields
七.TCP/IP协议分层,网络层能不能保证可靠性,为什么,传输层能不能保证可靠性,为什么,TCP的三次握手和四次挥手。
TCP/IP协议分为五层:应用层、传输层、网络层、数据链路层和物理层,具体就不展开了
网络层智能提供尽最大努力服务,并不能保证可靠性。
传输层中有两个协议,TCP和UDP。
TCP---传输控制协议,提供的是面向连接、可靠的字节流服务。当客户和服务器彼此交换数据时,必须先在双方之间建立一个TCP连接,之后才能传输数据。TCP提供超时重发、丢弃重复数据、流量控制等功能,保证数据能从一端传到另一端。
UDP---用户数据协议,是一个简单的面向数据的运输层协议。UDP不提供可靠性,它只是把应用程序传给IP层的数据报发送出去,但是并不能保证它们能到达目的地。由于UDP在传输数据报不用在客户和服务器之间建立一个连接,且没有重发机制,故而传输速度很快。
TCP的三次挥手和四次挥手见下图:
图是盗的,侵必删,原文地址:TCP协议中的三次握手和四次挥手(图解)
八.HTTPS是什么,HTTPS过程中,证书具体是怎么起作用的
这个时候就需要搬出大神的博客了:SSL/TLS协议运行机制的概述
比我写的好了100倍不止,膜拜!
九.操作系统:死锁的产生、预防和避免
只能继续贴了:死锁的产生、预防和避免
十.iOS:为什么category无法使用property,如果需要类似于property的行为,怎么办
实际上来说,category中是可以使用property的,只是类不会自动生成对应的实例变量,也不会自动实现getter和setter,这样的property就是名存实亡了。至于原因,google到了美团技术团队博客(好尴尬。。。),里面是这么讲的:
extension看起来很像一个匿名的category,但是extension和有名字的category几乎完全是两个东西。 extension在编译期决议,它就是类的一部分,在编译期和头文件里的@interface以及实现文件里的@implement一起形成一个完整的类,它伴随类的产生而产生,亦随之一起消亡。extension一般用来隐藏类的私有信息,你必须有一个类的源码才能为一个类添加extension,所以你无法为系统的类比如NSString添加extension。
但是category则完全不一样,它是在运行期决议的。
就category和extension的区别来看,我们可以推导出一个明显的事实,extension可以添加实例变量,而category是无法添加实例变量的(因为在运行期,对象的内存布局已经确定,如果添加实例变量就会破坏类的内部布局,这对编译型语言来说是灾难性的)。
而关于实现property类似的行为,博客中讲到可以求助关联对象来实现。
MyClass+Category1.h:
#import "MyClass.h"
@interface MyClass (Category1)
@property(nonatomic,copy) NSString *name;
@end
MyClass+Category1.m:
#import "MyClass+Category1.h"
#import <objc/runtime.h>
@implementation MyClass (Category1)
+ (void)load
{
NSLog(@"%@",@"load in Category1");
}
- (void)setName:(NSString *)name
{
objc_setAssociatedObject(self,
"name",
name,
OBJC_ASSOCIATION_COPY);
}
- (NSString*)name
{
NSString *nameObject = objc_getAssociatedObject(self, "name");
return nameObject;
}
@end
对这个博客感兴趣的,链接在此:http://tech.meituan.com/DiveIntoCategory.html
十一.iOS:为什么UI必须在主线程修改
这个问题严格意义上来说并不是一个iOS的问题,考官对我也有提示,奈何自己还是没答出来。
其实这就是一个操作系统题。答案应该是UI操作并不是线程安全的,多线程更新UI会造成死锁,竞争条件等多种问题。因为Java的AWT库的痛苦教训,一般设计都不会允许多线程操作UI。iOS推荐UI操作在主线程中进行,避免出现crash等无法预知的问题。
十二.iOS:UI编写怎么多人协作,有哪些方法,优缺点
我只能想到两种:
- 建立多个Xib,最后合到一个StoryBoard中去
- 代码构建
不知道考官还有什么高招,请教他,他也不回答我,惆怅。。。
十三.iOS:ARC是什么,strong、weak和assign关键词,weak和assign的区别
这里就不详细写了,挺简单的,稍微重要一点的就是weak和assign的区别。weak修饰的属性,当指向的对象被释放(引用计数为0)的时候,会被自动置为nil,而assign没有这个功能。
十四.iOS:为什么iOS开发中,控件一般为weak而不是strong
好吧,当时也没回答好,这里搜到一个知乎问题:为什么iOS开发中,控件一般为weak而不是strong?
大概总结就是:
IBOutlet的属性一般可以设为weak是因为它已经被view引用了,除非view被释放,否则IBOutlet的属性也不会被释放,另外IBOutlet属性的生命周期和view应该是一致的,所以IBOutlet属性一般设为weak。
简单的说,如果IBOutlet对象是nib/sb scene的拥有者(File’s owner)所持有的对象,那么很显然拥有者必须“拥有”对象的指针,因此属性应设置为strong。而其他的IBOutlet对象的属性需要设置为weak,因为拥有者并不需要“拥有”他们的指针。
但是,我搜到了一个stackoverflow的问题:Should IBOutlets be strong or weak under ARC?
stackoverflow有一些争论,大家能理解中间的思想就好。
十五.iOS:关于runtime你知道哪些,运行时调用selector有哪些方法
runtime真是太大一个部分了,直接求助大神了:Objective-C Runtime
十六.iOS:iOS9新特性,Swift2新特性
关于这样的问题,我一般都只能浮于表面,完全没有自己去玩过新特性,需要多看多试啊!
再再再附:开发者所需要知道的iOS9 SDK新特性
十七.iOS:MVVM设计模式
- Model - model 在 MVVM 中没有真正的变化. 取决于你的偏好, 你的 model 可能会或可能不会封装一些额外的业务逻辑工作.
- View - view 包含实际 UI 本身(不论是 UIView 代码, storyboard 和 xib), 任何视图特定的逻辑, 和对用户输入的反馈. 在 iOS 中这不仅需要 UIView 代码和那些文件, 还包括很多需由 UIViewController 处理的工作.
- View-Model - 它的职责之一就是作为一个表现视图显示自身所需数据的静态模型;但它也有收集, 解释和转换那些数据的责任. 这留给了 view (controller) 一个更加清晰明确的任务: 呈现由 view-model 提供的数据.
我的理解就是把MVC中一些本来由Controller做的事情分出来给View做了,解决了Controller臃肿的问题,不知道这种理解对不对。
十八.设计API完成客户端和服务器订单的增量更新
直接给这个问题给跪了,自己以前也没做过相应的东西,回答的时候基本无法组织语言。
找到一篇文章,说得还不错:app后端设计(10)--数据增量更新
贴下文章中增量更新的原理吧:
增量更新的原理是在数据库中,每条数据都必须有update_time这个值,记录数据最后更新的时间,当app从服务器获取了一次数据后(返回的数据必须按时间排序,update_time最近的在第一条),记录下第一条数据的update_time,当再次获取数据就只需要获取上个时间点到访问服务器这刻为止所更新的数据即可