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

Questions

1. Ice bucket challenge
   

   There are 3 buckets of 8, 5, 3 liters in front of you. The bucket with capacity 8 is completely filled with ice water. 8 liters of 2 liters of each liter into 2 portions of 4 liter each using above 3 buckets.
   

   Transfer

   In front of you are 3 buckets with a capacity of 8, 5 and 3 liters. 8 l bucket completely filled with cold water. You need to divide 8 liters into 2 portions of 4 liters. using these three buckets.
   
   
   
2. Torch and bridge
   

   There are 4 persons (A, B, C and D).
   
   A takes 1 minute to cross the bridge.
   B takes 2 minutes to cross the bridge.
   C takes 5 minutes to cross the bridge.
   D takes 8 minutes to cross the bridge.
   
   Cannot be crossed without the torch. There is no way for you to go.
   
   Can they all cross the bridge in 15 minutes?
   

   Transfer

   4 people (A, B, C, D) even want to cross the bridge at night.
   
   A need 1 minute to go over the bridge.
   B need 2 minutes.
   C need 5 minutes.
   D need 8 minutes.
   
   They have only one lantern, without which it is impossible to cross the bridge. Also, there can be no more than 2 people on the bridge, and when two are walking along the bridge - they walk at the speed of the slowest walker.
   
   Will they be able to move in 15 minutes?
   

Tasks

1. Sort an array of 0s, 1s and 2x
   

   Given an array of A [] const 0s, 1s and 2s, write a function that sorts A []. The functions should be put all 0s first, then all 1s and all 2s in last.
   Examples:
   
   Input: {0, 1, 2, 0, 1, 2}
   Output: {0, 0, 1, 1, 2, 2}
   
   Input: {0, 1, 1, 0, 1, 2, 1, 2, 0, 0, 0, 1}
   Output: {0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2}
   
   

   Transfer

   Given an array of A [], consisting of 0, 1, and 2. Write a function that sorts A []. The function must first have 0, then 1, the last 2.
   
   Examples:
   
   Input: {0, 1, 2, 0, 1, 2}
   Output: {0, 0, 1, 1, 2, 2}
   
   Input: {0, 1, 1, 0, 1, 2, 1, 2, 0, 0, 0, 1}
   Output: {0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2}
   
   
   
2. Select a random number from stream, using fixed space
   

   Given a generator producing random numbers. If you’re still a number of people.
   
   This is a random number from 1 / n. with O (1) extra space?

   Transfer

   A random number generator is given. It is allowed to use only O (1) memory, the input data is presented as a stream, so there is no possibility to save the previous numbers.
   
   The task is to select a random number from the incoming stream, ensuring the probability of 1 / n, using only O (1) additional memory.
   
   
   
3. Maximize the sum of selected numbers
   

   The sum of selected numbers. If you want to select a number, if you want, you need to add one Repeat these steps until the array gets empty. The sum of selected numbers.
   
   Note: We have to delete A _i + 1 and A _i -1 elements if I’m ₁ and A _{i – 1} .
   
   Examples:
   
   Input: a [] = {1, 2, 3}
   Output: 4
   Explanation: At first step we select 1, so 1 and 2 are deleted from the sequence leaving us with 3.
   Then we select 3 from the sequence and delete it. So the sum of selected numbers is 1 + 3 = 4.
   
   Input: a [] = {1, 2, 2, 2, 3, 4}
   Output: 10
   Explanation: Select one of the 2s, 2-1, 2 + 1 will be deleted from the 2, 2, 4, 1, 3, 1, 3, 1, and 3 are deleted. Select 2 in the last step. We get a sum of 2 + 2 + 2 + 4 = 10 which is the maximum possible.
   

   Transfer

   Given an array of N numbers, we need to select the elements with the maximum amount. For each sample of the element (A _i ), it is necessary to remove one element occurrence per unit less and one element occurrence per unit more (A _i -1) and (A _i +1) if present, and the element itself. These steps are repeated until the array is empty. The task is to ensure the maximum amount of selected items.
   It is necessary to delete elements with the value of A _i +1 and A _i -1, and not at position A _i-1 and A _{i + 1}
   
   Examples:
   
   Input: a [] = {1, 2, 3}
   Output: 4
   Explanation: In the first step, select 1, therefore, 1 and 2 are removed from the array. In the next step we take the remaining 3. The sum of the selected elements 1 + 3 = 4.
   
   Input: a [] = {1, 2, 2, 2, 3, 4}
   Output: 10
   Explanation: Select one 2 from the array - delete 1 and 3 (2-1 and 2 + 1, respectively), remain {2, 2, 4}. In the course of the next 2 steps, choose the remaining 2 and the last step, select 4. The total amount is 2 + 2 + 2 + 4 = 10, which is the maximum possible.
   

Solutions

1. Question 1

   The correct solution is suggested in the comments :
   8 -> 5 (3, 5, 0)
   5 -> 3 (3, 2, 3)
   3 -> 8 (6, 2, 0)
   5 -> 3 (6, 0, 2)
   8 -> 5 (1, 5, 2)
   5 -> 3 (1, 4, 3)
   3 -> 8 (4, 4, 0)
   
   
   
2. Question 2

   The correct solution was found in the comments .
   
   
   
3. Task 1

   They offered the right solution - sorting by calculation. The code may be, for example.
   
   
   
4. Task 2

   The decision algorithm was correctly explained in the commentary . The code could be:
   // An efficient C program to randomly select a number from stream of numbers.
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

// A function to randomly select a item from stream[0], stream[1], .. stream[i-1]
int selectRandom(int x)
{
static int res; // The resultant random number
static int count = 0; //Count of numbers visited so far in stream

count++; // increment count of numbers seen so far

// If this is the first element from stream, return it
if (count == 1)
res = x;
else
{
// Generate a random number from 0 to count - 1
int i = rand() % count;

// Replace the prev random number with new number with 1/count probability
if (i == count - 1)
res = x;
}
return res;
}

// Driver program to test above function.
int main()
{
int stream[] = {1, 2, 3, 4};
int n = sizeof(stream)/sizeof(stream[0]);

// Use a different seed value for every run.
srand(time(NULL));
for (int i = 0; i < n; ++i)
printf("Random number from first %d numbers is %d \n",
i+1, selectRandom(stream[i]));
return 0;
}

   
   
   
5. Task 3

   The correct solution was proposed, for example, here . Code:
   // CPP program to Maximize the sum of selected
// numbers by deleting three consecutive numbers.
#include <bits/stdc++.h>
using namespace std;

// function to maximize the sum of selected numbers
int maximizeSum(int a[], int n) {

// stores the occurrences of the numbers
unordered_map<int, int> ans;

// marks the occurrence of every number in the sequence
for (int i = 0; i < n; i++)
ans[a[i]]++;

// maximum in the sequence
int maximum = *max_element(a, a + n);

// traverse till maximum and apply the recurrence relation
for (int i = 2; i <= maximum; i++)
ans[i] = max(ans[i - 1], ans[i - 2] + ans[i] * i);

// return the ans stored in the index of maximum
return ans[maximum];
}

// Driver code
int main()
{
int a[] = {1, 2, 3};
int n = sizeof(a) / sizeof(a[0]);
cout << maximizeSum(a, n);
return 0;
}