字节跳动IOS面试题及答题思路整理
2020-03-09 本文已影响0人
KingLionsFrank
1、使用method
swizzling要注意什么？（进行版本迭代的时候需要进行一些检验，防止系统库的函数发生了变化） 1.避免交换父类方法： 如果当前类未实现被交换的方法而父类实现了的情况下，此时父类的实现会被交换，若此父类的多个继承者都在交换时会导致方法被交换多次而混乱，同时当调用父类的方法时会因为找不到而发生崩溃。 所以在交换前都应该先尝试为当前类添加被交换的函数的新的实现IMP，如果添加成功则说明类没有实现被交换的方法，则只需要替代分类交换方法的实现为原方法的实现，如果添加失败，则原类中实现了被交换的方法，则可以直接进行交换
2、iOS中copy,strong,retain,weak和assign的区别
copy，strong，weak，assign的区别。 可变变量中，copy是重新开辟一个内存，strong，weak，assgin后三者不开辟内存，只是指针指向原来保存值的内存的位置，storng指向后会对该内存引用计数+1，而weak，assgin不会。weak，assgin会在引用保存值的内存引用计数为0的时候值为空，并且weak会将内存值设为nil，assign不会，assign在内存没有被重写前依旧可以输出，但一旦被重写将出现奔溃 不可变变量中，因为值本身不可被改变，copy没必要开辟出一块内存存放和原来内存一模一样的值，所以内存管理系统默认都是浅拷贝。其他和可变变量一样，如weak修饰的变量同样会在内存引用计数为0时变为nil。 容器本身遵守上面准则，但容器内部的每个值都是浅拷贝。 **综上所述，当创建property构造器创建变量value1的时候，使用copy，strong，weak，assign根据具体使用情况来决定。value1 = value2，如果你希望value1和value2的修改不会互相影响的就用用copy，反之用strong,weak,assign。如果你还希望原来值C(C是什么见示意图1)为nil的时候，你的变量不为nil就用strong,反之用weak和assign。weak和assign保证了不强引用某一块内存，如delegate我们就用weak表示，就是为了防止循环引用的产生。 另外，我们上面讨论的是类变量，直接创建局部变量默认是Strong修饰 **
3、iOS-OC实现LRU算法NSDictionary容器（非线程安全)
LRU（Least recently used，最近最少使用）算法根据数据的历史访问记录来进行淘汰数据，其核心思想是“如果数据最近被访问过，那么将来被访问的几率也更高”。
设计原理：
核心数据属性
@property (nonatomic, strong) NSMutableDictionary *dict; // 存储数据
@property (nonatomic, strong) NSMutableArray *arrayForLRU; // 对常用key 进行排序记录处理
@property (nonatomic, assign) NSUInteger maxCountLRU; 设置的最大内存数
1、每次进行读取或存储key数据时，将key设置为优先级最高，最近使用的数据，完成LRU算法记录
2、当最大存储数据达到了上限时，根据LRU算法获取最不常用的key，在存储容器中进行删除这些存储的数据
3、然后对新数据进行存储，同时更新LRU算法记录
另外需要配置一些对外接口方法供给调用
设计过程：
#import <Foundation/Foundation.h>
@interface LRUMutableDictionary<__covariant KeyType, __covariant ObjectType> : NSObject
// maxCountLRU: 执行LRU算法时的最大存储的元素数量
- (instancetype)initWithMaxCountLRU:(NSUInteger)maxCountLRU;
//*****NSDictionary
@property (readonly) NSUInteger count;
- (NSEnumerator<KeyType> *)keyEnumerator;
- (void)enumerateKeysAndObjectsUsingBlock:(void (^)(KeyType key, ObjectType obj, BOOL *stop))block;
//*****NSMutableDictionary
- (void)removeObjectForKey:(KeyType)aKey;
- (void)setObject:(ObjectType)anObject forKey:(KeyType <NSCopying>)aKey;
- (void)removeAllObjects;
- (void)removeObjectsForKeys:(NSArray<KeyType> *)keyArray;
//*****LRUMutableDictionary
// 执行LRU算法，当访问的元素可能是被淘汰的时候，可以通过在block中返回需要访问的对象，会根据LRU机制自动添加到dictionary中
- (ObjectType)objectForKey:(KeyType)aKey returnEliminateObjectUsingBlock:(ObjectType (^)(BOOL maybeEliminate))block;
@end
#import "LRUMutableDictionary.h"
// 定义一个开始准备启动LRU的值，当 (MaxCount - CurCount < LRU_RISK_COUNT) 时才启动 LRU
#define LRU_RISK_COUNT 100
@interface LRUMutableDictionary ()
@property (nonatomic, strong) NSMutableDictionary *dict; // 存储数据的字典
@property (nonatomic, strong) NSMutableArray *arrayForLRU; // 存放LRU的数组
@property (nonatomic, assign) NSUInteger maxCountLRU; // 最大存储值，存储量超出这个值，启动LRU淘汰算法
@property (nonatomic, assign) BOOL isOpenLRU; // 是否开启LRU算法，如果存储量远低于最大存储值时，其实没有必要开启LRU算法
@end
@implementation LRUMutableDictionary
- (instancetype)initWithMaxCountLRU:(NSUInteger)maxCountLRU
{
self = [super init];
if (self) {
_dict = [[NSMutableDictionary alloc] initWithCapacity:maxCountLRU];
_arrayForLRU = [[NSMutableArray alloc] initWithCapacity:maxCountLRU];
_maxCountLRU = maxCountLRU;
}
return self;
}
#pragma mark - NSDictionary
- (NSUInteger)count
{
return [_dict count];
}
- (NSEnumerator *)keyEnumerator
{
return [_dict keyEnumerator];
}
- (id)objectForKey:(id)aKey
{
return [self objectForKey:aKey returnEliminateObjectUsingBlock:^id(BOOL maybeEliminate) {
return nil;
}];
}
- (void)enumerateKeysAndObjectsUsingBlock:(void (^)(id, id, BOOL *))block
{
[_dict enumerateKeysAndObjectsUsingBlock:block];
}
#pragma mark - NSMutableDictionary
- (void)removeObjectForKey:(id)aKey
{
[_dict removeObjectForKey:aKey];
[self _removeObjectLRU:aKey];
}
- (void)setObject:(id)anObject forKey:(id<NSCopying>)aKey
{
BOOL isExist = ([_dict objectForKey:aKey] != nil);
[_dict setObject:anObject forKey:aKey];
if (isExist) {
[self _adjustPositionLRU:aKey];
} else {
[self _addObjectLRU:aKey];
}
}
- (void)removeAllObjects
{
[_dict removeAllObjects];
[self _removeAllObjectsLRU];
}
- (void)removeObjectsForKeys:(NSArray *)keyArray
{
if (keyArray.count > 0) {
[_dict removeObjectsForKeys:keyArray];
[self _removeObjectsLRU:keyArray];
}
}
#pragma mark - LRUMutableDictionary
- (id)objectForKey:(id)aKey returnEliminateObjectUsingBlock:(id (^)(BOOL))block
{
id object = [_dict objectForKey:aKey];
if (object) {
[self _adjustPositionLRU:aKey];
}
if (block) {
BOOL maybeEliminate = object ? NO : YES;
id newObject = block(maybeEliminate);
if (newObject) {
[self setObject:newObject forKey:aKey];
return [_dict objectForKey:aKey];
}
}
return object;
}
#pragma mark - LRU
- (void)_adjustPositionLRU:(id)anObject
{
if (_isOpenLRU) {
NSUInteger idx = [_arrayForLRU indexOfObject:anObject];
if (idx != NSNotFound) {
[_arrayForLRU removeObjectAtIndex:idx];
[_arrayForLRU insertObject:anObject atIndex:0];
}
}
}
- (void)_addObjectLRU:(id)anObject
{
if (!_isOpenLRU && [self isNeedOpenLRU:_dict.count]) {
// 如果原来没有开启 LRU，现在增加一个元素之后达到了存储量临界条件，则开启，一次性将所有的Key导入
[_arrayForLRU removeAllObjects];
[_arrayForLRU addObjectsFromArray:_dict.allKeys];
[_arrayForLRU removeObject:anObject];
_isOpenLRU = YES;
}
if (_isOpenLRU) {
[_arrayForLRU insertObject:anObject atIndex:0];
// 当超出LRU算法限制之后，将最不常使用的元素淘汰
if ((_maxCountLRU > 0) && (_arrayForLRU.count > _maxCountLRU)) {
[_dict removeObjectForKey:[_arrayForLRU lastObject]];
[_arrayForLRU removeLastObject];
// 【注意】这里不要直接调用下面这个方法，因为内部调用[_arrayForLRU removeObject:anObject];的时候，
// 每次都将Array从头开始遍历到最后一个，这里既然已经知道是删除最后一个了，直接删除即可。
// 使用下面这种方法会增加上百倍的耗时。
// [self removeObjectForKey:[_arrayForLRU lastObject]];
}
}
}
- (void)_removeObjectLRU:(id)anObject
{
if (_isOpenLRU) {
[_arrayForLRU removeObject:anObject];
if (![self isNeedOpenLRU:_arrayForLRU.count]) {
[_arrayForLRU removeAllObjects];
_isOpenLRU = NO;
}
}
}
- (void)_removeObjectsLRU:(NSArray *)otherArray
{
if (_isOpenLRU) {
[_arrayForLRU removeObjectsInArray:otherArray];
if (![self isNeedOpenLRU:_arrayForLRU.count]) {
[_arrayForLRU removeAllObjects];
_isOpenLRU = NO;
}
}
}
- (void)_removeAllObjectsLRU
{
if (_isOpenLRU) {
[_arrayForLRU removeAllObjects];
_isOpenLRU = NO; // 清空全部元素了，一定可以关闭LRU
}
}
- (BOOL)isNeedOpenLRU:(NSUInteger)count
{
return (_maxCountLRU - count) < LRU_RISK_COUNT;
}
@end
4、链表反转
构建一个指定链表 1->3->8->5->4->2，并将其翻转打印
思路：头插法实现链表反转。定义一个新的head指针作为链表的头部指针，定义一个P指针遍历链表，将每次遍历到的元素插入到head指针后。
// 链表反转
struct Node * reverseList(struct Node *head) {
// 定义变量指针，初始化为头结点
struct Node *p = head;
// 反转后的链表头
struct Node *newH = NULL;
while (p != NULL) {
// 记录下一个结点
struct Node *temp = p -> next;
p->next = newH;
// 更新链表头部为当前节点
newH = p;
// 移动P指针
p = temp;
}
return newH;
}
// 构建一个链表
struct Node * constructList(void) {
// 头结点
struct Node *head = NULL;
// 记录当前节点
struct Node *cur = NULL;
for (int i = 0; i < 5; i++) {
struct Node *node = malloc(sizeof(struct Node));
node->data = I;
if (head == NULL) {
head = node;
} else {
cur->next = node;
}
cur = node;
}
return head;
}
// 打印链表
void printList(struct Node *head) {
struct Node *temp = head;
while (temp != NULL) {
printf("node is %d \n", temp->data);
temp = temp->next;
}
}
5、字符串反转
给定字符串 Hello, world, 实现将其反转。输出结果dlrow,olleh。
思路：使用两个指针，一个指向字符串首部begin，一个指向字符串尾部end。遍历过程逐渐交换两个指针指向的字符，结束条件begin大于end。
void char_reverse(char * cha) {
// 指向第一个字符
char * begin = cha;
// 指向字符串末尾
char * end = cha + strlen(cha) - 1;
while (begin < end) {
// 交换字符，同时移动指针
char temp = *begin;
*(begin++) = *end;
*(end--) = temp;
}
}
