Как я проходил тестовое задание на летнюю стажировку в Яндекс

в 12:00, , рубрики: c++, c++11 яндекс, java, Алгоритмы, олимпиадное программирование, Программирование, яндекс.алгоритм
image

Привет Хабр, сегодня я расскажу о том, как я проходил тестовое задание на летнюю стажировку в Яндекс. Эта публикация будет полезна начинающим разработчикам, любителям олимпиадного программирования, тем кто неравнодушен к С++ и Java, или просто хочет прочесть интересную статью после трудного рабочего дня.

Чего ожидать от этой статьи?

  • Introduction, о том что такое стажировки в Яндкесе, как и когда на них подать
  • Мотивация к написанию данной статьи
  • Примеры задач, моё решение и краткий разбор (Можно смело пропустить первые два пункта, и начинать именно отсюда)

Introduction

Для тех кто мало знаком с системой отбора на стажировку в Яндексе расскажу вкратце. На сайте яндекса, за несколько месяцев до лета объявляется оплачиваемая вакансия для начинающих разработчиков, в том отделе, в котором вы бы хотели работать (i.e. Яндекс.Диск, Яндекс.Алиса). По ссылке, нужно заполнить форму, о том где Вы учитесь, чем занимаетесь, какой был опыт работы, о чем писали дипломную работы итп. После заполнения формы Вам на почту присылают тестовое задание, на выполнение которого у Вас есть 6 часов, в любой день в течении недели с момента, когда Вы получили это письмо.

Выбрать это время было сложно, поэтому я дотянул практически до последнего дня. А все потому что, я не знал какого рода тестовое задание мне ожидать. Прогуглив много статей, я не нашел ни одного примера, или совета о том, какого рода задачи Яндекс задает на свои стажировки. Именно поэтому, я решил написать эту статью. Я не буду давать правильное решение этих задач, лишь предоставлю то, к чему я успел прийти за отведенные мне 6 часов.

В тестовом задании было 6 задач разной тематики, и разной сложности. Были задачи на графы, на строки, на динамическое программирование, и Ad-Hoc о форматировании времени и чисел с плавающей точкой.

Задача 1. Ошибка

Условия задания

Вы обслуживаете сайт и отслеживаете возникающие проблемы. Клиент получил ошибку после того, как попытался добавить свой пост в систему. Вы хотите понять на каком из серверов эта ошибка произошла.

Есть n серверов, на i-й из них приходится ai процентов запросов, из которых bi процентов завершаются с ошибкой. Для каждого сервера найдите вероятность того, что ошибка произошла именно на нём.

Формат ввода
В первой строке входного файла содержится одно целое число n (1 ≤n≤ 100) — количество серверов.

В каждой из следующих n строк содержится два целых числа ai bi (0 ≤ ai, bi ≤ 100) — вероятность того что запрос пойдет на i-й сервер в процентах и вероятность того что на i-м сервере случится ошибка в процентах.

Гарантируется, что сумма всех ai равна 100 и ошибка в системе может произойти.

Формат вывода
Выведите n строк. В каждой строке должно находиться одно вещественное число (0 ≤ pi ≤ 1) — вероятность, что ошибка произошла на соответствующем сервере.

Абсолютная или относительная погрешность каждого из ответов не должна превышать 10-9.
Пример 1.
Ввод

2
50 1
50 2
Вывод
0.333333333333
0.666666666667

Пример 2.
Ввод

3
10 100
30 10
60 2
Вывод
0.704225352113
0.211267605634
0.084507042254

Для решения данной задачи я решил использовать Java.

Алгоритм работы предельно прост: считываем a, b для n случаев, перемножаем a и b, и сохраняем результат умножения в arr[i], также суммируем результат в переменную total, чтобы посчитать чему равно 100%.
Для вывода нужно просто разделить arr[i] на 100%

Решение

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Locale;
import java.util.StringTokenizer;

public class Main
{
	
