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

Questions

1. Faulty machine
   

   Weighing 1 gram. One of the machines, however, produces weighing weighing 0.9 grams only. It is allowed.

   
   
   Transfer

   We have 10 machines that produce screws, each weighing 1 gram. True, one of the machines produces screws weighing 0.9 grams. We are allowed to make only one weighing ( approx. Screws ) to find a machine that produces defective screws.
   
2. Holmes and cipher
   

   Sherlock Holmes was decoding an encrypted message. If it is in the form of encryption, it is a DISTANCE and it is written as ODDVNTNE.
   
   Can you help him decipher HTTQYAD?
   

   
   
   Transfer

   Sherlock Holmes solves an encrypted message. In the cipher, DISTANCE is designated as IDTUBECN, and DOCUMENT - as ODDVNTNE.
   
   Can you help him decrypt HTTQYAD?

Tasks

1. Research center and rare elements
   

   If you want to find out how to do it, you can’t get it. If you’ve been on the road, you’ve been able to build it up. Task: - from the location of rare-elements.
   ')
   Locations are given in the matrix cell form where the 1 represents the roads and 0 no road. The number of rare-and-a-half-numbers was not given to (20).
   

   
   
   Transfer

   The research team wants to establish a research center in a region where some rare elements are found. They want to place it as close as possible to all sources of elements in order to reduce overall costs. Sources of elements are connected by roads. Also, a research center can only be built near the road. The team decides to entrust the task to the developer, and if you feel your potential - find the optimal location of the center, based on the locations of the elements.
   
   Locations are given in the form of a matrix, where 1 in the cell indicates the presence of a road, and 0 - its absence.
   Also given are locations of elments (<= 5). The order of the square matrix is ​​<= 20.
2. Stack down or up
   

   This is a function that has been saved. It’s a time when you’ve saved it. This is a function of
   
   It can be compiled, that is, depends on the compiler. Write downward or upward?

   
   
   Transfer

   Usually, a program stack segment contains local variables with information stored each time a function is called. When a function is called, the return address and the information about the environment are saved to the stack — for example, some registers. The called function then takes its place on the stack for its automatic and temporary variables.
   
   The stack can grow up or down depending on the environment for which the code is compiled, that is, it depends on the compiler. Implement a program to determine if the stack is growing down or up.
3. Next greater element
   

   Given an array, print the Next Greater Element (NGE) for every element. There is no need for more information. Consider, consider next greater element as -1.
   
   Examples:
   a) For any array, rightmost element always has next greater element as -1.
   b) for an array which is the sorted in decreasing order, all elements have the next greater element as -1.
   c) For the input array [4, 5, 2, 25],
   

    Element nge
       4 -> 5
       5 -> 25
       2 -> 25
       25 -> -1
   

   
   d) For the input array [13, 7, 6, 12],
   

      Element nge
       13 -> -1
       7 -> 12
       6 -> 12
       12 -> -1
   

   
   

   
   
   Transfer

   Given an array, type the next larger element (NGE) for each of the elements. The next big element for x is the first big element on the right side of x in the array. If there is no such element, NGE is considered -1.
   Examples:
   a) For any array, the rightmost element always has NGE = -1.
   b) For any array sorted in descending order, all elements have NGE = -1.
   c) For array elements [4, 5, 2, 25] NGE will be as follows:
   

    Element nge
       4 -> 5
       5 -> 25
       2 -> 25
       25 -> -1
   

   
   d) For array elements [13, 7, 6, 12], NGE will be as follows:
   

     Element nge
       13 -> -1
       7 -> 12
       6 -> 12
       12 -> -1
   

   
   

Solutions

1. Question 1

   jmdorian gave the correct answer - weigh for each car the number of bolts equal to its number. Also noteworthy is the version with a balanced disk .
   
   
   
2. Question 2

   Answer: THURDAY.
   Principle of the decision .
   
   
   
3. Task 1

   Solution option with potential for optimization:
   

   using namespace std ; bool ar[21][21]; bool visited[21][21]; int ans[21][21]; int xa[]={0,-1,0,1}; int yb[]={1,0,-1,0}; int n; typedef struct Point{ int x,y; }P; typedef struct C { int x,y; int dis; } C; bool issafe(int x,int y) { return (x>=0 && x<n &&="" y="">=0 && y<n && ar[x][y] && !visited[x][y]); } void bfs(int x,int y) { queue<c> q; C in; in.x=x; in.y=y; in.dis=0; q.push(in); visited[x][y]=1; while(!q.empty()) { C c=q.front(); q.pop(); int a=cx; int b=cy; int d=c.dis; ans[a][b]=d; for(int i=0;i<4;i++) { int nx=a+xa[i]; int ny=b+yb[i]; if(issafe(nx,ny)) { visited[nx][ny]=1; in.x=nx; in.y=ny; in.dis=d+1; q.push(in); } } } } int main() { cin>>n; for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { cin>>ar[i][j]; } } int q; cin>>q; P rare[q]; int fans=10000; int mx=-1; for(int i=0;i<q;i++) { int a,b; cin>>a>>b; rare[i].x=a; rare[i].y=b; } for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { memset(ans,10000,sizeof(ans)); int flag=0; memset(visited,0,sizeof(visited)); mx=-1; if(ar[i][j]) { bfs(i,j); for(int k=0;k<q;k++) { if(ans[rare[k].x][rare[k].y]==10000) { flag=1; break; } } if(!flag) { for(int k=0;k<q;k++) { mx=max(mx,ans[rare[k].x][rare[k].y]); } } fans=min(fans,mx); } } } cout<<fans<<endl; } 

   
   
   
   
4. Task 2

   Many answered correctly. Initial option:
   

    void stupdown(int *main_local_addr) { int fun_local; if (main_local_addr < &fun_local) printf("Stack grows upward\n"); else printf("Stack grows downward\n"); } int main() { // st's local variable int main_local; stupdown(&main_local); return 0; } 

   
   
   
   
5. Task 3

   Initial solution:
   

    // A Stack based C++ program to find next // greater element for all array elements. #include<bits/stdc++.h> using namespace std; /* prints element and NGE pair for all elements of arr[] of size n */ void printNGE(int arr[], int n) { stack<int> s; /* push the first element to stack */ s.push(arr[0]); // iterate for rest of the elements for (int i=1; i<n; i++) { int next = arr[i]; if (s.empty() == false) { // if stack is not empty, then // pop an element from stack int element = s.top(); s.pop(); /* If the popped element is smaller than next, then a) print the pair b) keep popping while elements are smaller and stack is not empty */ while (element < next) { cout << element << " --> " << next << endl; if (s.empty() == true) break; element = s.top(); s.pop(); } /* If element is greater than next, then push the element back */ if (element > next) s.push(element); } /* push next to stack so that we can find next greater for it */ s.push(next); } /* After iterating over the loop, the remaining elements in stack do not have the next greater element, so print -1 for them */ while (s.empty() == false) { cout << s.top() << " --> " << -1 << endl; s.pop(); } } /* Driver program to test above functions */ int main() { int arr[] = {11, 13, 21, 3}; int n = sizeof(arr)/sizeof(arr[0]); printNGE(arr, n); return 0; }