Read N Characters Given Read4 ll - Call Multiple Times

Moderate
0/80
Average time to solve is 25m
profile
Contributed by
4 upvotes
Asked in company
Uber

Problem statement

Ninja has been given a file ‘FILE’ that can be read using a given method, ‘READ4’. Ninja has to implement a method ‘READ’, which reads ’N’ characters from the ‘FILE’ using the ‘READ4’ method.

How ‘READ4’ and ‘READ’ method’s work:

‘READ4(char ‘BUFFER[]’)’

 1) It reads 4 characters at a time from the ‘FILE’.
 2) The return value of the ‘READ4’ method is the actual number of characters read.
 3) For example, if in a ‘FILE’ only three characters are remaining, then it returns 3.

‘READ(char ‘BUFFER[]’, int ‘N’)’

 1) ‘N’ represents the number of characters to be read from ‘FILE’.
 2) In this method, you have to store your result in ‘BUFFER’.
 3) In this method, you have to return the number of characters read from ‘FILE’.

Note: The method ‘READ’ may be called multiple times.

For example:

‘FILE’ = “abcdef”

Initially file pointer ‘FP’ points to ‘a’.
‘READ4(BUFFER) returns 4 and ‘BUFFER’ contains “abcd”, Now the ‘FP’ points to ‘e’.
‘READ4(BUFFER) returns 2 and ‘BUFFER’ contains “ef”, Now the ‘FP’ points to the end of the ‘FILE’.
Detailed explanation ( Input/output format, Notes, Images )
Input Format 
The first line of input contains an integer ‘T’ which denotes the number of test cases or queries to be run. Then the test cases follow.

The first line of each test case contains a string ‘FILE’ which represents a file that Ninja has to read.

The next line of each test case contains an integer ‘Q’, representing how many times the ‘READ’ function is called.

The next lines of each test case contain ‘Q’ space-separated integers which represent how many characters are to be read from the ‘FILE’.
Output Format : 
For each test case, print the number of characters and actual characters which are read by Ninja from the ‘FILE’. 

Print the output of each test case in a separate line.

Note:

You do not need to print anything; it has already been taken care 
of. Just implement the given function.
Constraints: 
1 <= ‘T’ <= 100
1 <= |’FILE’| <= 5000
‘FILE[i]’ = {‘a’ to ‘z’}

Where ‘T’ denotes the total number of test cases, ‘FILE’  represents the file that Ninja has to read, and |’FILE’| represents the length of the ‘FILE’.

Time Limit: 1 second
Sample Input 1:
2
abcdefgh
2
6 4
ffggdd
4
3 4 5 2
Sample Output 1:
6 abcdef
2 gh
3 ffg
3 gdd
0  
0

Explanation For Sample Input 1:

For sample test case 1: 

In this test case, ‘FILE’ is “abcdefgh” and initially the file pointer ‘FP’ points to ‘a’ (0-index). First, we have to read 6 characters from the file.

First, we call the ‘READ4(‘BUFFER’)’ method, it returns 4 and the ‘BUFFER’ contains “abcd”.
Then we again call the ‘READ4(‘BUFFER’)’ method, it returns 4 and now the ‘BUFFER’ contains “efgh”. 
Then, we print the first 6 characters of the ‘FILE’ i.e. “abcedef”.

Second, we have to read 4 characters from the file.
But there are only two characters are remaining so we print only these two characters i.e. “gh”.

For sample test case 2: 

In this test case, ‘FILE’ is “ffggdd” and initially the file pointer ‘FP’ 
points to “f” (0-index). First, we have to read 3 characters from the file.

First, we call the ‘READ4(‘BUFFER’)’ method, it returns 4 and the ‘BUFFER’ contains “ffgg”.
Then, we print the first 3 characters of the ‘FILE’ i.e. “ffg”.

Second, we have to read 4 characters from the file.
Now in ‘BUFFER’, we have only one character remaining. So we again call the ‘READ4(‘BUFFER’)’ method, it returns 2 and now the ‘BUFFER’ contains “dd”.
As we know we have to print the next characters of the ‘FILE’ but only 3 characters are remaining in the ‘FILE’ so we print these 3 characters only i.e. “gdd”.

Third, we have to read 5 characters from the file.
As we know we read all the characters of the ‘FILE’. 
Now the file pointer ‘FP’ points to the end of the file so we print an empty string.

Fourth, we have to read 2 characters from the file.
As we know we read all the characters of the ‘FILE’. 
Now the file pointer ‘FP’ points to the end of the file so we print an empty string.
Sample Input 2:
2
abcd
1
2
psadas
2 
3 4
Sample Output 2:
2 ab
3 psa
3 das
Hint

Think of the Brute Force Approach.

Approaches (1)
Brute Force

As we know, we have to implement the ‘READ’ method using the ‘READ4’ method. 

So first, we call the ‘READ4’ method and pass a ‘TEMP_BUFFER’ array/list of 4 sizes. And this method returns the number of characters reads from the ‘FILE’ and all these characters are stored in this ‘TEMP_BUFFER’ array/list. When we read the ‘N’ characters from the ‘FILE’ we return the number of actual characters that are read from ‘FILE’.


 

As we know, the ‘READ’ method is called any number of times. So we have to store the remaining characters of the ‘TEMP_BUFFER’ array/list also. So that's why we declare this ‘TEMP_BUFFER’ array/list as a global variable.

 

Here is the algorithm:

 

  1. We declare an array/list ‘TEMP_BUFFER’ of size 4 in which we store the current 4 characters of the ‘FILE’.
  2. We declare two variables ‘TEMP_POINTER’ and ‘TEMP_COUNT’ where ‘TEMP_POINTER’ points to the location of the current character in ‘TEMP_BUFFER’ and  ‘TEMP_COUNT’ stores how many characters are present in ‘TEMP_BUFFER’.
  3. We declare a variable ‘COUNTER’ which represents the number of characters read from the ‘FILE’.
  4. We run a loop while ‘COUNTER’ less than ‘N’:
    • If ‘TEMP_POINTER’ == 0:
      • ‘TEMP_COUNT’ = ‘READ4[‘TEMP_BUFFER’].
    • If ‘TEMP_COUNT’ == 0:
      • Break.
    • We run a loop while ‘COUNTER’ less than ‘N’ and ‘TEMP_POINTER’ less than ‘TEMP_COUNT’:
      • BUFFER[POINTER] =  ‘TEMP_BUFFER[‘TEMP_POINTER’]’
      • POINTER.
      • ‘TEMP_POINTER’.
    • If ‘TEMP_POINTER’ equal to ‘TEMP_COUNT’:
      • ‘TEMP_POINTER’ = 0.
  5. Return ‘COUNTER’.
Time Complexity

O(N)  where ‘N’ represents the length of ‘FILE’.


Because to read the ‘FILE’ we have to traverse the ‘FILE’ once. Hence the time complexity is O(N).

Space Complexity

O(1).


Because we are using only a ‘TEMP_BUFFER’ array/list which is of size 4. So the overall space complexity is constant or we can also say O(1).

Code Solution
(100% EXP penalty)
Read N Characters Given Read4 ll - Call Multiple Times
Full screen
Console