Lecture
When hiring an employee for an office position as a programmer, an employer tests candidates not only with questions about skills, but also with all kinds of logic puzzles, IT cases, and development tasks for professional programmers.
As a rule, the list of these tasks is the same across employers, which means we can prepare for any interview!
Our tasks section already has more than 100 questions with detailed solution walkthroughs. We decided to gather together all the most interesting and popular tasks for programmers that you might encounter at an interview.
There is a singly linked list of structures. In it, random points to some other element of the same list. You need to write a function that copies this list while preserving the structure (i.e. if in the old list the random pointer of the first node pointed to the 4th node, in the new list the same should hold – the random pointer of the first node points to the 4th node of the new list). O(n), constant additional memory + memory for the elements of the new list. You cannot allocate memory for all the data at once in a single chunk, i.e. the list must be genuine, scattered across separate parts, and not a single block like an array.
Answer An implementation option
A classic Google interview question. Numbers are written on the board; you need to answer the question: what number comes next?
Answer
Suppose you fly from Moscow to Vladivostok and then back, in perfectly calm conditions. Then you make exactly the same flight, but this time a constant westerly wind blows throughout the entire flight: a tailwind in one direction, a headwind in the other.
How will the total round-trip flight time change?
or see the results
Answer
What's wrong with this piece of C++ code?
operator int() const {
return *this;
}
Answer
A task that was popular at one time in Amazon interviews. We have Russified it, but the meaning stays the same. You need to continue the sequence.
The author's answer with a review of subscribers' answer options
How do you calculate this without a calculator? Can you give an approximate answer?
Answer
«You have been shrunk to the size of a nickel and thrown into a blender. Your weight has decreased so that your body's density remains the same. The blades will start rotating in 60 seconds. What do you do?»
This is a classic Google puzzle, a good breakdown of which is not so easy to find on the Russian-language internet. We have prepared one for you. There is no absolutely correct answer, but there are answers that are clearly better than others.
Review of answer options
A question about C++. What is the "pure virtual function call" error? In what situation can it be generated? Provide minimal code that leads to it.
Answer
You have at your disposal 10 thousand servers in a data center with remote management capability and one day to make a million dollars. What will you do to achieve this?
Answer
You have an analog clock with a second hand. How many times a day do all three clock hands overlap each other?
Answer
What is the difference between string and String in C#?
Answer
You are playing soccer on a desert island and want to flip a coin to decide which team gets the ball. The only coin you have is bent, and therefore introduces a clear bias into the outcome when flipped. How can you nevertheless use such a coin to make a fair decision?
Answer
How many golf balls would fit into a school bus?
Golang Live 2020 Conference
October 14–17, Online, From 6900 to 40 000 ₽
tproger.ru
Events and courses on tproger.ru
For reference: the 1995 US National School Bus Standards specify maximum school bus dimensions of 40 feet in length and 8.5 feet in width. The standard diameter of a golf ball is 1.69 inches with a tolerance of 0.005 inches.
Answer
Imagine a spinning disc, such as a DVD. You have black (B) and white (W) paint at your disposal. A small sensor is mounted at the edge of the disc, which detects the color beneath it and outputs the result as a signal. How would you paint the disc so that it would be possible to determine the direction of rotation from the sensor readings?
Let's give a brief clarification of the problem. The first thing to keep in mind is that you cannot observe the disc itself. For example, you are sitting in an office while the disc spins in a closed laboratory. The only way to determine the direction of rotation is to use the digitized sensor readings, and nothing else.
The sensor records the color of the point at its fixed location at successive moments in time. The readings are presented in the form «BBBWW…». The task comes down to finding a coloring of the disc where the sequence of readings differs when spinning forward versus in the opposite direction.
Answer
You have the source code of an application in C that crashes after being launched. After ten runs in the debugger, you discover that each time the program crashes at a different location. The application is single-threaded and uses only the standard C library. What errors could cause the application to crash? How would you check for each of them?
Answer
Find the errors in the following code.
unsigned int i;
for (i = 100; i >= 0; --i)
printf("%d
", i);
Answer
Explain what this code does.
((n & (n – 1)) == 0)
Answer
Given a 100-story building. If an egg is dropped from the N-th floor (or a greater height), it will break. If it is dropped from any lower floor, it will not break. You have two eggs. Find N using the minimum number of drops.
Answer
Continuing with C/C++ tasks. What does the volatile keyword mean and in what situations can it be applied? Even if you remember the formal definition, try to give an example of a situation where volatile would actually be useful.
Answer
You have a sorted matrix of size MxN. Propose an algorithm for searching for an arbitrary element in it. By a sorted matrix we mean a matrix whose rows and columns are sorted (see example).
Answer
Write a method that finds the maximum of two numbers without using if-else operators or any other comparison operators.
Answer
On a deserted highway, the probability of a car appearing within a 30-minute period is 0.95. What is the probability of it appearing within 10 minutes?
Answer
Write a function that sums two integers without using "+" or other arithmetic operators.
Answer
You have a fleet of 50 trucks. Each of them is fully fueled and can travel 100 km. How far can you deliver a certain cargo using them? What happens if you have N trucks at your disposal?
Not everyone immediately understands what this is about: geographically, this is a place with no gas stations at all. The only place here where you can find fuel is the fuel tanks of the trucks. You cannot switch from a truck to a hybrid Prius passenger car. Abandoning a truck without fuel, wherever that happens, and without a driver, is business as usual. And the only thing that matters here is delivering the valuable cargo as far as possible.
Answer
Describe an algorithm for finding the million smallest numbers in a set of a billion numbers. The computer's memory is enough to store the entire billion numbers. If you came up with some solution, evaluate its time efficiency. Is there a more efficient solution?
Answer
Write a method that counts the number of digits «2» used in the decimal representation of the integers from 0 to n (inclusive). The picture is given as a hint toward one of the possible solutions.
Answer
Where will you swim faster — in water or in syrup?
This is a classic problem with a long history, which even Isaac Newton once discussed. At one time it was also used in IT interviews at Google (not anymore). Nevertheless, we invite you to think through a solution.
Answer
Write methods for multiplying, subtracting, and dividing integers, using only the addition operator among arithmetic operations. The implementation language does not matter, and you also don't need to worry much about optimizing execution speed or memory usage. The main thing is that only addition can be used. In problems like this, it is useful to recall the essence of mathematical operations.
Answer
Suppose you are writing a pipeline in which 2 threads, using a shared buffer, process data. The producer thread creates this data, and the consumer thread processes it (the Producer–consumer problem). The following code represents the simplest model: using std::thread we spawn a consumer thread, and we will create the data in the main thread.
Let's set aside the synchronization mechanisms of the two threads, and pay attention to the main() function. Try to guess what's wrong with this code, and how to fix it?
void produce() {
// create a task and put it into the queue
}
void consume() {
// read data from the queue and process it
}
int main(int , char **) {
std::thread thr(consume); // spawn a thread
produce(); // create data to be processed
thr.join(); // wait for the consume() function to finish
return 0;
}
Answer
You are given 20 jars of pills. In 19 of them the pills weigh 1 g, and in one – they weigh 1.1 g. You are given a scale that shows the exact weight. How do you find the jar with the heavy pills in a single weighing?
Answer
You are given an 8×8 chessboard from which two diagonally opposite corners have been cut out, and 31 dominoes; each domino can cover two squares on the board. Can the entire board be tiled with the dominoes? Justify your answer.
Answer
You are given an input file containing four billion 32-bit integers. Propose an algorithm that generates a number not present in the file. You have 1 GB of memory available for this task. Bonus: what if you only have 10 MB? The number of passes over the file must be minimal.
Answer
Propose an algorithm that generates all valid combinations of pairs of parentheses. By valid combinations of pairs we mean correctly opened and closed parentheses. The input is the number of pairs of parentheses, and the output should be all their possible combinations as a set of strings.
Answer
You place a glass of water on the platter of a vinyl record player and slowly increase the rotation speed. What will happen first: the glass will slide sideways, the glass will tip over, or the water will splash out?
This question has previously been asked at interviews at Apple. In your answer, consider the possible scenarios and specify what the answer depends on if there is more than one.
Answer
A short C++ problem posed as a question for beginners. Why must the destructor of a polymorphic base class be declared virtual? We consider a class polymorphic if it has at least one virtual function.
Answer
Write a function that swaps the values of two variables without using a temporary variable. Suggest as many approaches as possible.
Answer
Propose an algorithm for finding the k-th element from the end of a singly linked list. The list is implemented manually; only the operation of getting the next element and a pointer to the first element are available. The algorithm should, if possible, be optimal in both time and memory.
Answer
Write a function that determines the number of bits that must be changed to turn integer A into integer B. Assume the numbers are 32-bit, in any language.
This is one of the typical bit-manipulation problems that interviewers like to give. If you have never encountered them before, it will be hard to solve this problem right away under stressful conditions, so remember the tricks used to solve it.
Answer
A book has N pages, numbered as usual from 1 to N. If you add up the number of digits contained in each page number, the total is 1095. How many pages are in the book?
Answer
A C++ problem that will nevertheless be useful for other languages too. Compare a hash table and the map from the Standard Template Library (STL). How is a hash table organized? Which data structure would be optimal for small amounts of data?
Answer
Design a class that provides locking in such a way as to prevent deadlock from occurring.
Answer
Write a function in C++ that outputs the last K lines of a file to standard output. The file is very large, say 50 GB, the length of each line does not exceed 256 characters, and the number K < 1000.
Answer
You are given a piece of cheese in the shape of a cube and a knife. What is the minimum number of cuts needed to divide this piece into 27 identical small cubes? What about into 64 cubes? After each cut, the pieces can be rearranged in any way.
This kind of problem used to be given often at interviews, and it was actually invented back in 1950.
Answer
Implement a method that determines whether one string is a permutation of another. By permutation we mean any reordering of the characters. Case matters, and spaces are significant.
Answer
In a dark room you are handed a deck of cards, in which a known number N of the cards are lying face up, and the rest are face down. You cannot see the cards, but you can flip them. How would you divide the deck into two stacks so that each stack has the same number of face-up cards?
This puzzle was once popular at JP Morgan Chase. Obviously, if you found yourself in the dark, you would simply take out your cell phone and use its screen as a flashlight. However, this problem originated before the era of cell phones, and it can be solved even without seeing the cards.
Answer
Implement a stack by hand with the standard push/pop functions and an additional min function that returns the minimum element of the stack. All of these functions must run in O(1). Optimize the solution for memory usage.
Answer
How many integers in the range from 1 to 1000 contain the digit 3? You need to count this without using a computer, giving your reasoning in the comments.
Answer
You have a large number of URLs, on the order of 10 billion. How would you organize an efficient search for duplicates, given that of course they will not all fit in memory?
Answer
You must choose one of two bets. In the first option, you have to throw a basketball into the hoop in a single shot. If you make it, you get 50,000 rubles. In the second option, you need to make two out of three throws, and then you also get the same 50,000 rubles. Which of these options would you prefer? Would your skill at shooting baskets affect your choice?
Answer
Imagine a triangle made up of numbers. One number sits at the apex. Below it are two numbers, then three, and so on down to the bottom row. You start at the apex and need to descend to the base of the triangle. On each move you can go down one level and choose between the two numbers below your current position. As you move, you «collect» and sum up the numbers you pass through. Your goal is to find the maximum sum obtainable from the various routes.
What algorithm would you propose? What is its complexity, and can you suggest a better solution?
Answer
You are given two words or phrases, and your task is to check whether they are anagrams.
An anagram is a word game where rearranging the letters of a word or phrase produces another word or phrase. Two words are anagrams if one can be obtained from the other by rearranging the letters.
Answer
Propose an algorithm that zeroes out column N and row M of a matrix if the element at cell (N, M) is zero. Naturally, you need to minimize both memory usage and running time.
Answer
Design an algorithm that finds all pairs of integers in an array whose sum equals a given value.
Answer
Suppose you need to design an algorithm that shows a person's circle of acquaintances for a social network. How would you do this, given that the database is very large?
By a large database we mean on the order of a billion registered users and no fewer than 100 billion «friend» connections between them.
Answer
Suppose you have a singly linked list with a loop. Its «last» element contains a pointer to one of the elements of this same list, and not necessarily to the first one. Your task is to find the starting node of the loop.
The elements of the list cannot be modified, and you may use only constant memory.
Answer
There is a rule on the island — blue-eyed people are not allowed to be there. A plane leaves the island every evening at 20:00. All the inhabitants gather around a round table every day; each person can see the eye color of the other people, but does not know their own. No one is allowed to tell anyone what color their eyes are. There is at least one blue-eyed person on the island. How many days will it take for all the blue-eyed people to leave?
Answer
Write code that removes duplicates from an unsorted linked list. You may only use constant memory.
Answer
Write a method that shuffles a deck of cards. The deck must be perfectly shuffled, i.e. all permutations of the cards must be equally likely. You may use a perfect random number generator.
Answer
Suppose you are tasked with developing a web crawler — a program that, roughly speaking, visits pages on the Internet, indexes them, extracts links from them, follows those links, and repeats the process. Question: how do you avoid infinite loops?
Answer
You have a glass jar containing small marbles, and at any time you can determine how many there are. You and a friend play the following game: each of you, in turn, takes 1 or 2 marbles from the jar. The player who takes the last marble wins. What is the best strategy in this game? Can you predict who will win right from the start?
Answer
There are N companies, and you want them to merge into one large company. How many different ways can you do this? An acquisition can be considered a special case of a merger, where A acquires B and B acquires A count as two different ways. Equal mergers are also possible.
Answer
What is the minimum set of coins needed to give any amount of change from 1 to 99 cents? The available coin denominations are 1, 5, 10, 25, 50 cents and 1 dollar.
Answer
You have 25 horses. How many races do you need to hold to determine the three fastest of them? You cannot use a stopwatch. Only five horses can take part in each race.
Answer
A short brain-teaser. A study found that 70% of people like coffee, while 80% like tea. What are the upper and lower bounds on the share of people who like both coffee and tea?
Answer
A problem that must be solved without a calculator or computer, with only a pencil and paper at hand. How many trailing zeros are there in 100 factorial?
Answer
Propose an algorithm for finding the largest sum of a contiguous subsequence from an array of integers, both positive and negative.
Answer
Write a program to compute the median value in a stream of numbers, dynamically tracking new incoming numbers obtained at random.
Answer
It is raining, and you need to get to your car, which is parked at the far end of the parking lot. Will you run to it or not, if your goal is to get as little wet as possible? How would you behave if you have an umbrella?
Answer
Imagine there is a square matrix, each pixel of which can be black or white. Design an algorithm for finding the largest sub-square whose sides are all black.
An analysis of two solutions with O(N^4) and O(N^3). Can you find other approaches?
Answer
Suppose only unsociable patrons go to a certain bar. There are 25 seats along the bar counter. Whenever a new patron enters, they always sit in the seat that is as far as possible from the other guests. No one will sit next to anyone else: if a patron enters and sees that there are no «free» seats, they immediately turn around and leave the bar. The bartender, naturally, wants as many customers as possible to be sitting at the counter. If he is allowed to seat the first patron anywhere, where is the most advantageous seat for him from the bartender's point of view?
Answer
Describe how a single one-dimensional array could be used to implement three stacks.
Answer
You have an unlimited number of coins with denominations of 25, 10, 5, and 1 cent. Write code that determines the number of ways to represent n cents.
Answer
Write code that finds the minimum distance (expressed as a number of words) between any two words in a file. Order does not matter.
Will linear time be sufficient?
How much memory will be needed for the solution?
Answer
Simulate rolling a seven-sided die if all you have available is a five-sided die.
In other words, how do you obtain a random number in the range from 1 to 7 using a random integer generator that produces numbers from 1 to 5?
Answer
Write code that partitions a linked list around a given value so that all nodes smaller than the value come before nodes greater than or equal to it.
Answer
Write a method that generates a random sequence of m integers from an array of size n. All elements must be chosen with equal probability.
The first thing that comes to mind is to pick random elements from the array and place them in a new array. But what if we pick the same element twice?
Answer
Imagine a robot located in the top-left corner of a grid with coordinates (X, Y). The robot can move in two directions: right and down. How many routes are there from point (0, 0) to point (X, Y)?
Additionally, assume that the grid contains regions that the robot cannot cross. Design an algorithm for building a route from the top-left corner to the bottom-right corner.
Answer
Implement a string compression method based on counting repeated characters. For example, the string aabcccccaaa should turn into a2b1c5a3. If the «compressed» string turns out to be longer than the original, the method should return the original string.
Answer
You are in a car, where a helium-filled balloon is tied to the floor with a string. The windows are closed. You press the gas pedal. What will happen to the balloon: will it move forward, backward, or stay in the same position?
What will happen to the balloon?
or see the results
Answer
A problem that can be used as a brief introduction to the basics of RSA cryptography.
Suppose you want to make sure that your friend Petya has your phone number. But you cannot ask him about it directly. You will have to write him a message on a card and give the card to Katya, who will act as an intermediary. Katya will take the card to Petya, he will write his message and give it to Katya, who will pass it on to you. You do not want Katya to find out your phone number. Under these circumstances, how should you phrase your question to Petya?
Even without knowing anything about RSA, you can try to come up with an answer.
Answer
A problem that tests knowledge of specific languages. Explain the difference between templates in C++ and generics in Java.
Many programmers believe that C++ templates and generics (for example in Java) are the same thing, since their syntax is similar: in both cases you can write something like List. But there actually are differences.
Answer
Implement a «smart» pointer with automatic memory management in C++ by hand.
A smart pointer is the same as an ordinary pointer, but it provides safety through automatic memory management. Such a pointer helps avoid many problems: dangling pointers, memory «leaks», and memory allocation failures. A smart pointer must keep a count of the number of references to the pointed-to object.
At first glance this problem seems quite difficult, especially if you are not an expert in C++.
Answer
This puzzle, in which you are made to second-guess yourself by being offered a chance to switch your answer, is also known as the «Monty Hall Problem». Monty Hall was the first host of the television game show «Let's Make a Deal»
In front of you are three boxes, one of which contains a valuable prize, while the other two are empty. You may choose any box, but you still do not know which one has the prize. One of the two boxes you did not choose is opened and shown to be empty. Now you can either keep the box you originally chose (stay), or switch it for the other unopened box (switch). Which would you prefer to do (stay or switch)?
Answer
You have an empty room and a group of people outside it. On each move you can either let one person enter the room, or let one person leave it. Can you propose a sequence of moves such that every possible combination of people in the room occurs exactly once?
It takes some time to figure out exactly what the interviewer wants from you. A simple example helps clarify this. Say there are two people outside the door, Larry and Sergey. There are four possible combinations of their presence in the room, counting the case when no one is in the room at all.
Here they are:
The question is whether we can start with no one in the room, and then go through the given sequence of steps.
In other words, how do you generate non-repeating combinations by changing only one element at a time?
Answer
Write code to find the submatrix with the maximum possible sum in an N*N matrix containing positive and negative numbers.
Answer
A difficult problem that requires the ability to come up with algorithms.
According to the problem statement, you need to design an algorithm that finds the k-th number from an ordered numeric sequence in which the elements' prime factorizations contain only 3, 5, and 7.
A solution with Java code examples is available on our site.
Solution with code examples
You are given a list of a million words. Design an algorithm that builds the largest possible rectangle of letters so that every row and every column form a word (reading left to right and top to bottom). Words may be chosen in any order, the rows must be the same length, and the columns must be the same height.
Answer
You are given an array of Integer values. You need to write a function that takes the original array as input and returns an array in which each value is obtained by multiplying together all the values of the original array whose index differs from the current one.
For clarity, here is an example. Suppose the original array is:
[1, 7, 3, 4]
Then the function should return:
[84, 12, 28, 21]
The values are calculated as follows:
[7*3*4, 1*3*4, 1*7*4, 1*7*3]
Additional conditions:
Answer
A problem that tests your ability to reason. The specific answer does not matter; what matters is showing how you think. Imagine that you need to get from point A to point B, but you do not know how. What would you do?
Answer
Imagine you were given the task of developing an evacuation plan for a large city (in the classic version — San Francisco). Where would you start?
Answer
A problem that was asked at interviews at Apple: you have an array of integers, including negative ones, and you need to find the largest product of 3 numbers from this array.
For example: you have an array list_of_ints containing the numbers -10, -10, 1, 3, 2. The function that processes this array should return 300, since -10 * -10 * 3 = 300. The task must be performed as efficiently as possible, without forgetting to account for negative numbers.
Answer
Imagine a country where all parents want to have a boy. Every family keeps having children until they have a boy, and then stops. What is the ratio of boys to girls in this country?
Ignore situations involving twins, triplets, and so on, couples who have no children, and couples who die before having a boy.
As usual, we invite you to reason about the solution in the comments. You can check your answer on the site via the attached link, where we give our version of the solution.
Answer
Estimation problems, meaning problems that call for an approximate solution, are a popular class of questions asked at IT company interviews. We offer you several such problems, along with a discussion of general methods for solving them and specific interview tips.
How many bottles of shampoo are produced in the world per year? Answer
How many ridges are there on the edge of a quarter — a 25-cent coin? Answer
What is 2 to the 64th power? Answer
How much toilet paper would be needed to cover an entire state? Answer
How many atoms of rubber are worn off a car tire with each rotation of the wheel? Answer
How much money would be needed to wash all the windows in Seattle? Answer
Also see examples of other problems for practicing on your own.
A problem that was asked at interviews at Apple. You are required to write a function that returns the maximum profit from a single trade of a single stock (buy first, then sell). The input data is an array of yesterday's quotes, stock_prices_yesterday, with Apple's share prices.
Information about the array:
For example: if the stock cost 20 dollars at 10:00 am, then
stock_prices_yesterday[30] = 20.
Suppose we have the following conditions:
stock_prices_yesterday = [10, 7, 5, 8, 11, 9] profit = get_max_profit(stock_prices_yesterday) #returns 6 (bought at 5, sold at 11)
The array can be anything, even a whole day's worth. You need to write the get_max_profit function as efficiently as possible — with the lowest running time and memory usage.
Answer
A problem about merging intervals in a calendar.
Suppose the company you work for is developing an electronic calendar. The calendar has a feature that shows when various programming teams will be busy in some meeting.
The periods when a team is busy are marked on the calendar as time ranges, for example, from 10:00 to 12:30 or from 12:30 to 13:00. In the program being developed, a time interval is represented as a tuple of two integers. The number represents the index of the 30-minute block that comes after 9:00 am. For example, the tuple (2, 4) represents the range from 10:00 to 11:00, and (0, 1) is the interval 9:00-9:30.
You need to write a function that should simplify the output in such a way that if a team is busy in the intervals from 10:00 to 12:30 and from 12:30 to 13:00, this is displayed as 10:00-13:00. For example: the input to your function is an unordered array of tuples [(0, 1), (3, 5), (4, 8), (10, 12), (9, 10)], and the output should be the ordered array [(0, 1), (3, 8), (9, 12)].
In the future, it is planned to modify the program so that instead of 30-minute blocks it will use minute blocks, as implemented in the Unix time representation. Given this upcoming change, your function should already be able to work with large numbers. Also, do not forget that a tuple is a data type whose contents cannot be changed after it is created.
Answer
A problem that was asked at interviews at Apple. Imagine that you got a job as a cashier in a store. Your boss accidentally found out that you have programming skills, and wants you to help him write a program.
Input data:
You need to write a function that outputs the number of all possible ways to make the specified amount of money using the various available coin denominations. For example, if you need to make 4 cents from coins with denominations of 1, 2, and 3 cents, then the function returns 4 — that is exactly how many possible combinations of the numbers 1, 2, and 3 there are that sum to 4:
Answer
This problem was once asked at Google.
You need to climb a staircase. In one step you can go up one or two stairs. How many ways are there to reach the N-th stair?
Answer
This problem was asked at an interview at Twitter.
Consider the following picture:
This picture shows walls of various heights in a certain flat world. The picture is represented by an array of integers, where the index is a point on the X axis, and the value at each index is the height of the wall (the value on the Y axis). The array [2, 5, 1, 2, 3, 4, 7, 7, 6] corresponds to the picture above.
Now imagine that it started raining, and the rain never stops, pouring down on the walls from above in a uniform stream. How much water will collect in the «puddles» between the walls?
walls and rain problem, Twitter interview
We take the unit of water volume to be a 1×1 square block. In the picture above, everything to the left of point 1 spills out. Water to the right of point 7 also spills out. We are left with a puddle between 1 and 6 — so the resulting volume of water is 10.
Answer
A problem about an infinite train.
Imagine a railway that forms a closed loop. A train runs along it, whose last car is coupled to the first one so that you can move freely between cars inside. You find yourself in some random car, and your task is to count their total number. In each car you can turn the light on or off, but the initial position of the switches is random and unknown in advance.
All the cars look exactly the same inside, the windows are covered so it's impossible to look outside, and the train moves at a constant speed. You cannot mark the cars in any way other than turning the light on or off. The number of cars is finite (don't be fooled by the name of the problem).
Answer
You are standing in front of a closed room that contains three light bulbs. On the wall in front of you are three switches, each of which turns one of the bulbs on or off. You need to figure out which switch corresponds to which bulb, given that you can enter the room only once.
The arrangement of the switches is random, and the wiring order is unknown in advance. Once you enter the room, you can do anything you like with the bulbs, but you can no longer go back to the switches. Initially all the bulbs are off.
If you want to solve the problem on your own but nothing comes to mind, you can use our hint.
See the hint
Under the initial conditions, the bulbs have only two states: on or off. Clearly, this is not enough to split them into three groups. You need to come up with some additional states for the bulbs and a way to achieve them using the switches.
Or go straight to the answer
A classic problem. In the string given to you, find the longest substring that is a palindrome (that is, it reads the same left to right and right to left). Propose as efficient an algorithm as possible.
Answer
Implement a square root extraction function without using the language's built-in root-finding and exponentiation facilities.
Answer
In this problem you need to implement a function that checks whether a number is even, using only the bitwise operations AND, OR, NOT.
Answer
On a line, N segments are given (in real life these could be time intervals, for example), specified by the coordinates of their left and right endpoints. For each given segment, you need to find out how many of the given segments lie entirely within it. One segment is entirely contained in a second one if the left endpoint of the first segment is to the right of the left endpoint of the second, and the right endpoint of the first is to the left of the right endpoint of the second. Propose as efficient a solution as possible for this problem. It is guaranteed that all the endpoints of the given segments are distinct.
If you come up with a solution, you can write and test it here, on Codeforces.
Can you solve this problem efficiently in the case where the endpoints of the segments may coincide?
Answer
Come up with an algorithm that determines whether all the characters in a string occur exactly once.
You may not use additional data structures when completing this task.
Answer
In an array of random numbers A[0…n-1], there is a single «magic» index: one such that A[i] = i. The values of the elements in the array cannot repeat. Given that the array is sorted by value in increasing order, write a method that determines this «magic» index if it exists in array A. If there is no such element in the array, return any negative number.
How would the solution change if it is known that there are several such indices in the array?
Answer
How can you find out the number of days in a month, knowing its number? In other words, describe how to obtain a function f(x) that would give the following list of values:
As the argument we only get the month number, i.e. we do not account for leap years, and f(2) = 28.
Answer
A problem for Python fans: you need to go through all pairs of characters in a string, and stop as soon as you find two identical characters.
The solution is fairly obvious, but a question arises:
s = "some string"
for i in range(len(s)):
for j in range(i+1, len(s)):
if s[i] == s[j]:
print(i, j)
break # How to break out of both loops at once?
If we were programming in, say, Java, we could use the labeled loop mechanism:
outterLoop: for(int i=0; i
However, there is no such mechanism in Python. You need to propose the most convenient and readable solution.
Answer
Write code that checks whether two given lines, lying in the same plane, will intersect. Suppose that we need to design a data structure for storing information about a line, and let's assume that if two lines coincide, they are considered to intersect.
See the hint
You probably remember from school that if two lines lying in the same plane are not parallel, then they intersect. So, to check whether two lines intersect, it is enough to check whether their slopes differ and their intercepts do not coincide.
Answer
A classic problem: compute the N-th number of a sequence in which each element equals the sum of the two preceding ones. Such a sequence is called the Fibonacci sequence: 1, 1, 2, 3, 5, 8…
Problems like this often show up at various olympiads, and at first glance it seems they can be solved with simple brute force. But if we count the number of possible cases, we immediately see how inefficient this approach is: for example, the simple recursive function below will already consume significant resources by the 30th Fibonacci number, whereas at olympiads the time limit is often 1-5 seconds.
int fibo(int n)
{
if (n == 1 || n == 2) {
return 1;
} else {
return fibo(n - 1) + fibo(n - 2);
}
}
Figure out how to find the N-th Fibonacci number in a reasonable amount of time.
Answer
To get a better grasp of the topic, we recommend reading our article on dynamic programming for beginners.
One of the most famous problems on the Internet, one that has troubled many brilliant minds of humanity.
A plane is standing on a runway with a moving surface, like a conveyor belt. The surface can move against the direction of the plane's takeoff, that is, toward it. The conveyor automatically adjusts its speed so that the plane remains stationary. Question: can the plane take off under these conditions?
A small caveat
It should be noted here that on closer inspection the problem statement turns out to be incorrect. First, the landing gear rotates with angular velocity, while the belt moves with linear velocity, so comparing them is not correct. Second, if we assume that the angular velocity of the conveyor's wheels equals the angular velocity of the plane's wheels and their diameters are equal, then the problem reduces to a plane that is stationary relative to the ground. But let's proceed from the assumption that the conveyor simply moves so as to prevent the plane riding on it from moving relative to the ground. Of course, from a physics standpoint the problem is not entirely correct for other reasons too, but one can try to solve it empirically.
Answer
A problem about function overloading in C++ that may turn out to be harder than it looks.
Suppose we have two classes:
class Parent {
public:
virtual void print() {
std::cout << "Parent class" << std::endl;
}
};
class Derived : public Parent {
public:
virtual void print(int x) {
std::cout << "Derived class" << std::endl;
}
};
What will the following two pieces of code print, and why?
int main() {
Derived *derived = new Derived;
derived -> print();
return 0;
}
int main() {
Parent *derived = new Derived;
derived -> print();
return 0;
}
Answer
Consider a situation where three employees want to compute their average salary, given that each knows their own salary but cannot tell it to the others directly. Exchanging information between the people is allowed, but the messages they pass to each other must not contain any specific information about salary levels. How can this be done?
Answer
Suppose we have an array of positive numbers in which every number except three occurs twice, while those three numbers differ from all the rest and each occurs exactly once. You need to find these three numbers. The numbers fit into a 32-bit integer type.
Answer
Suppose we have some finite sequence of numbers and we have an iterator pointing to the first element. Using the iterator we can look at the value of the current element and move to the next element. You need to build an algorithm for choosing a random element from this sequence such that every element has an equal probability of being chosen.
Constraints: we can use O(1) additional memory and cannot create a new iterator. You may use a function that generates a random number in [0;1).
Answer
A well-known IT interview problem with several possible solutions: how do you correctly swap the values of two variables?
An incorrect implementation
a = b; b = a;
If you try to swap values this way, you will see that both variables now hold the value of variable b. This happens because the code executes line by line. The first assignment stores the value of variable b into variable a. Then the second one stores the new value of a into b, in other words the value of b into b. Thus, we completely lose the contents of container a.
Answer
On one side of a river there are three people and three lions. They all need to end up on the other bank of the river. There is only one boat, which can hold only two living creatures at a time (a person or a lion). You cannot leave more lions than people on either bank of the river, because in that case the animals will eat the people left in the minority. How do you get everyone across the river?
Answer
If you were given a stack of one-penny coins as tall as the Empire State Building, would all that money fit in a single room?
At first it may seem like one of those puzzles where you're supposed to estimate some absurd number. But that's actually not the case — think it over carefully.
Comments