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

We have prepared for you a new release of IT training - with tasks from Amazon.

Below are questions and tasks for applicants for the position of a development engineer at Amazon, complexity traditionally varies from low to high. And some questions can only be solved by the most inquiring minds :) We offer to solve them to those who are preparing for an interview in a company of this level and just to test their own strengths.

#### Questions

1. Find missing int
We are given an Excel sheet which contains integers from 1 to 50, including both. However, the numbers are in a jumbled form and there is 1 integer missing. You have to identify the missing integer. Only the logic is required.

Transfer
Given an Excel spreadsheet containing numbers from 1 to 50 inclusive. The numbers are unordered, and one number is missing. It is necessary to find this number. Logic is enough to solve the problem.

2. Robots and parachutes
Two robots land with their parachutes on an infinite one-dimensional number line. They both release their parachutes as soon as they land and start moving. They are allowed only to make use of the following functions.

I. moveLeft () // robot moves to left by 1 unit in 1 unit time

II. moveRight () // robot moves to right by 1 unit in 1 unit time

III. noOperation () // robot does not move and takes 1 unit time

IV. onTopOfParachute () // returns true if the robot is standing on top of either of the parachute, else false

V. didWeMeet () // returns true if the robot meets to the other robot, else false

Write a function in order to make the robots meet each other. Robots will be executing the same copy of this function. Pseudocode is accepted.

Transfer
Two robots with parachutes land on an endless flat ribbon. Both unfasten the parachutes and begin to move. Robots can execute the following instructions:

I. moveLeft () // the robot moves to the left by 1 unit for 1 unit of time

II. moveRight () // the robot moves to the right by 1 unit for 1 unit of time

III. noOperation () // the robot waits in place 1 unit of time

IV. onTopOfParachute () // returns true if the robot is parachuting, otherwise returns false

V. didWeMeet () // returns true if the robot met another robot, otherwise false.

Write a function for meeting robots. Robots perform identical copies of this function. Pseudocode is acceptable.

1. Run length encoding
Given an input string, write a function that returns the Run Length Encoded string for the input string.

For example, if the input string is “wwwwaaadexxxxxx”, then the function should return “w4a3d1e1x6”.
Transfer
Given an input string, write a function that returns the encoding of the lengths of the series of the input string.

For example, the input string “wwwwaaadexxxxxx” should be converted to “w4a3d1e1x6”.

2. Students and chocolates
Given n boxes containing some chocolates arranged in a row. There are k number of students. The problem is to distribute maximum number of chocolates equally among k students by selecting a consecutive sequence of boxes from the given lot. Consider the boxes are arranged in a row with numbers from 1 to n from left to right. We have to select a group of boxes which are in consecutive order that could provide maximum number of chocolates equally to all the k students. An array arr [] is given representing the row arrangement of the boxes and arr [i] represents number of chocolates in that box at position 'i'.

Examples:

Input: arr [] = {2, 7, 6, 1, 4, 5}, k = 3
Output: 6
The subarray is {7, 6, 1, 4} with sum 18.
Equal distribution of 18 chocolates among
3 students is 6.
Note that the selected boxes are in consecutive order
with indexes {1, 2, 3, 4}.
Transfer
Given n boxes of chocolate stacked in a row. There are also k students present. The task is to divide the maximum possible amount of chocolate equally among students, choosing a subsequence of boxes in a row. Suppose the boxes are numbered 1 to n from left to right. We must sequentially select a group of boxes located next to each other that contain the maximum amount of chocolate, equally divided between students. The arr [] array represents boxes in a row, and the arr [i] value represents the amount of chocolate in the 'i' box.

For example:

Input: arr [] = {2, 7, 6, 1, 4, 5}, k = 3
Output: 6 (the amount of chocolate that will go to one student)
Sub-array {7, 6, 1, 4} with the sum of 18. Distributing 18 chocolates between students will give 6 shock / person. The selected box indices are {1, 2, 3, 4}.

3. Print all anagrams together
Given an array of words, print all anagrams together. For example, if the given array is {“cat”, “dog”, “tac”, “god”, “act”}, then output may be “cat tac act dog god”.
Transfer
Given an array of words, print all anagrams together. For example, in the array {"cat", "dog", "tac", "god", "act"} the output could be "cat tac act dog god".

Answers will be given within the next week - have time to decide. Good luck

#### Solutions

