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?
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.
4. Sometimes it is necessary to go through system documentation / language / library set, 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 at least to one seminar on algorithms and on their implementation in 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.
Let be G(a,b) - the smallest non-negative integer n , for which Gcd(n3+b,(n+a)3+b) has the greatest possible value.
For example, G(1,1)=5 , because Gcd(n3+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)=$12887 and H(10,10)=$3293654 . Find H(18,1900) .
Task. Fortunately, this is a very rare task on Project Euler. For the given text of the program, find the strong and weak points of the algorithm and indicate 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 number ” option . How is it limited?
9. I wish you a good interview!
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 - does not limit the width of integers
- Erlang - built-in numeric type (integer ())
- Go - Int and Rat types from the big library.
- Haskell - the built-in type Integer
- Java - class java.math.BigInteger (February 1997)
- OCaml - num library
- Pascal / Delphi - MPArith Library
- Perl - bignum and bigrat modules
- PHP module BCMath
- Python - the built-in type long (since the creation of the language, February 1991)
- Ruby - Bignum Type
- Scala - BigInt class
- Scheme - with R6RS
- Languages .NET - System.Numerics.BigInteger class (appeared in .NET Framework 4.0, almost 10 years ago)
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.
4. Sometimes it is necessary to go through system documentation / language / library set, 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 at least to one seminar on algorithms and on their implementation in 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(n3+b,(n+a)3+b) has the greatest possible value.
For example, G(1,1)=5 , because Gcd(n3+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)=$12887 and H(10,10)=$3293654 . Find H(18,1900) .
Task. Fortunately, this is a very rare task on Project Euler. For the given text of the program, find the strong and weak points of the algorithm and indicate 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 number ” option . How is it limited?
A few more words if you could not solve it
If we were talking about local maxima, then the answers should be less, but after calculations, it suddenly turns out that we are talking about global maxima, about which there is not a word in the text of the problem.
And further, GCD(n3+1444,(n+1)3+1444)=1 at any n . Which one n suit the authors of the problem?
And further, GCD(n3+1444,(n+1)3+1444)=1 at any n . Which one n suit the authors of the problem?
Code for a 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 a good interview!
Source: https://habr.com/ru/post/438498/