Макс

Родной город: Омск

Фото галерея: смотреть

Контакты: написать

О себе:

Интересы:

- программирование

- интернет

- психология

- менеджмент

- автоматизация

Погляди
Голосование

Нравиться ли вам блог

  Да
  Нет
  Я тут случайно

 

ГлавнаяКарта сайтаПечать страницы

Что надо знать начинающему программисту


 

Начинающему программисту

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


Некоторые рассмотренные здесь темы могут вообще не пригодиться некоторым программистам, а могут и быть обязательными, решать вам. Мой совет – старайтесь как можно больше изучать темы/разделы/аспекты указанные здесь.


И так, в качестве обязательных знаний:

- Структуры данных
- Алгоритмы и «концепции»
- Язык программирования

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

Структуры данных:


- Массивы и строки
- Связанные списки
- Стек и очередь
- Деревья и графы


Алгоритмы и «концепции»:
- Сортировка и поиск
- Рекурсия
- Манипуляция битами
- Объектно-ориентированное проектирование


Язык программирования:
- Базовые составляющие
- «Домашние» реализованные проекты
- Как можно больше
- А теперь по полочкам, что, как и почему?

Структуры данных

Массивы и строки

Задачки для определения уровня кандитата:
1) «Реализуйте функцию определяющую все ли символы неповторяющиеся в заданной строке».
Для простоты представим, что имеется ASCII набор символов (если нет, нужно будет изменить размер «контейнера», логика по-любому не изменится).

2) Для размышления — классическая задача: «Переверните C-строку (имеется в виду, что “abcd” – это пять символов, пятый – завершающий нуль-символ ‘’)».

3) В качестве домашнего задания, попробуйте решить эту задачку: «Дано изображение в виде массива NxN, где каждый элемент – один пиксел и каждый пиксел весит в 4 байта. Напишите функцию, которая перевернет изображение на 90 градусов».

Связанные списки

Вопросы по связанным спискам, мягко говоря, достаточно общие. Вопрос может быть от простого «удалить узел из связанного списка» до более мыслительно-напрягающих. Помните, когда вас спросят про связанные списки, уточните -о каком именно списке идет речь — односвязном или двухсвязном. Вы должны знать, опять таки, обязательно, как создать список и как удалить узел из односвязного списка.

1) Примеры задачи: "Напишите код удаляющий повторяющиеся элементы из несортированного связанного списка".

2) "Реализуйте алгоритм, который удаляет узел из середины односвязного списка, есть доступ только к этому узлу".

3) Вопросы для размышления, ака домашнее задание:
"У вас есть два числа представленные в виде связанного списка, где каждый узел содержит одну цифру. Числа хранятся в обратном порядке. Напишите функцию, которая вычилсяет сумму этих чисел и возвращает в виде связанного списка.
Пример:
Вход: (5 -> 9 -> 2), (3 -> 1 -> 5)
Выход: (8 -> 0 -> 8)".
"Найдите середину связанного списка".

Стек и очередь

Необходимые знания — умение реализовать стек и очередь. Не забудьте проверить все входные значения и «граничные случаи» в реализованных методах класса.

1) "Напишите класс my_queue, который реализует очередь используя два стека".

2) Для размышления: "Напишите программу, которая сортирует стек в восходящем порядке".

Деревья и графы

Вопросы по деревьям и графам в основном «бывают» в следующих формах:
 - Реализуйте дерево / найдите узел / удалите узел / другие немаловажные алгоритмы
 - Реализуйте модифицированный вариант известного алгоритма


Строго рекомендуется хорошенько подготовиться по деревьям и графам перед собеседованием и помните — «не все бинарные деревья — бинарные деревья поиска».

Вы должны уметь с легкостью реализовать следующие алгоритмы:
 - Прямой обход дерева (pre-order)
 - Симметричный обход (in-order)
 - Обратный обход (post-order)
 - Вставка узла


Графовые обязательные знания:
 - Поиск в глубину (Depth First Search)
 - Поиск в ширину (Breadth First Search)

1) "Дан сортированный (в восходящем порядке) массив, напишите алгоритм создающий бинарное дерево минимальной высоты".

Алгоритм:
 - Вставить в дерево средний элемент массива
 - Вставить (в левое поддерево) элементы «левого подмассива»
 - Вставить (в правое поддерево) элементы «правого подмассива»
 - И так рекурсивно

2) Для размышлений: "Реализуйте не рекурсивный симметричный обход дерева".

Алгоритмы и концепции

Сортировка и поиск

Понимание/знание известных алгоритмов сортировки очень важно, поскольку многие решения связанные с сортировкой или поиском, мягко говоря, требуют владения этими алгоритмами. Хороший способ показать свои знания перед интервьюером, когда дана здача на сортировку – это «пробежать» по известным алгоритмам и увидеть/выяснить какой из них лучше всего подходит для решения данной задачи. Вы получите и решение и то, что интервьюер будет довольным вашими «разными» способов решения одной и той же задачи.
Например, "у вас есть большой массив обьектов Employee, сортируйте служащих по возрастам".

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


Какие алгоритмы следует знать (какие же эти «известные»):
- Пузырьковая сортировка (bubble sort).
- Сортировка выбором (selection sort).
- Сортировка слиянием (merge sort).
- Быстрая сортировка (quick sort).
- Блочная сортировка (bucket sort).

1) «У вас два сортированных массива A и B, размер А больше настолько, чтобы содержать массив B. Напишите метод, слияющий B в А сохраняя порядок сортировки».

2) «Дан массив, в котором каждая строка и каждый столбец сортированы, напишите функцию находящую элемент в массиве».

