Maximum subsequence sum

import java.util.ArrayList;

/**
 * Created by Arun on 9/11/14.
 */
public class SequenceResult
{
    public static void maximumContSubSeq(int[] a) {
        int sum[] = new int[a.length]; // Sum at every element
        sum[0] = a[0];
        int max = 0;
        for (int i = 1; i < a.length; i++) {
            sum[i] = Math.max(sum[i - 1] + a[i], a[i]);
            if(sum[i-1]+a[i]>a[i]){
                sum[i] = sum[i - 1] + a[i];
            }
            if (max < sum[i]) {
                max = sum[i];
            }
        }
        System.out.println(max);
    }


    public static void main(String args[]){
        int x[] = {-2, 3, -16, 100, -4, 5, 21 };
        maximumContSubSeq(x);
    }

}

Program to find whether a number is a perfect square or not

You can write an algorithm in linear time something like below

for(int i=1; i<numberToCheck; i++) {
    if(i*i==numberToCheck) {
        return true;
        break;
    }
    return false;
}

The above code can be optimized as follows, since we are sure that the number of times it has to be traversed is less than or equal to half the size of the input number we can divide it by 2.

for(int i=1; i<numberToCheck/2; i++) {
    if(i*i==numberToCheck) {
        return true;
        break;
    }
    return false;
}

Optimized? Not quite... We can still optimize it to <=sqrt(input) number of times!

/**
 * Created by Arun on 9/12/14.
 */
public class Square {

    public static boolean findPerfectSquare(int a) {
        int currentSquare = 1;
        for(int i=1;currentSquare<a;i++) {
            System.out.println(i);
            if(i*i==a) {
                return true;
            }
            currentSquare = i * i;
        }
        return false;
    }

    public static void main(String args[]) {
        System.out.println(findPerfectSquare(1222));

    }
}

Given a sorted array arr[] and a value X, find the k closest elements to X in arr[]. Examples: Input: K = 4, X = 35 arr[] = {12, 16, 22, 30, 35, 39, 42, 45, 48, 50, 53, 55, 56} Output: 30 39 42 45

import java.util.Arrays;

/**
 * Created by Arun on 8/11/14.
 */
public class ClosestArray {
    private static int[] getClosest(int num, int element, int arr[]){
        int elementIndex = -1;
        int closeArray [] = new int[num];
        for(int i=0;i<arr.length;i++) {
            if(arr[i]==element){
                elementIndex = i;
            }
        }
        for(int i=0, j=elementIndex-1, k=elementIndex+1;i<num;i++){
            int diff1 = element-arr[j];
            int diff2  = arr[k]-element;
            if(diff1<diff2){
                closeArray[i]=arr[j];
                j--;
            }
            else if(diff1>diff2) {
                closeArray[i]=arr[k];
                k++;
            }
            else{
                closeArray[i]=arr[j];
                if(i<num){
                    i++;
                    closeArray[i]=arr[k];
                    j--;
                    k++;
                }
                else {
                    break;
                }
            }
        }
        return closeArray;
    }

    public static void main(String args[]) {
        int arr[] = {12, 16, 22, 31, 35, 39, 42, 45, 48, 50, 53, 55, 56};
        getClosest(4, 35, arr);
    }
}

Given an array of integers. This array denotes ‘our’ own ascending order of the elements. So if the array is {2,3,1,4}, by mathematics we can say that 2<3<1<4. Given another array, sort this new array in ‘our’ ascending order.
Let’s say the new array is {1,2,4,3,5,4,9,2}, output will be {2,2,3,1,4,4,5,9}. Note that since 5 and 9 do not occur, they are sorted by actual ascending order at the end.

import java.util.*;

/**
 * Created by Arun on 8/9/14.
 */
