iOS面试必问的一道面试题

前言

最近面试了几家公司, 我总结出来了两点与大家共勉, 该文章就是围绕以下两点开展:

• 个人发展和工资想更上一层楼, 必须熟悉算法和数据结构
• 程序员的英文水平很重要

1.出乎我所料的很多公司都问到了有关topK的问题. 所谓topK问题就是在海量数据中, 找到频率最高的K个数据.例如在淘宝中选择'价格由高到低' , 就会在所有相关的物品中把价格最高的前K个展示给用户.
一般topK问题会使用堆(heap)和快速排序, 面试时答上来这两点, 基本就已经满足面试官想要的回答了.使用OC的实现代码我会在下面讲解.但是我有一点愚见,OC因为语言的局限性, 可能不适用于上亿数据的搜索和排序, 但是在万级别的topK中效率也是很高的
2.强烈给大家安利一个我最近在用的背单词神器墨墨背单词, 这个App最吸引我的是可以自定义文本题词. 我之前再用扇贝和百词斩的时候, 推送给我的单词百分之80对我现在的工作没有意义. 但是墨墨可以自定义想背的单词, 可是如何获取到有效的单词呢. 我在阅读英文文档的时候, 会把不会的单词写入墨墨中. 可是一个一个查找效率低, 所以我写了一个计算文本中所有单词的频率, 并按频率大小进行排序的工具.源码已经上传到Github, 方便大家进行理解.

正文

1.效果展示

将txt文本的内容进行展示

计算单词频率并按需求排序

2.代码讲解

使用NSFileManager和NSFileHandle获取txt的文字内容

- (NSString *)getWordData
{
    NSFileManager *manager = [NSFileManager defaultManager];
    NSString *filePath = [[NSBundle mainBundle] pathForResource:@"word" ofType:@"txt"];
    
    if ([manager fileExistsAtPath:filePath]) {
        NSString *str = [self getStringFrom:filePath];
        return str;
    } else {
        [NSException raise:NSGenericException format:@"word.txt did not exist in filePath"];
        return nil;
    }
}

- (NSString *)getStringFrom:(NSString *)filePath
{
    NSString *txtStrings = nil;
    NSFileHandle *fileHandle = [NSFileHandle fileHandleForReadingAtPath:filePath];
    if (fileHandle != nil) {
        NSData *wordData = fileHandle.availableData;
        txtStrings = [[NSString alloc] initWithData:wordData encoding:NSUTF8StringEncoding];
    }
    [fileHandle closeFile];
    return txtStrings;
}

使用NSCharacterSet对英文内容进行处理, 拆分出每一个英文单词, 使用NSPredicate去空

- (NSArray *)getWordArray
{
    NSString *txtStrings = [self getWordData];
    NSCharacterSet *characterSet = [NSCharacterSet characterSetWithCharactersInString:@", . ; ( ) : — \n-"];
    NSArray *originalWordArray = [txtStrings componentsSeparatedByCharactersInSet:characterSet];

    //使用谓语对数据进行去空, 使用forin对数组进行遍历去空虽然也行, 但是使用谓语性能更好
    NSArray *noBlankArray = [originalWordArray filteredArrayUsingPredicate:[NSPredicate predicateWithFormat:@"self <> ''"]];
    return noBlankArray;
}

计算每一个单词的频率, 并将结果保存到字典中. key为单词, value为单词的频率. 判断是否支持大小写敏感
我曾经看过一篇技术文章, forin是iOS中遍历性能最高的一个函数. 使用双层遍历. 外层遍历每一个单词, 内层遍历计算该单词的频率.
有一种特殊的情况, 如果一个单词文档中包含100个heap单词和100stack单词, 这种情况如果外层遍历仍然遍历200次的话, 那么性能极差.所以我用了一行代码来优化这个算法: [tempArray removeObject:word];. 这行代码会将计算过频率的单词从元数组中删除, 所以优化后的代码的外层循环只会循环两次. 时间复杂度没有变, 但是N(优) < N(原), 在乘以内层遍历的所需的时间, 性能差别就很明显了.

- (NSMutableDictionary *)getWordFrequencyDictIsCaseSensitive:(BOOL)isCaseSensitive
{
    NSArray *wordArray = [self getWordArray];
    NSMutableArray *originalArray = [wordArray mutableCopy];
    NSMutableDictionary *dict = [NSMutableDictionary dictionary];
    NSMutableArray *tempArray = [originalArray mutableCopy];
    NSInteger times = 0;
 

    for (NSInteger i = 0; i <= originalArray.count; i++) {

        i = 0;
        NSString *compareWord = originalArray[i];
        NSInteger count = 0;
        for (NSString *word in originalArray) {
            
            if (isCaseSensitive == YES) {
                if ([compareWord isEqualToString:word]) {
                    count += 1;
                    times += 1;
                    [tempArray removeObject:word];
                }
            } else {
                if ([compareWord caseInsensitiveCompare:word] == NSOrderedSame) {
                    count += 1;
                    times += 1;
                    [tempArray removeObject:word];
                }
            }
        }

        originalArray = [tempArray mutableCopy];
        dict[compareWord] = [NSString stringWithFormat:@"%zd", count];
        NSLog(@"%计算次数zd>>>>>", times);
    }
    return dict;
}

排序本来想用快排来实现, 可是在数据量不是很多的. 用系统自带的排序方法性能会更好.
排序前需要了解NSComparisonResult, 它是一个枚举类型, 有三个成员变量.

• NSOrderedAscendingThe left operand is smaller than the right operand. 左边的操作对象小于右边的
• NSOrderedSameThe two operands are equal.两个操作对象相同
• NSOrderedDescendingThe left operand is greater than the right operand.左边的操作对象大于右边的操作对象

排序

- (NSArray *)getSortKeysFromDictionary:(NSMutableDictionary *)dictionary withSortType:(SortType)type
{
    NSMutableDictionary *dict = dictionary;
    NSArray *sortArray = [dict keysSortedByValueUsingComparator:^NSComparisonResult(id  _Nonnull obj1, id  _Nonnull obj2) {
        if ([obj1 integerValue] > [obj2 integerValue]) {
            if (type == KLowerType) {
               return (NSComparisonResult)NSOrderedAscending;
            } else {
               return (NSComparisonResult)NSOrderedDescending;
            }
        }
        if ([obj1 integerValue] < [obj2 integerValue]) {
            if (type == KLowerType) {
                return (NSComparisonResult)NSOrderedDescending;
            } else {
                return (NSComparisonResult)NSOrderedAscending;
            }
        }
        return (NSComparisonResult)NSOrderedSame;
    }];
    return sortArray;
}

结尾

以上就是我的代码. 因为我相信大家的水平都很高, 就没有讲的很细. 想深入了解的话, 可以看我的源码欢迎大家fork and pull requests, 因为个人水平所限, 性能还可以在提升, 如果pull request被我接受, 我会发一个6.66的红包表示感谢的~~~
希望大家能通过我的这篇文章有一些收货.在职的努力提高英文水平和算法水平, 找工作的可以找到理想的工作,
加油

                2017夏天的某一天于家中