#hackerrank algorithms

Problem Statement James found a love letter his friend Harry has written for his girlfriend. James is a prankster, so he decides to meddle with the letter. He changes all the words in the letter intopalindromes.

To do this, he follows two rules:

He can reduce the value of a letter, e.g. he can change d to c, but he cannot change c to d.

In order to form a palindrome, if he has to repeatedly reduce the value of a letter, he can do it until the letter becomes a. Once a letter has been changed to a, it can no longer be changed.

Each reduction in the value of any letter is counted as a single operation. Find the minimum number of operations required to convert a given string into a palindrome.

Input Format The first line contains an integer T, i.e., the number of test cases. The next T lines will contain a string each. The strings do not contain any spaces.

Thoughts

Retrospectively speaking, this problem was a lot of fun.  I learned quite a lot!  One of the first things I did after reading the problem statement was Googling and refreshing myself on some palindrome algorithms.  A popular hit was basically an algorithm to determine if a particular string was a palindrome.  This problem was a bit easier because I didn't have to worry about white space, which now thinking about it wouldn't really have given me too much trouble.

The two prime distinctions among the algorithms I found were algorithms that use recursion and algorithms that used loops.  Initially, I sought to solve the problem recursively using the following psudocode:

function int palindromize(string)     int numReductions = 0     char firstChar = string[0];     char lastChar = string[length-1]     if (frontChar != backChar)         numReductions += palindromize(string.substring(1, length-1)     return numReductions

However, in the interest of cleaning up code and optimizing the execution time, I decided against using recursion and instead parsed through each String as an array and iterating through the elements using a simple while loop and 2 loop counters, one on either of the string which would increment and decrement towards each other.  The pseudocode for this implementation looks something like this:

function int palindromize(string)        char[] charArr = string.toCharArray();        int numReductions = 0;        int frontIndex = 0;        int backIndex = input.length()-1;        while (frontIndex <= backIndex){            char frontChar = inputCharArr[frontIndex];            char backChar = inputCharArr[backIndex];            numReductions += abs(frontChar-backChar);            ++frontIndex;            --backIndex;        }        return numReductions;

Here the function "abs()" refers to a function that calculates the absolute value of a value using bitwise operations as follows:

public static int abs(int value){        int mask = value>>31;        return (value ^ mask) - mask;  }

I found this snippet over at StackOverflow in answer #4:  http://stackoverflow.com/questions/12041632/how-to-compute-the-integer-absolute-value

Solving the problem this way yielded the best execution times across all test cases.

Here, I learned that simplicity wins out over elegance.  I'm much more satisfied with this solution.  It's very straight forward and I believe any novice to intermediate programmer can understand the solution without having to think too much.

Problem Statement

You will be given a list of 32 bits unsigned integers. You are required to output the list of the unsigned integers you get by flipping bits in its binary representation (i.e. unset bits must be set, and set bits must be unset).

Input Format The first line of the input contains the list size T, which is followed by T lines, each line having an integer from the list.

Output Format Output one line per element from the list with the requested result.

Thoughts

A few things learned and refreshed from this problem

Writing classes and function with levels of abstraction in mind

Refresher of Two's Complement

This problem was a bit tricky.  I also, quite honestly, inspected the discussion section a bit to get some clues on where to attack the problem.  One of the first problems I encountered at the outset was the fact that Java (below Java 8) does not have first class support for unsigned integers.  

Applied some guidelines on abstracting out the class to try and abide by the "Only 1 job per function" principle.  Currently reading through "Clean Code" by Robert C. Martin right now.  In it, he defines different levels of abstraction that we as software engineers should really be mindful of when assembling a class and its functions.  This was somewhat an eye opener for me.  I've never really put much thought into designing my code in such a way that I organize the levels of abstraction within my classes and functions.

The common rule is that functions should do 1 job.  In addition, functions should only have 1 level of abstraction.  Robert gives examples of high, medium and low levels of abstraction.

Examples of the three he gave are as follows:

High level - processIntegerList()

Medium level - List<Long> integerInputs = new ArrayList<Long>()

Low level - integerList.get(i)

Problem Statement

There are N integers in an array A. All but one integer occur in pairs. Your task is to find the number that occurs only once.

Input Format The first line of the input contains an integer N, indicating the number of integers. The next line contains N space-separated integers that form the array A.

Output Format Output S, the number that occurs only once.

Solution 1 Pseudocode:

Use map to store key-value pairs of integers encountered as key and frequency of appearance as the value

Iterate through map and find key whose value appears only 1 time

Solution 1 Learning: Learned how to create a HashMap Learned how to iterate through HashMap Learned how to use try-catch statement

Final Solution Pseudocode:

Bitwise XOR input integer set successively