Added solution for the read input buffer problem.

anxious-coder-lhs · anxious-coder-lhs · commit 410707a07791 · 2020-10-11T21:35:55.000+05:30
diff --git a/README.md b/README.md
@@ -54,6 +54,7 @@ Happy to accept any contributions to this in any langugage.
 
 ## Hard
 1. [Find Missing Positive](https://leetcode.com/problems/first-missing-positive/) | [Solution](./level_hard/LeetCode_41_Hard.ts)
+2. [Read N Characters Given Read 4 II - Call Multiple Times - LeetCode 158](https://leetcode.com/problems/read-n-characters-given-read4-ii-call-multiple-times/) | [Solution 1](./level_hard/LeetCode_158_Hard.java) | [Solution 2 Optimized](./level_hard/LeetCode_158_Hard_1.java)
 
 ## Sorting
 1. Bubble Sort | [Solution](./sorting/Sort_Bubble.js)
diff --git a/level_hard/LeetCode_158_Hard.java b/level_hard/LeetCode_158_Hard.java
@@ -0,0 +1,77 @@
+/**
+ * The read4 API is defined in the parent class Reader4.
+ *     int read4(char[] buf4); 
+ */
+/**
+ * Problem: Leetcode 158
+ */
+public class Solution extends Reader4 {
+    
+    char[] buffer = new char[16];
+    int writePtr = 0;
+    int readPtr = 0;
+     
+    /**
+     * @param buf Destination buffer
+     * @param n   Number of characters to read
+     * @return    The number of actual characters read
+     */
+    public int read(char[] buf, int n) {
+        if (writePtr - readPtr >= n) {
+            // All data is already available in the buffer, read and return
+            this.copyRange(buffer, readPtr, n + readPtr, buf, 0);
+            this.readPtr += n;
+            return n;
+        } else {
+            // Not enough items are available, try to get more items into the internal buffer.
+            this.readInternal(n - (writePtr - readPtr));
+            if (writePtr - readPtr >= n) {
+                // All the n items can be fetched and updated.
+                this.copyRange(buffer, readPtr, n + readPtr, buf, 0);
+                this.readPtr += n;
+                return n;
+            } else {
+                this.copyRange(buffer, readPtr, writePtr, buf, 0);
+                int itemsRead = writePtr - readPtr;
+                this.readPtr = writePtr;
+                return itemsRead;
+            }
+        }
+    }
+    
+    private void readInternal(int n) {
+        int readItems = n % 4 == 0 ? n : (n/4 + 1) * 4;
+        
+        if (this.buffer.length < this.writePtr + readItems) {
+            this.expandInternalBuffer(this.writePtr + readItems);
+        }
+        
+        while(readItems > 0) {
+            char[] buff4 = new char[4];
+            int newItems = this.read4(buff4);
+            if (newItems == 0) break;
+            this.copyRange(buff4, 0, newItems, this.buffer, this.writePtr);
+            this.writePtr += newItems;
+            readItems -= newItems;
+        }
+    }
+    
+    private void expandInternalBuffer(int length) {
+        int newLength = (length / 16 + 1) * 16;
+        char[] newBuffer = new char[newLength];
+        this.copyRange(buffer, 0, this.writePtr, newBuffer, 0);
+        this.buffer = newBuffer;
+    }
+    
+    // Copy the items from the input buffer to the output buffer.
+    private void copyRange(char[] source,
+                     int sourceBeg,
+                     int sourceEnd,
+                     char[] target,
+                     int targetBeg) {
+        // for (int idx = sourceBeg; idx < sourceEnd; idx++) {
+        //     target[targetBeg++] = source[idx];
+        // }
+        System.arraycopy(source, sourceBeg, target, targetBeg, sourceEnd - sourceBeg);
+    }
+}
diff --git a/level_hard/LeetCode_158_Hard_1.java b/level_hard/LeetCode_158_Hard_1.java
@@ -0,0 +1,42 @@
+/**
+ * The read4 API is defined in the parent class Reader4.
+ *     int read4(char[] buf4); 
+ */
+public class Solution extends Reader4 {
+
+    /**
+     * Solution uses a buffering approach in order to read and write. The write operation
+     * continues to write the elements into the output buffer one step at a time in the iteration
+     * loop. The read step updates the internal read buffer when the internal buffer gets empty.
+     */
+    
+    private char[] intBuf = new char[4];
+    private int intBufWritePtr = 0;
+    private int intBufReadPtr = 0;
+    
+    /**
+     * @param buf Destination buffer
+     * @param n   Number of characters to read
+     * @return    The number of actual characters read
+     */
+    public int read(char[] buf, int n) {
+        
+        int writeLoc = 0;
+        
+        // Repeat adding new elements till the write location does not reach till n-1
+        while (n > writeLoc) {
+            if (intBufReadPtr < intBufWritePtr) {
+                // If there is something already existing in the input buffers, use it.
+                buf[writeLoc++] = intBuf[intBufReadPtr++];
+            } else {
+                // If not, lets fetch more items and fill the internal buffer for further use.
+                int totalItems = this.read4(intBuf);
+                intBufReadPtr = 0;
+                intBufWritePtr = totalItems;
+                if (totalItems == 0) break;
+            }
+        }
+        
+        return writeLoc;
+    }
+}
