Выпуск#25: ITренировка — актуальные вопросы и задачи от ведущих компаний

Вопросы

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' взаимно простые числа.
   

Решения

1. Вопрос 1

   andyudol предложил решение.
   
   
   
2. Вопрос 2

   В комментариях предложили верное решение — тут, а тут — еще и несколько вариантов.
   
   
   
3. Задача 1

   Исходный вариант решения:
   

   #include<bits/stdc++.h>
   using namespace std;
    
   // Used for sorting
   struct ele
   {
       int count, index, val;
   };
    
   // Used for sorting by value
   bool mycomp(struct ele a, struct ele b) {
       return (a.val < b.val);
   }
    
   // Used for sorting by frequency. And if frequency is same,
   // then by appearance
   bool mycomp2(struct ele a, struct ele b) {
       if (a.count != b.count) return (a.count < b.count);
       else return a.index > b.index;
   }
    
   void sortByFrequency(int arr[], int n)
   {
       struct ele element[n];
       for (int i = 0; i < n; i++)
       {
           element[i].index = i;    /* Fill Indexes */
           element[i].count = 0;    /* Initialize counts as 0 */
           element[i].val = arr[i]; /* Fill values in structure
                                        elements */
       }
    
       /* Sort the structure elements according to value,
          we used stable sort so relative order is maintained. */
       stable_sort(element, element+n, mycomp);
    
       /* initialize count of first element as 1 */
       element[0].count = 1;
    
       /* Count occurrences of remaining elements */
       for (int i = 1; i < n; i++)
       {
           if (element[i].val == element[i-1].val)
           {
               element[i].count += element[i-1].count+1;
    
               /* Set count of previous element as -1 , we are
                  doing this because we'll again sort on the
                  basis of counts (if counts are equal than on
                  the basis of index)*/
               element[i-1].count = -1;
    
               /* Retain the first index (Remember first index
                  is always present in the first duplicate we
                  used stable sort. */
               element[i].index = element[i-1].index;
           }
    
           /* Else If previous element is not equal to current
             so set the count to 1 */
           else element[i].count = 1;
       }
    
       /* Now we have counts and first index for each element so now
          sort on the basis of count and in case of tie use index
          to sort.*/
       stable_sort(element, element+n, mycomp2);
       for (int i = n-1, index=0; i >= 0; i--)
           if (element[i].count != -1)
              for (int j=0; j<element[i].count; j++)
                   arr[index++] = element[i].val;
   }
    
   // Driver program
   int main()
   {
       int arr[] = {2, 5, 2, 6, -1, 9999999, 5, 8, 8, 8};
       int n = sizeof(arr)/sizeof(arr[0]);
    
       sortByFrequency(arr, n);
    
       for (int i=0; i<n; i++)
          cout << arr[i] << " ";
       return 0;
   }

   
   
   
   
4. Задача 2

   Решение на Java:
   

   /Java implementation to check if given Binary tree
   //is a BST or not
    
   /* Class containing left and right child of current
    node and key value*/
   class Node
   {
       int data;
       Node left, right;
    
       public Node(int item)
       {
           data = item;
           left = right = null;
       }
   }
    
   public class BinaryTree
   {
       //Root of the Binary Tree
       Node root;
    
       /* can give min and max value according to your code or
       can write a function to find min and max value of tree. */
    
       /* returns true if given search tree is binary
        search tree (efficient version) */
       boolean isBST()  {
           return isBSTUtil(root, Integer.MIN_VALUE,
                                  Integer.MAX_VALUE);
       }
    
       /* Returns true if the given tree is a BST and its
         values are >= min and <= max. */
       boolean isBSTUtil(Node node, int min, int max)
       {
           /* an empty tree is BST */
           if (node == null)
               return true;
    
           /* false if this node violates the min/max constraints */
           if (node.data < min || node.data > max)
               return false;
    
           /* otherwise check the subtrees recursively
           tightening the min/max constraints */
           // Allow only distinct values
           return (isBSTUtil(node.left, min, node.data-1) &&
                   isBSTUtil(node.right, node.data+1, max));
       }
    
       /* Driver program to test above functions */
       public static void main(String args[])
       {
           BinaryTree tree = new BinaryTree();
           tree.root = new Node(4);
           tree.root.left = new Node(2);
           tree.root.right = new Node(5);
           tree.root.left.left = new Node(1);
           tree.root.left.right = new Node(3);
    
           if (tree.isBST())
               System.out.println("IS BST");
           else
               System.out.println("Not a BST");
       }
   }
   

   
   
   
   
5. Задача 3

   Вариант решения:
   

   
   #include <iostream>
   using namespace std;
    
   // A utility function to get GCD of two numbers
   int gcd(int a, int b) { return b? gcd(b, a % b) : a; }
    
   // Class to represent a Vessel
   class Vessel
   {
       // A vessel has capacity, and current amount of water in it
       int capacity, current;
   public:
       // Constructor: initializes capacity as given, and current as 0
       Vessel(int capacity) { this->capacity = capacity; current = 0; }
    
       // The main function to fill one litre in this vessel. Capacity of V2
       // must be greater than this vessel and two capacities must be co-prime
       void makeOneLitre(Vessel &V2);
    
       // Fills vessel with given amount and returns the amount of water 
       // transferred to it. If the vessel becomes full, then the vessel 
       // is made empty.
       int transfer(int amount);
   };
    
   // The main function to fill one litre in this vessel. Capacity 
   // of V2 must be greater than this vessel and two capacities 
   // must be coprime
   void Vessel:: makeOneLitre(Vessel &V2)
   {
       // solution exists iff a and b are co-prime
       if (gcd(capacity, V2.capacity) != 1)
           return;
    
       while (current != 1)
       {
           // fill A (smaller vessel)
           if (current == 0)
               current = capacity;
    
           cout << "Vessel 1: " << current << "   Vessel 2: "
                << V2.current << endl;
    
           // Transfer water from V1 to V2 and reduce current of V1 by
           //  the amount equal to transferred water
           current = current - V2.transfer(current);
       }
    
       // Finally, there will be 1 litre in vessel 1
       cout << "Vessel 1: " << current << "   Vessel 2: "
            << V2.current << endl;
   }
    
   // Fills vessel with given amount and returns the amount of water 
   // transferred to it. If the vessel becomes full, then the vessel 
   // is made empty
   int Vessel::transfer(int amount)
   {
       // If the vessel can accommodate the given amount
       if (current + amount < capacity)
       {
           current += amount;
           return amount;
       }
    
       // If the vessel cannot accommodate the given amount, then
       // store the amount of water transferred
       int transferred = capacity - current;
    
       // Since the vessel becomes full, make the vessel
       // empty so that it can be filled again
       current = 0;
    
       return transferred;
   }
    
   // Driver program to test above function
   int main()
   {
       int a = 3, b = 7;  // a must be smaller than b
    
       // Create two vessels of capacities a and b
       Vessel V1(a), V2(b);
    
       // Get 1 litre in first vessel
       V1.makeOneLitre(V2);
    
       return 0;
   }