string to int

str = '1234'

str - '0' = [1 2 3 4]

When you use arithmetic operators with strings, strings is cast as doubles, which converts a string to ascii values,
Thus, subtraction will work just fine, though addition will give weird results

minimal sum of two integers that are made of the digits contained in the array

Given the array of digits (0 is also allowed), what is the minimal sum of two integers that are made of the digits contained in the array.
For example, array: 1 2 7 8 9. The min sum (129 + 78) should be 207

ANSWER
Sort the array. The largest numbers should be in the least significant positions, so build up your two integers by alternating from the two arrays.
E.g. 1 3 5 7 8 9 => 1 and 3, then 15 and 37, then 158 and 379. 0 is a special case, if not allowed to use that as a leading digit then have to use it as the second digit.

Try adding two numbers, you would find all that matters is the order of magnitude of a digit and not which of the two numbers that a digit belongs. (e.g. 178+29 = 128+79 = 179+28 = 129+78)

Collections in Java

Iterator interface

Iterator interface provides the facility of iterating the elements in forward direction only.

Methods of Iterator interface

There are only three methods in the Iterator interface. They are:

1. public boolean hasNext() it returns true if iterator has more elements.
2. public object next() it returns the element and moves the cursor pointer to the next element.
3. public void remove() it removes the last elements returned by the iterator. It is rarely used.

Nuts & Bolts Problem (Lock & Key problem)

Given a set of n nuts of different sizes and n bolts of different sizes. There is a one-one mapping between nuts and bolts. Match nuts and bolts efficiently.
Constraint: Comparison of a nut to another nut or a bolt to another bolt is not allowed. It means nut can only be compared with bolt and bolt can only be compared with nut to see which one is bigger/smaller.

Other way of asking this problem is, given a box with locks and keys where one lock can be opened by one key in the box. We need to match the pair.

Logic

• first performs a partition by picking last element of bolts array as pivot,
• rearrange the array of nuts and returns the partition index ‘i’ such that all nuts smaller than nuts[i] are on the left side and all nuts greater than nuts[i] are on the right side.
• Next using the nuts[i] we can partition the array of bolts. This operation also makes nuts and bolts array nicely partitioned.
• Now we apply this partitioning recursively on the left and right sub-array of nuts and bolts.

As we apply partitioning on nuts and bolts both so the total time complexity will be Θ(2*nlogn) = Θ(nlogn) on average.

CODE

    private static void matchPairs(char[] nuts, char[] bolts, int low, int high)

    {

        if (low < high)

        {

            // Choose last character of bolts array for nuts partition.

            int pivot = partition(nuts, low, high, bolts[high]);

            // Now using the partition of nuts choose that for bolts

            partition(bolts, low, high, nuts[pivot]);

            // Recur for [low...pivot-1] & [pivot+1...high] for nuts and bolts array.

            matchPairs(nuts, bolts, low, pivot-1);

            matchPairs(nuts, bolts, pivot+1, high);

        }

    }