Google Code Jam Practice Problem – File Fix-it

Problem

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 different names. These directories might have even more directories contained inside of them, and so on.

package avdongre.google.code.jam;

import java.util.HashSet;
import java.util.Scanner;

public class Solution {
	private static void solve(String[] existingDirectories,
			String[] directoriesTobeCreated) {
		HashSet<String> availableDirectories = new HashSet<String>();
		for ( int i = 0; i < existingDirectories.length; i++) {
			String[] splits = existingDirectories[i].split("/");
			StringBuilder sb = new StringBuilder();
			for ( int j = 0; j < splits.length; j++ ) {
				if ( splits[j].length() != 0) {					
					availableDirectories.add(sb.append("/").append(splits[j]).toString());
				} 
			}
			sb.setLength(0);
		}
		int mkdirCount = 0;
		for ( int i = 0; i < directoriesTobeCreated.length; i++) {
			String[] splits = directoriesTobeCreated[i].split("/");
			StringBuilder sb = new StringBuilder();
			for ( int j = 0; j < splits.length; j++ ) {
				if ( splits[j].length() != 0) {
					String possibleNewDirectory = sb.append("/").append(splits[j]).toString();
					if ( availableDirectories.contains(possibleNewDirectory) == false) {						
						availableDirectories.add(possibleNewDirectory);						
						mkdirCount++;
					} else {
					}
				}
			}
			sb.setLength(0);
		}
		System.out.println(mkdirCount);
	}

	public static void main(String[] args) {
		Scanner stdin = new Scanner(System.in);
		// number of test cases
		int T = Integer.parseInt(stdin.nextLine());
		for (int i = 0; i < T; i++) {
			String next = stdin.nextLine();
			String[] next_split = next.split(" ");
			int N = Integer.parseInt(next_split[0]);
			int M = Integer.parseInt(next_split[1]);

			String[] existingDirectories = new String[N];
			for (int j = 0; j < N; j++) {
				existingDirectories[j] = stdin.nextLine();
			}
			String[] directoriesTobeCreated = new String[M];
			for (int k = 0; k < M; k++) {
				directoriesTobeCreated[k] = stdin.nextLine();
			}
			System.out.print("Case #" + ( i + 1) + ": ");
			solve(existingDirectories, directoriesTobeCreated);
		}

	}

}

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s