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

Questions

1. Dominos on the chessboard
   

   There is an 8 by 8 chessboard in which there are diagonally opposite corners. You are given 31 dominos, and a single domino can cover exactly two squares. Can you use the 31 dominos to cover the entire board?
   

   
   
   Transfer

   In an ordinary chessboard, two diagonally opposed cells are cut off. You are given 31 dominoes. One bone covers exactly 2 chess cells. Can you cover the whole field with these bones?
   
   
   
2. Gold for work
   

   You can’t get to know them. For every day. If you’re not allowed to pay your worker (Assuming the amount of work for each day)
   

   
   
   Transfer

   Someone works for you for seven days with payment for work in a bar of gold. You must pay the employee daily at the end of the day. How will you settle with an employee if you are allowed to break an ingot only twice? (It is assumed that the same amount of work is done every day, requiring the same pay)
   
   
   

Tasks

1. Reverse a linked list
   

   The list is a list of We need to reverse the list by changing links between nodes.
   ')
   Examples:
   
   Input: Head of following linked list
   1-> 2-> 3-> 4-> NULL
   Output: Linked list should be changed to,
   4-> 3-> 2-> 1-> NULL
   
   Input: Head of following linked list
   1-> 2-> 3-> 4-> 5-> NULL
   Output: Linked list should be changed to,
   5-> 4-> 3-> 2-> 1-> NULL
   
   Input: NULL
   Output: NULL
   
   Input: 1-> NULL
   Output: 1-> NULL
   
   

   
   
   Transfer

   A pointer to the head node of the linked list is given, the task is to convert the list to the reverse one. You need to change pointers between nodes.
   
   Examples:
   Input: Pointer to the head node, and the list itself - 1-> 2-> 3-> 4-> NULL
   Output: 4-> 3-> 2-> 1-> NULL
   
   Input: 1-> 2-> 3-> 4-> 5-> NULL
   Output: 5-> 4-> 3-> 2-> 1-> NULL
   
   Login: NULL
   Output: NULL
   
   Input: 1-> NULL
   Output: 1-> NULL
   
   
   
2. Longest bitonic subsequence
   

   Given an array of arr [0 ... n-1] containing a number of positive integers, it is a bit of a sequence. The bit of the longest bitonic subsequence.
   A sequence, sorted ordering is considered bitonic with the decreasing part as empty. Similarly, the decreasing order sequence is considered.
   
   Examples:
   
   Input arr [] = {1, 11, 2, 10, 4, 5, 2, 1};
   Output: 6 (A Longest Bitonic Subsequence of length 6 is 1, 2, 10, 4, 2, 1)
   
   Input arr [] = {12, 11, 40, 5, 3, 1}
   Output: 5 (A Longest Bitonic Subsequence of length 5 is 12, 11, 5, 3, 1)
   
   Input arr [] = {80, 60, 30, 40, 20, 10}
   Output: 5 (A Longest Bitonic Subsequence of length 5 is 80, 60, 30, 20, 10)
   

   
   
   Transfer

   I will give the array arr [0 ... n-1] containing n positive integers. We call a subsequence arr [] “Bitonic” if the elements in it first increase, then decrease. Write a function that takes an array as an argument and returns the length of the longest biton subsequence.
   The sequence, sorted in ascending order, is considered to be a bitonic with a missing descending part.
   Similarly, a sequence sorted in descending order is considered to be bitone, with no missing part.
   
   Example:
   
   Input: arr [] = {1, 11, 2, 10, 4, 5, 2, 1};
   Output: 6 (Length of the longest biton subsequence - 6 {1, 2, 10, 4, 2, 1})
   
   Input: arr [] = {12, 11, 40, 5, 3, 1}
   Output: 5 (12, 11, 5, 3, 1)
   
   Input: arr [] = {80, 60, 30, 40, 20, 10}
   Output: 5 (80, 60, 30, 20, 10)
   
   
   
3. Inplace transformation
   

   Given a string, move all even elements of elements to end of string. For all the elements of space and space for movement.
   In this case, it should be converted to [abcd1234].
   

   
   
   Transfer

   Given a string, you must move all elements that are in the even position to the end of the string. When moving elements, it is necessary to preserve the relative order of elements, even and odd. Limitations are O (1) memory and O (n) runtime.
   In other words, a string with alternating elements (numbers and letters), for example [a1b2c3d4] should be converted to [abcd1234].
   
   
   

Solutions

