package com.fishercoder.solutions;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class _609 {

    public static class Solution1 {
        public List<List<String>> findDuplicate(String[] paths) {
            Map<String, List<String>> map = new HashMap<>();//key is the file content, value is the list of directories that has this directory/file
            for (String path : paths) {
                String[] dirAndFiles = path.split(" ");
                for (int i = 1; i < dirAndFiles.length; i++) {
                    String content = dirAndFiles[i].substring(dirAndFiles[i].indexOf("(") + 1, dirAndFiles[i].indexOf(")"));
                    if (!map.containsKey(content)) {
                        map.put(content, new ArrayList<>());
                    }
                    List<String> dirs = map.get(content);
                    dirs.add(dirAndFiles[0] + "/" + dirAndFiles[i].substring(0, dirAndFiles[i].indexOf("(")));
                    map.put(content, dirs);
                }
            }

            List<List<String>> result = new ArrayList<>();
            for (String content : map.keySet()) {
                if (map.get(content).size() > 1) {
                    List<String> dupFile = new ArrayList<>();
                    for (String dir : map.get(content)) {
                        dupFile.add(dir);
                    }
                    result.add(dupFile);
                }
            }
            return result;
        }
    }

    /**Answers to follow-up questions:
     * 1. Imagine you are given a real file system, how will you search files? DFS or BFS ?
     * A: Both BFS and DFS could do the work, but BFS will use extra memory, however, BFS takes advantage of memory locality, so BFS could be faster.
     *
     * 2. If the file content is very large (GB level), how will you modify your solution?
     * A: We'll fist map all files according to their sizes, since files with different sizes are guaranteed to be different, then
     * we can hash a small part of the files using MD5, SHA256, etc. Only when their md5 or sha256 is the same, we'll compare the contents byte by byte.
     *
     * 3. If you can only read the file by 1kb each time, how will you modify your solution?
     * A: This is not going to change the solution, we can hash this 1kb chunk, and then also only compare byte by byte when it's necessary.
     *
     * 4. What is the time complexity of your modified solution? What is the most time consuming part and memory consuming part of it? How to optimize?
     * A: O(n^2*k), in the worst time, we'll have to compare the file with every other file, k is the length of the file.
     * Comparing the file (by size, by hash and eventually byte by byte) is the most time consuming part.
     * Generating hash for every file will be the most memory consuming part.
     *
     * 5. How to make sure the duplicated files you find are not false positive?
     * A: Size comparision, hash detection, byte by byte check, etc. will pretty sure to rule out false positive.
     * */

}

@@ -290,17 +290,24 @@
 tring%3E%3E 
-m
+contentM
 ap = new
@@ -323,96 +323,8 @@
 %3E();
-//key is the file content, value is the list of directories that has this directory/file
 %0A   
@@ -385,26 +385,23 @@
 tring%5B%5D 
-dirAndFile
+content
 s = path
@@ -413,16 +413,71 @@
 t(%22 %22);%0A
+                List%3CString%3E list = new ArrayList%3C%3E();%0A
         
@@ -504,26 +504,23 @@
  1; i %3C 
-dirAndFile
+content
 s.length
@@ -552,110 +552,218 @@
     
-String content = dirAndFiles%5Bi%5D.substring(dirAndFiles%5Bi%5D.indexOf(%22(%22) + 1, dirAndFiles%5Bi%5D.indexOf(%22)%22)
+list.add(contents%5Bi%5D);%0A                    int start = contents%5Bi%5D.indexOf('(');%0A                    int end = contents%5Bi%5D.indexOf(')');%0A                    String content = contents%5Bi%5D.substring(start + 1, end
 );%0A 
@@ -786,17 +786,24 @@
    if (!
-m
+contentM
 ap.conta
@@ -837,33 +837,40 @@
                 
-m
+contentM
 ap.put(content, 
@@ -949,15 +949,26 @@
 g%3E d
-irs = m
+upFiles = contentM
 ap.g
@@ -1005,26 +1005,27 @@
    d
-irs.add(dirAndFile
+upFiles.add(content
 s%5B0%5D
@@ -1033,26 +1033,23 @@
 + %22/%22 + 
-dirAndFile
+content
 s%5Bi%5D.sub
@@ -1062,80 +1062,14 @@
 (0, 
-dirAndFiles%5Bi%5D.indexOf(%22(%22)));%0A                    map.put(content, dirs
+start)
 );%0A 
@@ -1095,25 +1095,24 @@
           %7D%0A
-%0A
             
@@ -1181,24 +1181,30 @@
  (String
+ key :
  content
  : map.k
@@ -1195,20 +1195,17 @@
  content
- : m
+M
 ap.keySe
@@ -1235,281 +1235,41 @@
 if (
-map.get(content).size() %3E 1) %7B%0A                    List%3CString%3E dupFile = new ArrayList%3C%3E();%0A                    for (String dir : map.get(content)) %7B%0A                        dupFile.add(dir);%0A                    %7D%0A                    result.add(dupFile);%0A                %7D
+contentMap.get(key).size() %3E 1) %7B
 %0A   
@@ -1265,38 +1265,32 @@
  %3E 1) %7B%0A        
-    %7D%0A
             retu
@@ -1291,1618 +1291,112 @@
   re
-turn result;%0A        %7D%0A    %7D%0A%0A    /**Answers to follow-up questions:%0A     * 1. Imagine you are given a real file system, how will you search files? DFS or BFS ?%0A     * A: Both BFS and DFS could do the work, but BFS will use extra memory, however, BFS takes advantage of memory locality, so BFS could be faster.%0A     *%0A     * 2. If the file content is very large (GB level), how will you modify your solution?%0A     * A: We'll fist map all files according to their sizes, since files with different sizes are guaranteed to be different, then%0A     * we can hash a small part of the files using MD5, SHA256, etc. Only when their md5 or sha256 is the same, we'll compare the contents byte by byte.%0A     *%0A     * 3. If you can only read the file by 1kb each time, how will you modify your solution?%0A     * A: This is not going to change the solution, we can hash this 1kb chunk, and then also only compare byte by byte when it's necessary.
+sult.add(contentMap.get(key));
 %0A     
-*%0A
      
-* 4. What is the time complexity of your modified solution? What is the most time consuming part and memory consuming part of it? How to optimize?%0A     * A: O(n%5E2*k), in the worst time, we'll have to compare the file with every other file, k is the length of the file.%0A     * Comparing the file (by size, by hash and eventually byte by byte) is the most time consuming part.%0A     * Generating hash for every file will be the most memory consuming part.%0A     *%0A     * 5. How to make sure the duplicated files you find are not false positive?%0A     * A: Size comparision, hash detection, byte by byte check, etc. will pretty sure to rule out false positive.%0A     * */%0A
+      %7D%0A            %7D%0A            return result;%0A        %7D%0A    %7D
 %0A%7D%0A

refactor 609