The longest absolute path in file system.


  • 0
    D

    take away.
    '''
    int lengthLongestPath(string input) {
    if (input.empty()) {
    return 0;
    }
    int result = 0;
    std::istringstream iss(input);
    std::string line;
    std::unordered_map<int, int> m{{0, 0}};
    while (std::getline(iss, line)) {
    int level = line.find_last_of('\t') + 1;
    int length = line.substr(level).size();
    if (line.find('.') != std::string::npos) {
    result = std::max(result, m[level] + length);
    } else {
    m[level + 1] = m[level] + length + 1;
    }
    }
    return result;
    }
    '''


  • 0
    R

    @kecen said in The longest absolute path in file system.:

    dir/subdr2/subsubdir2/file.ext

    There is a typo

    "dir/subdir2/subsubdir2/file2.ext" so ans is 32 and not 30.


  • 0
    S
    This post is deleted!

  • 0
    P

    Short javascript solution with O(n) complexity

    const countMax = (s) => {
        let acc = []
            , soFarMax = 0
            , countByDir = (n)=>/^.+\.\w+$/.test(n)?0:1
            ;
    
        s.split("\n").forEach(item => {
                let infos = /(\t*)([\w.]+)/.exec(item)
                    , level = infos[1].split("\t").length - 1
                    , name = infos[2]
                    ;
                acc[level] = (level == 0)
                    ? name.length + countByDir(name)
                    : acc[level - 1] + name.length + countByDir(name);
                soFarMax = Math.max(acc[level], soFarMax);
            }
        );
    
        return soFarMax;
    };
    

  • 1
    H

    Cleaner and Simpler !

    public int _lengthLongestPath2(String input) {
    	int maxLength = 0, pathLength = 0, currentDepth = 0, idx = 0, len = input.length();
            Stack <Integer> stk = new Stack<>();
            
            while (idx < len) {
                boolean isFile = false;
                int currentLength = 0;
                
                while (stk.size() > currentDepth) pathLength -= stk.pop();
                
                for (; idx < len && input.charAt(idx) != '\n'; idx ++, currentLength ++) 
                    if (input.charAt(idx) == '.') isFile = true;
                
                idx ++;
                if (isFile) maxLength = Math.max (maxLength, pathLength + currentLength);
                else pathLength += stk.push (currentLength + 1);
                
                for (currentDepth = 0; idx < len && input.charAt(idx) == '\t'; idx ++, currentDepth ++); 
            }
            
            return maxLength;
    }
    

  • 0
    H

    @alex.shuaibo.gaogmail.com
    here is my solution, main idea is:first split string to lines by "\n";then parse lines one by one,split line to parts by "\t", if current part is file,check and update maxPath.

    public static void main(String[] args) {
        Assert.assertEquals(getLongestPath("dir\n\tsubdir1\n\t\tfile1.ext\n\t\tsubsubdir1\n\tsubdir2\n\t\tsubsubdir2\n\t\t\tfile2.ext"),"dir/subdir2/subsubdir2/file2.ext");
        Assert.assertEquals(getLongestPath("dir\n\tsubdir1\n\tsubdir2\n\t\tfile.ext"),"dir/subdir2/file.ext");
        Assert.assertEquals(getLongestPath("dir"),"");
        Assert.assertEquals(getLongestPath(""),"");
        Assert.assertEquals(getLongestPath(null),"");
    }
    
    private static String getLongestPath(String s) {
        if (s == null || s.equals("")) { return ""; }
        String[] prefix = new String[100];
        String[] lines = s.split("\\n");
    
        String maxPath = "";
        for (String line : lines) {
            String[] parts = line.split("\\t");
            for (int i = 0; i <= parts.length - 1; i++) {
                if (!parts[i].equals("")) {
                    prefix[i] = parts[i];
                    if (parts[i].contains(".ext")) {
                        String path = getPath(prefix, i);
                        if (path.length() > maxPath.length()) {
                            maxPath = path;
                        }
                    }
                }
            }
        }
    
        return maxPath;
    }
    
    private static String getPath(String[] prefix, int i) {
        String root = prefix[0];
        for (int cur = 1; cur <= i; cur++) {
            root = String.join("/", root, prefix[cur]);
        }
        return root;
    }

  • 0

    This is my solution in JAVA using two Stacks.
    The solution runs in O(n).

    package difficultyModerate;
    
    import java.util.Stack;
    
    public class LongestAbsolutePath 
    {
    	public static void main(String[] args) 
    	{		
    		//String path = "dir\n\tsubdir1\n\t\tfile1.ext\n\t\tsubsubdir1\n\tsubdir2\n\t\tsubsubdir2\n\t\t\tfile2.ext";
    		String path = "dir\n\tsubdir1\n\tsubdir2\n\t\tfile.ext";
    		Stack<PathNode> stk = new Stack<PathNode>();
    
    		String[] lines = path.split("\n");
    		
    		 
    		for(int x=0;x<lines.length;x++)
    		{
    			int level=0;
    			String line = lines[x];
    			while(level<line.length())
    			{
    				if(line.charAt(level)=='\t')
    				{
    					level++;				
    				}
    				else
    				{
    					break;
    				}
    			}			
    			if(stk.isEmpty() || stk.peek().level<level)
    			{
    				stk.push(new PathNode(line.substring(level), level));
    			}
    			else if(stk.peek().level>=level)
    			{
    				while(stk.peek().level>=level)
    					stk.pop();
    				stk.push(new PathNode(line.substring(level), level));
    			}
    		}
    		
    		Stack<PathNode> stkTemp = new Stack<PathNode>();
    		while(!stk.empty())
    		{
    			stkTemp.push(stk.pop());
    		}
    		
    		while(!stkTemp.empty())
    		{
    			System.out.print(stkTemp.pop().data+"/");
    		}
    		
    	}
    	
    	
    }
    class PathNode
    {
    	int level;
    	String data;
    	
    	PathNode(String data, int level)
    	{
    		this.data = data;
    		this.level = level;
    	}
    }
    

  • 0
    E

    @ericfernat-gmail.com Apologies for the messy code. Could have organized the code into separate functions according to their distinct tasks, but yeah, whatever!


  • 0
    F

    Guys, passing an interview is not about just having a code that works, it's also about having a code that is readable and well written. Do not hesitate to separate tasks into other functions, and use new structures or classes when it makes sense.

    Here's my JavaScript tentative:

    function longestPath(fs) {
      // stack stores the length of the current folder's path
      const stack = [0];
      let currentLevel = -1;
      let i = 0;
      let max = 0;
    
      // Browse the file system and process each asset as they come
      while (i < fs.length) {
        const {name, level} = nextAsset(fs, i);
        i += name.length + level + 1;
        // When we reach a file, we check for maximum path length
        if (isFile(name)) {
          max = Math.max(max, stack[stack.length-1] + name.length);
          continue;
        }
    
        // When we access a child directory
        if (level > currentLevel) {
          stack.push(stack[stack.length-1] + name.length + 1);
          currentLevel = level;
        }
        // When we return to a parent directory
        else {
          let diff = currentLevel - level;
          while (diff--) { stack.pop(); }
          currentLevel = level;
        }
      }
      return max;
    }
    
    /* Extract the next asset name and its level in files hierarchy */
    function nextAsset(fs, i) {
      let name = '';
      let level = 0;
      while (i < fs.length && fs[i] !== '\n') {
        if (fs[i] === '\t') { level++; } else { name += fs[i]; }
        i++;
      }
      return {level, name};
    }
    
    function isFile(name) {
      return !!name.match(/.+\..+/);
    };
    
    longestPath('dir\n\tsubdir1\n\t\tfile1.ext\n\t\tsubsubdir1\n\tsubdir2\n\t\tsubsubdir2\n\t\t\tfile2.ext');
    // returns 32
    

    PS: The example given in OP message is wrong, result is 32 because they are a couple of types.


Log in to reply