Issue # 25: IT training - current issues and challenges from leading companies

    Today we have prepared the latest release of IT training in the current format.
    KDPV
    We picked up tasks for you from interviews at Cisco. They ask questions not only about routing and hardware (there are such questions in the collection), but also logical tasks. The most interesting of them are waiting for you under the cut.

    It should be noted also that this release will be the last in this format, but will be continued in a modified form. We decided to change the format and platform for future releases of the training - the sequel will be in Typical Programmer.

    Questions


    1. Magnet, Magnetic and Nonmagnetic
      How can you differentiate between a magnet, magnetic material and nonmagnetic material?

      Transfer
      How to distinguish a magnet, a magnetic material and a non-magnet? ( approx. Question on iron in an unexpected perspective. Requires some knowledge of physics )
    2. Viral infection
      The world is facing a serious viral infection. Various countries have issued each citizen two bottles. You as well have been given the same. It’s a problem to get rid of it. If you are taking a bottle of water, you’re going to die.

      Pour it in your hand. Three tablets come out the same and have the same characteristics. You can’t get away from it. How would you solve this problem?

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

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

      (прим. Похожая задача уже была в ранних выпусках.)

    Tasks


    1. Sort elements by frequency
      Print the elements of the decreasing frequency. If 2 numbers have the same frequency then print

      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}

      Transfer
      Выведите элементы массива в порядке убывания по частоте вхождения. Если два числа имеют одинаковую частоту — выводить первым то, что встречается первым.

      Примеры:

      Вход: 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.

      • The left subtree of the node contains no keys.
      • The node contains no keys.
      • Both the left and right subtrees must also be binary search trees.

      From each above properties it naturally follows that:
      • Each node (item in the tree) has a distinct key.

                           four
                        / \
                      2 5
                    / \
                  13
      

      If your binary tree is BST or not.

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

      Из описанного следует, что каждый узел в дереве содержит уникальный ключ.

                           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. 1 liter of water. You can throw it at any time. Assume that 'a' and 'b' are Coprimes.

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

    Answers will be given within the next week - have time to decide. Good luck!

    Solutions


    1. Question 1
      andyudol предложил решение.

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

    3. Task 1
      Исходный вариант решения:
      #include<bits/stdc++.h>usingnamespacestd;
      // Used for sortingstructele
      {int count, index, val;
      };
      // Used for sorting by valueboolmycomp(struct ele a, struct ele b){
          return (a.val < b.val);
      }
      // Used for sorting by frequency. And if frequency is same,// then by appearanceboolmycomp2(struct ele a, struct ele b){
          if (a.count != b.count) return (a.count < b.count);
          elsereturn a.index > b.index;
      }
      voidsortByFrequency(int arr[], int n){
          structeleelement[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 programintmain(){
          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] << " ";
          return0;
      }


    4. Task 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*/classNode{
          int data;
          Node left, right;
          publicNode(int item){
              data = item;
              left = right = null;
          }
      }
      publicclassBinaryTree{
          //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) */booleanisBST(){
              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. */booleanisBSTUtil(Node node, int min, int max){
              /* an empty tree is BST */if (node == null)
                  returntrue;
              /* false if this node violates the min/max constraints */if (node.data < min || node.data > max)
                  returnfalse;
              /* otherwise check the subtrees recursively
              tightening the min/max constraints */// Allow only distinct valuesreturn (isBSTUtil(node.left, min, node.data-1) &&
                      isBSTUtil(node.right, node.data+1, max));
          }
          /* Driver program to test above functions */publicstaticvoidmain(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. Task 3
      Вариант решения:
      #include<iostream>usingnamespacestd;
      // A utility function to get GCD of two numbersintgcd(int a, int b){ return b? gcd(b, a % b) : a; }
      // Class to represent a VesselclassVessel
      {// A vessel has capacity, and current amount of water in itint 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-primevoidmakeOneLitre(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.inttransfer(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 coprimevoid Vessel:: makeOneLitre(Vessel &V2)
      {
          // solution exists iff a and b are co-primeif (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 1cout << "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 emptyint Vessel::transfer(int amount)
      {
          // If the vessel can accommodate the given amountif (current + amount < capacity)
          {
              current += amount;
              return amount;
          }
          // If the vessel cannot accommodate the given amount, then// store the amount of water transferredint 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 functionintmain(){
          int a = 3, b = 7;  // a must be smaller than b// Create two vessels of capacities a and bVessel V1(a), V2(b);
          // Get 1 litre in first vessel
          V1.makeOneLitre(V2);
          return0;
      }
      



    Also popular now: