Issue # 22: IT training - current issues and challenges from leading companies / Spice IT Recruitment Blog

Questions

1. Faulty machine
   

   We have 10 machines that produce screws, each weighing 1 gram. One of the machines, however, produces screws weighing 0.9 grams only. We are allowed only one weighing and need to determine which machine is faulty.

   
   
   Transfer

   We have 10 machines producing screws, each weighing 1 gram. True, one of the machines produces screws weighing 0.9 grams. We are allowed 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 in the encryption, DISTANCE is written as IDTUBECN and DOCUMENT is written as ODDVNTNE.
   
   Can you help him decipher HTTQYAD?
   

   
   
   Transfer

   Sherlock Holmes unravels 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
   

   A Research team want to establish a research center in a region where they found some rare-elements.They want to make it closest to all the rare-elements as close as possible so that they can reduce overall cost of research over there.It is given that all the rare-element's location is connected by roads.It is also given that Research Center can only be build on road.Team decided to assign this task to a coder.If you feel you have that much potential..Here is the Task: - Find the optimal position of research center from given locations of rare-elements.
   
   Locations are given in the matrix cell form where 1 represents roads and 0 no road. Number of rare-element and their location was also given (number <= 5) and order of square matrix was less than equal to (20).
   

   
   
   Transfer

   The research team wants to establish a research center in the 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 center location based on the locations of the elements.
   
   Locations are given in the form of a matrix, where 1 in the cell means the presence of the road, and 0 - its absence.
   Element locations are also given (number <= 5). The order of the square matrix <= 20.
2. Stack down or up
   

   In a typical process, a stack segment of program contains local variables along with information that is saved each time a function is called. Each time a function is called, the address of where to return to and certain information about the caller's environment, such as some of the machine registers, are saved on the stack. The newly called function then allocates room on the stack for its automatic and temporary variables.
   
   Stack may grow downward or upward depending on environment for which code is compiled, ie, depends on compiler. Write down the program to determine whether stack grows downward or upward?

   
   
   Transfer

   Typically, a program stack segment contains local variables with information that is stored every time the function is called. When a function is called, the return address and information about the environment — for example, some registers — are stored on the stack. Then the called function takes a 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, i.e. it depends on the compiler. Implement a program to determine if the stack is growing up or down.
3. Next greater element
   

   Given an array, print the Next Greater Element (NGE) for every element. The Next greater Element for an element x is the first greater element on the right side of x in array. Elements for which no greater element exist, 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 sorted in decreasing order, all elements have next greater element as -1.
   c) For the input array [4, 5, 2, 25], the next greater elements for each element are as follows.
   

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

   
   d) For the input array [13, 7, 6, 12], the next greater elements for each element are as follows.
   

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

   
   

   
   
   Transfer

   Given an array, type the next larger element (NGE) for each element. The next larger element for x is the first larger element to the right of x in the array. If such an element does not exist, NGE is -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:
   

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

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

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

   
   

Solutions

1. Question 1

   jmdorian gave the correct answer - to weigh for each machine the number of bolts equal to its number. Attention deserves the option with a balanced disk .
   
   
   
2. Question 2

   Answer: THURDAY.
   Decision principle .
   
   
   
3. Task 1

   A solution 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=0 && y 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=c.x;
       int b=c.y;
       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>ar[i][j];
       }
   }
   int q;
   cin>>q;
   P rare[q];
   int fans=10000;
   int mx=-1;
   for(int i=0;i>a>>b;
       rare[i].x=a;
       rare[i].y=b;
   }
   for(int i=0;i

   

   

4. Задача 2

   Многие ответили верно. Исходный вариант:
   

   
   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. Задача 3

   Исходный вариант решения:
   

   
   // A Stack based C++ program to find next
   // greater element for all array elements.
   #include
   using namespace std;
   /* prints element and NGE pair for all
      elements of arr[] of size n */
   void printNGE(int arr[], int n)
   {
       stack s;
       /* push the first element to stack */
       s.push(arr[0]);
       // iterate for rest of the elements
       for (int i=1; i " << 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;
   }