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

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

   An Excel spreadsheet containing numbers from 1 to 50 inclusive is given. Numbers are out of order, and one number is missing. Need to find this number. Logic is enough to solve the problem.
   
   
   
2. Robots and parachutes
   

   Two robots land with one-dimensional number line. They would like to move. 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
   
   Iv. onTopOfParachute () // returns true if false
   
   V. didWeMeet () // returns true
   
   Write a function in order to make sure you meet each other. Robots will be executing the same copy of this function. Pseudocode is accepted.

   
   
   Transfer

   Two parachute robots land on an endless flat ribbon. Both unfasten parachutes and begin to move. Robots can follow these instructions:
   
   I. moveLeft () // the robot moves left 1 unit for 1 time unit
   
   Ii. moveRight () // the robot moves to the right by 1 unit for 1 unit of time
   
   Iii. noOperation () // the robot waits in place of 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 to allow robots to meet. Robots perform identical copies of this function. Pseudocode is acceptable.
   

Tasks

1. Run length encoding
   

   The length of the input string is given 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 run lengths of the input string.
   
   For example, the input string “wwwwaaadexxxxxx” should be converted to “w4a3d1e1x6”.
   
   
   
2. Students and chocolates
   

   Chocolates arranged in a row. There are k number of students. The number of cholesters should be selected. From the left to the right. The number of chocolates can be given. An array of arrays [] is representing the number of chocolates in a 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, laid in a row. There are also k students. The task is to divide the maximum possible amount of chocolate equally between students by choosing a subsequence of boxes in a row. Suppose the boxes are numbered from 1 to n from left to right. We must consistently select a group of boxes located side by side, which contain the maximum amount of chocolate divided equally between students. The arr [] array is boxes arranged in a row, and the value arr [i] 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)
   Subarray {7, 6, 1, 4} with the sum of 18. The distribution of 18 chocolates between students will give 6 shock / person. The selected mailbox 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 the output may be “cat tac act dog god”.
   

   Transfer

   Given an array of words, type all the anagrams together. For example, in the array {“cat”, “dog”, “tac”, “god”, “act”}, the output can be “cat tac act dog god”.
   
   
   

Solutions

1. Question 1

   The correct answer is given in the first comment . Also correct, under some conditions, the solution proposed here.
   
   
   
2. Question 2

   The correct solution is suggested by Rsa97 in this comment.
   
   
   
3. Task 1

   It was suggested several correct options. Source:
   

   #include<stdio.h> #include<string.h> #include<stdlib.h> #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(); } 

   
   
   
   
4. Task 2

   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 <Integer,Integer> um = new HashMap<Integer,Integer>(); // '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)); } } 

   
   
   
   
5. Task 3

   Solution 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)