Issue # 9: IT training - current issues and challenges from leading companies

Questions

1. Transport the bananas
   

   A person has 3000 bananas and a camel. The number of bananas is 1000 KMs away. The camel cant carry more than 1000 bananas at a time and eats a banana every km it travels. It can be transferred to your destination.
   

   Transfer

   A man has 3000 bananas and a camel. He wants to take a maximum of bananas to a destination that is 1000 km away, using a camel as a transport. A camel cannot carry more than 1,000 bananas at a time and eats one banana per kilometer of track.
   What is the largest number of bananas that can be delivered in this way (other modes of transport are not allowed)?
   
2. Measure forty-five minutes using wires
   

   For each wire you use, for each wire you use, it will take you a few minutes. We have matchsticks with us. The wires burn non-uniformly. So, for example, it can burn in 10 minutes and 50 minutes respectively.

   Transfer

   There are 2 identical cords, each of which burns in an hour. Matches with us, cords burn unevenly. For example, half can burn in 10 minutes and the remaining half in 50 minutes. How, using these cords, we count 45 minutes?
   

Tasks

1. Elephants lifetime
   

   Given life time of different elephants. The number of elephants were alive.
   ')
   Input: [2005, 2010], [2006, 2015], [2002, 2007]
   Output: [2006, 2007].

   Transfer

   Given the lifetime of several elephants. Find the period in which the greatest number of elephants lived.
   
   Login: [2005, 2010], [2006, 2015], [2002, 2007]
   Output: [2006, 2007].

If there is a triplet (a, b, c) that satisfies a ^ 2 + b ^ 2 = c ^ 2.

Example:

Input: arr [] = {3, 1, 4, 6, 5}
Output: True
There is a Pythagorean triplet (3, 4, 5).

Input: arr [] = {10, 4, 6, 12, 5}
Output: False
There is no Pythagorean triplet.

Consider an array of distinct integers sorted in increasing order. The array has been rotated (anti-clockwise) k number of times. Given such an array, find the value of k.

Array rotation:

* * 0 1 5 1 => 0 2 4 2 5 3 3 4 

Examples:

Input: arr [] = {15, 18, 2, 3, 6, 12}
Output: 4
Initial array must be {2, 3, 6, 12, 15. 18}. We get the given array after rotating the initial array twice.

Input: arr [] = {7, 9, 11, 12, 5}
Output: 1

Input: arr [] = {7, 9, 11, 12, 15};
Output: 0

  * * 0 1 5 1 => 0 2 4 2 5 3 3 4 

Solutions

1. Question 1

   At first glance, it seems that a camel, capable of carrying only 1,000 bananas at an expense of 1 banana / km, will come empty to the 1000-kilometer mark. However, the key to the solution is in intermediate stops. We will proceed from the assumption that the camel consumes 1 banana / km while being loaded and empty. Then, stopping at a distance of> = 500 km does not make sense to do (at least 2 stops), we get the following route plan:
   

                       === there ===>
                      <=== here ==== === there ===>
    And (starting point) === there ===> A <=== here ==== B === there ===> C (goal)
                      <=== here ==== === there ===>
                       === there ===>	 
   

   
   Note that the cost of a kilometer on a segment of IA is 5 bananas, on a segment of AB - 3 bananas, on a segment of BC - 1. To keep a maximum of bananas, we must try to reduce the most costly segments.
   From point A, the camel will be able to take away a maximum of 2000 bananas, therefore, 2000 point bananas should be delivered to point B, from where you can get the length of IA: 3000 - 5IA = 2000, i.e. IA = 200 km.
   The calculation of AB is similar. Since, from B, the camel will take a maximum of 1000 bananas, the AB length is 2000-3AB = 1000, i.e. AB = 333⅓. The BC length is 466⅔, and 533⅓ bananas will be delivered to the target.
   
   The correct answer was also proposed in the comments.
   
   
   
2. Question 2

   The comment was given the correct answer. Indeed, no matter how uneven the cord burned, if you ignite it from two sides, it will burn in half an hour. Therefore, you first need to light one cord on both sides, one - only one. When the first burns down (it means half an hour has passed) - to set fire to the second cord from the second end, it will burn for another 15 minutes. Total - 45 minutes.
   
   
   
