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

The next issue of the IT training arrived, and today in the issue are tasks from Microsoft interviewers.

The selection includes tasks from Microsoft interviews. Difficulty, traditionally, ranges from simple to those that need a little reflection. We prefer to do this in a relaxed atmosphere than in a time pressure during an interview, and we wish your interviews to be held just as calmly, relaxedly and constructively :)

The selection includes tasks from Microsoft interviews. Difficulty, traditionally, ranges from simple to those that need a little reflection. We prefer to do this in a relaxed atmosphere than in a time pressure during an interview, and we wish your interviews to be held just as calmly, relaxedly and constructively :)

#### Questions

**Dominos on the chessboard**There is an 8 by 8 chessboard in which two diagonally opposite corners have been cut off. 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 a regular chessboard, two diagonally opposite cells are cut off. You have been given 31 dominoes. One bone covers exactly 2 chess cells. Can you cover the whole field with these seeds?**Gold for work**You've got someone working for you for seven days and a gold bar to pay them. You must pay the worker for their work at the end of every day. If you are only allowed to make two breaks in the gold bar, how do you pay your worker? (Assuming equal amount of work is done during each day thus requiring equal amount of pay for each day)

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

#### Tasks

**Reverse a linked list**Given pointer to the head node of a linked list, the task is to reverse the linked list. We need to reverse the list by changing links between nodes.

Examples:

Input: Head of the following linked list

1-> 2-> 3-> 4-> NULL

Output: Linked list should be changed to,

4-> 3-> 2-> 1-> NULL

Input: Head of the 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 a linked list is given, the task is to convert the list to the reverse one. You need to change the pointers between the 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

Input: NULL

Output: NULL

Input: 1-> NULL

Output: 1-> NULL**Longest bitonic subsequence**Given an array arr [0 ... n-1] containing n positive integers, a subsequence of arr [] is called Bitonic if it is first increasing, then decreasing. Write a function that takes an array as argument and returns the length of the longest bitonic subsequence.

A sequence, sorted in increasing order is considered Bitonic with the decreasing part as empty. Similarly, decreasing order sequence is considered Bitonic with the increasing part as empty.

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 an array arr [0 ... n-1] containing n positive integers. We call the 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 bitwise subsequence.

A sequence sorted in ascending order is considered to be bitonic with no decreasing part.

Similarly, a sequence sorted in descending order is considered to be bitone, with no increasing part.

Example:

Input: arr [] = {1, 11, 2, 10, 4, 5, 2, 1};

Output: 6 (The length of the largest bitone subsequence is 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)**Inplace transformation**Given a string, move all even positioned elements to end of string. While moving elements, keep the relative order of all even positioned and odd positioned elements same with O (1) space and O (n) time.

In other words given a string with alternating elements (numbers and letters) like this [a1b2c3d4] should be converted to [abcd1234].**Transfer**Given a line, it is necessary to shift all elements located in an even position to the end of the line. When moving elements, it is necessary to maintain 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], must be converted to [abcd1234].

#### Solutions

**Question 2****Task 1**A correct solution was suggested in the comments. 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; }`

**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)); } }`

**Task 3**Solution Option:`#include`

#include #include // 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; }