public class CustomizedSort {
    public static ArrayList<Integer> sort(int customSortList[], Integer arr[]){
        Map<Integer, Integer> mp = new LinkedHashMap<Integer, Integer>();
        for(int i=0;i<customSortList.length;i++) {
            mp.put(customSortList[i], i);
        }
        System.out.println(mp);
        List<Integer> a = Arrays.asList(arr);
        Collections.sort(a);
        arr = a.toArray(new Integer[arr.length]);
        ArrayList<Integer> newArr = new ArrayList<Integer> (arr.length);

        Iterator it = mp.entrySet().iterator();
        while (it.hasNext()){
            Map.Entry pairs = (Map.Entry)it.next();
            int key = (Integer)pairs.getKey();
            for(int i=0;i<a.size();i++){
                if(a.get(i)==key){
                    newArr.add(key);
                }
            }
        }
        for(int i=0;i<a.size();i++){
            if (!newArr.contains(a.get(i))){
                newArr.add(a.get(i));
            }
        }
        return newArr;
    }
    public static void main(String args[]){
        int customSortList[] = {2,3,1,4};
        Integer arr [] = {1,2,4,3,5,4,9,2};
        System.out.println(sort(customSortList, arr));
    }
}

Given a text txt[0..n-1] and a pattern pat[0..m-1], write a function search(char pat[], char txt[]) that prints all occurrences of pat[] and its permutations (or anagrams) in txt[]. You may assume that n > m.E.g. : I/p : txt[] = “BACDGABCDA” pat[] = “ABCD”o/p :0,5,6

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;

/**
 * Created by Arun on 8/9/14.
 */
public class PatternMatching {
    public static boolean isPrime(int n) {
        if (n <= 1) {
            return false;
        }
        for (int i = 2; i < Math.sqrt(n); i++) {
            if (n % i == 0) {
                return false;
            }
        }
        return true;
    }

    public static ArrayList<Integer> getPrimes() {
        ArrayList<Integer> arr = new ArrayList<Integer>();
        for(int i=0, j=0;j<26;i++){
            if(isPrime(i)){
                arr.add(i);
                j++;
            }
        }
        return arr;
    }

    private static ArrayList<Integer> matchPattern(String str, String pattern) {
        ArrayList<Integer> a = getPrimes();
        String alphabets = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
        Map<String, Integer> valMap = new HashMap<String, Integer>();
        int patternProduct = 1;
        for(int i=0;i<alphabets.length();i++) {
            valMap.put(String.valueOf(alphabets.charAt(i)), a.get(i));
        }
        for(int i=0;i<pattern.length();i++) {
            patternProduct = patternProduct * valMap.get(String.valueOf(pattern.charAt(i)));
        }
        for(int i=0;i<=str.length()-pattern.length();i++) {
            int tempVal=1;
            for(int j=i, k=0;k<pattern.length();k++,j++){
                tempVal = tempVal * valMap.get(String.valueOf(str.charAt(j)));
            }
            if(tempVal==patternProduct) {
                System.out.println(i);
            }
        }
        return null;
    }
    public static void main(String args[]) {
        matchPattern("BACDGABCDABCD", "ABCD");
    }
}

Given an array of integers. Segregate all the non-zero numbers at the beginning. Print the number of non-zero integers and the minimum number of swaps required for these operations.Eg. : I/p : 1, 0, 0, -6, 2, 0o/p : Number of non-zero integers : 3

import java.util.ArrayList;

/**
 * Created by Arun on 8/9/14.
 */
public class ArrayNonZero {
    public static void main(String args[]) {
        int arr []  = {1, 0, 0, -6, 2, 0};
        ArrayList<Integer> nonZero = new ArrayList<Integer>();
        ArrayList<Integer> zero = new ArrayList<Integer>();
        int i=0;
      //get the indexes of the zero and non zero elements
        for(int val: arr) {
            if(val!=0) {
                nonZero.add(i);
            }
            else {
                zero.add(i);
            }
            i++;
        }
        int newArr [] = new int[arr.length];
        i=0;
       //put the non-zero elements at the end and zero element at the beginning
        for(int val: nonZero){
            newArr[i]=arr[val];
            i++;
        }
        for(int val: zero) {
            newArr[i] = arr[val];
            i++;
        }
        for(int val: newArr){
            System.out.println(val);
        }
    }
}