A modest interview guide: part 2
In the second part of the post will be considered “Algorithms and concepts” , if you have not read the previous post or want to “remember” the list of topics, then look here .
Understanding / knowledge of well-known sorting algorithms is very important, since many decisions related to sorting or searching, to put it mildly, require ownership of these algorithms. A good way to show your knowledge in front of the interviewer, when the task for sorting is given is to “run” according to known algorithms and see / find out which of them is best suited for solving this problem. You will receive both a solution and the fact that the interviewer will be satisfied with your “different” ways of solving the same problem.
For example, " you have a large array of Employee objects, sort employees by age ."
Here you need to pay attention to at least two things. Firstly, the array is large, it means efficiency first of all, and secondly, the sorting is based on ages, that is, it is already clear to us that the values are in a small interval. You can safely use the block sorting algorithm.
What algorithms you should know (what are these "known"):
" You have two sorted arrays A and B, the size A is larger enough to contain an array B. Write a method that merges B into A while maintaining the sort order ."
')
With the search, you find yourself in a more “advantageous” position, it’s enough to know linear and binary algorithms and the matter is, so to speak, in a hat.
" Given an array in which each row and column is sorted, write a function to find the element in the array ."
Take a look at the solution below and suggest the best solution:
Note that it does not really matter here that the code in the post is in C ++, in most cases the same code is syntactically equivalent, for example, to Java or C # code.
Tasks for reflection:
" Implement a binary search algorithm ."
“ How to organize the sorting of a million floating point numbers? ".
" Implement an array sorting from Employee objects by salary (we assume that Employee contains fields for name, age, salary and address) ".
There are a huge variety of tasks with recursion, many tasks follow the pattern. If the task can be divided into subtasks, then this is a hint that the task is “recursive”. If you hear tasks like “ Write a code that outputs the first n ... ”, “ Implement a function that considers everything ... ”, first try to use, well, at least think about using, the recursive method of solving.
It should be noted that in all cases practice is your best friend, how many problems you solve, the easier it becomes for you not only to solve a new problem, but also to focus on the method of solving the problem itself.
And so, first try to recognize the subtasks. Solve / find the “basic” problem, the one at which the recursion stops (basically it is a hard coded value). Solve the problem for the 2nd subtask and understand how to solve the third subtask, based on the second. Summarize the solution for the nth subtask.
Remember, any problem solved by recursion also has an iterative solution. And yet, a recursive algorithm can be very inefficient in terms of free space.
" Write a function that generates the n-th Fibonacci number. "
Recursive option:
Iterative option:
For reflection:
" How would you improve the solution to the problem above? "
" Write a function that returns all subsets of a certain set ."
" Solve the queen's problem "
Bit manipulation can be scary for many candidates, although it should not.
It is enough just to make a mistake when solving these problems, so be careful, or rather, be careful. Consider each line of code you write carefully.
Do not forget about the shift, x << y (left shift) means that x is shifted to the left by y bits and x >> y (right shift), respectively, y bits to the right.
There is one quite popular problem, try to solve it yourself (I quote from the “reverse side”) - “ Explain the following code: ((n & (n - 1)) == 0) ”.
“There are two 32-bit numbers, N and M. There are also two bit positions, i and j. Write a function that sets all bits between i and j to N equal to M (that is, M becomes a substring of N)
Example:
Input: N = 100000000, M = 101, i = 2, j = 3
Yield: N = 100010100. "
For reflection: “ Given a floating-point number as a string, output a binary representation. "
Questions about the PLO (here P - design) are of great importance, at least I think so. Knowledge of OOP has some confidence in the interviewer, since it becomes clear that the candidate will “understand” the class diagrams of the project on which he will work. This is only a small plus, there are other important advantages of the PLO in favor of the candidate. But the lack of knowledge will cause the interviewer a feeling of "who is next there?" This, of course, refers to posts related to the PLO, and then, in my opinion, the driver developer is unlikely to ask about PLO. However, during the interview, be prepared that you will be asked to design some application, or even a “non-application,” such as a television. Ask to talk about the relationship between, say, the remote and the TV. Be prepared for questions like “What is the difference between is-a and has-a?”.
" Design a chat server ."
This is a simple example, in reality the questions / tasks are of “good quality”.
For reflection: “ Design data structures for online book readers ”.
I think this is enough, in the following posts there is an intention to write not only about the programming language, but also about other topics / questions that will be related to more complex interviews.
Algorithms and Concepts
Sort and search
Understanding / knowledge of well-known sorting algorithms is very important, since many decisions related to sorting or searching, to put it mildly, require ownership of these algorithms. A good way to show your knowledge in front of the interviewer, when the task for sorting is given is to “run” according to known algorithms and see / find out which of them is best suited for solving this problem. You will receive both a solution and the fact that the interviewer will be satisfied with your “different” ways of solving the same problem.
For example, " you have a large array of Employee objects, sort employees by age ."
Here you need to pay attention to at least two things. Firstly, the array is large, it means efficiency first of all, and secondly, the sorting is based on ages, that is, it is already clear to us that the values are in a small interval. You can safely use the block sorting algorithm.
What algorithms you should know (what are these "known"):
- Bubble sort.
- Sort selection (selection sort).
- Merge sort.
- Quick sort.
- Block sorting (bucket sort).
" You have two sorted arrays A and B, the size A is larger enough to contain an array B. Write a method that merges B into A while maintaining the sort order ."
')
void merge(int a[], int b[], int n, int m) { int k = m + n - 1; int i = n - 1; int j = m - 1; while (i >= 0 && j >= 0) { if (a[i] > b[j]) { a[k--] = a[i--]; } else { a[k--] = b[j--]; } } while (j >= 0) { a[k--] = b[j--]; } } With the search, you find yourself in a more “advantageous” position, it’s enough to know linear and binary algorithms and the matter is, so to speak, in a hat.
" Given an array in which each row and column is sorted, write a function to find the element in the array ."
Take a look at the solution below and suggest the best solution:
bool find_element(int** mat, int elem, int M, int N) { int row = 0; int col = N - 1; while (row < M && col >= 0) { if (mat[row][col] == elem) { return true; } else if (mat[row][col] > elem) { --col; } else { ++row; } } return false; }
Note that it does not really matter here that the code in the post is in C ++, in most cases the same code is syntactically equivalent, for example, to Java or C # code.
Tasks for reflection:
" Implement a binary search algorithm ."
“ How to organize the sorting of a million floating point numbers? ".
" Implement an array sorting from Employee objects by salary (we assume that Employee contains fields for name, age, salary and address) ".
Recursion
There are a huge variety of tasks with recursion, many tasks follow the pattern. If the task can be divided into subtasks, then this is a hint that the task is “recursive”. If you hear tasks like “ Write a code that outputs the first n ... ”, “ Implement a function that considers everything ... ”, first try to use, well, at least think about using, the recursive method of solving.
It should be noted that in all cases practice is your best friend, how many problems you solve, the easier it becomes for you not only to solve a new problem, but also to focus on the method of solving the problem itself.
And so, first try to recognize the subtasks. Solve / find the “basic” problem, the one at which the recursion stops (basically it is a hard coded value). Solve the problem for the 2nd subtask and understand how to solve the third subtask, based on the second. Summarize the solution for the nth subtask.
Remember, any problem solved by recursion also has an iterative solution. And yet, a recursive algorithm can be very inefficient in terms of free space.
" Write a function that generates the n-th Fibonacci number. "
Recursive option:
int fibonacci(int n) { if (0 == n) { return 0; } if (1 == n) { return 1; } // if(0 == n || 1 == n) { return n; } if (n > 1) { return fibonacci(n - 1) + fibonacci(n - 2); } return -1; // }
Iterative option:
int fibonacci(int n) { if (n < 0) { return -1; } if (n == 0) { return 0; } int a = 1, b = 1; for (int i = 3; i <= n; ++i) { int c = a + b; a = b; b = c; } return b; }
For reflection:
" How would you improve the solution to the problem above? "
" Write a function that returns all subsets of a certain set ."
" Solve the queen's problem "
Bit manipulation
Bit manipulation can be scary for many candidates, although it should not.
It is enough just to make a mistake when solving these problems, so be careful, or rather, be careful. Consider each line of code you write carefully.
Do not forget about the shift, x << y (left shift) means that x is shifted to the left by y bits and x >> y (right shift), respectively, y bits to the right.
There is one quite popular problem, try to solve it yourself (I quote from the “reverse side”) - “ Explain the following code: ((n & (n - 1)) == 0) ”.
“There are two 32-bit numbers, N and M. There are also two bit positions, i and j. Write a function that sets all bits between i and j to N equal to M (that is, M becomes a substring of N)
Example:
Input: N = 100000000, M = 101, i = 2, j = 3
Yield: N = 100010100. "
int update_bits(int n, int m, int i, int j) { int max = ~0; // 1' // 1' j, 0' int left = max - ((1 << j) - 1); //1' i int right = ((1 << i) - 1); // 1' i j int mask = left | right; //"" i j m return (n & mask) | (m << i); }
For reflection: “ Given a floating-point number as a string, output a binary representation. "
Object Oriented Design
Questions about the PLO (here P - design) are of great importance, at least I think so. Knowledge of OOP has some confidence in the interviewer, since it becomes clear that the candidate will “understand” the class diagrams of the project on which he will work. This is only a small plus, there are other important advantages of the PLO in favor of the candidate. But the lack of knowledge will cause the interviewer a feeling of "who is next there?" This, of course, refers to posts related to the PLO, and then, in my opinion, the driver developer is unlikely to ask about PLO. However, during the interview, be prepared that you will be asked to design some application, or even a “non-application,” such as a television. Ask to talk about the relationship between, say, the remote and the TV. Be prepared for questions like “What is the difference between is-a and has-a?”.
" Design a chat server ."
enum status_type { online, offline, away }; struct status { status_type m_status_type; std::string m_status_message; }; struct add_request; class user { private: std::string m_username; std::string m_display_name; std::list<user*> m_contact_list; std::list<add_request*> requests; public: bool update_status(status_type stype, const std::string& msg); bool add_user_with_username(const std::string& name); bool approve_request(const std::string& username); bool deny_request(const std::string& username); bool remove_contact(const std::string& username); bool send_message(const std::string& username, const std::string& message); }; struct add_request { user* m_from_user; user* m_to_user; }; class server { user* get_user_by_username(const std::string& username); };
This is a simple example, in reality the questions / tasks are of “good quality”.
For reflection: “ Design data structures for online book readers ”.
I think this is enough, in the following posts there is an intention to write not only about the programming language, but also about other topics / questions that will be related to more complex interviews.
Source: https://habr.com/ru/post/128730/
All Articles