第25期：IT培训-当前问题和领先公司的挑战

问题

1. 磁铁，磁性和非磁性
   

   您如何区分磁体，磁性材料和非磁性材料？

   
   
   笔译

   如何区分磁铁，磁性材料和非磁铁？ （ 大约在一个意想不到的角度上关于铁的问题。需要一些物理知识 ）
   
2. 病毒感染
   

   世界正面临严重的病毒感染。 各国政府已向每个公民发放了两瓶。 您也已获得相同的待遇。 现在每个月要从每个瓶中服用一粒药，持续一个月，以抵抗该病毒。 问题是，如果您只吃一个，或者从同一瓶中拿两个，您将死于痛苦。
   
   使用时，您急忙打开瓶子，将药片倒在手中。 三个平板电脑落在您的手中，您会意识到它们看起来完全相同，并且具有相同的特征。 由于药丸有限，您不能扔掉药丸，也不能将其放回原处，否则您可能会放错药并有一天可能死亡。 您将如何解决这个问题？

   
   
   笔译

   世界面临着可怕的病毒感染。 各国政府给每个公民两瓶药。 您也得到了相同的工具包。 您需要每天从每个瓶中服用一片药片，持续一个月才能获得对该病毒的免疫力。 如果您从同一瓶中只服用一两片药，将导致痛苦的死亡。
   
   服用另一份片剂，您打开两个瓶子，然后将片剂倒入手掌。 太晚了，但您了解到有三颗药丸溢出，而且它们看起来完全一样。 数位板的数量有限，无法将其丢弃，您不能将其放回原位，否则，如果发生错误，您总有一天会死掉。 您将如何解决这个问题？
   
   （ 请注意，早期版本中已经有类似的任务。 ）
   

任务

1. 按频率对元素进行排序
   

   以递减的频率打印数组的元素。 如果2个数字具有相同的频率，则打印第一个出现的频率。
   
   范例：
   
   输入：arr [] = {2，5，2，8，5，6，8，8}
   输出：arr [] = {8、8、8、2、2、5、5、6}
   
   输入：arr [] = {2，5，2，6，-1，9999999，5，8，8，8}
   输出：arr [] = {8，8，8，2，2，5，5，6，-1，9999999}
   

   
   
   笔译

   按出现频率降序打印数组的元素。 如果两个数字具有相同的频率-首先输出，然后发生。
   
   范例：
   
   输入：arr [] = {2，5，2，8，5，6，8，8}
   输出：arr [] = {8、8、8、2、2、5、5、6}
   
   输入：arr [] = {2，5，2，6，-1，9999999，5，8，8，8}
   输出：arr [] = {8，8，8，2，2，5，5，6，-1，9999999}
2. 检查bst
   

   二进制搜索树（BST）是基于节点的二进制树数据结构，具有以下属性。
   
   •节点的左子树仅包含键小于节点键的节点。
   •节点的右子树仅包含键大于节点的键的节点。
   •左子树和右子树都必须也是二进制搜索树。
   
   从以上属性自然可以得出：
   •每个节点（树中的项目）都有一个不同的键。
   
   

                         4
                      / \
                    2 5
                  / \
                1 3
   

   
   您的任务是创建一个程序来检查二进制树是否为BST。
   

   
   
   笔译

   给定具有以下属性的二进制搜索树 ：
   *每个节点的左子树包含的数字小于此节点的值。
   *每个节点的右子树包含的数字大于此节点的值。
   *左和右子树都是二进制搜索树。
   
   从描述中可以得出，树中的每个节点都包含一个唯一键。
   
   

                         4
                      / \
                    2 5
                  / \
                1 3
   

   
   您的任务是编写一个程序来检查树是否是二进制搜索树。
3. 升，水和2个罩好的 “互质”船
   

   分别有两个容量为“ a”和“ b”的容器。 我们有无限的供水。 给出一种有效的算法以在其中一个容器中精确地制造1升水。 您可以在任何时间点将任何船只上的水全部倒掉。 假设“ a”和“ b”是互质数。

   
   
   笔译

   给定2艘容量为“ a”和“ b”的船只，水源不竭。 建议使用这些容器测量1升水的有效算法。 您可以在任何给定时间从任何容器中倒出所有水。 我们还假设'a'和'b' 是互质的 。
   

解决方案

1. 问题1

   andyudol提出了一个解决方案 。
   
   
   
2. 问题2

   在评论中，他们提出了正确的解决方案-here和here-还有一些选择。
   
   
   
3. 任务1

   初始解决方案：
   

   #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. 任务2

   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. 任务3

   解决方案选项：
   

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