	public static void main(String[] args)throws IOException
	{
		Locale.setDefault(Locale.US);//для форматирования вывода с точкой (0.3333, вместо 0,333)
		String line;
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//Buffered Reader это же что и Scanner, но работает во много раз быстрее, и считывает всю строку целиком
		StringTokenizer tk;//используется для разделения целой строки на переменные


		
		int n = Integer.parseInt(br.readLine());
		int arr[] = new int[n];
		int total = 0;
		for(int i = 0; i< n;++i)
		{
			line = br.readLine();
			tk = new StringTokenizer(line);
			//уверен, эта часть кода понятна и без комментариев
			int a = Integer.parseInt(tk.nextToken());
			int b = Integer.parseInt(tk.nextToken());
			arr[i] = (a*b);
			total += arr[i];
		}
		
		for(int i = 0; i< n;++i)
		{
			System.out.printf("%.12fn", (double)arr[i]/ total);
		}
		
	}
}

На этом все, это была первая и последняя задача которую я смог решить полностью. Остальные, к сожалению, не успел, потому что расслабился, думая что все последующие задачи будут на таком же уровне. Увы, это оказалось не так. Я постараюсь разобрать с Вами свой код для следующих задач.

Задача 2. Встречи

Условия задания

Чтобы не мешать коллегам на рабочем месте громкими обсуждениями, ребята назначают встречи на определенное время и бронируют переговорки. При бронировании нужно указать дату и время встречи, её длительность и список участников. Если у кого-то из участников получается две встречи в один и тот же момент времени, то в бронировании будет отказано с указанием списка людей, у которых время встречи пересекается с другими встречами. Вам необходимо реализовать прототип такой системы.

Формат ввода
В первой строке входного файла содержится одно число n (1 ≤ n ≤ 1000) — число запросов.

В следующих n строках содержатся запросы по одному в строке. Запросы бывают двух типов:

APPOINT day time duration k names1 names2… namesk
PRINT day name
day — номер дня в 2018 году (1 ≤ day ≤ 365)

time — время встречи, строка в формате HH:MM (08 ≤ HH ≤ 21, 00 ≤ MM ≤ 59)

duration — длительность встречи в минутах (15 ≤ duration ≤ 120)

k — число участников встречи (1 ≤ k ≤ 10)

namesi, name — имена участников, строки, состоящие из маленьких латинских букв (1 ≤ |name| ≤ 20). У всех коллег уникальные имена. Кроме того гарантируется, что среди участников одной встречи ни одно имя не встречается дважды.

Формат вывода
Если удалось назначить встречу (первый тип запросов), выведите OK.

Иначе выведите в первой строке FAIL, а в следующей строке через пробел список имен участников, для которых время встречи пересекается с другими встречами, в том порядке, в котором имена были даны в запросе.

Для второго типа запросов выведите для данного дня и участника список всех событий на данный момент в этот день в хронологическом порядке, по одному в строке, в формате

HH:MM duration names1 names2 … namesk

где имена участников следуют в том же порядке, что и в исходном описании встречи. Если событий в данный день для этого человека нет, то ничего выводить не нужно.
Пример 1.
Ввод

7
APPOINT 1 12:30 30 2 andrey alex
APPOINT 1 12:00 30 2 alex sergey
APPOINT 1 12:59 60 2 alex andrey
PRINT 1 alex
PRINT 1 andrey
PRINT 1 sergey
PRINT 2 alex
Вывод
OK
OK
FAIL
alex andrey
12:00 30 alex sergey
12:30 30 andrey alex
12:30 30 andrey alex
12:00 30 alex sergey

Я потратил много времени на обдумывание решения этой задачи, перепробовал много вариантов, но так и не решил как наиболее эффективно упаковать время+день + количество человек. Я хотел написать struct {int day; int time_ms; string people[];}, но это бы неэффективно занимало память.

Другим вариантом было представить все дни и время линейно, и создать струтуру(meeting) которая хранит три переменные — начало встречи как (day * 24 * 60) (hour* 60 + minute), конец встречи (start+ duration), имена людей этой встречи. Все объекты данной структуры можно упаковать в вектор(vec). Затем, при попытке назначить новую встречу, проверить есть ли среди существующих в векторе встреч такая, для которой следующее утверждение является истинным.

