TopcoderArchiveVisit Topcoder
Archive
SRM24 Sep 2002
SRM 114

Dirsort

Problem statement, definition, constraints, and public examples.

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.

Definition

Class:
Dirsort
Method:
sort
Parameters:
String[]
Returns:
String[]
Method signature:
String[] sort(String[] dirs)
(be sure your method is public)

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

  1. {"/","/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/".
  2. {"/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/" }
  3. {"/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/" }
  4. {"/","/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/" }
  5. {"/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/" }
  6. {"/a/b/","/ab/cd/","/c/d/","/a/b/c/","/ab/c/d/","/a/bc/d/","/a/b/cd/"}
    Returns: { "/a/b/",  "/ab/cd/",  "/c/d/",  "/a/b/c/",  "/a/b/cd/",  "/a/bc/d/",  "/ab/c/d/" }

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.

Back to all problems