1. Question 1

   No, kardan2 answered why.
   
   
   
2. Question 2

   It was suggested the right decision
   
   
   
3. Task 1

   The comments suggested the correct solution. Initial option:
   
   

   void ReverseRecursive(struct Node** head_ref) { struct Node* first; struct Node* rest; /* empty list */ if (*head_ref == NULL) return; /* suppose first = {1, 2, 3}, rest = {2, 3} */ first = *head_ref; rest = first->next; /* List has only one node */ if (rest == NULL) return; /* reverse the rest list and put the first element at the end */ recursiveReverse(&rest); first->next->next = first; /* tricky step -- see the diagram */ first->next = NULL; /* fix the head pointer */ *head_ref = rest; } 

   
   
   
   
4. Task 2

   Solution option:
   

    using System; class LBS { /* lbs() returns the length of the Longest Bitonic Subsequence in arr[] of size n. The function mainly creates two temporary arrays lis[] and lds[] and returns the maximum lis[i] + lds[i] - 1. lis[i] ==> Longest Increasing subsequence ending with arr[i] lds[i] ==> Longest decreasing subsequence starting with arr[i] */ static int lbs(int[] arr, int n) { int i, j; /* Allocate memory for LIS[] and initialize LIS values as 1 for all indexes */ int[] lis = new int[n]; for (i = 0; i < n; i++) lis[i] = 1; /* Compute LIS values from left to right */ for (i = 1; i < n; i++) for (j = 0; j < i; j++) if (arr[i] > arr[j] && lis[i] < lis[j] + 1) lis[i] = lis[j] + 1; /* Allocate memory for lds and initialize LDS values for all indexes */ int[] lds = new int[n]; for (i = 0; i < n; i++) lds[i] = 1; /* Compute LDS values from right to left */ for (i = n - 2; i >= 0; i--) for (j = n - 1; j > i; j--) if (arr[i] > arr[j] && lds[i] < lds[j] + 1) lds[i] = lds[j] + 1; /* Return the maximum value of lis[i] + lds[i] - 1*/ int max = lis[0] + lds[0] - 1; for (i = 1; i < n; i++) if (lis[i] + lds[i] - 1 > max) max = lis[i] + lds[i] - 1; return max; } // Driver code public static void Main() { int[] arr = { 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15 }; int n = arr.Length; Console.WriteLine("Length of LBS is " + lbs(arr, n)); } } 

   
   
   
   
5. Task 3

   Solution option:
   

    #include <stdio.h> #include <string.h> #include <math.h> // A utility function to swap characters void swap ( char* a, char* b ) { char t = *a; *a = *b; *b = t; } // A utility function to reverse string str[low..high] void reverse ( char* str, int low, int high ) { while ( low < high ) { swap( &str[low], &str[high] ); ++low; --high; } } // Cycle leader algorithm to move all even positioned elements // at the end. void cycleLeader ( char* str, int shift, int len ) { int j; char item; for (int i = 1; i < len; i *= 3 ) { j = i; item = str[j + shift]; do { // odd index if ( j & 1 ) j = len / 2 + j / 2; // even index else j /= 2; // keep the back-up of element at new position swap (&str[j + shift], &item); } while ( j != i ); } } // The main function to transform a string. This function mainly uses // cycleLeader() to transform void moveNumberToSecondHalf( char* str ) { int k, lenFirst; int lenRemaining = strlen( str ); int shift = 0; while ( lenRemaining ) { k = 0; // Step 1: Find the largest prefix subarray of the form 3^k + 1 while ( pow( 3, k ) + 1 <= lenRemaining ) k++; lenFirst = pow( 3, k - 1 ) + 1; lenRemaining -= lenFirst; // Step 2: Apply cycle leader algorithm for the largest subarrau cycleLeader ( str, shift, lenFirst ); // Step 4.1: Reverse the second half of first subarray reverse ( str, shift / 2, shift - 1 ); // Step 4.2: Reverse the first half of second sub-string. reverse ( str, shift, shift + lenFirst / 2 - 1 ); // Step 4.3 Reverse the second half of first sub-string and first // half of second sub-string together reverse ( str, shift / 2, shift + lenFirst / 2 - 1 ); // Increase the length of first subarray shift += lenFirst; } } // Driver program to test above function int main() { char str[] = "a1b2c3d4e5f6g7"; moveNumberToSecondHalf( str ); printf( "%s", str ); return 0; }