vec[i] -> start<= meeting->start && vec[i] -> end >= meeting->start
or
vec[i] -> start <= meeting->end && vec[i] -> end >= meeting->end

Если да, сказать что это время занято, если нет, добавить новый элемент в вектор.
Я также пробовал решить эту задачу с dict на Python, но осознав что потратил очень много времени перешел к другим задачам. Я вернулся к этой задаче буквально за 10 минут до конца 6 часов, когда у меня уже практически не было сил думать, написал что успел и сдал хоть что то. Вероятно, если бы я доработал именно второй вариант решения это задачи, OnlineJudge бы принял. Но я сдал следующий код на Java. Его можно смело пропустить, он практически ничего не делает.

Решение

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class p2
{

	public static void main(String[] args) throws IOException
	{
		String line;
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer tk;

		long unixTime = System.currentTimeMillis() / 1000L;
		System.out.println(unixTime);

		int n = Integer.parseInt(br.readLine());
		for (int i = 0; i < n; ++i)
		{
			line = br.readLine();
			tk = new StringTokenizer(line, " :");
			String cmd = tk.nextToken();

			if (cmd.compareTo("APPOINT") == 0)
			{
				int day = Integer.parseInt(tk.nextToken());
				int hour = Integer.parseInt(tk.nextToken());
				int minute = Integer.parseInt(tk.nextToken());
				int duration = Integer.parseInt(tk.nextToken());
				int peopleN = Integer.parseInt(tk.nextToken());
				String people[] = new String[peopleN];

				for (int j = 0; j < peopleN; ++j)
				{
					people[j] = tk.nextToken();
				}

				int start = (hour * 60) + minute;
				int end = start + duration;

			}
		}
	}
}

Задача 3. Автодополнение

Условия задания

Аркадий реализовал интерактивную систему автодополнения, которая должна позволить ему быстрее набирать тексты университетских работ, в том числе и дипломной.

Система запоминает все слова, которые уже есть в тексте. Если Аркадий набирает очередное слово, введенная непустая часть которого совпадает с префиксом ровно одного из уже введенных слов, то после нажатия специальной комбинации клавиш введенную часть можно мгновенно дополнить имеющимся словом.

Например, Аркадий уже ввел слова дипломная работа и автодополнение в различных системах. Рассмотрим несколько вариантов очередного слова, которое ему нужно ввести:

  • диплом — после ввода первого символа система предложит принять автодополнение дипломная, но оно не подходит;
  • работа — после ввода первого и второго символа система не будет ничего предлагать, т.к. есть два различных слова в тексте, которые начинаются с текущего префикса, но после ввода третьего символа останется только одно слово (предложенное автодополнение следует принять);
  • различие — вновь вариант с автодополнением появится только после ввода третьего символа, но в этот раз принимать предложенный вариант не следует.

У Аркадия не работает клавиша удаления введенных символов, поэтому удалять символы из текста он не может.

Аркадий также решил, что не будет использовать автодополнение, если предлагаемое слово является началом набираемого, но не совпадает с ним целиком.

Помогите Аркадию определить, сколько раз он воспользуется функцией автодополнения, если хочет максимально уменьшить количество нажатий на клавиши клавиатуры, соответствующие буквенным символам.

Формат ввода
В первой строке входных данных записано одно целое число n (1 ≤ n ≤ 100 000) — количество слов, которые собирается набрать Аркадий. Во второй строке записаны n слов si (1 ≤ |si| ≤ 1000). Все слова в строке состоят только из строчных букв английского алфавита и разделены одиночными пробелами.

Суммарная длина всех слов не превосходит 1 000 000 символов.

Формат вывода
В единственной строке выведите одно целое число: количество нажатий буквенных клавиш на клавиатуре.
Пример 1
Ввод
3
hello world hello
Вывод
11
Пример 2
Ввод
5
an apple a big apple
Вывод
13
Пример 3
Ввод
5
aaaaa aaaab aaaaa abaaa abaaa
Вывод
22

Эта задача казалась мне намного проще, чем она оказалась в действительности, простите за тавтологию. В итоге, мое решение было не полным — выходил WA на 14м тесте. Тут я тоже потратил много времени, пытаясь понять где может быть ошибка, но так ни к чему и не пришел. Писать я решил на С++, потому что подумал что решить эту задачу будет просто при помощи структуры данных set.

