How to quickly prepare for the interview, which will be questions on algorithms and information processing technologies?

    Greetings to all readers of Habr! My name is Yuri, I have been teaching high technologies, Oracle, Microsoft and others for over 20 years, as well as creating, developing and supporting loaded information systems for various business customers. Today I would like to tell you about the current direction: interviews on data processing technologies.

    At interviews with such a plan, it is useless for an employer to ask the applicant about technologies associated with traditional programming. Therefore, I will popularly tell you how to prepare for an interview only in one narrow area related to information processing languages, namely, processing long integers (long arithmetic) and identifying information properties of real-world objects, which are described in long integers.

    1. Interviews with data processing technology questions are usually conducted when recruiting teams of analysts and developers who have previously had experience developing in declarative, imperative, object-oriented, and functional languages.

    Task. Determine the programming language for the program fragment.

    Therefore, you first need to prepare for the question - what is already good in the chosen language, which could interest a potential employer? By the way, the list may differ from version to version, from library to library, from implementation to implementation.

    Task. What languages ​​have support for arithmetic with long integers?

    Thought? Sample list:
    • C, C ++ - libgmp library
    • 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. If the employer has made a list in advance, it is necessary to isolate the common parts of the languages ​​that will be discussed at the interview.

    Task. What do you think are the most requested languages ​​from the employer's point of view? Here you can see the answer based on statistics.

    In large and super-large information systems, a number of quite routine operations are most often performed: various types of sorting, searching by certain criteria, algorithms on graphs, optimization problems on sets of different nature, problems of constructing objects with uncertain properties. But, due to the scale of the task, the simplest sorting can be done a month, and the search - a week. An exemplary task of understanding.

    Task.There is a birch tree outside the window. On it, as your colleagues calculated, 100,000 leaves, the diameter of the trunk at the root is 60 centimeters. Write these parameters in any mathematical notation. And prove its suitability: for correspondence with a colleague, because they want to cut a tree. Or for computer processing of his image.

    3. A few words about the mathematical part. In life, we rarely go beyond the bounds of ordinary arithmetic. Units of us use the achievements of algebra and mathematical analysis. Let the statements below help you remember, even shallowly, where forgotten knowledge is practically used.

    Task.Why were the phone numbers for five or six digits so long? Given a series of numbers - which of them is not a complete square? How many buses in your city have numbers - full squares? How many primes to 100 do you know? How much is a percentage of all numbers from 1 to 100? Let 2, 3, 5, 7 be prime numbers, find the number of prime numbers up to 100. How many arithmetic operations did you have to do? Solve the same problem on MS Excel for self-checking in two ways.

    Task. How is bulge and concavity used in practice? Give 2-3 examples of the use of convexity-concavity.

    four.Sometimes it is necessary to go through the documentation for the system / language / set of libraries, examples from in-depth and extended technical descriptions from the author / manufacturer himself. This is especially necessary if you call a non-standard library call.

    Task. Write the advanced Euclidean algorithm in one of the above, in paragraph 1, of programming languages. In what language is it not necessary to do? And why?

    5. It is advisable to understand the direction of the interview: will you write the algorithms yourself or will you have to maintain a set of third-party algorithms in which you have to clean up over time?

    Task.As regards the set of notes from the head physician made with the pen on the intern’s notepad, it is necessary to determine in a computerized way which patient has been assigned. What can advise the intern?

    6. If the choice of language of the interview is implied, then it is better to take a more standardized one so that the interviewer does not have a desire to change the conditions of the tasks during the conversation.

    Task. How many versions of the Pascal language appeared in the last 25 years? List the strengths and weaknesses of each version.

    7. It is advisable to go to at least one seminar on algorithms and on their incarnations into ready-made information solutions in a given subject area.

    Task.The poet turned to you with a question: can he write a poem "Eugene Onegin" in view of the poetic thesaurus of this author. Give two solutions to this problem.

    8. The resource for programmers has tasks for training the ability to process scientific information and program complex algorithms. Below we give the solution "in the forehead", but it is not optimal and is only a statement of the condition from the point of view of a high-level programming language. Due to the insufficiently accurate wording of the text of the task, your answers may not coincide with the answers given by the authors of this task.

    Problem 489 from “Project Euler”

    Let be $ G (a, b) $ - the smallest non-negative integer $ n $, for which $ Gcd (n ^ 3 + b, (n + a) ^ 3 + b) $has the greatest possible value.
    For example,$ G (1, 1) = 5 $, because $ Gcd (n ^ 3 + 1, (n + 1) ^ 3 + 1) $ reaches maximum value $ 7 $ at $ n = 5 $ and has lower values ​​when $ 0 ≤ n <5 $. Let be$ H (m, n) = Σ G (a, b) $ for $ 1 ≤ a ≤ m $, $ 1 ≤ b ≤ n $.
    It is known that$ H (5, 5) = $ 128878 and $ H (10, 10) = $ 32936544. Find$ H (18, 1900) $.

    Task. Fortunately, this is a very rare task on Project Euler. For the given text of the program, find the strengths and weaknesses of the algorithm and specify them. Can this program solve this problem in a working day? How can you speed it up? Indicate errors in the task, if any. Find the “ very large numberoption . How is it limited?

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

    Code for a sample solution
        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;
        publicstaticvoidmain(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");
        for (int a=1;a<19;a++) {
             for (int b=1;b<1901;b++) {
                      for(n=1;n<оченьбольшоечисло;n++) {
       int comparevalue = j.compareTo(i); 
       if (comparevalue==0)
         { temp=GcdExtended(i,j);
        elseif (comparevalue == 1)
        { temp=GcdExtended(j,i);
        else { temp=GcdExtended(i,j);
                    int compareTemp = temp.compareTo(temp1); 
                              if (compareTemp == 1) {
                               String fileContent = a + ";" + b +";"+ temp1 +";"+ n1 + "\n";
                                     try {
                                         } catch (IOException e) { 
            String fileContent = count + "\n";
        try {
            } catch (IOException e) {     

    9. I wish you a good interview!

    Also popular now: