अंक # 25: आईटी प्रशिक्षण - वर्तमान मुद्दों और प्रमुख कंपनियों से चुनौतियां

सवाल

1. चुंबक, चुंबकीय और गैर चुंबकीय
   

   आप एक चुंबक, चुंबकीय सामग्री और गैर-चुंबकीय सामग्री के बीच अंतर कैसे कर सकते हैं?

   
   
   अनुवाद

   चुंबक, चुंबकीय सामग्री और गैर-चुंबक को कैसे भेद करें? ( लगभग अप्रत्याशित परिप्रेक्ष्य में लोहे पर प्रश्न। भौतिकी के कुछ ज्ञान की आवश्यकता है )
   
2. वायरल संक्रमण
   

   दुनिया एक गंभीर वायरल संक्रमण का सामना कर रही है। विभिन्न देशों की सरकार ने प्रत्येक नागरिक को दो बोतलें जारी की हैं। आपको भी समान दिया गया है। अब प्रत्येक बोतल में से एक गोली हर महीने एक महीने के लिए वायरस से प्रतिरक्षा के लिए ली जानी है। समस्या यह है कि यदि आप सिर्फ एक लेते हैं, या यदि आप एक ही बोतल से दो लेते हैं, तो आप एक दर्दनाक मौत मर जाएंगे।
   
   इसका उपयोग करते समय, आप जल्दी से बोतल खोलते हैं और अपने हाथ में गोलियां डालते हैं। तीन गोलियां आपके हाथ में आ जाती हैं और आपको एहसास होता है कि वे बिल्कुल एक जैसी हैं और उनमें एक जैसी विशेषताएं हैं। आप गोली को फेंक नहीं सकते क्योंकि वे सीमित हैं और आप उन्हें वापस नहीं डाल सकते हैं या आप इसे गलत डाल सकते हैं और किसी दिन मर सकते हैं। आप इस समस्या को कैसे हल करेंगे?

   
   
   अनुवाद

   दुनिया एक भयानक वायरल संक्रमण का सामना कर रही है। सभी देशों की सरकारें प्रत्येक नागरिक को दो बोतल दवा देती हैं। आपको एक ही किट दी गई थी। वायरस से प्रतिरोधक क्षमता हासिल करने के लिए आपको प्रत्येक बोतल से प्रति माह एक गोली लेनी होगी। यदि आप एक ही बोतल से केवल एक गोली या दो लेते हैं, तो दर्दनाक मौत हो जाएगी।
   
   गोलियों की एक और सेवा लेते हुए, आप दोनों बोतलें खोलते हैं और जल्दी से अपनी हथेली में गोलियाँ डालते हैं। देर से, लेकिन आप समझते हैं कि तीन गोलियां छीनी गईं, साथ ही इस तथ्य को भी कि वे बिल्कुल एक जैसी दिखती हैं। टेबलेट को फेंका नहीं जा सकता है, क्योंकि उनकी मात्रा सीमित है, और आप उन्हें वापस नहीं डाल सकते हैं, अन्यथा, किसी त्रुटि के मामले में, आप किसी दिन मर जाएंगे। आप इस समस्या को कैसे हल करेंगे?
   
   ( नोट एक समान कार्य पहले से जारी था। )
   

कार्य

1. तत्वों को आवृत्ति द्वारा क्रमबद्ध करें
   

   घटती आवृत्ति में एक सरणी के तत्वों को प्रिंट करें। यदि 2 संख्याओं में समान आवृत्ति है तो जो पहले आया था उसे प्रिंट करें।
   
   उदाहरण:
   
   इनपुट: गिरफ्तारी [] = {२, ५, २, =, ५, ६, =, =}
   आउटपुट: गिरफ्तारी [] = {=, =, =, २, २, ५, ५, ५, ६}
   
   इनपुट: गिरफ्तारी [] = {२, ५, २, ६, १, ९९९९९९९, ५, =, =, =, =}
   आउटपुट: गिरफ्तारी [] = {=, =, =, २, २, ५, ५, ५, ६, १, ९९९९९९}
   

   
   
   अनुवाद

   सरणी के तत्वों को घटना आवृत्ति के अवरोही क्रम में प्रिंट करें। यदि दो संख्याओं में समान आवृत्ति होती है - आउटपुट पहले जो होता है।
   
   उदाहरण:
   
   इनपुट: गिरफ्तारी [] = {२, ५, २, =, ५, ६, =, =}
   आउटपुट: गिरफ्तारी [] = {=, =, =, २, २, ५, ५, ५, ६}
   
   इनपुट: गिरफ्तारी [] = {२, ५, २, ६, १, ९९९९९९९, ५, =, =, =, =}
   आउटपुट: गिरफ्तारी [] = {=, =, =, २, २, ५, ५, ५, ६, १, ९९९९९९}