Решение

#include <iostream>
#include <set>

using namespace std;

int main() 
{
  set<string> myset;
  string in;
  int n; cin >> n;
  
  int count = 0;
  
  for(int i = 0;i<n;++i)
  {
	cin>>in;  
	if(myset.empty())
	{
		count += in.length();
		myset.insert(in);
	} 
	
	else if(myset.find(in) != myset.end())
	{
		//if a word is in set
		//check if other words in set contain similar chars
		//count += the greatest common subsequence
		int max = 0;
		for(auto e: myset)
		{
			int temp = 0;
			//case when entered sequence is less than element in set
			
			if(e == in)
			{
				++count;
			}
			
			if(e.length() > in.length())
			{
				
				for(int j = 0; j< in.length(); ++j)
				{
				
					if(e[j] == in[j])
					{
						++temp;
					}
					else
					{
						break;
					}
				
				}
				
				if(temp > max)
				{
					max = temp;
				}
				
			}
			
			
			else if(e.length() <= in.length() && e != in)
			{
				for(int j = 0; j< e.length(); ++j)
				{
				
					if(e[j] == in[j])
					{
						++temp;
					}
					else
					{
						break;
					}
				}
				if(temp > max)
				{
					max = temp;
				}
			}
			
		}
		count += max;
	}
	else if(myset.find(in) == myset.end())
	{
		//case when entered word is not in the set
		count += in.length();
		myset.insert(in);
	}
	
  }
  cout << count<<endl;
  return 0;
}

В целом эту задачу можно разбить на два больших случая: вводится новое слово (word is not in the set) и вводится слово, которое уже вводилось ранее (word in set).

Второй случай разбивается на несколько других случаев, и проверяется 1. есть ли слова в set начинающиеся с таких же символов(символа), что и наше вводимое слово, 2. является ли наше слово subsequence какого-то другого слова в set. Как видно в коде, в каждом из случаев суммируются разное количество нажатия на клавиши в переменную count.

Задача 4. Тимбилдинг

Условия задания

Тимбилдинг — весёлое сплочающее мероприятие. Коллеги активно участвуют в конкурсах, квестах, вместе преодолевают игровые трудности. Подчас люди так увлекаются, что реорганизовать их для какой-то новой активности довольно сложно. Прямо сейчас ведущему нужно разбить всех коллег на две команды так, чтобы каждые два человека в одной команде хорошо знали друг друга — и это непростая задача.

Вам дан граф, в котором каждому человеку сопоставлена ровно одна вершина. Ребро (u, v) означает, что коллега u хорошо знает коллегу v (и в то же время коллега v хорошо знает коллегу u). Проверьте, можно ли разбить вершины графа на два множества требуемым образом, и, если это возможно, выведите любое подходящее разбиение.

Формат ввода
В первой строке даны два целых числа n и m (2 ≤ n ≤ 5000, 0 ≤ m ≤ 200000) — число вершин и число рёбер в графе.

В следующих m строках даны описания рёбер — пары целых чисел a b (1 ≤ a, b ≤ n, a ≠ b), означающих наличие ребра между вершинами a и b.

Гарантируется, что каждая пара вершин соединена не более чем одним ребром, и что никакая вершина не соединена с собой.

Формат вывода
Если разбить вершины требуемым образом нельзя, выведите -1.

Иначе в первой строке выведите число k (1 ≤ k < n) — количество вершин в одной из частей разбиения.

В следующей строке выведите k чисел — вершины из этой части разбиения.

В следующей строке выведите n — k чисел — вершины из второй части разбиения.

Каждая вершина должна принадлежать ровно одной из этих частей.
Пример 1
Ввод
3 1
1 2
Вывод
2
1 2
3
Пример 1
Ввод
3 0
Вывод
-1

Тут у меня уже началась паника, и та уверенность, которую я чувствовал после решения первой задачи растворилась бесследно. Я не знал на какой задаче именно сконцентрироваться, и просто метался читая условия то одной, то другой задачи. На то, что совладать с паникой тоже ушло около 20 минут. Это катастрофически много для решения контестных задач.

