Вопросы

1. Magnet, Magnetic and Nonmagnetic
   

   How can you differentiate among a magnet, magnetic material and nonmagnetic material?

   
   
   Перевод

   Как отличить магнит, магнитный материал и немагнит? (прим. Вопрос по железу в неожиданном ракурсе. Требует некоторых знаний физики)
   
2. Viral infection
   

   The world is facing a serious viral infection. The government of various countries have issued every citizen two bottles. You as well have been given the same. Now one pill from each bottle is to be taken every day for a month to become immune to the virus. The problem is that if you take just one, or if you take two from the same bottle, you will die a painful death.
   
   While using it, you hurriedly open the bottles and pour the tablets in your hand. Three tablets come down in your hand and you realize they look exactly the same and have same characteristics. You can’t throw away the pill as they are limited and you can’t put them back or you may put it wrong and may die someday. How would you solve this problem?

   
   
   Перевод

   Мир столкнулся со страшной вирусной инфекцией. Правительства всех стран выдают каждому гражданину две бутылочки с лекарством. Вам выдали такой же комплект. Нужно принимать по одной таблетке из каждой бутылки ежедневно в течении месяца, чтобы приобрести иммунитет к вирусу. Если же принять только одну таблетку или две из одной бутылки — наступит мучительная смерть.
   
   Принимая очередную порцию таблеток, Вы открываете обе бутыли и поспешно высыпаете таблетки в ладонь. Поздно, но Вы понимаете, что высыпалось три таблетки, а также то, что они выглядят абсолютно одинаково. Таблетку выбросить нельзя, поскольку их количество ограничено, и Вы не можете положить их обратно, иначе, в случае ошибки, Вы когда-нибудь умрете. Как бы Вы решили эту проблему?
   
   (прим. Похожая задача уже была в ранних выпусках.)
   

Задачи

1. Sort elements by frequency
   

   Print the elements of an array in the decreasing frequency. If 2 numbers have same frequency then print the one which came first.
   
   Examples:
   
   Input: arr[] = {2, 5, 2, 8, 5, 6, 8, 8}
   Output: arr[] = {8, 8, 8, 2, 2, 5, 5, 6}
   
   Input: arr[] = {2, 5, 2, 6, -1, 9999999, 5, 8, 8, 8}
   Output: arr[] = {8, 8, 8, 2, 2, 5, 5, 6, -1, 9999999}
   

   
   
   Перевод

   Выведите элементы массива в порядке убывания по частоте вхождения. Если два числа имеют одинаковую частоту — выводить первым то, что встречается первым.
   
   Примеры:
   
   Вход: arr[] = {2, 5, 2, 8, 5, 6, 8, 8}
   Выход: arr[] = {8, 8, 8, 2, 2, 5, 5, 6}
   
   Вход: arr[] = {2, 5, 2, 6, -1, 9999999, 5, 8, 8, 8}
   Выход: arr[] = {8, 8, 8, 2, 2, 5, 5, 6, -1, 9999999}
2. Check BST
   

   A binary search tree (BST) is a node based binary tree data structure which has the following properties.
   
   • The left subtree of a node contains only nodes with keys less than the node’s key.
   • The right subtree of a node contains only nodes with keys greater than the node’s key.
   • Both the left and right subtrees must also be binary search trees.
   
   From the above properties it naturally follows that:
   • Each node (item in the tree) has a distinct key.
   
   

                        4
                     /                     2        5
                 /                1       3
   

   
   Your task is to create a program to check if a binary tree is BST or not.
   

   
   
   Перевод

   Дано двоичное дерево поиска, которое имеет следующие свойства:
   * Левое поддерево для каждого узла содержит числа меньше значения данного узла.
   * Правое поддерево для каждого узла содержит числа больше значения данного узла.
   * И левое и правое поддеревья являются двоичными деревьями поиска.
   
   Из описанного следует, что каждый узел в дереве содержит уникальный ключ.
   
   

                        4
                     /                     2        5
                 /                1       3
   

   
   Ваша задача — написать программу для проверки, является ли дерево двоичным деревом поиска или нет.
3. Liter, water and 2 smocking «coprime» vessels
   

   There are two vessels of capacities ‘a’ and ‘b’ respectively. We have infinite water supply. Give an efficient algorithm to make exactly 1 litre of water in one of the vessels. You can throw all the water from any vessel any point of time. Assume that ‘a’ and ‘b’ are Coprimes.

   
   
   Перевод

   Даны 2 сосуда емкостью 'a' и 'b' и бесконечный источник воды. Предложите эффективный алгоритм для отмера ровно 1 литра воды с помощью этих сосудов. Вы можете вылить всю воду из любого сосуда в любой момент времени. Примем также, что 'a' и 'b' взаимно простые числа.