Dirsort

SRM 114 · 2002-09-24 · by chogyonim

Class Name: Dirsort

Return Type: String[]

Method Name: sort

Arg Types: (vector<string>)

Problem Statement

Most operating systems have some sort of utility to search for a particular file. The order in which these utilites search through subdirectories can make a big difference in how fast a file is found. For example, if a user tends to put files in less nested directories, it would make sense to search those first. You are to write the code for such a utility that sorts a list of directories primarily by directory depth so that directories with lower directory come first.

The algorithm should take a String[] dirs as an input and should sort dirs first by directory depth, and then lexicographically for each depth. So "/d/e/" comes before "/a/b/c/", but not before "/c/d/". Also, "/a/bc/", comes before "/ab/c/", since "a" comes before "ab" in lexicographical order.

Notes

For a directory to exist, it's superdirectory does not necessarily need to exist. For example, you can have "/usr/admin/" without having "/usr/" or even "/".

Constraints

dirs will contain between 1 and 50 elements, inclusive.
each element of dirs will be of length 1 to 50, inclusive.
each element of dirs will contain only lowercase letters [a-z], inclusive, and the slash ('/') character.
each element of dirs will begin with a slash, end with a slash, and not have double slashes anywhere.

Examples

{"/","/usr/","/usr/local/","/usr/local/bin/","/games/",
 "/games/snake/","/homework/","/temp/downloads/"}
Returns: { "/",  "/games/",  "/homework/",  "/usr/",  "/games/snake/",  "/temp/downloads/",  "/usr/local/",  "/usr/local/bin/" }

Notice that "/temp/downloads/" can exist even without "/temp/".

{"/usr/","/usr/local/","/bin/","/usr/local/bin/",
 "/usr/bin/","/bin/local/","/bin/local/"}
Returns: { "/bin/",  "/usr/",  "/bin/local/",  "/bin/local/",  "/usr/bin/",  "/usr/local/",  "/usr/local/bin/" }

{"/a/b/c/d/e/f/g/h/i/j/k/l/m/n/","/o/p/q/r/s/t/u/v/w/x/y/z/"}
Returns: { "/o/p/q/r/s/t/u/v/w/x/y/z/",  "/a/b/c/d/e/f/g/h/i/j/k/l/m/n/" }

{"/","/a/","/b/","/c/","/d/","/e/","/f/","/g/","/a/a/","/b/g/c/","/g/f/"}
Returns: { "/",  "/a/",  "/b/",  "/c/",  "/d/",  "/e/",  "/f/",  "/g/",  "/a/a/",  "/g/f/",  "/b/g/c/" }

{"/a/b/c/d/e/f/g/h/i/j/k/l/m/n/","/o/p/q/r/s/t/u/v/w/x/y/z/"}
Returns: { "/o/p/q/r/s/t/u/v/w/x/y/z/",  "/a/b/c/d/e/f/g/h/i/j/k/l/m/n/" }

Submissions are judged against all 34 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class Dirsort with a public method vector<string> sort(vector<string> dirs) · 34 test cases · 2 s / 256 MB per case