Здесь я тоже решил использовать set. А точнее, 3 Set'a: initial — где хранятся значения от 1 до n, teamA, куда будут добавляться первые звенья графа, и teamB куда будут добавляться звенья, не соедененные с teamA, а также все оставшиеся звенья в initial.

Мой алгоритм прост, но видимо, Яндекс ждал от меня большего. WA на третьем кейсе.

решение

#include<iostream>
#include<set>
 using namespace std;
 
 
 int main()
 {
	int people; cin >>people;
	int pairs; cin >> pairs;
	
	set<int> initial;
	set<int> teamA;
	set<int> teamB;
	
	int a;
	int b;
	
	if(pairs == 0)
	{
		cout<<"-1"<<endl;
	}
	else
	{
		//fill set with people 
		for(int i = 1;i<=people;++i)
		{
			initial.insert(i);
		}
		for(int i = 0;i<pairs;++i)
		{
			cin >> a;
			cin >> b;
			// case when a and b aren't in teamB
			
			
			if(initial.find(a) != initial.end() && initial.find(a) != initial.end() && !teamA.empty())
			{
				teamB.insert(a);
				teamB.insert(b);
				
				initial.erase(a);
				initial.erase(b);
			} 
			
			else if(teamB.find(a) == teamB.end() && teamB.find(b) == teamB.end())
			{
				teamA.insert(a);
				teamA.insert(b);
				
				initial.erase(a);
				initial.erase(b);
			} 
			else if ((teamA.find(a) != teamA.end() && teamB.find(b) != teamB.end()) or 
					 (teamA.find(b) != teamA.end() && teamB.find(a) != teamB.end()))
			{
				for(auto e: teamB)
				{
					teamA.insert(e);
					teamB.erase(e);
				}
			}
			
		}
	}
	
	
	cout <<"teamA"<< endl;

	for( auto e: teamA)
	{
		cout << e<<" ";
	}
	cout <<endl<<"teamB"<< endl;
	
	for( auto e: teamB)
	{
		cout << e<<" ";
	}
	cout << endl;
	 return 0;
 }

Задача 5. Библиотека

Условия задания

Коля очень любит читать, и он ходил бы в библиотеку каждый день. К вечеру он остаётся довольным, только если прочитал ровно на одну книгу больше, чем вчера. Однако, к сожалению, библиотека не работает по субботам и воскресеньям. Поэтому Коля ходит в неё каждый рабочий день и берёт там за раз k книг — больше нельзя по правилам. Однако, Колю радует, что брать новые k книг можно, даже если ты не отдал какие-то книги из взятых ранее. Также Колю радует, что в его домашней библиотеке есть запас из m книг.

Вам известно, какой сегодня день недели. Коля недавно встал и задался целью прочитать сегодня ровно одну книгу. Насколько долго Коля может оставаться довольным, если будет ходить в библиотеку каждый раз, когда это возможно, начиная с сегодняшнего дня? Можно считать, что запас книг в библиотеке бесконечен.

Формат ввода
В первой строке входного файла даны три целых числа k, m, d — лимит на количество книг, которые можно взять в библиотеке в день, количество книг дома у Коли и сегодняшний день недели (1 ≤ k ≤ 109, 0 ≤ m ≤ 109, 1 ≤ d ≤ 7). Суббота и воскресенье обозначаются числами 6 и 7.

Формат вывода
Выведите одно число — максимальное количество дней в периоде, в течение которого Коля каждый день сможет читать столько книг, чтобы оставаться довольным.
Пример 1.
Ввод
4 2 5
Вывод
4
Пример 2.
Ввод
4 3 5
Вывод
5

Решая эту задачу, я понял как сильно мне не хватает
uDebug. Мое решение выкинуло WA на 10м тесте.

Решение

#include<iostream>

using namespace std;