3. Task 1

   The correct algorithms were suggested in the comments, but there were no code examples.
   Solution option:
   
   

    #include <iostream> #include <iomanip> #include <iterator> using namespace std; typedef struct{ int birthYear; int deathYear; }LIFE; typedef struct{ int startYear; int endYear; }PERIOD; int FindMinStartYear(LIFE* anmimals, int len) { int startYear = anmimals[0].birthYear; for(int i = 1; i < len; ++i){ if(anmimals[i].birthYear < startYear){ startYear = anmimals[i].birthYear; } } return startYear; } int FindMaxEndYear(LIFE* anmimals, int len) { int endYear = anmimals[0].deathYear; for(int i = 1; i < len; ++i){ if(anmimals[i].deathYear > endYear){ endYear = anmimals[i].deathYear; } } return endYear; } int FindPeriodOfMaxAnimal(LIFE* anmimals, int len, PERIOD& p) { int startYear = FindMinStartYear( anmimals, len); int endYear = FindMaxEndYear( anmimals, len); int* period = new int[endYear - startYear + 1]; for(int i = 0; i < endYear - startYear + 1; ++i){ period[i] = 0; } for(int i = 0; i < len; ++i){ for(int j = anmimals[i].birthYear; j <= anmimals[i].deathYear; ++j){ period[j - startYear]++; } } cout << endl; copy(period, period + endYear - startYear + 1, ostream_iterator<int>(cout, " ")); cout << endl; int maxAnimals = period[0]; int maxStart = 0; int maxEnd = 0; for(int i = 0; i <= endYear - startYear; ++i){ if(period[i] > maxAnimals){ maxStart = i; maxAnimals = period[i]; } if(period[i] == maxAnimals){ maxEnd = i; } } delete[] period; p.startYear = maxStart + startYear; p.endYear = maxEnd + startYear; return maxAnimals; } int main(int argc, char* argv[]) { LIFE testCases[] = { {5, 11}, {6, 18}, {2, 5}, {3, 12} }; PERIOD p; int maxAnimals = FindPeriodOfMaxAnimal(testCases, sizeof(testCases)/sizeof(testCases[0]), p); cout << "In the period " << p.startYear << " and "; cout << p.endYear << ", there are " << maxAnimals << endl; return 0; 

   
   
   
   
4. Task 2

   Solution solution with sorting:
   

    // A C++ program that returns true if there is a Pythagorean // Triplet in a given array. #include <iostream> #include <algorithm> using namespace std; // Returns true if there is a triplet with following property // A[i]*A[i] = A[j]*A[j] + A[k]*[k] // Note that this function modifies given array bool isTriplet(int arr[], int n) { // Square array elements for (int i=0; i<n; i++) arr[i] = arr[i]*arr[i]; // Sort array elements sort(arr, arr + n); // Now fix one element one by one and find the other two // elements for (int i = n-1; i >= 2; i--) { // To find the other two elements, start two index // variables from two corners of the array and move // them toward each other int l = 0; // index of the first element in arr[0..i-1] int r = i-1; // index of the last element in arr[0..i-1] while (l < r) { // A triplet found if (arr[l] + arr[r] == arr[i]) return true; // Else either move 'l' or 'r' (arr[l] + arr[r] < arr[i])? l++: r--; } } // If we reach here, then no triplet found return false; } /* Driver program to test above function */ int main() { int arr[] = {3, 1, 4, 6, 5}; int arr_size = sizeof(arr)/sizeof(arr[0]); isTriplet(arr, arr_size)? cout << "Yes": cout << "No"; return 0; } 

   
   
   
   
5. Task 3

   Upon careful consideration of the problem, it can be noted that the number of turns of the array is equal to the length of the array — the index of the minimum element that can be found by binary search. Solution option:
   
   

    // Binary Search based C++ program to find number // of rotations in a sorted and rotated array. #include<bits/stdc++.h> using namespace std; // Returns count of rotations for an array which // is first sorted in ascending order, then rotated int countRotations(int arr[], int low, int high) { // This condition is needed to handle the case // when array is not rotated at all if (high < low) return 0; // If there is only one element left if (high == low) return low; // Find mid int mid = low + (high - low)/2; /*(low + high)/2;*/ // Check if element (mid+1) is minimum element. // Consider the cases like {3, 4, 5, 1, 2} if (mid < high && arr[mid+1] < arr[mid]) return (mid+1); // Check if mid itself is minimum element if (mid > low && arr[mid] < arr[mid - 1]) return mid; // Decide whether we need to go to left half or // right half if (arr[high] > arr[mid]) return countRotations(arr, low, mid-1); return countRotations(arr, mid+1, high); } // Driver code int main() { int arr[] = {15, 18, 2, 3, 6, 12}; int n = sizeof(arr)/sizeof(arr[0]); int sizearr = n -1 ; int countr = sizearr -countRotations(arr, 0, sizearr); cout << countr; return 0; }