Edição 24: Treinamento em TI - problemas e desafios atuais das principais empresas

Perguntas

1. Galinhas
   

   Um fazendeiro vendeu algumas galinhas para quatro clientes diferentes em um dia específico. Foi assim que cada cliente comprou metade das galinhas restantes e meia galinha mais.
   
   Você pode descobrir quantas galinhas foram vendidas pelo agricultor naquele dia se lhe dissermos que o quarto cliente comprou uma única galinha?

   
   
   Tradução

   Em um dia, o fazendeiro vendeu várias galinhas para quatro compradores. Descobriu-se que cada um deles comprou metade das galinhas restantes e outro meio filme.
   
   Você pode me dizer quantas galinhas foram vendidas naquele dia, se for sabido que o quarto comprador comprou uma galinha inteira?
   
   
   
2. Balas e revólver
   

   Um gangster russo sequestra você. Ele coloca duas balas em ordem consecutiva em um revólver vazio de seis cartuchos, gira, aponta para sua cabeça e atira. * clique * Você ainda está vivo. Ele então pergunta: "você quer que eu gire novamente e atire ou puxe o gatilho novamente imediatamente?" Para cada opção, qual é a probabilidade de você levar um tiro?

   
   
   Tradução

   Você foi sequestrado por um bandido russo ( oh, esses estereótipos! ). Ele inseriu sequencialmente duas balas em um revólver de seis tiros, rolou o tambor, apontou para sua cabeça e apertou o gatilho. * clique *. Você ainda está vivo. O bandido perguntou a você: "Você quer que eu role novamente e atire ou atire imediatamente?" Qual é a probabilidade de levar um tiro em cada caso?
   
   
   

As tarefas

1. Classifique uma pilha usando recursão
   

   Dada uma pilha, a tarefa é classificá-la usando recursão. O uso de qualquer construção de loop como while, for..etc não é permitido. Só podemos usar as seguintes funções ADT na pilha S:
   
   is_empty (S): testa se a pilha está vazia ou não.
   push (S): adiciona novo elemento à pilha.
   pop (S): remove o elemento superior da pilha.
   top (S): retorna o valor do elemento top. Observe que esta função não remove o elemento da pilha.
   
   Exemplo:
   
   Entrada: -3 <- Início
   14
   18
   -5
   30
   
   Saída: 30 <- Topo
   18
   14
   -3
   -5

   
   
   Tradução

   Dada uma pilha, a tarefa é classificá-la usando recursão. É proibido o uso de construções cíclicas, como while, for ..., etc. Somente os seguintes comandos de abstração são permitidos na pilha S:
   
   is_empty (S): verifica se a pilha está vazia.
   push (S): adiciona um novo item à pilha.
   pop (S): remove o elemento superior da pilha.
   top (S): retorna o valor do elemento top. Observe que o item não é excluído ao mesmo tempo.
   
   Exemplos:
   
   Entrada: -3 <- Topo da pilha
   14
   18
   -5
   30
   
   Saída: 30 <- Topo da pilha
   18
   14
   -3
   -5
   
   

Dada uma sequência de entrada e um dicionário de palavras, descubra se a sequência de entrada pode ser segmentada em uma sequência de palavras do dicionário separada por espaço. Veja os exemplos a seguir para mais detalhes.

Considere o seguinte dicionário
{i, como, sam, cantado, samsung, celular, gelo,
creme, sorvete, cara, vá, manga}

Entrada: ilike
Saída: Sim
A string pode ser segmentada como "eu gosto".

Entrada: ilikesamsung
Saída: Sim
A sequência pode ser segmentada como "eu gosto de samsung"
ou "eu gosto de sam cantado".

Uma torre estável de altura n é uma torre que consiste exatamente em n blocos de altura da unidade empilhados verticalmente de maneira que nenhum bloco maior seja colocado em um bloco menor. Um exemplo é mostrado abaixo:

           [1]
        [2]
     [3]
 [4]

Temos um número infinito de peças dos tamanhos 1, 2, ..., m. A tarefa é calcular o número de diferentes torres estáveis ​​de altura n que podem ser construídas a partir desses ladrilhos, com uma restrição que você pode usar no máximo k ladrilhos de cada tamanho na torre.

Nota: Duas torres de altura n são diferentes se e somente se existir uma altura h (1 <= h <= n), de modo que as torres tenham ladrilhos de tamanhos diferentes na altura h.

Exemplos:

Entrada: n = 3, m = 3, k = 1.
Saída: 1
Sequências possíveis: {1, 2, 3}.
Portanto, a resposta é 1.

Entrada: n = 3, m = 3, k = 2.
Saída: 7
{1, 1, 2}, {1, 1, 3}, {1, 2, 2}, {1, 2, 3}, {1, 3, 3}, {2, 2, 3}, {2 , 3, 3}.

           [1]
        [2]
     [3]
 [4]

Soluções

1. Pergunta 1

   Resposta: 15. Aqui eles explicaram o porquê.
   
   
2. Questão 2

   Nos comentários respondeu corretamente a esta pergunta
   A probabilidade de que no próximo slot do tambor seja um cartucho - 1/4
   Se você rolar o tambor, a probabilidade de ele parar no cartucho é 2/6 = 1/3
   
   
   