1. Question 1
The correct answer is given in the first comment . Also the right, under certain conditions, solution is proposed here.

2. Question 2
The correct solution was suggested by Rsa97 in this comment.

Several correct options have been suggested. Source:
``````#include
#include
#include
#define MAX_RLEN 50
/* Returns the Run Length Encoded string for the
source string src */
char *encode(char *src)
{
int rLen;
char count[MAX_RLEN];
int len = strlen(src);
/* If all characters in the source string are different,
then size of destination string would be twice of input string.
For example if the src is "abcd", then dest would be "a1b1c1d1"
For other inputs, size would be less than twice.  */
char *dest = (char *)malloc(sizeof(char)*(len*2 + 1));
int i, j = 0, k;
/* traverse the input string one by one */
for(i = 0; i < len; i++)
{
/* Copy the first occurrence of the new character */
dest[j++] = src[i];
/* Count the number of occurrences of the new character */
rLen = 1;
while(i + 1 < len && src[i] == src[i+1])
{
rLen++;
i++;
}
/* Store rLen in a character array count[] */
sprintf(count, "%d", rLen);
/* Copy the count[] to destination */
for(k = 0; *(count+k); k++, j++)
{
dest[j] = count[k];
}
}
/*terminate the destination string */
dest[j] = '\0';
return dest;
}
/*driver program to test above function */
int main()
{
char str[] = "geeksforgeeks";
char *res = encode(str);
printf("%s", res);
getchar();
}
``````

Initial solution:
``````// Java implementation to find the maximum number
// of chocolates to be distributed equally among
// k students
import java.io.*;
import java.util.*;
class GFG {
// Function to find the maximum number of chocolates
// to be distributed equally among k students
static int maxNumOfChocolates(int arr[], int n, int k)
{
// Hash table
HashMap  um = new HashMap();
// 'sum[]' to store cumulative sum, where
// sum[i] = sum(arr[0]+..arr[i])
int[] sum=new int[n];
int curr_rem;
// To store sum of sub-array having maximum sum
int maxSum = 0;
// Building up 'sum[]'
sum[0] = arr[0];
for (int i = 1; i < n; i++)
sum[i] = sum[i - 1] + arr[i];
// Traversing 'sum[]'
for (int i = 0; i < n; i++) {
// Finding current remainder
curr_rem = sum[i] % k;
// If true then sum(0..i) is divisible
// by k
if (curr_rem == 0) {
// update 'maxSum'
if (maxSum < sum[i])
maxSum = sum[i];
}
// If value 'curr_rem' not present in 'um'
// then store it in 'um' with index of its
// first occurrence
else if (!um.containsKey(curr_rem) )
um.put(curr_rem , i);
else
// If true, then update 'max'
if (maxSum < (sum[i] - sum[um.get(curr_rem)]))
maxSum = sum[i] - sum[um.get(curr_rem)];
}
// Required maximum number of chocolates to be
// distributed equally among 'k' students
return (maxSum / k);
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 2, 7, 6, 1, 4, 5 };
int n = arr.length;
int k = 3;
System.out.println("Maximum number of chocolates: "
+ maxNumOfChocolates(arr, n, k));
}
}
``````

Solution option in python:
``````# structure for each word of duplicate array
class Word(object):
def __init__(self, string, index):
self.string = string
self.index = index
# Create a DupArray object that contains an array
# of Words
def createDupArray(string, size):
dupArray = []
# One by one copy words from the given wordArray
# to dupArray
for i in xrange(size):
dupArray.append(Word(string[i], i))
return dupArray
# Given a list of words in wordArr[]
def printAnagramsTogether(wordArr, size):
# Step 1: Create a copy of all words present in
# given wordArr.
# The copy will also have orignal indexes of words
dupArray = createDupArray(wordArr, size)
# Step 2: Iterate through all words in dupArray and sort
# individual words.
for i in xrange(size):
dupArray[i].string = ''.join(sorted(dupArray[i].string))
# Step 3: Now sort the array of words in dupArray
dupArray = sorted(dupArray, key=lambda k: k.string)
# Step 4: Now all words in dupArray are together, but
# these words are changed. Use the index member of word
# struct to get the corresponding original word
for word in dupArray:
print wordArr[word.index],
# Driver program
wordArr = ["cat", "dog", "tac", "god", "act"]
size = len(wordArr)
printAnagramsTogether(wordArr, size)
``````