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

   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.
   

Tasks

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

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

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

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

   
   
   
   
5. Task 3

   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)