3. Tarefa 1

   Opção de solução, programação dinâmica:
   

   #include <iostream> #include <string.h> using namespace std; /* A utility function to check whether a word is present in dictionary or not. An array of strings is used for dictionary. Using array of strings for dictionary is definitely not a good idea. We have used for simplicity of the program*/ int dictionaryContains(string word) { string dictionary[] = {"mobile","samsung","sam","sung","man","mango", "icecream","and","go","i","like","ice","cream"}; int size = sizeof(dictionary)/sizeof(dictionary[0]); for (int i = 0; i < size; i++) if (dictionary[i].compare(word) == 0) return true; return false; } // Returns true if string can be segmented into space separated // words, otherwise returns false bool wordBreak(string str) { int size = str.size(); if (size == 0) return true; // Create the DP table to store results of subroblems. The value wb[i] // will be true if str[0..i-1] can be segmented into dictionary words, // otherwise false. bool wb[size+1]; memset(wb, 0, sizeof(wb)); // Initialize all values as false. for (int i=1; i<=size; i++) { // if wb[i] is false, then check if current prefix can make it true. // Current prefix is "str.substr(0, i)" if (wb[i] == false && dictionaryContains( str.substr(0, i) )) wb[i] = true; // wb[i] is true, then check for all substrings starting from // (i+1)th character and store their results. if (wb[i] == true) { // If we reached the last prefix if (i == size) return true; for (int j = i+1; j <= size; j++) { // Update wb[j] if it is false and can be updated // Note the parameter passed to dictionaryContains() is // substring starting from index 'i' and length 'ji' if (wb[j] == false && dictionaryContains( str.substr(i, ji) )) wb[j] = true; // If we reached the last character if (j == size && wb[j] == true) return true; } } } /* Uncomment these lines to print DP table "wb[]" for (int i = 1; i <= size; i++) cout << " " << wb[i]; */ // If we have tried all prefixes and none of them worked return false; } // Driver program to test above functions int main() { wordBreak("ilikesamsung")? cout <<"Yesn": cout << "Non"; wordBreak("iiiiiiii")? cout <<"Yesn": cout << "Non"; wordBreak("")? cout <<"Yesn": cout << "Non"; wordBreak("ilikelikeimangoiii")? cout <<"Yesn": cout << "Non"; wordBreak("samsungandmango")? cout <<"Yesn": cout << "Non"; wordBreak("samsungandmangok")? cout <<"Yesn": cout << "Non"; return 0; } 

   
   
   
   
4. Tarefa 2

   Solução em java:
   

    import java.util.ListIterator; import java.util.Stack; class Test { // Recursive Method to insert an item x in sorted way static void sortedInsert(Stack<Integer> s, int x) { // Base case: Either stack is empty or newly inserted // item is greater than top (more than all existing) if (s.isEmpty() || x > s.peek()) { s.push(x); return; } // If top is greater, remove the top item and recur int temp = s.pop(); sortedInsert(s, x); // Put back the top item removed earlier s.push(temp); } // Method to sort stack static void sortStack(Stack<Integer> s) { // If stack is not empty if (!s.isEmpty()) { // Remove the top item int x = s.pop(); // Sort remaining stack sortStack(s); // Push the top item back in sorted stack sortedInsert(s, x); } } // Utility Method to print contents of stack static void printStack(Stack<Integer> s) { ListIterator<Integer> lt = s.listIterator(); // forwarding while(lt.hasNext()) lt.next(); // printing from top to bottom while(lt.hasPrevious()) System.out.print(lt.previous()+" "); } // Driver method public static void main(String[] args) { Stack<Integer> s = new Stack<>(); s.push(30); s.push(-5); s.push(18); s.push(14); s.push(-3); System.out.println("Stack elements before sorting: "); printStack(s); sortStack(s); System.out.println(" \n\nStack elements after sorting:"); printStack(s); } } 

   
   
   
   
5. Tarefa 3

   Opção de solução:
   

    #include <bits/stdc++.h> using namespace std; #define N 100 int possibleWays(int n, int m, int k) { int dp[N][N]; int presum[N][N]; memset(dp, 0, sizeof dp); memset(presum, 0, sizeof presum); // Initialing 0th row to 0. for (int i = 1; i < n + 1; i++) { dp[0][i] = 0; presum[0][i] = 1; } // Initialing 0th column to 0. for (int i = 0; i < m + 1; i++) presum[i][0] = dp[i][0] = 1; // For each row from 1 to m for (int i = 1; i < m + 1; i++) { // For each column from 1 to n. for (int j = 1; j < n + 1; j++) { // Initialing dp[i][j] to presum of (i - 1, j). dp[i][j] = presum[i - 1][j]; if (j > k) { dp[i][j] -= presum[i - 1][j - k - 1]; } } // Calculating presum for each i, 1 <= i <= n. for (int j = 1; j < n + 1; j++) presum[i][j] = dp[i][j] + presum[i][j - 1]; } return dp[m][n]; } // Driver Program int main() { int n = 3, m = 3, k = 2; cout << possibleWays(n, m, k) << endl; return 0; }