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

Questions

1. Days of month using 2 dice
   

   How can you represent these two sided dice? For example for 1, for example for 1, for example for 1, one should be show 1 and another should show 9.
   

   
   
   Transfer

   How would you represent the days of the month with 2 hexagonal cubes? You can write numbers from 0 to 9 on each face of the cube, while you need to designate numbers from 1 to 31. For example, for the 1st, one cube can be rotated with a “0” face and the other with a “1”; similarly for the number 29 - one die with “2”, the second - with “9”.
   
   
   
2. Blindfolded and coins
   

   You are blindfolded and 10 coins are in place. But you can't touch the coins. You are told that there are 5 coins and 5 coins.
   
   The same number of heads up? You can flip your coins any number of times.
   
   

   
   
   Transfer

   You are blindfolded, and on the table in front of you are 10 coins. You are allowed to touch them, but to the touch you cannot tell which side they are turned. It is also stated that 5 coins lie eagle up, 5 - tails.
   
   How to make 2 piles with an equal number of coins turned by an eagle up? You can flip coins an unlimited number of times.
   
   
   

Tasks

1. Tug of war
   

   This is not the case. If it is a bit, then it will be the n / 2 .
   
   For example, let given set be {3, 4, 5, -3, 100, 1, 89, 54, 23, 20}, the size of set is 10. Output for this set should be {4, 100, 1, 23, 20} and {3, 5, -3, 89, 54}. Both output subsets are the size of both elements (148 and 148).
   Let us consider another example where n is odd. Let given set be {23, 45, -34, 12, 0, 98, -99, 4, 189, -1, 4}. The output subsets should be {45, -34, 12, 98, -1} and {23, 0, -99, 4, 189, 4}. In two subsets are 120 and 121 respectively.
   

   
   
   Transfer

   Given a set of n integers, it is necessary to divide it into 2 subsets, each of dimension n / 2, so that the difference between the sums of these subsets is minimal. If n is even, then the sizes of the subsets must be exactly n / 2, if n is odd, then the size of one subset must be (n-1) / 2, the second - (n + 1) / 2.
   
   For example:
   Login: {3, 4, 5, -3, 100, 1, 89, 54, 23, 20}
   Output: {4, 100, 1, 23, 20} and {3, 5, -3, 89, 54}. The sizes of both subsets are 5, and the amounts are 148.
   
   Entry: {23, 45, -34, 12, 0, 98, -99, 4, 189, -1, 4}
   Output: {45, -34, 12, 98, -1} and {23, 0, -99, 4, 189, 4}. The sums of the subsets are 120 and 121, respectively.
   
   
   
2. Maximum sum such that no two elements are
   

   If there are no numbers in the sequence, it should be So 3 2 7 10 should return 13 (sum of 3 and 10) or 3 2 5 10 7 should return 15 (sum of 3, 5 and 7). Answer your question in the most efficient way.
   
   Examples:
   
   Input: arr [] = {5, 5, 10, 100, 10, 5}
   Output: 110
   
   Input: arr [] = {1, 2, 3}
   Output: 4
   
   Input: arr [] = {1, 20, 3}
   Output: 20
   

   
   
   Transfer

   Given an array of positive numbers, find the maximum sum of the subsequence with the condition that no two elements of the subsequence are in the neighboring cells of the array. So, 3 2 7 10 should return 13 (sum 3 and 10), and 3 2 5 10 7 should return 15 (sum 3 5 7). The code should be as efficient as possible.
   
   Examples:
   
   Input: arr [] = {5, 5, 10, 100, 10, 5}
   Output: 110
   
   Input: arr [] = {1, 2, 3}
   Output: 4
   
   Input: arr [] = {1, 20, 3}
   Output: 20
   
   
   
   
3. Program to find a glass of water
   

   1 liter. The glasses are kept as follows:
   

                       one
                     2 3
                  4 5 6
                7 8 9 10
   

   
   You can put water to only top glass. If you put on a glass of water, you can’t get it in the 1st glass. Glass 5 will get water.
   If you have a liter of water glass? Write a program to find it.
   
   Example If you will put 2 liter on top.
   1st - 1 liter
   2nd - 1/2 liter
   3rd - 1/2 liter
   

   
   
   Transfer

   Several cans with a capacity of 1 liter are lined up with a pyramid like this:
   

                       one
                     2 3
                  4 5 6
                7 8 9 10
   

   
   You can only pour water into the topmost jar. At overflow of banks, the water will begin to flow evenly into the lower (2 and 3). Bank 5 will receive water from 2 and 3 cans, etc.
   If you have X liters of water that you pour into the top can, how much water will go into the can j? Write a program to resolve this issue.
   
   Example. If you pour 2 liters, then:
   1st - 1 liter
   2nd - 1/2 liters
   3rd - 1/2 liters
   

Solutions

1. Question 1

   The answer was quickly found .
   
   
   
2. Question 2

   Rsa97 offered the right solution .
   
   
   
