Numéro 25: Formation informatique - problèmes et défis actuels des grandes entreprises

Des questions

1. Aimant, magnétique et non magnétique
   

   Comment différencier un aimant, un matériau magnétique et un matériau non magnétique?

   
   
   La traduction

   Comment distinguer aimant, matériau magnétique et non aimant? ( environ. Question sur le fer dans une perspective inattendue. Nécessite une certaine connaissance de la physique )
   
2. Infection virale
   

   Le monde est confronté à une grave infection virale. Le gouvernement de divers pays a délivré à chaque citoyen deux bouteilles. Vous avez également reçu la même chose. Maintenant, un comprimé de chaque bouteille doit être pris chaque jour pendant un mois pour devenir immunisé contre le virus. Le problème est que si vous n'en prenez qu'un ou si vous en prenez deux dans la même bouteille, vous mourrez d'une mort douloureuse.
   
   En l'utilisant, vous ouvrez les bouteilles à la hâte et versez les comprimés dans votre main. Trois comprimés tombent dans votre main et vous vous rendez compte qu'ils se ressemblent exactement et ont les mêmes caractéristiques. Vous ne pouvez pas jeter la pilule car elle est limitée et vous ne pouvez pas la remettre ou vous pouvez la mal faire et peut mourir un jour. Comment résoudriez-vous ce problème?

   
   
   La traduction

   Le monde est confronté à une terrible infection virale. Les gouvernements de tous les pays donnent à chaque citoyen deux bouteilles de médicaments. On vous a donné le même kit. Vous devez prendre un comprimé de chaque bouteille par jour pendant un mois afin de bénéficier d'une immunité contre le virus. Si vous ne prenez qu'une ou deux pilules dans la même bouteille, une mort douloureuse s'ensuivra.
   
   En prenant une autre portion de comprimés, vous ouvrez les deux flacons et versez rapidement les comprimés dans votre paume. Tard, mais vous comprenez que trois pilules se sont répandues, ainsi que le fait qu'elles se ressemblent exactement. La tablette ne peut pas être jetée, car leur quantité est limitée, et vous ne pouvez pas la remettre, sinon, en cas d'erreur, vous mourrez un jour. Comment résoudriez-vous ce problème?
   
   ( Remarque Une tâche similaire figurait déjà dans les versions antérieures. )
   

Les tâches

1. Trier les éléments par fréquence
   

   Imprime les éléments d'un tableau dans la fréquence décroissante. Si 2 nombres ont la même fréquence, imprimez celui qui est arrivé en premier.
   
   Exemples:
   
   Entrée: arr [] = {2, 5, 2, 8, 5, 6, 8, 8}
   Sortie: arr [] = {8, 8, 8, 2, 2, 5, 5, 6}
   
   Entrée: arr [] = {2, 5, 2, 6, -1, 9999999, 5, 8, 8, 8}
   Sortie: arr [] = {8, 8, 8, 2, 2, 5, 5, 6, -1, 9999999}
   

   
   
   La traduction

   Imprime les éléments du tableau par ordre décroissant de fréquence d'occurrence. Si deux nombres ont la même fréquence, émettez d'abord ce qui se produit en premier.
   
   Exemples:
   
   Entrée: arr [] = {2, 5, 2, 8, 5, 6, 8, 8}
   Sortie: arr [] = {8, 8, 8, 2, 2, 5, 5, 6}
   
   Entrée: arr [] = {2, 5, 2, 6, -1, 9999999, 5, 8, 8, 8}
   Sortie: arr [] = {8, 8, 8, 2, 2, 5, 5, 6, -1, 9999999}
2. Vérifiez bst
   

   Un arbre de recherche binaire (BST) est une structure de données d'arbre binaire basée sur un nœud qui a les propriétés suivantes.
   
   • La sous-arborescence gauche d'un nœud ne contient que des nœuds avec des clés inférieures à la clé du nœud.
   • Le sous-arbre droit d'un nœud ne contient que des nœuds avec des clés supérieures à la clé du nœud.
   • Les sous-arborescences gauche et droite doivent également être des arbres de recherche binaires.
   
   Des propriétés ci-dessus, il résulte naturellement que:
   • Chaque nœud (élément dans l'arborescence) a une clé distincte.
   
   

                         4
                      / \
                    2 5
                  / \
                1 3
   

   
   Votre tâche consiste à créer un programme pour vérifier si un arbre binaire est BST ou non.
   

   
   
   La traduction

   Étant donné un arbre de recherche binaire qui a les propriétés suivantes:
   * Le sous-arbre gauche de chaque nœud contient des nombres inférieurs à la valeur de ce nœud.
   * Le sous-arbre droit de chaque nœud contient des nombres supérieurs à la valeur de ce nœud.
   * Les sous-arbres gauche et droit sont des arbres de recherche binaires.
   
   D'après ce qui est décrit, il s'ensuit que chaque nœud de l'arborescence contient une clé unique.
   
   

                         4
                      / \
                    2 5
                  / \
                1 3
   

   
   Votre tâche consiste à écrire un programme pour vérifier si l'arbre est un arbre de recherche binaire ou non.
3. Litre, eau et 2 vases à coprime à smocks
   

   Il existe deux navires de capacités «a» et «b» respectivement. Nous avons un approvisionnement en eau infini. Donnez un algorithme efficace pour faire exactement 1 litre d'eau dans l'un des récipients. Vous pouvez jeter toute l'eau de n'importe quel navire à tout moment. Supposons que «a» et «b» soient des coprimes.

   
   
   La traduction

   Compte tenu de 2 navires avec une capacité de «a» et «b» et une source infinie d'eau. Suggérer un algorithme efficace pour mesurer exactement 1 litre d'eau à l'aide de ces récipients. Vous pouvez verser toute l'eau de n'importe quel récipient à tout moment. Nous supposons également que «a» et «b» sont des coprimes .
   

Des solutions

1. Question 1

   andyudol a proposé une solution .
   
   
   
2. Question 2

   Dans les commentaires, ils ont suggéré la bonne solution - ici et ici - ainsi que quelques options.
   
   
   
3. Tâche 1

   Solution initiale:
   

   #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. Tâche 2

   Solution 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. Tâche 3

   Option de solution:
   

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