Edisi # 25: Pelatihan TI - masalah saat ini dan tantangan dari perusahaan terkemuka

Pertanyaan

1. Magnet, Magnetik dan Nonmagnetik
   

   Bagaimana Anda bisa membedakan antara magnet, material magnetik, dan material nonmagnetik?

   
   
   Terjemahan

   Bagaimana membedakan magnet, material magnetik dan non-magnet? ( Kira-kira. Pertanyaan tentang besi dalam perspektif yang tidak terduga. Memerlukan pengetahuan fisika )
   
2. Infeksi virus
   

   Dunia sedang menghadapi infeksi virus yang serius. Pemerintah dari berbagai negara telah mengeluarkan setiap warga negara dua botol. Anda juga telah diberikan hal yang sama. Sekarang satu pil dari setiap botol harus diminum setiap hari selama sebulan untuk menjadi kebal terhadap virus. Masalahnya adalah bahwa jika Anda mengambil hanya satu, atau jika Anda mengambil dua dari botol yang sama, Anda akan mati dengan kematian yang menyakitkan.
   
   Saat menggunakannya, Anda segera membuka botol dan menuangkan tablet di tangan Anda. Tiga tablet turun di tangan Anda dan Anda menyadari mereka terlihat persis sama dan memiliki karakteristik yang sama. Anda tidak dapat membuang pil karena terbatas dan Anda tidak dapat mengembalikannya atau Anda mungkin salah dan mungkin mati suatu hari. Bagaimana Anda memecahkan masalah ini?

   
   
   Terjemahan

   Dunia dihadapkan dengan infeksi virus yang mengerikan. Pemerintah semua negara memberi setiap warga negara dua botol obat. Anda diberi kit yang sama. Anda perlu mengambil satu tablet dari setiap botol setiap hari selama sebulan untuk mendapatkan kekebalan terhadap virus. Jika Anda hanya mengambil satu atau dua pil dari botol yang sama, kematian yang menyakitkan akan terjadi.
   
   Mengambil satu porsi tablet lagi, Anda membuka kedua botol dan dengan cepat menuangkan tablet ke telapak tangan Anda. Terlambat, tetapi Anda mengerti bahwa tiga pil tumpah, serta fakta bahwa mereka terlihat persis sama. Tablet tidak dapat dibuang, karena jumlahnya terbatas, dan Anda tidak dapat mengembalikannya, jika tidak, jika terjadi kesalahan, suatu hari Anda akan mati. Bagaimana Anda memecahkan masalah ini?
   
   ( Catatan Tugas serupa sudah ada di rilis sebelumnya. )
   

Tugasnya

1. Mengurutkan elemen berdasarkan frekuensi
   

   Cetak elemen-elemen dari array dalam frekuensi yang menurun. Jika 2 angka memiliki frekuensi yang sama maka cetak yang datang lebih dulu.
   
   Contoh:
   
   Input: arr [] = {2, 5, 2, 8, 5, 6, 8, 8}
   Output: arr [] = {8, 8, 8, 2, 2, 5, 5, 6}
   
   Input: arr [] = {2, 5, 2, 6, -1, 9999999, 5, 8, 8, 8}
   Output: arr [] = {8, 8, 8, 2, 2, 5, 5, 6, -1, 9999999}
   

   
   
   Terjemahan

   Cetak elemen-elemen array dalam urutan frekuensi kemunculannya. Jika dua angka memiliki frekuensi yang sama - output terlebih dahulu apa yang terjadi terlebih dahulu.
   
   Contoh:
   
   Input: arr [] = {2, 5, 2, 8, 5, 6, 8, 8}
   Output: arr [] = {8, 8, 8, 2, 2, 5, 5, 6}
   
   Input: arr [] = {2, 5, 2, 6, -1, 9999999, 5, 8, 8, 8}
   Output: arr [] = {8, 8, 8, 2, 2, 5, 5, 6, -1, 9999999}
2. Periksa bst
   

   Pohon pencarian biner (BST) adalah struktur data pohon biner berbasis simpul yang memiliki properti berikut.
   
   • Subtree kiri dari sebuah node hanya berisi node dengan kunci kurang dari kunci node.
   • Subtree kanan sebuah node hanya berisi node dengan kunci lebih besar dari kunci node.
   • Sub pohon kiri dan kanan juga harus pohon pencarian biner.
   
   Dari properti di atas secara alami berikut bahwa:
   • Setiap node (item di pohon) memiliki kunci yang berbeda.
   
   

                         4
                      / \
                    2 5
                  / \
                1 3
   

   
   Tugas Anda adalah membuat program untuk memeriksa apakah pohon biner BST atau tidak.
   

   
   
   Terjemahan

   Diberikan pohon pencarian biner yang memiliki properti berikut:
   * Subtree kiri untuk setiap node berisi angka yang lebih kecil dari nilai node ini.
   * Subpohon yang tepat untuk setiap simpul berisi angka yang lebih besar dari nilai simpul ini.
   * Subpohon kiri dan kanan adalah pohon pencarian biner.
   
   Dari uraian di atas, setiap node di dalam pohon berisi kunci unik.
   
   

                         4
                      / \
                    2 5
                  / \
                1 3
   

   
   Tugas Anda adalah menulis program untuk memeriksa apakah pohon itu pohon pencarian biner atau tidak.
3. Liter, air, dan 2 kapal "coprime" smocking
   

   Ada dua kapal kapasitas 'a' dan 'b' masing-masing. Kami memiliki persediaan air yang tak terbatas. Berikan algoritma yang efisien untuk menghasilkan 1 liter air di salah satu bejana. Anda dapat membuang semua air dari kapal mana pun kapan saja. Anggaplah bahwa 'a' dan 'b' adalah Coprimes.

   
   
   Terjemahan

   Diberi 2 kapal dengan kapasitas 'a' dan 'b' dan sumber air yang tak ada habisnya. Sarankan algoritma yang efektif untuk mengukur tepat 1 liter air menggunakan bejana ini. Anda dapat menuangkan semua air dari kapal apa pun pada waktu tertentu. Kami juga berasumsi bahwa 'a' dan 'b' adalah koprime .
   

Solusi

1. Pertanyaan 1

   andyudol mengusulkan solusi .
   
   
   
2. Pertanyaan 2

   Dalam komentar, mereka menyarankan solusi yang tepat - di sini , dan di sini - juga beberapa opsi.
   
   
   
3. Tugas 1

   Solusi awal:
   

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

   Solusi 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. Tugas 3

   Opsi Solusi:
   

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