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

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

   The world is faced with a terrible viral infection. Governments of all countries give each citizen two bottles of medicine. You have been given the same kit. It is necessary to take one tablet from each bottle daily for a month to acquire immunity to the virus. If you take only one pill or two from one bottle - painful death will come.
   
   Taking the next portion of pills, you open both bottles and quickly pour the pills into the palm of your hand. It's late, but you realize that three pills have gone enough, and also that they look exactly the same. The tablet cannot be thrown away, because their number is limited, and you cannot put them back, otherwise, in case of an error, you will ever die. How would you solve this problem?
   
   ( note. A similar problem was already in the early releases. )
   

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

   Output the array elements in descending order by frequency of occurrence. If two numbers have the same frequency, output first what occurs 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}
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 the 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

   Given a binary search tree , which has the following properties:
   * The left subtree for each node contains numbers less than the value of this node.
   * The right subtree for each node contains numbers greater than the value of this node.
   * Both left and right subtrees are binary search trees.
   
   From the above it follows that each node in the tree contains a unique key.
   
   

                         four
                      / \
                    2 5
                  / \
                13
   

   
   Your task is to write a program to check whether the tree is a binary search tree or not.
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

   Given 2 vessels with a capacity of 'a' and 'b' and an endless source of water. Suggest an efficient algorithm for measuring exactly 1 liter of water using these vessels. You can pour all the water from any vessel at any time. We also assume that 'a' and 'b' are mutually simple numbers .
   

Solutions

1. Question 1

   andyudol proposed a solution .
   
   
   
2. Question 2

   The comments offered the right solution - here , and here - also several options.
   
   
   
3. Task 1

   Initial solution:
   

   #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. Task 2

   Java solution:
   

    /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. Task 3

   Solution option:
   

    #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; }