How to quickly prepare for a job interview with questions on algorithms and technologies

    Greetings to all readers of Habr! My name is Yuriy, I have been teaching high technologies, Oracle, Microsoft and others for more than 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. The Russian variant of this post you can find here.

    It doesn't really make sense for an employer to ask the applicant about traditional programming technologies. That is why I'm going to tell you how to prepare for an interview in only one narrow area related to information processing languages, namely, the processing of long integers(long arithmetic) and the identification of information properties of real world objects, which are described in long integers.

    1. Data processing technology interviews are normally held to hire teams of analysts and developers who have previously had development experience in declarative, imperative, object-oriented and functional languages.

    Task. Determine the programming language by the following program fragment.



    First you need to answer the question: which features in the chosen language can be relevant and will attract the potential employer? Depending on this, the list can vary from version to version, from library to library, from implementation to implementation.



    Task. What languages support arithmetic with long integers?

    Ready to answer? Here's a suggested list:
    • C, C++ — libgmp library
    • Common Lisp-does not limit the bit width of integers
    • Erlang-built-in numerical type (integer())
    • Go-Int and Rat types from the big library.
    • Haskell-built-in Integer type
    • Java-java class.math.BigInteger (February 1997)
    • OCaml-num library
    • Pascal — Delphi-MPArith library
    • Perl modules bignum and bigrat
    • PHP module BCMath
    • Python is a built-in long type (since the language was created, February 1991)
    • Ruby — type Bignum
    • Scala-BigInt class
    • Scheme-with R6RS
    • .NET languages-System class.Numerics.BigInteger (introduced in .NET Framework 4.0, almost 10 years ago)


    2. If the employer already has a ready-made list, it is necessary to single out general parts of the languages that will be discussed at the interview.

    Task. What, in your opinion, are the most popular languages from the employer's point of view? Here you can see the answer based on statistics.

    A number of such routine operations is often performed in large and ultra-large information systems. There are different types of sorting, search for certain criteria, algorithms on graphs, optimization problems on sets of different nature, tasks of designing objects with uncertain properties. But because of the scale of these tasks the easiest sorting may take a month, search may take a week. See the task below for better understanding.

    Task. Imagine there is a birch tree outside your office. As calculated by your colleagues, there are 100 000 leaves on it, and the diameter of the trunk at its root is 60 centimeters. Write these parameters in any mathematical notation. Prove its suitability: a) for written communication with a colleague in case the tree is going to be cut down, b) to perform computer processing of its image.



    3. A few words about the mathimatical part of the interview. In real life, we rarely go beyond the boundaries of ordinary arithmetics. Some of us use the achievements of algebra and analysis. So I decided to add some real-life problems to get your heads into gear.

    Task. Why were the phone numbers five or six digits for such a long time? There is a list of numbers — which of them are not complete squares? How many buses in your town have a number consisting only of complete squares? How many primes up to 100 do you know? What is their percentage among the row of numbers from 1 to 100? Let 2, 3, 5, 7 be prime numbers, according to this fact find the quantity of prime numbers up to 100. How many arithmetic operations will you have to do? Solve the same problem in MS Excel in two ways as a self-test.

    Task. How are convexity and concavity used in practice? Give 2-3 examples of convexity-concavity usage.



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

    Task. Write the extended Euclid algorithm in one of the programming languages mentioned above in step 1. In what language is it not necessary to do? Why?

    5. It would be nice to understand the direction of the interview: if you are expected to write algorithms by yourself or if you have to maintain a set of third-party algorithms, probably having to introduce a proper order later?

    Task. There are notes made by a chief medical officer in the notebook of his trainee. It is necessary to computerize this notes in order to make correct patient appointments. What would you advise the intern?



    6. If the choice of the interview language is implied, it is better to select a more standardized one, so that the interviewer won't have much of possibility to change the conditions of the tasks during the conversation.

    Task. How many versions of Pascal have been created during the last 25 years? Specify the strengths and weaknesses of each version.



    7. It would be nice to attend at least one seminar on algorithms and their implementation in the chosen information product in a given subject area.

    Task. The poet asked you whether it is possible for him to write a poem «Eugene Onegin» taking into account the thesaurus of its author. Give two solutions to this problem.

    8. On the site for programmers there are tasks for training the ability to process scientific information and programming complex algorithms. Below we give a solution «head-on», but it is not optimal. It is only a formulation of the condition from the point of view of the high-level programming language.
    Please, pay attention to the fact that despite all authors' effort in formulating the problems, some mistakes still can be there. So it is possible to discuss the issues occurred.

    Task 489 of the Euler Project


    Let $G(a,b)$ be the smallest non-negative integer $n$ for which $GCD(n^3 + b, (n + a)^3 + b)$ is maximized.
    For example, $G(1, 1) = 5$ because $GCD(n^3 + 1, (n + 1)^3 + 1)$ reaches its maximum value of $7$ for $n = 5$, and is smaller for $0 ≤ n < 5$.
    Let $H(m, n) = Σ G(a, b)$ for $1 ≤ a ≤ m$, $1 ≤ b ≤ n$.
    You are given $H(5, 5) = 128878$ и $H(10, 10) = 32936544$.

    Find $H(18, 1900)$.

    Task. fortunately, this is a very rarely solved problem on the Euler Project. Based on the text of the program, find the strengths and weaknesses of the algorithm and specify them. Will this program be able to solve this problem during a working day? How can it be accelerated? Specify errors in the task, if any. Find the parameter "verylargenumber". What it is limited by?

    A few more words if you couldn't solve it
    If we were talking about local maxima, the answers should be less, but after the calculations, it suddenly turns out that we are talking about global maxima, which is not mentioned in the text of the problem. And yet, there is a suspicion that the $GCD(n^3 +1444, (n + 1)^3+ 1444)=1$ under any $n$. What will $n$ suit the authors of the problem?

    Code for the sample solution
    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. I wish you pass the interview on the up-and-up!

    UPD Specially for the publication of the English version of the article, we give a few non-trivial relations found after deep modernization of the above solution. When calculating to $n = 500 000 000$.
    $GCD(n^3 +1444, (n + 1)^3+ 1444)=56298673, n=28147170$; $GCD(n^3 +1445, (n + 1)^3+ 1445)=14094169, n=14092001$; $GCD(n^3 +1446, (n + 1)^3+ 1446)=56454733, n=28225197$; $GCD(n^3 +1447, (n + 1)^3+ 1447)=14133211, n=14131040$.
    РДТЕХ (Разумные Деловые Технологии)
    39.32
    Company
    Share post

    Comments 0

    Only users with full accounts can post comments. Log in, please.