Как быстро подготовиться к собеседованию, на котором будут вопросы по алгоритмам и технологиям обработки информации?

    Приветствую всех читателей Хабра! Меня зовут Юрий, более 20 лет преподаю высокие технологии, Oracle, Microsoft и другие, а также занимаюсь созданием, разработкой и поддержкой нагруженных информационных систем для различных бизнес-заказчиков. Сегодня хотел бы рассказать вам об актуальном направлении: собеседованиях по технологиям обработки данных.

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

    1. Собеседование с вопросами по технологиям обработки данных обычно проводится при наборе команд аналитиков и разработчиков, ранее уже имевших опыт разработки на декларативных, императивных, объектно-ориентированных и функциональных языках.

    Задача. Определите язык программирования по фрагменту программы.



    Следовательно, сначала надо подготовиться к вопросу — а что уже есть хорошего в выбранном языке, что могло бы заинтересовать потенциального работодателя? Кстати, список может разниться от версии к версии, от библиотеки к библиотеке, от реализации к реализации.



    Задача. На каких языках есть поддержка арифметики с длинными целыми?

    Подумали? Примерный перечень:
    • C, C++ — библиотека libgmp
    • Common Lisp — не ограничивает разрядность целых чисел
    • Erlang — встроенный численный тип (integer())
    • Go — типы Int и Rat из библиотеки big.
    • Haskell — встроенный тип Integer
    • Java — класс java.math.BigInteger (февраль 1997 года)
    • OCaml — библиотека num
    • Pascal/Delphi — библиотека MPArith
    • Perl — модули bignum и bigrat
    • PHP — модуль BCMath
    • Python — встроенный тип long (с момента создания языка, февраль 1991 года)
    • Ruby — тип Bignum
    • Scala — класс BigInt
    • Scheme — с R6RS
    • Языки .NET — класс System.Numerics.BigInteger (появился в .NET Framework 4.0, почти 10 лет назад)


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

    Задача. Какие, по вашему мнению, самые востребованные языки с точки зрения работодателя? Тут можно посмотреть ответ на основе статистики.

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

    Задача. За окном стоит береза. На ней, как подсчитали ваши коллеги, 100 000 листьев, диаметр ствола у корня — 60 сантиметров. Запишите указанные параметры в любой математической нотации. И докажите ее пригодность: для переписки с коллегой, так как дерево хотят спилить. Или для компьютерной обработки его изображения.



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

    Задача. Почему номера телефонов так долго были пяти-шестизначными? Дан ряд чисел — какое из них не является полным квадратом? Сколько автобусов в вашем городе имеют номера — полные квадраты? Сколько простых чисел до 100 вы знаете? Сколько это в процентах от всех чисел от 1 до 100? Пусть 2, 3, 5, 7 — простые числа, найдите количество простых чисел до 100. Сколько вам пришлось сделать арифметических операций? Решите эту же задачу на MS Excel для самопроверки двумя способами.

    Задача. Как используется выпуклость и вогнутость на практике? Приведите 2-3 примера использования выпуклости-вогнутости.



    4. Иногда необходимо пройтись по документации к системе/языку/набору библиотек, примерам из углубленных и расширенных технических описаний от самого автора/производителя. Это особенно необходимо, если подразумевается вызов нестандартных библиотек.

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

    5. Желательно понять направление собеседования: будете ли вы писать алгоритмы самостоятельно или вам предстоит обслуживать набор сторонних алгоритмов, в котором со временем придется наводить порядок?

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



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

    Задача. Сколько версий у языка Паскаль появилось за последние 25 лет? Укажите сильные и слабые стороны каждой версии.



    7. Желательно сходить хотя бы на один семинар по алгоритмам и по их воплощениям в готовые информационные решения в заданной предметной области.

    Задача. К вам обратился поэт с вопросом: можно ли ему написать поэму «Евгений Онегин» с учетом поэтического тезауруса данного автора. Приведите два решения этой задачи.

    8. На ресурсе для программистов есть задачи для тренировки умения обрабатывать научную информацию и программировать сложные алгоритмы. Ниже мы приводим решение «в лоб», но оно не оптимальное и является лишь формулировкой условия с точки зрения языка программирования высокого уровня. Из-за недостаточно точной формулировки самого текста задачи ваши ответы могут не совпадать с ответами, которые приводят авторы этой задачи.

    Задача 489 из «Проекта Эйлер»


    Пусть $G(a,b)$ — наименьшее неотрицательное целое число $n$, для которого $НОД(n^3 + b, (n + a)^3 + b)$ имеет наибольшее возможное значение.
    Например, $G(1, 1) = 5$, так как $НОД(n^3 + 1, (n + 1)^3 + 1)$ достигает максимального значения $7$ при $n = 5$ и имеет меньшие значения при $0 ≤ n < 5$. Пусть $H(m, n) = Σ G(a, b)$ для $1 ≤ a ≤ m$, $1 ≤ b ≤ n$.
    Известно, что $H(5, 5) = 128878$ и $H(10, 10) = 32936544$. Найдите $H(18, 1900)$.

    Задача. К счастью, это очень редко решаемая на «Проекте Эйлер» задача. По заданному тексту программы найдите сильные и слабые места алгоритма и укажите их. Сможет ли эта программа решить данную задачу за рабочий день? Как ее можно ускорить? Укажите ошибки в задаче, если они есть. Найдите параметр «оченьбольшоечисло». Чем он ограничен?

    Еще несколько слов, если вы не смогли ее решить
    Если речь шла о локальных максимумах, то ответы должны быть меньше, но после расчетов вдруг выясняется, что речь идет о глобальных максимумах, о чем в тексте задачи нет ни слова.
    И еще, $НОД(n^3 +1444, (n + 1)^3+ 1444)=1$ при любом $n$. Какое $n$ устроит авторов задачи?

    Код для примерного решения
    public class Start {
        
        
        static BigInteger[] GcdExtended(BigInteger a, BigInteger b)
    
          {
            BigInteger res[] = new BigInteger[3];
            if (b == BigInteger.valueOf(0))
            {
              res[0] = a; res[1] = BigInteger.valueOf(1); res[2] = BigInteger.valueOf(0);
              return res;
            }
            res = GcdExtended(b,a.divideAndRemainder(b)[1]);
            BigInteger s = res[2];
            res[2] = res[1].subtract((a.divideAndRemainder(b)[0]).multiply(res[2]));
            res[1] = s;
            return res;
    
          }
      
        public static void main(String[]args) throws IOException {
        BigInteger i; 
        BigInteger j;
        int n,n1;
        BigInteger temp;
        BigInteger temp1;
        BigInteger count;
            
        FileWriter fileWriter = new FileWriter("c:/temp/terribleanswer.txt");
                
        n1=1;
        count=BigInteger.ZERO;
        i=BigInteger.ZERO;
        j=BigInteger.ZERO;
        temp1=BigInteger.ZERO;
        temp=BigInteger.ZERO;
        
        for (int a=1;a<19;a++) {
             for (int b=1;b<1901;b++) {
                      for(n=1;n<оченьбольшоечисло;n++) {
                        
        j=((BigInteger.valueOf(n)).pow(3));
        j=j.add(BigInteger.valueOf(b));
           
        i=(((BigInteger.valueOf(n)).add(BigInteger.valueOf(a))).pow(3));
        i=i.add(BigInteger.valueOf(b));
                    
                    
       int comparevalue = j.compareTo(i); 
       
       if (comparevalue==0)
        
         { temp=GcdExtended(i,j);
         
          }
        
        else if (comparevalue == 1)
        
        { temp=GcdExtended(j,i);
         }    
        
        else { temp=GcdExtended(i,j);
            }    
                              
                                    
                    int compareTemp = temp.compareTo(temp1); 
                              
                              if (compareTemp == 1) {
                                  temp1=temp;
                                  n1=n;
                                  continue;
                              }
                              
                               }
                                 
                               String fileContent = a + ";" + b +";"+ temp1 +";"+ n1 + "\n";
                                    
                                     temp1=BigInteger.ZERO;
                                     count=count.add(BigInteger.valueOf(n1));
                                     n1=1;
                                                                      
                                     try {
                                        
                                         fileWriter.append(fileContent);
                                         
                                         } catch (IOException e) { 
         
                                 }
                               }
                           }
        
            String fileContent = count + "\n";
                                       
        try {
           
            fileWriter.append(fileContent);
            
            } catch (IOException e) {     
        
        }
        fileWriter.close();
    }
    }
    


    9. Желаю вам пройти собеседование на хорошем уровне!
    • +8
    • 5,3k
    • 8
    РДТЕХ (Разумные Деловые Технологии)
    47,00
    Компания
    Поделиться публикацией

    Комментарии 8

      +1
      Очередной случай не подходящей для собеседования задачи. Слишком сложна при очном интервью и слаба(слишком известна) в качестве домашнего задания.
        +2
        Можно переспросить — в каком именно пункте вы увидели очень известную задачу? В статье рассматривается именно связка задач, а не одиночная постановка.
          0
          Имеет значение среднее время, которое отведено на решение задачи планом по интервью ( для выработки времени подходит задача или нет).
          Кстати, это статья для организации очного или заочного интервью?
            0
            Итак, перед вами план интервью. Среднего времени я не пишу, так как задания относятся к категории творческих. Сначала, конечно, идет обычная, сказал бы даже рутинная часть. Если под «выработкой времени» подразумевается «выработка решения за определенное время», то однозначно нужны специалисты не «вырабатывающие время», а находящие решения.
            Заочное интервью — отдельный вид собеседования. Для него могут быть вопросы как более легкие, так и более трудные.
              0
              План? Допустим. Но тогда, допустим так же, что вы делегируете работу по плану какому-либо работнику (очень частый случай в больших корпорациях, когда на одну позицию человек 20+ опрашивают). А работник должен спланировать свое время == знать среднее время, отведенное на интервью.
                0
                Рассуждения понятны. Получается, что я — технический специалист, должен заботиться о планах кадрового работника, чтобы он мне подобрал сотрудника или сотрудников, по 20 человек опрашивая в день? Кадровик, если надо, даст мне сигнал — этого достаточно.
                  +1
                  Если вы составляете план, то должны дать его основные характеристики, а именно, временные (на то он и план). А так, я согласен, менеджеры напридумывали всякой фигни, чтобы усложнить жизнь техническим специалистам :)

                    0
                    Я составляю план на извлечение информации, а не на развлечение одного сотрудника другим(и). )) Считаю, что кадровый сотрудник должен быть высок, строен, привлекателен и подкован на любое собеседование. А план — 20 человек в день, или 2 утром и 2 вечером — логичнее ему самому составлять. Технологически сервер в голове у программиста может быть настроен как на разное время суток, так и на разные языки. Хорошо конечно, когда запросом на запрос отвечать не приходится.

      Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

      Самое читаемое