Tasks for the interview

I sometimes conduct interviews of candidates for work. In addition to defining the professional skills of a candidate, my duties include “driving a person through tasks”.

I would like to share a set of tasks that I have collected through interviews, acquaintances, Internet resources, open spaces of my own imagination. I would like to hear an opinion on the complexity / adequacy of these tasks and, possibly, to replenish my collection.

Group 1: Oral puzzles - checking for a fool

1.1 Invert the proposal (it was “Mommy washed the frame”, it became “the frame of the soap Mom”); do it without using additional memory
')
1.2 Given an array of integers. It is known that one of the numbers occurs twice. Find this number by O (n)

1.3 Given a string, for example thisisastringwithoutdelimiters. How to sort through all possible breaks it into words?

1.4 rnd () returns a random integer from 1 to 5. Implement rnd2 () which, using only rnd (), returns a random integer from 1 to 7

1.5 Shuffle a sorted array (i.e., arrange its elements in a random order). Are additional structures needed? What is the difficulty?

Group 2: Write or draw a rough solution on the board

2.1 Derive the central coefficients of Pascal's triangle. For example, for a triangle

                                                 one
                                              eleven
                                           1 2 1
                                        1 3 3 1
                                     1 4 6 4 1
                                  1 5 10 10 5 1
                               1 6 15 20 15 6 1

it will be: 1, 1, 2, 3, 6, 10, 20.
How to do it in the most optimal way?

2.2 Given a square matrix. Print all elements of the matrix in a spiral. For example, for a matrix

                                                 1 2 3 
                                                 4 5 6
                                                 7 8 9

it will be 1, 2, 3, 6, 9, 8, 7, 4, 5

2.3 From a solid cube, a small cube, completely located inside the large cube, was cut out at random. It is required to find a plane that cuts the resulting figure (a large cube with a cavity inside) into two figures of the same size.

2.4 Come up with a data structure that works like a stack FIFO, push () and pop () operations are performed in O (1). The max () operation is also defined, which returns the largest element in the structure and is executed in O (1).

2.5 Using unlimited stacks (FILO) to implement a queue (FIFO)? And vice versa (from the queues to make a stack)?

Group 3: Think Out Loud

3.1 On some island live liars and knights. Liars always tell lies, knights - the truth. Both those and others are able to answer binary questions with the words "tick" and "so"; that means yes, that no is unknown (maybe “tick” is yes, and “so” is not, but maybe vice versa).
Before you is a resident of the island. Ask him one question and, depending on the answer, determine whether he is a knight or a liar.

3.2 There is a dictionary of all words. It is required to come up with a data structure for a dictionary and an algorithm that will be for the shortest time (preferably O (1)) determine which anagram is a given sequence of letters (for example, “naragamam” is an anagram of the word “anagram”)

3.3 There is a sentence in English and a list of bad words. Need to replace all bad words in a sentence with asterisks? And how to replace only the root of the word (for example, “This **** ing shop-assistant is such an *** hole!”)?

3.4 You have a base of famous sequences (for example, numbers of binomial coefficients, Catalan numbers, lost “4 8 16 16 23 42”, etc.); How to organize the storage of these sequences and what algorithm to use in order to determine by user-defined sequence what the numbers are. For example, if the user enters 34, 55, 89, 144, then the algorithm should say that these are Fibonacci numbers.

3.5 You need to create a task scheduler that meets the following conditions:
(a) any task should be executed at a specified frequency (integer seconds),
(b) a new task can be added at any time,
(c) the scheduler should be implemented in a single thread,
(d) the scheduler wakes up every second,
(e) time tasks are executed instantly.
Thus, if 2 tasks were added, A and B, A has a frequency of 2 seconds, and B - 3, in the second second the scheduler will perform A, in the third - B, in the fourth - A, in the fifth - nothing, in the sixth A and B, etc.
How much memory do you need? How to optimize the search time of the task to be performed in the current second? How can you take advantage of the fact that the scheduler step is 1 second?

PS

I realize that the speed / quality of solving problems does not fully characterize the candidate.
And I also like Joel Spolsky's article about conducting an interview .