2. Bst चेक करें
   

   एक बाइनरी सर्च ट्री (BST) एक नोड आधारित बाइनरी ट्री डेटा संरचना है जिसमें निम्नलिखित गुण होते हैं।
   
   • एक नोड के बाएं उपप्रकार में केवल नोड की कुंजी की तुलना में कम कुंजी वाले नोड होते हैं।
   • नोड के सही उपप्रकार में केवल नोड की कुंजी की तुलना में अधिक कुंजी वाले नोड होते हैं।
   • बाएं और दाएं दोनों उपप्रकारों में बाइनरी सर्च ट्री भी होना चाहिए।
   
   उपरोक्त गुणों से यह स्वाभाविक रूप से निम्नानुसार है:
   • प्रत्येक नोड (पेड़ में आइटम) की एक अलग कुंजी है।
   
   

                         4
                      / \ _
                    २ ५
                  / \ _
                1 3
   

   
   आपका कार्य यह जाँचने के लिए है कि बाइनरी ट्री BST है या नहीं।
   

   
   
   अनुवाद

   एक बाइनरी सर्च ट्री दिया गया जिसमें निम्नलिखित गुण हैं:
   * प्रत्येक नोड के लिए बाईं सबट्री में इस नोड के मान से कम नंबर होते हैं।
   * प्रत्येक नोड के लिए सही सबट्री में इस नोड के मान से अधिक संख्याएं होती हैं।
   * दोनों बाएँ और दाएँ उप-पेड़ बाइनरी सर्च ट्री हैं।
   
   वर्णित से यह इस प्रकार है कि पेड़ में प्रत्येक नोड में एक अद्वितीय कुंजी होती है।
   
   

                         4
                      / \ _
                    २ ५
                  / \ _
                1 3
   

   
   आपका कार्य यह जांचने के लिए एक कार्यक्रम लिखना है कि क्या पेड़ एक द्विआधारी खोज पेड़ है या नहीं।
3. लीटर, पानी और 2 स्मोकिंग "कोप्राइम" बर्तन
   

   क्रमशः क्षमता 'ए' और 'बी' के दो पोत हैं। हमारे पास अनंत जल आपूर्ति है। जहाजों में से एक में ठीक 1 लीटर पानी बनाने के लिए एक कुशल एल्गोरिदम दें। आप किसी भी समय किसी भी बर्तन से सारा पानी फेंक सकते हैं। मान लें कि 'a' और 'b' कोप्राइम हैं।

   
   
   अनुवाद

   'ए' और 'बी' की क्षमता वाले 2 जहाजों और पानी के अंतहीन स्रोत को देखते हुए। इन जहाजों का उपयोग करके ठीक 1 लीटर पानी को मापने के लिए एक प्रभावी एल्गोरिदम का सुझाव दें। आप किसी भी समय किसी भी बर्तन से सारा पानी डाल सकते हैं। हम यह भी मानते हैं कि 'ए' और 'बी' कोप्राइम हैं ।
   

समाधान

1. प्रश्न 1

   andyudol ने एक समाधान प्रस्तावित किया।
   
   
   
2. प्रश्न २

   टिप्पणियों में, उन्होंने सही समाधान सुझाया - यहाँ , और यहाँ - कुछ विकल्प भी।
   
   
   
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. टास्क २

   जावा सॉल्यूशन:
   

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