Problem Nr. 25: IT-Schulung - aktuelle Probleme und Herausforderungen führender Unternehmen

Fragen

1. Magnet, magnetisch und nicht magnetisch
   

   Wie kann man zwischen einem Magneten, einem magnetischen Material und einem nichtmagnetischen Material unterscheiden?

   
   
   Übersetzung

   Wie unterscheidet man Magnet, magnetisches Material und Nichtmagnet? ( ca. Frage zu Eisen in einer unerwarteten Perspektive. Erfordert einige Kenntnisse der Physik )
   
2. Virusinfektion
   

   Die Welt ist mit einer schweren Virusinfektion konfrontiert. Die Regierung verschiedener Länder hat jedem Bürger zwei Flaschen ausgegeben. Ihnen wurde auch das gleiche gegeben. Jetzt soll einen Monat lang jeden Tag eine Pille aus jeder Flasche eingenommen werden, um gegen das Virus immun zu werden. Das Problem ist, dass Sie einen schmerzhaften Tod sterben, wenn Sie nur eine oder zwei aus derselben Flasche nehmen.
   
   Während Sie es benutzen, öffnen Sie schnell die Flaschen und gießen die Tabletten in Ihre Hand. Drei Tabletten liegen in Ihrer Hand und Sie stellen fest, dass sie genau gleich aussehen und dieselben Eigenschaften haben. Sie können die Pille nicht wegwerfen, da sie begrenzt ist und Sie sie nicht zurücklegen können, oder Sie können sie falsch setzen und eines Tages sterben. Wie würden Sie dieses Problem lösen?

   
   
   Übersetzung

   Die Welt ist mit einer schrecklichen Virusinfektion konfrontiert. Die Regierungen aller Länder geben jedem Bürger zwei Flaschen Medizin. Sie erhielten das gleiche Kit. Sie müssen einen Monat lang täglich eine Tablette aus jeder Flasche einnehmen, um Immunität gegen das Virus zu erlangen. Wenn Sie nur eine oder zwei Tabletten aus derselben Flasche einnehmen, kommt es zu einem schmerzhaften Tod.
   
   Nehmen Sie eine weitere Portion Tabletten, öffnen Sie beide Flaschen und gießen Sie die Tabletten hastig in Ihre Handfläche. Spät, aber Sie verstehen, dass drei Pillen verschüttet wurden und dass sie genau gleich aussehen. Das Tablet kann nicht weggeworfen werden, da die Menge begrenzt ist und Sie es nicht zurücklegen können. Andernfalls sterben Sie eines Tages im Fehlerfall. Wie würden Sie dieses Problem lösen?
   
   ( Hinweis Eine ähnliche Aufgabe gab es bereits in früheren Versionen. )
   

Die Aufgaben

1. Elemente nach Häufigkeit sortieren
   

   Drucken Sie die Elemente eines Arrays in abnehmender Häufigkeit. Wenn 2 Zahlen dieselbe Frequenz haben, drucken Sie die zuerst kommende.
   
   Beispiele:
   
   Eingabe: arr [] = {2, 5, 2, 8, 5, 6, 8, 8}
   Ausgabe: arr [] = {8, 8, 8, 2, 2, 5, 5, 6}
   
   Eingabe: arr [] = {2, 5, 2, 6, -1, 9999999, 5, 8, 8, 8}
   Ausgabe: arr [] = {8, 8, 8, 2, 2, 5, 5, 6, -1, 9999999}
   

   
   
   Übersetzung

   Drucken Sie die Elemente des Arrays in absteigender Reihenfolge der Häufigkeit des Auftretens. Wenn zwei Zahlen die gleiche Frequenz haben - geben Sie zuerst aus, was zuerst auftritt.
   
   Beispiele:
   
   Eingabe: arr [] = {2, 5, 2, 8, 5, 6, 8, 8}
   Ausgabe: arr [] = {8, 8, 8, 2, 2, 5, 5, 6}
   
   Eingabe: arr [] = {2, 5, 2, 6, -1, 9999999, 5, 8, 8, 8}
   Ausgabe: arr [] = {8, 8, 8, 2, 2, 5, 5, 6, -1, 9999999}
2. Überprüfen Sie bst
   

   Ein binärer Suchbaum (BST) ist eine knotenbasierte binäre Baumdatenstruktur mit den folgenden Eigenschaften.
   
   • Der linke Teilbaum eines Knotens enthält nur Knoten mit Schlüsseln, die kleiner als der Schlüssel des Knotens sind.
   • Der rechte Teilbaum eines Knotens enthält nur Knoten mit Schlüsseln, die größer als der Schlüssel des Knotens sind.
   • Sowohl der linke als auch der rechte Teilbaum müssen binäre Suchbäume sein.
   
   Aus den obigen Eigenschaften folgt natürlich Folgendes:
   • Jeder Knoten (Element im Baum) hat einen eigenen Schlüssel.
   
   

                         4
                      / \.
                    2 5
                  / \.
                1 3
   

   
   Ihre Aufgabe ist es, ein Programm zu erstellen, um zu überprüfen, ob ein Binärbaum BST ist oder nicht.
   

   
   
   Übersetzung

   Gegeben ein binärer Suchbaum , der die folgenden Eigenschaften hat:
   * Der linke Teilbaum für jeden Knoten enthält Zahlen, die kleiner als der Wert dieses Knotens sind.
   * Der rechte Teilbaum für jeden Knoten enthält Zahlen, die größer als der Wert dieses Knotens sind.
   * Sowohl der linke als auch der rechte Teilbaum sind binäre Suchbäume.
   
   Aus dem Beschriebenen folgt, dass jeder Knoten im Baum einen eindeutigen Schlüssel enthält.
   
   

                         4
                      / \.
                    2 5
                  / \.
                1 3
   

   
   Ihre Aufgabe ist es, ein Programm zu schreiben, um zu überprüfen, ob der Baum ein binärer Suchbaum ist oder nicht.
3. Liter, Wasser und 2 rauchende "Koprime" Gefäße
   

   Es gibt zwei Gefäße mit den Kapazitäten 'a' und 'b'. Wir haben unendliche Wasserversorgung. Geben Sie einen effizienten Algorithmus an, um genau 1 Liter Wasser in einem der Gefäße herzustellen. Sie können jederzeit das gesamte Wasser aus jedem Schiff werfen. Angenommen, 'a' und 'b' sind Coprimes.

   
   
   Übersetzung

   Gegeben 2 Schiffe mit einer Kapazität von 'a' und 'b' und einer endlosen Wasserquelle. Schlagen Sie einen effektiven Algorithmus zur Messung von genau 1 Liter Wasser mit diesen Gefäßen vor. Sie können jederzeit das gesamte Wasser aus jedem Gefäß einfüllen. Wir nehmen auch an, dass 'a' und 'b' Koprime sind .
   

Lösungen

1. Frage 1

   Andyudol schlug eine Lösung vor .
   
   
   
2. Frage 2

   In den Kommentaren schlugen sie die richtige Lösung vor - hier und hier - auch einige Optionen.
   
   
   
3. Aufgabe 1

   Erste Lösung:
   

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

   Java-Lösung:
   

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

   Lösungsoption:
   

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