При заполнении анкеты на должность разработчика Яндекс.Музыки для iOS просят выполнить тестовые задания. Задания выложены в открытом виде, никакой просьбы не разглашать задания и не публиковать решения нет.
Приступим.
Вопрос 1. В системе авторизации есть следующее ограничение на формат логина: он должен начинаться с латинской буквы, может состоять из латинских букв, цифр, точки и минуса и должен заканчиваться латинской буквой или цифрой. Минимальная длина логина — 1 символ. Максимальная — 20 символов.
Напишите код, проверяющий, соответствует ли входная строка этому правилу.
Используем регулярное выражение. Класс NSRegularExpression появился в iOS 4.0.
BOOL loginTester(NSString* login) {
NSError *error = NULL;
NSRegularExpression *regex = [NSRegularExpression
regularExpressionWithPattern:@"\A[a-zA-Z](([a-zA-Z0-9\.\-]{0,18}[a-zA-Z0-9])|[a-zA-Z0-9]){0,1}\z"
options:NSRegularExpressionCaseInsensitive error:&error];
// Здесь надо бы проверить ошибки, но если регулярное выражение оттестированное и
// не из пользовательского ввода - можно пренебречь.
NSRange rangeOfFirstMatch = [regex rangeOfFirstMatchInString:login options:0 range:NSMakeRange(0, [login length])];
return (BOOL)(rangeOfFirstMatch.location!=NSNotFound);
}
Здесь готовый проект, использующий этот код. Можно потестировать.
Мне кажется, этот вопрос нацелен на то, чтоб отсеять тех, кто боится регулярных выражений.
Вопрос 2. Напишите метод, возвращающий N наиболее часто встречающихся слов во входной строке.
Гораздо интересней.
-(NSArray*)mostFriquentWordsInString:(NSString*)string count:(NSUInteger)count {
// получаем массив слов.
// такой подход для человеческих языков будет работать хорошо.
// для языков, вроде китайского, или когда язык заранее не известен,
// лучше использовать enumerateSubstringsInRange с опцией NSStringEnumerationByWords
NSMutableCharacterSet *separators = [[NSCharacterSet whitespaceAndNewlineCharacterSet] mutableCopy];
[separators formUnionWithCharacterSet:[NSCharacterSet punctuationCharacterSet]];
NSArray *words = [string componentsSeparatedByCharactersInSet:separators];
NSCountedSet *set = [NSCountedSet setWithArray:words];
// тут бы пригодился enumerateByCount, но его нет.
// будем строить вручную
NSMutableArray *selectedWords = [NSMutableArray arrayWithCapacity:count];
NSMutableArray *countsOfSelectedWords = [NSMutableArray arrayWithCapacity:count];
for (NSString *word in set) {
NSUInteger wordCount = [set countForObject:word];
NSNumber *countOfFirstSelectedWord = [countsOfSelectedWords count] ?
[countsOfSelectedWords objectAtIndex:0] : nil; // в iOS 7 появился firstObject
if ([selectedWords count] < count || wordCount >= [countOfFirstSelectedWord unsignedLongValue]) {
NSNumber *wordCountNSNumber = [NSNumber numberWithUnsignedLong:wordCount];
NSRange range = NSMakeRange(0, [countsOfSelectedWords count]);
NSUInteger indexToInsert = [countsOfSelectedWords indexOfObject:wordCountNSNumber inSortedRange:range
options:NSBinarySearchingInsertionIndex
usingComparator:^(NSNumber *n1, NSNumber *n2)
{
NSUInteger _n1 = [n1 unsignedLongValue];
NSUInteger _n2 = [n2 unsignedLongValue];
if (_n1 == _n2)
return NSOrderedSame;
else if (_n1 < _n2)
return NSOrderedAscending;
else
return NSOrderedDescending;
}];
[selectedWords insertObject:word atIndex:indexToInsert];
[countsOfSelectedWords insertObject:wordCountNSNumber atIndex:indexToInsert];
// если слов уже есть больше чем нужно, удаляем то что с наименьшим повторением
if ([selectedWords count] > count) {
[selectedWords removeObjectAtIndex:0];
[countsOfSelectedWords removeObjectAtIndex:0];
}
}
}
return [selectedWords copy];
// можно было бы сразу вернуть selectedWords,
// но возвращать вместо immutable класса его mutable сабклас нехорошо - может привести к багам
}
// очень интересный метод для юнитестов: правильный результат может быть разным и зависит от порядка слов в строке.
Я бы именно такой подход и использовал, если бы мне нужно было решить эту задачу в реальном iOS приложении, при условии, что я понимаю, откуда будут браться входные данные для поиска и предполагаю, что размеры входной строки не будут больше нескольких мегабайт. Вполне разумное допущение для iOS приложения, на мой взгляд. Иначе на входе не было бы строки, а был бы файл. При реально больших входных данных прийдется попотеть над регулярным выражением для перебора слов, чтоб избавиться от одного промежуточного массива. Такое регулярное выражение очень зависит от языка — то что сработает для русского не проканает для китайского. А вот что делать со словами дальше — кроме прямолинейного алгоритма в голову ничего не приходит. Если бы нужно было выбрать одно наиболее часто встречающееся слово — это Fast Majority Voting. Но вся красота этого алгоритма в том, что он работает для выбора одного значения. Модификаций алгоритма для выбора N значений мне не известны. Самому модифицировать не получилось.
Вопрос 3. Используя NSURLConnection, напишите метод для асинхронной загрузки текстового документа по HTTP. Приведите пример его использования.
-(void)pullTextFromURLString:(NSString*)urlString completion:(void(^)(NSString*text))callBack {
NSURLRequest *request = [NSURLRequest requestWithURL: [NSURL URLWithString:urlString]
cachePolicy:NSURLRequestUseProtocolCachePolicy timeoutInterval:60.0];
[NSURLConnection sendAsynchronousRequest:request
queue:[NSOperationQueue mainQueue]
completionHandler:^(NSURLResponse *response, NSData *data, NSError *error)
{
if (error) {
NSLog(@"Error %@", error.localizedDescription);
} else {
// вообще, не мешало бы определить кодировку, чтоб не было неприятностей
callBack( [[NSString alloc]initWithData:data encoding:NSUTF8StringEncoding] );
}
}];
}
Тут все просто. Наверное, как и первый вопрос, этот вопрос на знаю / не знаю.
Вопрос 4. Перечислите все проблемы, которые вы видите в приведенном ниже коде. Предложите, как их исправить.
NSOperation *operation = [NSBlockOperation blockOperationWithBlock:^{
for (int i = 0; i < 1000; ++i) {
if ([operation isCancelled]) return;
process(data[i]);
}
}];
[queue addOperation:operation];
Лично я вижу проблему в том, что переменная operation, «захваченная» блоком при создании блока, еще не проинициализирована до конца. Какое реально значение этой переменной будет в момент «захвата», зависит от того, используется ли этот код в методе класса или в простой функции. Вполне возможно, что сгенерированный код будет вполне работоспособен и так, но мне этот код не ясен. Как выйти из ситуации? Так:
NSBlockOperation *operation = [[NSBlockOperation alloc] init];
[operation addExecutionBlock:^{
for (int i = 0; i < 1000; ++i) {
if ([operation isCancelled]) return;
process(data[i]);
}
}];
[queue addOperation:operation];
Возможно, достаточно было бы просто добавить модификатор __block в объявление переменной operation. Но так, как в коде выше — наверняка. Некоторые даже создают __weak копию переменной operation и внутри блока используют ее. Хорошо подумав я решил, что в данном конкретном случае, когда известно время жизни переменной operation и блока — это излишне. Ну и я бы подумал, стоит ли использовать NSBlockOperation для таких сложных конструкций. Разумных доводов привести не могу — вопрос личных предпочтений.
Что еще с этим кодом не так? Я не люблю разных магических констант в коде и вместо 1000 использовал бы define, const, sizeof или что-то в этом роде.
В длинных циклах в objective-c нужно помнить об autoreleased переменных и, если такие переменные используются в функции или методе process, а сам этот метод или функция об этом не заботится, нужно завернуть этот вызов в @autoreleasepool {}. Создание нового пула при каждой итерации цикла может оказаться накладным или излишним. Если не используется ARC, можно создавать новый NSAutoreleasePool каждые, допустим, 10 итераций цикла. Если используется ARC, такой возможности нет. Кстати, это, наверное, единственный довод не использовать ARC.
По коду не ясно, меняются ли данные в процессе обработки, обращается ли кто-то еще к этим данным во время обработки из других потоков, какие используются структуры данных, заботится ли сам process о монопольном доступе к данным тогда когда это нужно. Может понадобиться позаботиться о блокировках.
Вопрос 5. Есть таблицы:
CREATE TABLE tracks (
id INT NOT NULL AUTO_INCREMENT,
name VARCHAR(255) NOT NULL,
PRIMARY KEY (id)
)
CREATE TABLE track_downloads (
download_id BIGINT(20) NOT NULL AUTO_INCREMENT,
track_id INT NOT NULL,
download_time TIMESTAMP NOT NULL DEFAULT 0,
ip INT NOT NULL,
PRIMARY KEY (download_id)
)
Напишите запрос, возвращающий названия треков, скачанных более 1000 раз.
Вот такой запрос справляется с задачей замечательно:
select name from tracks where id in
(select track_id from
(select track_id, count(*) as track_download_count from track_downloads
group by track_id order by track_download_count desc)
where track_download_count > 1000)
Проверено в sqlite. Предполагаю, что можно сократить на один select, но не знаю как.
Наличие этого вопроса в задании вполне объяснимо — примерно этим приложение и будет заниматься.
Жду критики.
Автор: valeriyvan