3) Задачи для размышления:
«Реализуйте алгоритм бинарного поиска».
«Как организовать сортировку миллиона чисел с плавающей точкой?».
«Реализуйте сортировку массива из обьектов Employee по зарплатам (будем считать, что Employee содержит поля для имени, возраста, зарплаты и адреса)».

Рекурсия

Есть огромное множество задач с рекурсией, многие задачи подчиняются шаблону. Если задачу можно разбить на подзадачи, то это уже подсказка, что задача «рекурсивная». Если вы услышите задачи, вроде «Напишите код, выводящий первые n…», «Реализуйте функцию считающую все...», то сперва попытайтесь использовать, ну хотя бы подумать использовать, рекурсивный метод решения.
Нужно заметить, что во всех случаях практика – ваш лучший друг, как много задач вы решите, тем легче для вас становится не только решение новой, но и ориентировка на метод решения, собственно, задачи.


И так, сначала попытайтесь распознать подзадачи. Решите/найдите «базовую» задачу, ту, при которой рекурсия остановится (в основном это жестко кодированное значение). Решите задачу для 2-й подзадачи и поймите как решить третью подзадачу, базируясь на второй. Обобщайте решение для n-й подзадачи.


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

1) «Напишите функцию, генерирующую n-ое число Фибоначчи».

2) Для размышления:
«Напишите функцию, которая возвращает все подмножества некоторого множества».
«Решите задачу ферзя»

Манипуляция битами

Манипуляция битами может быть страшной для многих кандидатов, хотя не должна.
Достаточно просто делать ошибку при решении этих задач, так что будьте осторожны, вернее – внимательны. Рассматривайте внимательно каждую строку написанную вами кода.
Не забудьте про сдвиг, x << y (левый сдвиг) означает, что x сдвиган налево на y бит и x >> y (правый сдвиг), соответственно, у бит в правую сторону.

1) Есть одна достаточно популярная задача, попробуйте решить ее сами (привожу с «обратной стороны») – «Объясните следующий код: (( n & (n — 1) ) == 0)».
«Даны два 32-битовые числа, N и M. Еще есть две позиции битов, i и j. Напишите функцию, которая установит все биты между i и j в N равную M(то есть M становится подстрокой N)
Пример:
Вход: N = 100000000, M = 101, i = 2, j = 3
Выход: N = 100010100».

2) Для размышлении: «Дано число с плавающей точкой в виде строки, выведите бинарное представление.»

Обьектно-ориентированное проектирование

Вопросы по ООП (здесь П — проектирование) имеют огромную важность, по крайней мере я так думаю. Знание ООП оказывает некоторое доверие на интервьюера, поскольку становиться понятным, что кандидат «поймет» диаграммы классов того проекта, на котором будет работать. Это только маленький плюс, есть другие немаловажные достоинства ООП, выступающие в пользу кандидата. А вот отсутствие знании вызовет у интервьюера чувство «кто там следующий?». Это, конечно, относится к должностям, связанным с ООП, а то, по-мне разработчику драйверов вряд-ли спросят об ООП. Тем не менее, во время интервью будьте готовы, что вас попросят спроектировать некоторое приложение, или даже «не-приложение», например, телевизор. Попросят рассказать об отношениях между, скажем, пультом и телевизором. Будьте готовы на вопросы типа «Чем отличается “is-a” от “has-a”?».

1) «Спроектируйте чат-сервер».

2) Для размышлении: «Спроектируйте структуры данных для онлайн-читалки книг».

Интересные ссылки.

1.CodeForces — Периодически проводятся онлайн-контесты. Имеются разборы некоторых соревнований.
2. Timus — Содержит крупнейший в России архив задач с различных соревнований по спортивному программированию.
3. CodeChef — Ежемесячные on-line контесты.
4. ACMP — Сайт содержит архив задач по олимпиадному программированию со встроенной проверяющей системой.
5. Informatics.mccme.ru — Так же полезный сборник задач, удобная навигация.






Дата публикации:19.09.2011 
Ирина Владимировна
avatar
02.03.2013

Максим, как вы считаете на каком этапе обучения программиста необходимо познакомить его с такой дисциплиной как "технология разработки программных продуктов"?
Ирина Владимировна
avatar
02.03.2013

Максим, как вы считаете на каком этапе обучения программиста необходимо познакомить его с такой дисциплиной как "технология разработки программных продуктов"?
JoshuaSnugh
avatar
13.06.2017

Я считаю, что Вы ошибаетесь. Могу отстоять свою позицию. Пишите мне в PM.


-----
Титан гель реальные отзывы покупателей и врачей
Kirbyphity
avatar
23.06.2017

Самое запоминающиеся впечатление от релакса, это же беспременно поездка с дорогим особой либо семьей на шикарной яхте на просторах перечисленных водах, путешествие что легко и решений будет расположить у личной жизни из помощью обслуживания презентованной организации. данная компания снабжает всяческие требуемые пропозиции по лизинга судна на Эгейском, Средиземном, Балтийском, Карибском, Ионическом плюс иных морях. только на сайте клиент может сделать для группой отдых по низкими ценам также обширным инициативой: оформить плавание лишь на сутки, 7 дней, месяц, выбрать необычный трассу, набрать умелую команду совместно с командиром, запись различных незаменимых документов, помощь в выборе боера, технический диагностика на исправность . фирма именно по чартеру катеров выставляет Вам комфортабельные двигательные также ветровые яхты разных объемов и категории прайс-листа в США, Канаде, Таиланде, Турции, Карибах, Франции, Польше, Греции также других странах. только на информационном сайте предпринимательства аренда моторной яхты клиент сможет получить все необходимые факты непосредственно для связи, осмотреть фотографии, парк яхт и прочитать ответы от потребителей. С нетерпежем ждем ваши конференцию также заявок.
RonaldOreni
avatar
23.06.2017

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