3. Task 1

   Initial solution:
   

   #include <iostream> #include <stdlib.h> #include <limits.h> using namespace std; // function that tries every possible solution by calling itself recursively void TOWUtil(int* arr, int n, bool* curr_elements, int no_of_selected_elements, bool* soln, int* min_diff, int sum, int curr_sum, int curr_position) { // checks whether the it is going out of bound if (curr_position == n) return; // checks that the numbers of elements left are not less than the // number of elements required to form the solution if ((n/2 - no_of_selected_elements) > (n - curr_position)) return; // consider the cases when current element is not included in the solution TOWUtil(arr, n, curr_elements, no_of_selected_elements, soln, min_diff, sum, curr_sum, curr_position+1); // add the current element to the solution no_of_selected_elements++; curr_sum = curr_sum + arr[curr_position]; curr_elements[curr_position] = true; // checks if a solution is formed if (no_of_selected_elements == n/2) { // checks if the solution formed is better than the best solution so far if (abs(sum/2 - curr_sum) < *min_diff) { *min_diff = abs(sum/2 - curr_sum); for (int i = 0; i<n; i++) soln[i] = curr_elements[i]; } } else { // consider the cases where current element is included in the solution TOWUtil(arr, n, curr_elements, no_of_selected_elements, soln, min_diff, sum, curr_sum, curr_position+1); } // removes current element before returning to the caller of this function curr_elements[curr_position] = false; } // main function that generate an arr void tugOfWar(int *arr, int n) { // the boolen array that contains the inclusion and exclusion of an element // in current set. The number excluded automatically form the other set bool* curr_elements = new bool[n]; // The inclusion/exclusion array for final solution bool* soln = new bool[n]; int min_diff = INT_MAX; int sum = 0; for (int i=0; i<n; i++) { sum += arr[i]; curr_elements[i] = soln[i] = false; } // Find the solution using recursive function TOWUtil() TOWUtil(arr, n, curr_elements, 0, soln, &min_diff, sum, 0, 0); // Print the solution cout << "The first subset is: "; for (int i=0; i<n; i++) { if (soln[i] == true) cout << arr[i] << " "; } cout << "\nThe second subset is: "; for (int i=0; i<n; i++) { if (soln[i] == false) cout << arr[i] << " "; } } // Driver program to test above functions int main() { int arr[] = {23, 45, -34, 12, 0, 98, -99, 4, 189, -1, 4}; int n = sizeof(arr)/sizeof(arr[0]); tugOfWar(arr, n); return 0; } 

   
   
   
   
4. Task 2

   Solution option:
   

    #include<stdio.h> /*Function to return max sum such that no two elements are adjacent */ int FindMaxSum(int arr[], int n) { int incl = arr[0]; int excl = 0; int excl_new; int i; for (i = 1; i < n; i++) { /* current max excluding i */ excl_new = (incl > excl)? incl: excl; /* current max including i */ incl = excl + arr[i]; excl = excl_new; } /* return max of incl and excl */ return ((incl > excl)? incl : excl); } /* Driver program to test above function */ int main() { int arr[] = {5, 5, 10, 100, 10, 5}; int n = sizeof(arr) / sizeof(arr[0]); printf("%dn", FindMaxSum(arr, n)); return 0; } 

   
   
   
   
5. Task 3

   Solution option:
   

    // Program to find the amount of water in j-th glass // of i-th row #include <stdio.h> #include <stdlib.h> #include <string.h> // Returns the amount of water in jth glass of ith row float findWater(int i, int j, float X) { // A row number i has maximum i columns. So input // column number must be less than i if (j > i) { printf("Incorrect Inputn"); exit(0); } // There will be i*(i+1)/2 glasses till ith row // (including ith row) float glass[i * (i + 1) / 2]; // Initialize all glasses as empty memset(glass, 0, sizeof(glass)); // Put all water in first glass int index = 0; glass[index] = X; // Now let the water flow to the downward glasses // till the row number is less than or/ equal to i (given row) // correction : X can be zero for side glasses as they have lower rate to fill for (int row = 1; row <= i ; ++row) { // Fill glasses in a given row. Number of // columns in a row is equal to row number for (int col = 1; col <= row; ++col, ++index) { // Get the water from current glass X = glass[index]; // Keep the amount less than or equal to // capacity in current glass glass[index] = (X >= 1.0f) ? 1.0f : X; // Get the remaining amount X = (X >= 1.0f) ? (X - 1) : 0.0f; // Distribute the remaining amount to // the down two glasses glass[index + row] += X / 2; glass[index + row + 1] += X / 2; } } // The index of jth glass in ith row will // be i*(i-1)/2 + j - 1 return glass[i*(i-1)/2 + j - 1]; } // Driver program to test above function int main() { int i = 2, j = 2; float X = 2.0; // Total amount of water printf("Amount of water in jth glass of ith row is: %f", findWater(i, j, X)); return 0; }