По вашему запросу ничего не найдено :(
Убедитесь, что запрос написан правильно, или посмотрите другие
наши статьи:
Еще в 2000 году до нашей эры, когда алгоритмы только были изобретены, их создатели, наверное, даже представить не могли, что их будут использовать для управления большими металлическими самоходными средствами передвижения, которые сейчас для нас больше известны как «автомобили». Но сейчас, когда мы с вами живем в 21 веке, мы используем алгоритмы для управления многими аспектами нашей жизни – от искусственного интеллекта до криптовалюты и входа в обычные онлайн-сервисы.
Так что, если вы планируете искать работу, связанную с алгоритмами, то вы открываете для себя очень актуальную область с большим количеством возможностей. А теперь пришло время подготовиться к тому, чтобы произвести впечатление! Мы подготовили для вас 15 вопросов по алгоритмам, которые помогут вам подготовиться к собеседованию.
Читайте дальше, чтобы узнать о самых распространенных вопросах об алгоритмах, а также ответы на них и о том, как усовершенствовать свои навыки, чтобы подготовиться к собеседованию.
Что такое алгоритм?
Несмотря на то, что этот вопрос – элементарный, если вам задают его, важно ответить на него уверенно и без лишних слов. Алгоритм представляет собой последовательность вычислительных шагов, которые принимают входные данные или несколько входных данных и преобразуют их в выходные данные. Алгоритм можно написать в разных формах, например, с помощью обычного русского языка или используя псевдокод.
После того, как вы дадите краткий ответ, как этот, вы можете углубиться в эту тему, если захотите. Лучше сделать это на каком-то примере.
Что такое быстрая сортировка?
Этот вопрос нужен для того, чтобы проверить, способны ли вы применять алгоритмы хотя бы на самом базовом уровне. Алгоритм быстрой сортировки подходит для быстрой сортировки запросов или списков. В его основе лежит так называемый метод «разделяй и властвуй», то есть он занимается перестановкой групп, каждая из которых является одной из трех частей списка элементов:
Опорный элемент, выбранный из массива
Элементы меньше опорного размещаются слева от него для формирования левого подмассива
Элементы больше опорного размещаются справа от него для формирования правого подмассива
В подмассивах также выбирается опорный элемент, а остальные значения сортируются относительного него аналогично. Процесс повторяется до тех пор, пока в подмассивах не останется только один элемент.
Временная сложность алгоритма:
Наилучший случай:
On log
n
. Значение опорного элемента близко к среднему значению всех сортируемых элементов.
Наихудший случай:
On2
. Значение опорного элемента – это либо наибольшее, либо наименьшее значение всех сортируемых элементов.
Средний случай:
On log
n
.
В чем заключается роль опорного элемента?
Это еще один вопрос из темы поверхностного погружения в основы алгоритмов. Вы можете ответить, сказав, что опорный элемент – это элемент, который алгоритм выбирает из массива или матрицы, с которыми мы работаем, и который будет служить первым элементом для вычислений.
Есть множество способов, как выбрать опорный элемент. Для массива опорным элементом может служить первый или последний элемент, выбранный из середины или случайным образом. В зависимости от алгоритма способ выбора опорного элемента может влиять на качество результата.
Что понимается под временной сложностью алгоритма?
Это еще одно базовое понятие, связанное с алгоритмами, и поэтому ваш ответ должен начинаться с краткого определения. Временная сложность алгоритма – это количество итераций, которые необходимы для его завершения, в зависимости от размера входных данных.
Объясните различные обозначения, которые используют, когда речь идет о временной сложности
Отвечая на этот и любые последующие вопросы, вы демонстрируете свои знания того, как работают алгоритмы, а также что вы знаете, как их можно изменить, чтобы достичь желаемого результата.
Обозначения могут помочь оценить эффективность алгоритма. Вот обозначения, которые вы используете для временной сложности:
Большая омега: это означает «больше или столько же» итераций. Это точная нижняя граница роста времени работы алгоритма. По сути это наилучший случай временной сложности.
Большое О: это означает «меньше или столько же» итераций. Это точная верхняя граница роста времени работы алгоритма. По сути это наихудший случай временной сложности.
Большая тета: это означает «столько же» итераций. Это одновременно и точная верхняя граница, и точная нижняя граница роста времени работы алгоритма.
Маленькое О: это означает «меньше чем» итераций. Это верхняя граница, которая не является асимптотически точной.
Маленькая омега: это означает «больше чем» итераций. Это нижняя граница, которая не является асимптотически точной.
Как работает бинарный поиск?
Бинарный поиск используется для поиска элемента в уже отсортированном массиве. Первым делом мы смотрим на элемент в середине массива. Если это и есть искомый элемент, то поиск завершен. В противном случае, если искомый элемент больше того, что мы выбрали, процедура поиска повторяется в верхней половине массива (то есть среди значений, которые больше выбранного нами). Если же он меньше, то процедура поиска выполняется в нижней половине массива (то есть среди значений, которые меньше выбранного нами).
Временная сложность алгоритма:
Наилучший случай:
O1
. Искомое значение - это первый выбранный средний элементом.
Наихудший случай:
Olog
n
. Мы нашли искомое значение на одном из последних шагов, или оно вовсе отсутствует.
Средний случай:
Olog
n
.
Что подразумевается под сортировкой кучей (пирамидальной сортировкой)?
Сортировка кучей, или пирамидальная сортировка, подразумевает сравнение элементов с помощью алгоритма сортировки. Входные данные делятся на отсортированную и неотсортированную части. То, что перемещается в отсортированную часть, зависит от того, работаете вы с невозрастающей или возрастающей кучей. Невозрастающая куча в корне имеет элемент с максимальным значением, а возрастающая – с минимальным. Когда вы используете пирамидальную сортировку на невозрастающей куче, то неотсортированная часть уменьшается, так как самый большой элемент перемещается в отсортированную часть. В случае с возрастающей кучей в отсортированную часть перемещается элемент с наименьшим значением.
В невозрастающей куче значение родительского узла всегда больше, чем значения дочерних узлов. Для того, чтобы отсортировать элементы невозрастающей кучи с помощью алгоритма пирамидальной сортировки, необходимо выполнить следующие шаги:
Заменить последний элемент кучи корневым узлом
Убрать последний элемент, который мы только что поместили, из кучи
Преобразовать теперь уже двоичную кучу обратно в невозрастающую
Повторять процесс, пока не закончатся элементы.
Временная сложность алгоритма:
Наилучший случай:
O (n log
n
)
.
Наихудший случай:
O (n log
n
)
.
Средний случай:
O (n log
n
)
.
Для чего используется список пропусков?
Список пропусков используется для структурирования данных. В его основе лежат связные списки. А для того, чтобы создавать уровни новых ссылок в исходном связном списке, он использует вероятности. Можно провести аналогию с сетью автобусных маршрутов. Есть автобусы, которые останавливаются на каждой остановке, а есть такие, которые останавливаются только на определенных. У последних остановок меньше, чем у обычных автобусов. Создание новых уровней в списке пропусков можно рассматривать как вот такие ускоренные маршруты с меньшим количеством остановок. Если вы можете получать более эффективный доступ к наиболее часто используемым узлам, то такие задачи, как вставки или удаление узлов, станут намного проще и быстрее. И это будет более эффективно, чем применение каких-то других алгоритмов.
Какие криптографические алгоритмы являются наиболее распространенными?
Этот вопрос может показаться чересчур сложным, потому что вам кажется, что вам нужно запомнить огромное количество информации, но если вы вдруг пропустите пару алгоритмов, то никто не будет вас за это наказывать. И к тому же существует огромное количество алгоритмов. Вот некоторые из них:
IDEA
Blowfish
CAST
LOKI
DES
GOST
3-way
Что такое алгоритм хеширования и как он используется?
Вам захочется устроиться поудобнее, отвечая на этот вопрос, ведь хеш-алгоритмы сейчас очень популярны, так как используются в криптографии. Алгоритм хеширования ссылается на хеш-функцию, которая берет строку и преобразует ее в строку фиксированной длины, и не важно, какой длины она была изначально. Вы можете использовать алгоритм хеширования для самых разных целей – от криптовалюты до паролей и ряда других инструментов проверки.
Какую роль играют алгоритмы в криптовалюте?
Если вы устраиваетесь на работу, связанную с криптовалютой, то этот вопрос может оказаться для вас не таким простым, особенно если вы умудрились заблудиться в трех соснах, отвечая на него. Один из способов, как ответить на этот вопрос – упомянуть, насколько сильно криптовалюты на основе блокчейна зависят от криптографии. Блоки или записи, составляющие блокчейн, защищены с помощью криптографических методов, таких как хеш-алгоритмы. Также есть алгоритмы, которые используют для генерации открытых и закрытых ключей и для «майнинга» криптовалют.
Как работает алгоритм шифрования?
Такого рода вопросы на собеседовании могут дать вам некоторую подсказку о том, для какой работы вам могут нанять. Алгоритм шифрования преобразует обычный текст в код, или зашифрованный текст. Для этого алгоритм использует ключи. Чем длиннее ключи, тем больше есть возможностей для создания зашифрованного текста.
Что такое алгоритм поразрядной сортировки?
Поразрядная сортировка может пригодиться при работе с базами данных, или если ваша должность предусматривает то, что вы должны быть готовы ответить на этот вопрос. Поразрядная сортировка – это алгоритм сортировки, который не сравнивает элементы, а распределяет их по «корзинам», основываясь на разрядах. Если есть элементы с более чем одной значащей цифрой, то распределение по «корзинам» повторяется для каждой цифры.
Что такое рекурсивный алгоритм?
Рекурсивный алгоритм опирается на способ решения, при котором сложная задача разбивается на более мелкие подзадачи. Это делается до тех пор, пока не получится достаточно простая задача, которую можно было бы легко решить. Одним из примеров алгоритма, который можно реализовать рекурсивно, является бинарный поиск.
Какие три закона должны выполняться для рекурсивных алгоритмов?
Такие вопросы на собеседовании могут быть продолжением вопроса «Что такое рекурсивный алгоритм?» Рекурсивный алгоритм должен следовать следующим законам:
У него должен быть нерекурсивный вариант реализации.
Он должен вызывать сам себя.
Его можно изменить и вернуть к нерекурсивному варианту.
Как системный администратор, вполне вероятно, что вы написали несколько сценариев Bash для автоматизации вашей работы. Например, вы можете запускать сценарии Bash для резервного копирования вашей работы или для регистрации некоторых событий, происходящих на вашем сервере.
Скрипты Bash, как и скрипты, написанные на других языках программирования, могут запускаться различными способами.
В этой статье мы расскажем о всех способах запуска скрипта Bash в Linux.
Подготовка
Прежде чем вы сможете запустить ваш скрипт, вам нужно, чтобы ваш скрипт был исполняемым. Чтобы сделать исполняемый скрипт в Linux, используйте команду chmod и присвойте файлу права execute. Вы можете использовать двоичную или символическую запись, чтобы сделать ее исполняемой.
$ chmod u+x script
$ chmod 744 script
Если вы не являетесь владельцем файла, вам необходимо убедиться, что вы принадлежите к правильной группе или что права доступа предоставлены «другой» группе в вашей системе.
В некоторых дистрибутивах ваш файл будет выделен другим цветом, когда он исполняемый.
Теперь, когда ваш файл исполняемый, давайте посмотрим, как можно легко запустить скрипт Bash.
Запустить Bash скрипт из пути к скрипту
Чтобы запустить Bash скрипт в Linux, просто укажите полный путь к скрипту и укажите аргументы, которые могут потребоваться для запуска Bash скрипта.
$ /path/to/script <arg1> <arg2> ... <argn>
В качестве примера, скажем, у вас есть Bash-скрипт, расположенный в вашем домашнем каталоге.
Чтобы выполнить этот скрипт, вы можете указать полный путь к скрипту, который вы хотите запустить.
# Абсолютный путь
$ /home/user/script
# Абсолютный путь с аргументами
$ /home/user/script "john" "jack" "jim"
Кроме того, вы можете указать относительный путь к скрипту Bash, который вы хотите запустить.
# Относительный путь
$ ./script
# Относительный путь с аргументами
$ ./script "john" "jack" "jim"
Таким образом вы узнали, как легко запустить Bash-скрипт в своей системе.
Запустить Bash скрипт, используя bash
Чтобы запустить скрипт Bash в вашей системе, вы должны использовать команду bash и указать имя скрипта, который вы хотите выполнить, с необязательными аргументами.
$ bash <script>
Кроме того, вы можете использовать sh, если в вашем дистрибутиве установлена утилита sh.
В качестве примера, скажем, вы хотите запустить скрипт Bash с именем script. Чтобы выполнить его с помощью утилиты bash, вы должны выполнить следующую команду
$ bash script
This is the output from your script!
Выполнить скрипт Bash, используя sh, zsh, dash
В зависимости от вашего дистрибутива, в вашей системе могут быть установлены другие утилиты оболочки.
Bash - интерпретатор оболочки, установленный по умолчанию, но вы можете захотеть выполнить ваш скрипт с использованием других интерпретаторов. Чтобы проверить, установлен ли интерпретатор оболочки в вашей системе, используйте команду which и укажите нужный интерпретатор.
$ which sh
/usr/bin/sh
$ which dash
/usr/bin/dash
Когда вы определили интерпретатор оболочки, который хотите использовать, просто вызовите его, чтобы легко запустить скрипт.
Запуск скрипта Bash из любого места
В некоторых случаях вы можете запускать скрипты Bash, где бы вы ни находились в вашей системе.
Чтобы запустить скрипт Bash из любой точки вашей системы, вам нужно добавить свой скрипт в переменную среды PATH.
$ export PATH="<path_to_script>:$PATH"
Благодаря тому, что путь к скрипту добавлен в PATH, вы можете вызывать его там, где хотите в своей системе.
$ script
This is the output from script!
Кроме того, вы можете изменить переменную среды PATH в вашем файле .bashrc и использовать команду source для обновления вашей текущей среды Bash.
$ sudo nano ~/.bashrc
export PATH="<path_to_script>:$PATH"
Выйдите из файла и используйте команду source для файла bashrc для внесения изменений.
$ source ~/.bashrc
$ echo $PATH
/home/user/bin:/usr/local/sbin:/usr/local/bin:/usr/sbin:/usr/bin:/sbin:/bin:/usr/games
Отлично! Теперь ваш скрипт может быть запущен из любой точки вашей системы.
Запуск Bash скриптов из графического интерфейса
Последний способ выполнения Bash скриптов - это использование графического интерфейса, в данном случае интерфейса GNOME.
Чтобы запустить ваши скрипты с использованием GNOME, вы должны установить в проводнике Ask what to do для исполняемых файлов.
Закройте это окно и дважды щелкните файл скрипта, который вы хотите выполнить.
При двойном щелчке вам предлагаются различные варианты: вы можете выбрать запуск скрипта (в терминале или нет) или просто отобразить содержимое файла.
В этом случае мы заинтересованы в запуске этого скрипта в терминале, поэтому нажмите на эту опцию.
Успех! Ваш скрипт был успешно выполнен
Заключение
Из этого руководства вы узнали, как легко запускать Bash скрипты в своей системе, указав путь к скрипту или интерпретаторы, доступные на вашем хосте. Вы узнали, что можете сделать это еще проще, добавив путь к скрипту в переменную среды PATH или используя существующие функции в пользовательском интерфейсе GNOME.
Как и любая современная АТС, Asterisk имеет свою встроенную систему хранения истории звонков - CDR (Call Detail Record). Она используется для снятия статистики, ведения отчетности, прослушивания вызовов или подсчета биллинговых показателей.
В Asterisk для этого создана база данных asteriskcdrdb, в которой существует таблица cdr. Давайте рассмотрим как пользоваться данной таблицей и ее структуру.
[root@asterisk]# mysql // подключаемся к MySQL
После успешного подключения, необходимо выбрать для работы базу данных asteriskcdrdb:
mysql> use asteriskcdrdb;
Reading table information for completion of table and column names
You can turn off this feature to get a quicker startup with -A
Database changed
Давайте убедимся, что у нас есть таблица cdr. Выполним это, как указано ниже:
mysql> show tables;
+-------------------------+
| Tables_in_asteriskcdrdb |
+-------------------------+
| cdr |
| cel |
+-------------------------+
2 rows in set (0.00 sec)
На данном этапе мы убедились, что у нас есть база данных asteriskcdrdb, в которой находится таблица cdr. Давайте попробуем посмотреть входящие звонки из города за сегодня (дата написания статьи 18 марта 2016 года), в период с 12:00 до 12:10, т.е за 10 минут:
SELECT `dst` , `src` , `duration` , `calldate` , `recordingfile`
FROM `cdr` WHERE `calldate` >= '2016-03-18 12:00:00' AND `calldate` <= '2016-03-18 12:10:00' AND LENGTH( `src` ) >3;
+-----+-------------+----------+---------------------+----------------------------------------------------------------+
| dst | src | duration | calldate | recordingfile |
+-----+-------------+----------+---------------------+----------------------------------------------------------------+
| 113 | 84991111111 | 140 | 2016-03-18 12:00:36 | external-113-84991111111-20160318-115933-1458291573.157155.wav |
| 104 | 89162222222 | 81 | 2016-03-18 12:01:33 | external-104-89162222222-20160318-120133-1458291693.157169.wav |
+-----+-------------+----------+---------------------+----------------------------------------------------------------+
2 rows in set (0.00 sec)
В вышеуказанном примере, в SQL запросе указано LENGTH( `src` ) >3. Столбец ‘src’ – показывает номер звонящего (source - источник). Это сделано для того, чтобы исключить внутренние звонки, так как у нас используется трехзначная нумерация. Тем самым, мы получаем в результате данные, с которыми затем можем работать. Например, отправить на почту в виде отчета. Ниже рассмотрена структура таблицы cdr в базе данных asteriskcdrdb:
Столбец
Пример значения
Описание
calldate
2016-03-18 12:00:36
Дата и время звонка
clid
"Oleg Ivanov" <84991111111>
В данное поле попадает полное CallerID (CLID, CID), которое состоит из имени и номера звонящего. Это доступно только для считывания.
src
84991111111
Номер звонящего в конструкции CallerID (CNUM). Это доступно только для считывания.
dst
113
Номер назначения для звонка. Это доступно только для считывания.
dcontext
CustomContext1
Контекст для обработки. Это доступно только для считывания.
channel
SIP/0002B2356854-a34bh3ef
Канал, через который поступил звонок
dstchannel
SIP/0004F6675969-97836bb0
Канал, через который ушел исходящий звонок
lastapp
Dial, Busy, Congestion
Приложение, которое последним отработало этот вызов перед попаданием в таблицу cdr
lastdata
SIP/0004F6675969,30,tT
Аргумент, который был передан приложению, которое отработало вызов последним (lastapp)
duration
75
Количество секунд от начала (отметка start) до окончания вызова (отметка end)
billsec
67
Количество секунд от ответа (отметка answer) до окончания вызова (отметка end). Данное значение всегда меньше значения duration, и отражает длительность самого разговора, что важно для подсчета стоимости.
disposition
ANSWERED, BUSY, NO ANSWER, FAILED
Результат звонка
amaflags
OMIT, BILLING, DOCUMENTATION, Unknown
Метка Automatic Message Accounting (AMA) – автоматический учет стоимости вызова.
accountcode
23232
Идентификатор аккаунта. Данное значение пустое по умолчанию, и определяется параметрами конкретного пользователя.
uniqueid
1458291693.157169
Уникальный идентификатор звонка
userfield
-
Пользовательское поле. Здесь можно передавать что угодно, добавляя данные в этот столбец при работе с вызовом внутри контекста обработки.
did
4996491913
DID (Direct Inward Dialing). На основании DID вызова на Asterisk осуществляется его маршрутизация (это значение приходит от провайдера).
recordingfile
external-113-84991111111-20160318-115933-1458291573.157155.wav
Имя файла, содержащего запись разговора. В данном имени можно проследить путь к файлу в файловой структуре сервера.
cnum
84991111111
Номер звонящего в структуре CallerID.
cnam
Oleg Ivanov
Имя звонящего в структуре CallerID.
Теперь, когда вы понимаете принцип формирования запросов к базе данных и ее структуру, вы можете без труда формировать собственные отчеты. Например, ежедневный отчет о количестве входящих звонков за текущий день на почту. Это реализуется средствами php скрипта и добавления расписания через cron. Поговорим об этом в следующей статье