Edição 25: treinamento em TI - problemas e desafios atuais das principais empresas

Perguntas

1. Ímã, Magnético e Não Magnético
   

   Como você pode diferenciar entre um ímã, material magnético e material não magnético?

   
   
   Tradução

   Como distinguir ímã, material magnético e não-ímã? ( aprox. Pergunta sobre ferro em uma perspectiva inesperada. Requer algum conhecimento de física )
   
2. Infecção viral
   

   O mundo está enfrentando uma infecção viral séria. O governo de vários países emitiu a cada cidadão duas garrafas. Você também recebeu o mesmo. Agora, um comprimido de cada frasco deve ser tomado todos os dias durante um mês para se tornar imune ao vírus. O problema é que, se você tomar apenas um ou se tomar dois da mesma garrafa, sofrerá uma morte dolorosa.
   
   Enquanto o usa, você abre as garrafas às pressas e despeja os comprimidos na mão. Três comprimidos caem na sua mão e você percebe que eles parecem exatamente iguais e têm as mesmas características. Você não pode jogar fora a pílula porque eles são limitados e não pode devolvê-los ou pode colocá-lo errado e morrer um dia. Como você resolveria esse problema?

   
   
   Tradução

   O mundo está enfrentando uma terrível infecção viral. Os governos de todos os países dão a cada cidadão dois frascos de remédio. Você recebeu o mesmo kit. Você precisa tomar um comprimido de cada frasco diariamente por um mês para ganhar imunidade ao vírus. Se você tomar apenas um comprimido ou dois do mesmo frasco, ocorrerá uma morte dolorosa.
   
   Tomando outra porção de comprimidos, você abre os dois frascos e despeja rapidamente os comprimidos na palma da mão. Tarde, mas você entende que três pílulas foram derramadas, além do fato de que elas parecem exatamente iguais. Você não pode jogar fora a pílula, porque a quantidade deles é limitada e não pode devolvê-las; caso contrário, em caso de erro, um dia você morrerá. Como você resolveria esse problema?
   
   ( Nota: uma tarefa semelhante já estava em versões anteriores. )
   

As tarefas

1. Classificar elementos por frequência
   

   Imprima os elementos de uma matriz na frequência decrescente. Se 2 números tiverem a mesma frequência, imprima o que veio primeiro.
   
   Exemplos:
   
   Entrada: arr [] = {2, 5, 2, 8, 5, 6, 8, 8}
   Saída: arr [] = {8, 8, 8, 2, 2, 5, 5, 6}
   
   Entrada: arr [] = {2, 5, 2, 6, -1, 9999999, 5, 8, 8, 8}
   Saída: arr [] = {8, 8, 8, 2, 2, 5, 5, 6, -1, 9999999}
   

   
   
   Tradução

   Imprima os elementos da matriz em ordem decrescente da frequência de ocorrência. Se dois números tiverem a mesma frequência - emita primeiro o que ocorre primeiro.
   
   Exemplos:
   
   Entrada: arr [] = {2, 5, 2, 8, 5, 6, 8, 8}
   Saída: arr [] = {8, 8, 8, 2, 2, 5, 5, 6}
   
   Entrada: arr [] = {2, 5, 2, 6, -1, 9999999, 5, 8, 8, 8}
   Saída: arr [] = {8, 8, 8, 2, 2, 5, 5, 6, -1, 9999999}
2. Verifique bst
   

   Uma árvore de pesquisa binária (BST) é uma estrutura de dados de árvore binária baseada em nó que possui as seguintes propriedades.
   
   • A subárvore esquerda de um nó contém apenas nós com chaves menores que a chave do nó.
   • A subárvore direita de um nó contém apenas nós com chaves maiores que a chave do nó.
   • As subárvores esquerda e direita também devem ser árvores de pesquisa binária.
   
   Das propriedades acima, segue-se naturalmente que:
   • Cada nó (item da árvore) possui uma chave distinta.
   
   

                         4
                      / \
                    2 5
                  / \
                1 3
   

   
   Sua tarefa é criar um programa para verificar se uma árvore binária é BST ou não.
   

   
   
   Tradução

   Dada uma árvore de pesquisa binária que possui as seguintes propriedades:
   * A subárvore esquerda de cada nó contém números menores que o valor desse nó.
   * A subárvore correta para cada nó contém números maiores que o valor desse nó.
   * As subárvores esquerda e direita são árvores de pesquisa binária.
   
   A partir do descrito, segue-se que cada nó na árvore contém uma chave exclusiva.
   
   

                         4
                      / \
                    2 5
                  / \
                1 3
   

   
   Sua tarefa é escrever um programa para verificar se a árvore é uma árvore de pesquisa binária ou não.
3. Litro, água e 2 vasos de "coprime"
   

   Existem dois vasos de capacidades 'a' e 'b' respectivamente. Temos um suprimento infinito de água. Forneça um algoritmo eficiente para fazer exatamente 1 litro de água em um dos vasos. Você pode jogar toda a água de qualquer navio em qualquer ponto do tempo. Suponha que 'a' e 'b' sejam coprimes.

   
   
   Tradução

   Dado 2 navios com capacidade de 'a' e 'b' e uma fonte inesgotável de água. Sugira um algoritmo eficaz para medir exatamente 1 litro de água usando esses vasos. Você pode derramar toda a água de qualquer vaso a qualquer momento. Também assumimos que 'a' e 'b' são coprime .
   

Soluções

1. Pergunta 1

   o andyudol propôs uma solução .
   
   
   
2. Questão 2

   Nos comentários, eles sugeriram a solução certa - aqui e aqui - também algumas opções.
   
   
   
3. Tarefa 1

   Solução 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. Tarefa 2

   Solução 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. Tarefa 3

   Opção de solução:
   

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