I think we can build a n-ary tree from the n directory paths that are
already available in the computer and then for each of the m directory paths
we can traverse the tree up until the directory which is already available
in the tree and then count the remaining directories in the path.
1 Question :
Can a test case be like this ?
1 2
/chicken
/chicken/egg
/chicken/egg/chicken
if yes then while processing second of the 2 directories that should be
created, should we consider egg folder is already created while processing
the previous one ?
On Thu, Feb 17, 2011 at 6:23 PM, Akshata Sharma
<akshatasharm...@gmail.com>wrote:
> On Unix computers, data is stored in directories. There is one root
> directory, and this might have several directories
> contained inside of it, each with di fferent names. These directories might
> have even more directories contained inside of them,
> and so on.
> A directory is uniquely identified by its name and its parent directory
> (the directory it is directly contained in). This is usually
> encoded in a path, which consists of several parts each preceded by a
> forward slash ('/'). The final part is the name of the
> directory, and everything else gives the path of its parent directory. For
> example, consider the path: /home/facebook/people
> This refers to the directory with name "people" in the directory described
> by "/home/facebook", which in turn refers to the
> directory with name "facebook" in the directory described by the path
> "/home". In this path, there is only one part, which means it
> refers to the directory with the name "home" in the root directory.
> To create a directory, you can use the mkdir command. You specify a path,
> and then mkdir wi ll create the directory described by
> that path, but only if the parent directory al ready exists. For example, i
> f you wanted to create the "/home/facebook/people" and
> "/home/facebook/tech" directories from scratch, you would need four
> commands:
> mkdir /home
> mkdir /home/facebook
> mkdir /home/facebook/people
> mkdir /home/facebook/tech
> Given the full set of directories already existing on your computer, and a
> set of new directories you want to create if they do not
> already exist, how many mkdir commands do you need to use?
>
> Input The first line of the input gives the number of test cases, T. T test
> cases follow. Each case begins with a line containing two
> integers N and M, separated by a space.
>
> The next N lines each give the path of one directory that already exists on
> your computer. This list will include every directory
> already on your computer other than the root directory. (The root directory
> is on every computer, so there is no need to l ist it
> explicitly.)
>
> The next M lines each give the path of one directory that you want to
> create.
> Each of the paths in the input is formatted as in the problem statement
> above. Speci fically, a path consists of one or more lower -
> case alpha-numeric strings (i .e., strings containing only the symbols
> 'a'-'z' and '0'-'9'), each preceded by a single forward slash.
> These alpha-numeric strings are never empty.
>
> Output For each test case, output one l ine containing "Case #x: y", where
> x is the case number (starting from 1) and y is the
> number of mkdir you need.
>
> Note: If a directory is listed as being on your computer, then its parent
> directory will also be listed, unless the parent is the root
> directory.
>
> INPUT
>
> 2
>
> 1 2
> /chicken
> /chicken/egg
> /chicken
>
> 1 3
> /a
> /a/b
> /a/c
> /b/b
>
> OUTPUT
>
> Case #1: 1
> Case #2: 4
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
