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

Suppressions in Valgrind

Recently I was trying to find all the memory leak in my product. Now my product is very complex and uses couple of third party libraries. When I ran valgrind it’s log file was full of errors from those third party libraries for which I do not have code.

If you want to find the memory leaks in your product only, one can use the Suppression facility in the valgrind

Following are the steps to create suppression file.

  • Create a file for example product.suppression
  • If you want to completely ignore certain shared library then add following lines to that file
  • {
       SUPPRESSION_TEST_OBJECT_COND
       Memcheck:Cond
       ...
       obj:<path to the shared library>
       ...
    }
    {
       SUPPRESSION_TEST_OBJECT_LEAK
       Memcheck:Leak
       ...
       obj:<path to the shared library>                                                                                                 
       ...
    }
    
  • Sometime I found that valgrind give false positive information. For example you may have code which is reusing certain buffer
  • In such case run the valgrind using –gen-suppressions=all option
  • Open the file and you will see output in some following format
  • Locate the memory leak which you think is false positive
  • Copy the suppression code and add it to your main suppression file
  • {
       <insert_a_suppression_name_here>
       Memcheck:Leak
       match-leak-kinds: possible
       fun:malloc
       fun:_ZN8stlp_std14__malloc_alloc8allocateEj
       fun:_ZN8stlp_std12basic_stringIcNS_11char_traitsIcEENS_9allocatorIcEEE9_M_appendEPKcS7_
       fun:_ZN5dunit4Task4initEi
       fun:_Z12runPutGetAllbb
       fun:_GLOBAL__I_main
       obj:/export/pnq-gst-dev01a/users/adongre/valgrind_702/nc/ThinClient702X_maint/build-artifacts/linux/tests/cppcache/testThinClientPutGetAll
       obj:/export/pnq-gst-dev01a/users/adongre/valgrind_702/nc/ThinClient702X_maint/build-artifacts/linux/tests/cppcache/testThinClientPutGetAll
       fun:__libc_csu_init
       fun:(below main)
    }
    
  • You can also add it like below so that any code path calling that function will be ignored
  • {
       <insert_a_suppression_name_here>
       Memcheck:Leak
       match-leak-kinds: possible
       ...
       fun:_ZN8stlp_std14__malloc_alloc8allocateEj
       ...
    }
    
  • Remember to replace the line with some identifier
  • Next time when you run valgrind use the option –suppressions=

FizzBuzz Test

I do not see what is this buzz about this FizzBuzz Test. It is very simple to code. Fizzbuzz test is as follows
Write a program that prints the numbers from 1 to 100. But for multiples of three print “Fizz” instead of the number and for the multiples of five print “Buzz“. For numbers which are multiples of both three and five print “FizzBuzz“.

Here are my solutions

#include <iostream>

int main ( int argc, char **argv) {
	for ( int i = 0; i <= 100; i++) {
		if (  ( i % 3 == 0 ) && (i % 5 == 0 )) {
			std::cout << "FizzBuzz" << std::endl;
		}
		else if ( i % 3 == 0 ) {
			std::cout << "Fizz" << std::endl;
		}
		else if ( i % 5  == 0 ) {
			std::cout << "Buzz" << std::endl;
		} else {
			std::cout << i << std::endl;
		}
	}
	return 0;
}

First if condition can be changed to one

#include <iostream>

int main ( int argc, char **argv) {
	for ( int i = 0; i <= 100; i++) {
		if ( i % 15 == 0 ) {
			std::cout << "FizzBuzz" << std::endl;
		}
		else if ( i % 3 == 0 ) {
			std::cout << "Fizz" << std::endl;
		}
		else if ( i % 5  == 0 ) {
			std::cout << "Buzz" << std::endl;
		} else {
			std::cout << i << std::endl;
		}
	}
	return 0;
}

Project Euler – Problem 3

The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?

#include <cstdio>
int main(int argc, char **argv){
	long long num = 600851475143LL;
	int ans = 0;
	for(int div = 3; ; div += 2)
		if(!(num % div)){
			do { num /= div; } while (!(num % div));
			if(num == 1){
				ans = div;
				break;
			}
		}		
		printf("Answer: %d\n", ans);
		return 0;
}

Pangrams

Description:

The sentence ‘A quick brown fox jumps over the lazy dog’ contains every single letter in the alphabet. Such sentences are called pangrams. You are to write a program, which takes a sentence, and returns all the letters it is missing (which prevent it from being a pangram). You should ignore the case of the letters in sentence, and your return should be all lower case letters, in alphabetical order. You should also ignore all non US-ASCII characters.In case the input sentence is already a pangram, print out the string NULL
Input sample:

