Tasks with interviews. Three adequate tasks to "think"
And again about the interview. Some simple tasks sometimes cause difficulty. In this post I want to consider three tasks from interviews that I liked, because you can come to their solution yourself, but you still have to think a bit.
Only one phrase “ordered sequence” is confusing, it may suggest using sorting to solve this problem. Programmers often use ready-made libraries and frameworks, so when solving problems with an automatic machine you think about what you will use from the library. For many programmers, the only obvious solution is to sort the resulting sequence and then elementwise compare the original and sorted sequences to the first mismatch. You can calculate the complexity of this solution:
sorting complexity plus linear search complexity. Hm, can it come to a solution in some other way?
This is my favorite puzzle game. On the one hand, you need to think a little, but on the other - it is really simple and adequate.
')
As it turned out, this is a rather popular puzzle. But I decided with a significant shortcoming.
The problem can be solved using arithmetic or bitwise operations. Since the arithmetic seemed easier, I decided to use them.
It remains only to wish all successful interviews!
And in the comments you can write what tasks you met.
Task 1. Check how spoiled you are a programmer.
Given an ordered sequence of numbers from 1 to N. One number was deleted from it, and the rest were mixed. Find the deleted number.
Only one phrase “ordered sequence” is confusing, it may suggest using sorting to solve this problem. Programmers often use ready-made libraries and frameworks, so when solving problems with an automatic machine you think about what you will use from the library. For many programmers, the only obvious solution is to sort the resulting sequence and then elementwise compare the original and sorted sequences to the first mismatch. You can calculate the complexity of this solution:
sorting complexity plus linear search complexity. Hm, can it come to a solution in some other way?There is a simpler solution
Let's forget that the sequence is ordered. Both sequences differ in only one number, which means that in order to find it you need to subtract the amount received from the sum of the elements of the original sequence. And by the way, if all elements are unique, then in the source array we have an arithmetic progression and the first sum can be calculated as 
.
.Task 2. Juggling with numbers
You have five-liter and three-liter jugs and an unlimited amount of water. How to measure exactly 4 liters of water? The jugs have an irregular shape, so it is impossible to accurately measure half of the jug.
This is my favorite puzzle game. On the one hand, you need to think a little, but on the other - it is really simple and adequate.
')
Decision
There will have to be a bit of prigong with primes 5 and 3.
1. Fill the three-liter jug. Pour these 3 liters into a five-liter jug.
2. Fill the three-liter jug again and pour it into the five-liter jug. Remember that in a five-liter jug is now 3 liters, until it is completely filled, 2 liters is poured from another jug. In the three-liter jug remained one liter.
3. Empty the five-liter jug. Pour into it a measured one liter. Fill the three-liter jug again and pour it into the five-liter jug. Now we have 4 liters of water in a large jug.
1. Fill the three-liter jug. Pour these 3 liters into a five-liter jug.
2. Fill the three-liter jug again and pour it into the five-liter jug. Remember that in a five-liter jug is now 3 liters, until it is completely filled, 2 liters is poured from another jug. In the three-liter jug remained one liter.
3. Empty the five-liter jug. Pour into it a measured one liter. Fill the three-liter jug again and pour it into the five-liter jug. Now we have 4 liters of water in a large jug.
Task 3. Without intermediaries
There are two numbers. Can I swap them without using an extra variable?
As it turned out, this is a rather popular puzzle. But I decided with a significant shortcoming.
The problem can be solved using arithmetic or bitwise operations. Since the arithmetic seemed easier, I decided to use them.
Decision
Suppose we have A and B.
A = A + B
B = A - B // After that, B becomes A, since in effect, we get (A + B) - B = A
A = A - B
This solution has a big disadvantage: the possibility of overflow. Therefore, it is better to use the bitwise XOR operation.
A = A ^ B
B = A ^ B
A = A ^ B
How it works: in the first line we get the mask for different bits, in these bits there will be one. Next, reset and set the necessary bits for the exchange of values.
The example will be clearer. Consider the exchange of numbers 5 and 9.
A = 0101 ^ 1001 = 1100
B = 1100 ^ 1001 = 0101
A = 1100 ^ 0101 = 1001
A = A + B
B = A - B // After that, B becomes A, since in effect, we get (A + B) - B = A
A = A - B
This solution has a big disadvantage: the possibility of overflow. Therefore, it is better to use the bitwise XOR operation.
A = A ^ B
B = A ^ B
A = A ^ B
How it works: in the first line we get the mask for different bits, in these bits there will be one. Next, reset and set the necessary bits for the exchange of values.
The example will be clearer. Consider the exchange of numbers 5 and 9.
A = 0101 ^ 1001 = 1100
B = 1100 ^ 1001 = 0101
A = 1100 ^ 0101 = 1001
It remains only to wish all successful interviews!
And in the comments you can write what tasks you met.
Source: https://habr.com/ru/post/332088/
All Articles