字节跳动IOS面试题及答题思路整理

作者: KingLionsFrank | 来源:发表于2020-03-09 14:11 被阅读0次

    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;
        }
    }
    

    相关文章

      网友评论

        本文标题:字节跳动IOS面试题及答题思路整理

        本文链接:https://www.haomeiwen.com/subject/qekpdhtx.html