Your program should accept as its first argument a filename. This file will contain several text strings, one per line. Ignore all empty lines. eg.

A quick brown fox jumps over the lazy dog
A slow yellow fox crawls under the proactive dog

Output sample:

Print out all the letters each string is missing in lowercase, alphabetical order .e.g.

NULL
bjkmqz

My solution

#include <fstream>
#include <string>
#include <algorithm>
#include <iostream>

struct InvalidChar {
    bool operator()(char c) const {
        return !isprint((unsigned)c);
    }
};

void print_missing_pangrams_chars(std::string &line) {
	bool found = true;
	std::transform(line.begin(), line.end(), 
		           line.begin(), ::tolower);

	std::sort(line.begin(), line.end());

	line.erase(std::remove_if(line.begin(),
		                      line.end(),
							  InvalidChar()), 
							  line.end());

	std::string dictionary = "abcdefghijklmnopqrstuvwxyz";
	for ( std::string::iterator itr = dictionary.begin();
		itr != dictionary.end();++itr) {
			if (line.find(*itr) == std::string::npos){
				std::cout << *itr;
				found = false;
			}
	}
	if ( found )
		std::cout << "NULL";
	std::cout << std::endl;
}
int main ( int argc, char **argv) {
    std::ifstream inpFile(argv[1]);
    if ( inpFile.peek() == EOF ){
        return -1;
	} 
    std::string line; 
    if (inpFile.is_open()) {
        while (! inpFile.eof() ) {               
            std::getline (inpFile,line);
			if ( !line.empty()) {
				print_missing_pangrams_chars(line);
			}
        }
        inpFile.close();
    }
	return 0;
}

Prefix expressions

Description:
You are given a prefix expression. Write a program to evaluate it.
Input sample:
The first argument will be an input file with one prefix expression per line. e.g.

* + 2 3 4

Your program has to read this and insert it into any data structure you like. Traverse that data structure and evaluate the prefix expression. Each token is delimited by a whitespace. You may assume that the only valid operators appearing in test data are ‘+’,’*’ and ‘/’
Output sample:
Print to stdout, the output of the prefix expression, one per line. e.g.

20

My solution

#include <iostream>
#include <fstream>
#include <string>
#include <stack>
#include <sstream>
#include <vector>
#include <algorithm>

void Tokenize(const std::string& str, 
			  std::vector<std::string>& tokens,
			  const std::string& delimiters = " ") {
	std::string::size_type lastPos = str.find_first_not_of(delimiters, 0);
	std::string::size_type pos     = str.find_first_of(delimiters, lastPos);
	while (std::string::npos != pos || std::string::npos != lastPos){
        tokens.push_back(str.substr(lastPos, pos - lastPos));
        lastPos = str.find_first_not_of(delimiters, pos);
        pos = str.find_first_of(delimiters, lastPos);
    }
}

int string_to_int(std::string const &val) {
	std::istringstream istr(val);
	int returnVal;
	istr >> returnVal;
	return returnVal;
}

void evaluate_prefix_expression( std::string &expr) {
	std::stack<int> operand_stack;
	std::string operators = "+*/-";
	//std::reverse(expr.begin(), expr.end());
	std::vector<std::string> tokens;
	Tokenize(expr,tokens);
	for ( std::vector<std::string>::reverse_iterator itr = tokens.rbegin();
		itr != tokens.rend(); ++itr) {
			if ( operators.find(*itr) == std::string::npos) {
				operand_stack.push(string_to_int(*itr));
			}
			if ( operators.find(*itr) != std::string::npos){
				int t1 = operand_stack.top(); operand_stack.pop();
				int t2 = operand_stack.top(); operand_stack.pop();
				if ( *itr == "+") {
					operand_stack.push(t1 + t2 );
				} else if ( *itr == "*" ) {
					operand_stack.push(t1 * t2 );
				} else if ( *itr == "/" ) {
					operand_stack.push(t1 / t2 );
				} else if ( *itr == "-" ) {
					operand_stack.push(t1 - t2 );
				}

			}
	}
	std::cout << operand_stack.top() << std::endl;
}
int main( int argc, char **argv) {
    std::ifstream inpFile(argv[1]);
    if ( inpFile.peek() == EOF ){
        return -1;
	} 
    std::string line; 
    if (inpFile.is_open()) {
        while (! inpFile.eof() ) {               
            std::getline (inpFile,line);
			if ( !line.empty()) {
				evaluate_prefix_expression(line);
			}
        }
	}
	return 0;
}