Número 25: capacitación en TI: problemas y desafíos actuales de las principales empresas

Preguntas

1. Imán, magnético y no magnético
   

   ¿Cómo puede diferenciar entre un imán, material magnético y material no magnético?

   
   
   Traducción

   ¿Cómo distinguir imán, material magnético y no imán? ( aprox. Pregunta sobre el hierro en una perspectiva inesperada. Requiere algunos conocimientos de física )
   
2. Infección viral
   

   El mundo se enfrenta a una infección viral grave. El gobierno de varios países ha emitido a cada ciudadano dos botellas. A ti también se te ha dado lo mismo. Ahora se debe tomar una píldora de cada botella todos los días durante un mes para volverse inmune al virus. El problema es que si toma solo uno, o si toma dos de la misma botella, morirá una muerte dolorosa.
   
   Mientras lo usa, abre apresuradamente las botellas y vierte las tabletas en su mano. Tres tabletas caen en tu mano y te das cuenta de que se ven exactamente iguales y tienen las mismas características. No puede tirar la píldora, ya que son limitadas y no puede volver a colocarla o puede equivocarse y morir algún día. ¿Cómo resolverías este problema?

   
   
   Traducción

   El mundo se enfrenta a una terrible infección viral. Los gobiernos de todos los países dan a cada ciudadano dos botellas de medicina. Te dieron el mismo kit. Debe tomar una tableta de cada botella diariamente durante un mes para obtener inmunidad al virus. Si toma solo una o dos pastillas de la misma botella, se producirá una muerte dolorosa.
   
   Tomando otra porción de tabletas, abres ambas botellas y rápidamente viertes las tabletas en tu palma. Tarde, pero entiendes que se derramaron tres píldoras, así como el hecho de que se ven exactamente iguales. La tableta no se puede tirar, porque su cantidad es limitada y no puede volver a colocarla, de lo contrario, en caso de error, algún día morirá. ¿Cómo resolverías este problema?
   
   ( Nota: una tarea similar ya estaba en versiones anteriores ) .
   

Las tareas

1. Ordenar elementos por frecuencia
   

   Imprima los elementos de una matriz en la frecuencia decreciente. Si 2 números tienen la misma frecuencia, imprima el primero.
   
   Ejemplos:
   
   Entrada: arr [] = {2, 5, 2, 8, 5, 6, 8, 8}
   Salida: arr [] = {8, 8, 8, 2, 2, 5, 5, 6}
   
   Entrada: arr [] = {2, 5, 2, 6, -1, 9999999, 5, 8, 8, 8}
   Salida: arr [] = {8, 8, 8, 2, 2, 5, 5, 6, -1, 9999999}
   

   
   
   Traducción

   Imprima los elementos de la matriz en orden descendente de frecuencia de ocurrencia. Si dos números tienen la misma frecuencia, salida primero lo que ocurre primero.
   
   Ejemplos:
   
   Entrada: arr [] = {2, 5, 2, 8, 5, 6, 8, 8}
   Salida: arr [] = {8, 8, 8, 2, 2, 5, 5, 6}
   
   Entrada: arr [] = {2, 5, 2, 6, -1, 9999999, 5, 8, 8, 8}
   Salida: arr [] = {8, 8, 8, 2, 2, 5, 5, 6, -1, 9999999}
2. Comprobar bst
   

   Un árbol de búsqueda binaria (BST) es una estructura de datos de árbol binario basada en nodos que tiene las siguientes propiedades.
   
   • El subárbol izquierdo de un nodo contiene solo nodos con claves menores que la clave del nodo.
   • El subárbol derecho de un nodo contiene solo nodos con claves mayores que la clave del nodo.
   • Tanto el subárbol izquierdo como el derecho también deben ser árboles de búsqueda binarios.
   
   De las propiedades anteriores se deduce naturalmente que:
   • Cada nodo (elemento en el árbol) tiene una clave distinta.
   
   

                         4 4
                      / \
                    2 5
                  / \
                1 3
   

   
   Su tarea es crear un programa para verificar si un árbol binario es BST o no.
   

   
   
   Traducción

   Dado un árbol de búsqueda binario que tiene las siguientes propiedades:
   * El subárbol izquierdo para cada nodo contiene números menores que el valor de este nodo.
   * El subárbol correcto para cada nodo contiene números mayores que el valor de este nodo.
   * Tanto el subárbol izquierdo como el derecho son árboles de búsqueda binarios.
   
   De lo descrito se deduce que cada nodo en el árbol contiene una clave única.
   
   

                         4 4
                      / \
                    2 5
                  / \
                1 3
   

   
   Su tarea es escribir un programa para verificar si el árbol es un árbol de búsqueda binario o no.
3. Litro, agua y 2 recipientes "coprime" de ahumado
   

   Hay dos recipientes de capacidades 'a' y 'b' respectivamente. Tenemos suministro de agua infinito. Dé un algoritmo eficiente para hacer exactamente 1 litro de agua en uno de los recipientes. Puede tirar toda el agua desde cualquier embarcación en cualquier momento. Suponga que 'a' y 'b' son Coprimes.

   
   
   Traducción

   Dados 2 recipientes con una capacidad de 'a' y 'b' y una fuente infinita de agua. Sugiera un algoritmo efectivo para medir exactamente 1 litro de agua usando estos recipientes. Puede verter toda el agua de cualquier recipiente en cualquier momento. También asumimos que 'a' y 'b' son coprimos .
   

Soluciones

1. Pregunta 1

   andyudol propuso una solución .
   
   
   
2. Pregunta 2

   En los comentarios, sugirieron la solución correcta, aquí y aquí , también algunas opciones.
   
   
   
3. Tarea 1

   Solución inicial:
   

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

   Solución 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. Tarea 3

   Opción de solución:
   

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