# 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 :)

#### Questions

1. 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?

2. 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)

1. 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

2. 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)

3. 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

1. Question 1

2. Question 2
The correct solution was proposed.

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} */
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 */
}
``````

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

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