The longest absolute path in file system.


  • 0
    E

    So I gave this a try with Javascript...:
    The idea was to build a hierarchy, keeping track of the max length / filepath along the way.

    You'd only ever need to grab the last one from the previous hierarchy, so that comparison shouldn't factor into the time complexity. The outermost loop goes through all of the characters once, so it should be O(n) - if I somehow got that wrong, please let me know!

      var longestPath = function(dirString) {
        var dirs = [];
        var startIndex = 0;
        var level = 0;
        var name, dir, maxLength = -1;
        var maxPath = prevPath = "";
    
        dirString += '\n';
        for (var i=0; i<dirString.length; i++) {
          if (dirString[i] == '\t') {
            level++;
            startIndex++;
          }
          if (dirString[i] == '\n') { // found a name
            name = dirString.substr(startIndex, i - startIndex);
    
            var dir = dirs;
            for (var j=0; j<level; j++) {
              prevPath = dir[dir.length-1].path;
              dir = dir[dir.length-1].li;
            }
            pathName = prevPath ? prevPath + '/' + name : name;
            dir.push({'path': pathName, 'li': []});
    
            level = 0;
            startIndex = i + 1;
    
            if ( pathName.length > maxLength ) {
              maxLength = pathName.length;
              maxPath = pathName;
            }
          }
        }
        return maxPath;
      };
    

  • 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;
    }
    '''


  • 2
    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.


  • 0
    K

    Here's my solution using a stack:

    import java.util.Stack;
    
    public class LongestAbsolutePath {
       public static void main(String[] args) {
          String input1 = "dir\n\tsubdir1\n\tsubdir2\n\t\tfile.ext";
          String input2 = "dir\n\tsubdir1\n\t\tfile1.ext\n\t\tsubsubdir1\n\tsubdir2\n\t\tsubsubdir2\n\t\t\tfile2.ext";
          LongestAbsolutePath longestAbsolutePath = new LongestAbsolutePath();
          System.out.println(longestAbsolutePath.getLongestAbsolutePath(null));
          System.out.println(longestAbsolutePath.getLongestAbsolutePath(input1));
          System.out.println(longestAbsolutePath.getLongestAbsolutePath(input2));
       }
    
       public int getLongestAbsolutePath(String input) {
          if (input == null || input.length() == 0)
             return 0;
          Stack<String> stack = new Stack<String>();
          int prevTabs = 0;
          int clength = 0;
          int maxLength = 0;
          for (String path : input.split("\n")) {
             String sanePath = path.replaceAll("\t", "");
             int noOfTabs = path.length() - sanePath.length();
    
             int pops = prevTabs - noOfTabs;
    
             for (int i = 0; i <= pops && stack.size() > 0; i++) {
                String popped = stack.pop();
                clength -= popped.length();
             }
    
             stack.push(sanePath);
             clength += sanePath.length();
    
             if (maxLength < clength) {
                maxLength = clength;
             }
    
             prevTabs = noOfTabs;
          }
          return maxLength;
       }
    }
    

  • 0
    S

    Kind of simply waterfall ... not sure it is O(n)

    std::string test = "dir\n\tsubdir1\n\t\tfile1.ext\n\t\tsubsubdir1\n\tsubdir2\n\t\tsubsubdir2\n\t\t\tfile2.ext";
    
    void main()
    {
        bool find_ext = false;
        bool counting_t = false;
        std::string max = "";
        std::vector<std::string> cur;
        std::string cur_max = "";
        std::string cur_sub = "";
        int t_counter = 0;
        for (int i = 0; i < test.size(); ++i)
        {     
            if (test[i] == '\n' || i == test.size()-1)
            {
                if (find_ext == true)
                {
                    if (max.size() < cur_max.size())
                    {
                        max = cur_max;
                    }
                    cur_max = "";
                    find_ext = false;
                }
                cur_sub = cur_sub + '/';
                cur_max = cur_max + '/';
                cur.push_back(cur_sub);
                cur_sub = "";
                continue;
            } 
            if (test[i] == '\t')
            {
                ++t_counter;
                counting_t = true;
                continue;
            }
            if (counting_t == true)
            {
                while (cur.size() > (t_counter))
                    cur.pop_back();
                if (cur.size() > 1)
                {
                    cur_max = "";
                    for (int i = 0; i < cur.size(); i++)
                        cur_max = cur_max + cur[i];
                }
                t_counter = 0;
                counting_t = false;
            }
            cur_sub = cur_sub + test[i];
            cur_max = cur_max + test[i];
            if (test[i] == '.')
            {
                find_ext = true;
            }
        }
        std::cout << "String:" << max << " Size:" << max.size();
    };
    

  • 0
    C

    straight forward O(n) runtime and O(1) space in Java

    public static int getLongestPathLength(String fileSystem) {
        // line syntax is (\t)*(file|directory)\n
        ArrayList<Integer> currentElements = new ArrayList<>();
        int pos = 0;
        int maxPathLength = 0;
        while(pos < fileSystem.length()) {
            // read the trailing tabs (0..n) to determine the level
            int level = 0;
            while(pos < fileSystem.length() && fileSystem.charAt(pos) == '\t') {
                level++;
                pos++;
            }
    
            // identify the length of this part of the path by reading until end of line ('\n')
            // if we see a '.' we can assume it's a file
            int nameLength = 0;
            boolean isFile = false;
            while(pos < fileSystem.length() && fileSystem.charAt(pos) != '\n') {
                if(fileSystem.charAt(pos) == '.') isFile = true;
                pos++;
                nameLength++;
            }
            pos++; // read the newline
    
            // check if the level is not this element actually had a preceding parent
            if(level > currentElements.size())
                throw new IllegalArgumentException("dir or file has no parent");
    
            // shorten the current elements length array list
            for(int i = currentElements.size(); i > level; i--) {
                currentElements.remove(i-1);
            }
    
            // calculate the current length
            int currentPathLength = nameLength + (isFile ? 0 : 1); // a path ends in "/"
            if(currentElements.size() > 0) {
                currentPathLength += currentElements.get(currentElements.size() - 1);
            }
    
            // if it was a path, add it to elements, if it was a file, consider it for max
            if(!isFile) currentElements.add(currentPathLength);
            else maxPathLength = Math.max(maxPathLength, currentPathLength);
        }
        return maxPathLength;
    }
    

  • 0
    E

    Two implementations. 1 for cases it doesn't fit in memory and we need to parse char by char, 2 if it fits in memory we can generate a list of "words" then parse through that to make it more intuitive. Basically we just need to keep track of the length at each directory we're working in. I'm assuming the input string is valid.

    from collections import deque
    
    # parsing char by char incase entire string doesn't fit in memory
    def longestFilePathMemory(s):
    	if not s: return 0
    	dot = False
    	stack = [0]
    	mx = depth = length = 0
    	for c in s:
    		if c == '\n':
    			while len(stack) > depth + 1: stack.pop()
    			if dot: # if file update max
    				mx = max(mx, stack[-1] + length)
    			else: # if not file add to stack
    				stack.append(stack[-1] + length)
    			# resetting values
    			depth = length = 0
    			dot = False
    		elif c == '\t': # increment depth
    			depth += 1
    		else: # regular char. increment length
    			dot = (c == '.') # indicate file
    			length += 1
    	return mx if not dot else max(mx, stack[-1] + length)
    
    # generate list of "words" if fits in memory
    def longestFilePath(s):
    	if not s: return 0
    	stack = [0]
    	mx = 0
    	# if string fits in memory
    	tokens = s.split("\n")
    	for t in tokens:
    		i = depth = 0
    		# parse depth. obtained by counting '\t'
    		while i < len(t) and t[i] == '\t':
    			depth += 1; i += 1
    		# align current path
    		while len(stack) > depth + 1: stack.pop()
    		if '.' in t[i:]: # if file
    			mx = max(mx, len(t) - i + stack[-1])
    		else: # if dir
    			stack.append(len(t) - i + stack[-1])
    	return mx
    
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.