int main()
{
	int bks; cin >> bks;
	int lib; cin >> lib;
	int day; cin >> day;
	
	
	int total = bks + lib;
	int count = 0;
	int read = 0;
	while(true)
	{
		++count;
		++read;
		if(day>=1 && day <= 5)
		{
			total -= read;
			if(total == 0)
			{
				break;
			}
			else
			{
				total += bks;
			}
		}	
		
		else if(day == 6)
		{
			total -= read;
			if(total == 0)
			{
				break;
			}
		}
		else if(day == 7)
		{
			total -= read;
			if(total == 0)
			{
				break;
			}
			day = 0;
		}
		++day;
	}
	cout << count;
	return 0;
}

Задача 6. Мобилизация

Эту задачу я в принципе не стал сдавать во время контеста. Написал код лишь к считыванию и выводу. После завершения контеста я разобрал все задачи кроме этой. Если честно, до сих пор не могу понять что именно нужно делать. Буду рад, комментариям Вашим комментариям.

Условия задания

В Яндексе снова стартует проект «Мобилизация»! Компания набирает на трёхмесячную подготовку n молодых людей, увлечённых мобильной разработкой. В начале проекта был проведён тест, где скилл участника i в разработке был оценен как ai, а скилл в управлении как bi.

На время проекта участников необходимо разделить на две равные по количеству участников команды — разработчиков и менеджеров. Планируется сделать это таким образом, чтобы максимизировать суммарную пользу, приносимую всеми участниками. Если участнику достанется роль разработчика, его польза будет равняться ai, в противном случае — bi.

Но даже занятые проектом, участники находят время для получения новых знаний! Иногда участники приносят сертификаты о прохождении курсов, где сказано, что скилл участника i в разработке или же в управлении увеличился на di. В таком случае может быть выгодно переформировать команды для максимизации суммарной пользы (равные размеры команд необходимо сохранить).

Ваша задача помочь Яндексу и после рассмотрения каждого нового принесённого участником сертификата посчитать текущую суммарную пользу команд.

Формат ввода
В первой строке входного файла дано число n (2 ≤ n ≤ 2 ⋅ 105, n — чётное) — количество участников проекта. Вторая строка задаёт n целых чисел ai (0 ≤ ai ≤ 109) — скилл каждого из участников в разработке. Следующая строка в том же формате задаёт скилл участников в управлении bi (0 ≤ bi ≤ 109).

Следующая строка содержит целое число m (1 ≤ m ≤ 105) — количество принесённых участниками сертификатов. Каждая из следующих m строк содержит три целых числа numi, typei, di (1 ≤ numi ≤ n, 1 ≤ typei ≤ 2, 1 ≤ di ≤ 104) — номер участника, тип увеличиваемого скилла (1 — разработка, 2 — управление) и значение увеличения соответствующего навыка.

Формат вывода
После обработки каждого запроса на поступление нового сертификата выведите текущую суммарную пользу всех участников.
Пример 1.
Ввод
4
7 15 3 4
10 10 0 6
3
1 1 4
4 1 6
2 2 10
Вывод
34
35
43

Код который я успел написать

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class p6 
{
	public static void main(String[] args)throws IOException
	{
		String line;
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer tk;
		int n = Integer.parseInt(br.readLine());
		
		int a[] = new int[n];
		int b[] = new int[n];
		
		tk = new StringTokenizer(br.readLine());
		
		int aSum = 0;
		for(int i = 0;i<n;++i)
		{
			a[i] = Integer.parseInt(tk.nextToken());
			aSum += a[i];
		}
		int bSum = 0;
		for(int i = 0;i<n;++i)
		{
			b[i] = Integer.parseInt(tk.nextToken());
			bSum += b[i];
		}		
	}
}

В целом, мне понравился этот опыт. Немного обидно, что я не смог выложиться в полной мере. Но зато, теперь я знаю что из себя представляют задачи на стажировку в Яндекс, а после прочтения этой статьи знаете и Вы. Надеюсь, эта статься была интересна и хоть немного полезна для Вас. Я буду искренне рад любым комментариям и советам. Во время написания этой статьи, я так же расчитывал, что Вы поделитесь своими вариантами решения этих задач, которые вероятно возникали у Вас в голове, или на бумаге при прочтении условий.

Всем спасибо!

Автор: iworeushankaonce

Источник

* - обязательные к заполнению поля


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js