CareerCup

// overflow is k here

sort(array); //ascending order

int lastindex = array.length-1;
int sum = 0;
for(int i=lastindex; i >= lastindex - (overflow - 1); i--)
sum += array[i];


int minsum = sum;
for(int i=lastindex-1; i >= overflow - 1; i--)
{
sum -= array[i+1];
sum += array[i-overflow] + array[i]*(lastindex - i);

if(sum < minsum)
minsum = sum;
}

print(minsum);

complexity of finding frequency of one number: log(n)
complexity of finding frequency of all numbers: d*log(n) where d is distinct numbers in array.

find_right_most_index_of_number() is modified version of binary search which return the right most index of value.

public class Main
{
    static int find_right_most_index_of_number(int[] array, int l, int r, int num)
    {
        if(l <= r)
        {
            int mid = (l + r) / 2;

            if(array[r] == num)
                return r;
            else if (array[mid] == num)
                return find_right_most_index_of_number(array, mid, r-1, num);

            if (num < array[mid])
                return find_right_most_index_of_number(array, l, mid - 1, num);
            else if (num > array[mid])
                return find_right_most_index_of_number(array, mid + 1, r, num);
        }

        return -1;
    }

    public static void main(String args[])
    {
        int[] array = {1, 2, 2, 3, 4, 5, 5, 5};

        int l = 0;
        int r;
        while(l < array.length)
        {
            r = find_right_most_index_of_number(array, l, array.length - 1, array[l]);
            if((r-l+1) > array.length/4)
                System.out.println(array[l]);
            l = r + 1;
        }
    }
}

complexity of finding frequency of one number: log(n)
complexity of finding frequency of all numbers: d*log(n) where d is distinct numbers in array.

find_right_most_index_of_number() is modified version of binary search which return the right most index of value.

public class Main
{
    static int find_right_most_index_of_number(int[] array, int l, int r, int num)
    {
        if(l <= r)
        {
            int mid = (l + r) / 2;

            if(array[r] == num)
                return r;
            else if (array[mid] == num)
                return find_right_most_index_of_number(array, mid, r-1, num);

            if (num < array[mid])
                return find_right_most_index_of_number(array, l, mid - 1, num);
            else if (num > array[mid])
                return find_right_most_index_of_number(array, mid + 1, r, num);
        }

        return -1;
    }

    public static void main(String args[])
    {
        int[] array = {1, 2, 2, 3, 4, 5, 5, 5};

        int l = 0;
        int r;
        while(l < array.length)
        {
            r = find_right_most_index_of_number(array, l, array.length - 1, array[l]);
            System.out.println("frequency of " + array[l] + " " + (r-l+1));
            l = r + 1;
        }
    }
}

Assuming array is sorted

if right most index of the number is subtracted from the left most index then we get the frequency of that number.

wrote two modified binary search functions, which give left most and right most index of number.
complexity O(log(n))

static int find_left_most_index_of_number(int[] array, int l, int r, int num)
    {
        if(l <= r)
        {
            int mid = (l+r)/2;

            if(array[l] == num)
                return l;
            else if(array[mid] == num)
                return find_left_most_index_of_number(array, l+1, mid, num);

            if(num < array[mid])
                return find_left_most_index_of_number(array, l, mid - 1, num);
            else if(num > array[mid])
                return find_left_most_index_of_number(array, mid + 1, r, num);
        }

        return -1;
    }

    static int find_right_most_index_of_number(int[] array, int l, int r, int num)
    {
        if(l <= r)
        {
            int mid = (l+r)/2;

            if(array[r] == num)
                return r;
            else if(array[mid] == num)
                return find_right_most_index_of_number(array, mid, r-1, num);

            if(num < array[mid])
                return find_right_most_index_of_number(array, l, mid - 1, num);
            else if(num > array[mid])
                return find_right_most_index_of_number(array, mid + 1, r, num);
        }

        return -1;
    }

    public static void main(String args[])
    {
        int[] array = {1, 2, 2, 3, 4, 5, 5, 5};
        for(int i=0; i<5; i++)
        {
            int left = find_left_most_index_of_number(array, 0, array.length - 1, i+1);
            int right = find_right_most_index_of_number(array, 0, array.length - 1, i+1);
            System.out.println("frequency of " + (i+1) + ": " + ((right - left) + 1));
        }
    }

Keep an index of the start of the segment when length of segments get above k, remove start element from sum and add new element, in this way the length of segment will always be <= k, and new elements can be checked for maximum sum.

int start = 0;
int maxsum = -infinity;

for(int i = 0; i < array.length; i++)
{
if(start - i > k)
{
sum = sum - array[start];
start++;
}

sum += array[i];

if(sum > maxsum)
maxsum = sum;
if(sum < 0)
{
start = i + 1;
sum = 0;
}
}

Keep an index of the start of the segment when length of segments get above k, remove start element from sum and add new element, in this way the length of segment will always be <= k, and new elements can be checked for maximum sum.

{{

int start = 0;
int maxsum = -infinity;

for(int i = 0; i < array.length; i++)
{
if(start - i > k)
{
sum = sum - array[start];
start++;
}

sum += array[i];

if(sum > maxsum)
maxsum = sum;
if(sum < 0)
{
start = i + 1;
sum = 0;
}
}

}}}

import java.util.ArrayList;
import java.util.List;

public class Main
{
    public static List<String> get_dearrangements(String str, String original, int depth)
    {
        if(str.length() == 1)
        {
            List<String> list = new ArrayList<String>();
            list.add(str);
            return list;
        }

        List<String> all_dearrangements = new ArrayList<String>();
        for(int i=0; i<str.length(); i++)
        if(str.charAt(i) != original.charAt(depth))
        {
            char c = str.charAt(i);
            List<String> dearrangements = get_dearrangements(remove_char_at(str, i), original, depth+1);
            for(String s : dearrangements)
                all_dearrangements.add(c + s);
        }
        return all_dearrangements;
    }

    public static String remove_char_at(String str, int index)
    {
        StringBuilder sb = new StringBuilder(str);
        sb.deleteCharAt(index);
        return sb.toString();
    }
    public static void main(String args[])
    {
        System.out.println(get_dearrangements("ABCDE", "ABCDE", 0));
    }
}

output:
[BADCE, BADEC, BAECD, BCAED, BCDAE, BCDEA, BCEAD, BDACE, BDAEC, BDEAC, BDECA, BEACD, BEDAC, BEDCA, CABED, CADBE, CADEB, CAEBD, CDABE, CDAEB, CDBAE, CDBEA, CDEAB, CDEBA, CEABD, CEBAD, CEDAB, CEDBA, DABCE, DABEC, DAEBC, DAECB, DCABE, DCAEB, DCBAE, DCBEA, DCEAB, DCEBA, DEABC, DEACB, DEBAC, DEBCA, EABCD, EADBC, EADCB, ECABD, ECBAD, ECDAB, ECDBA, EDABC, EDACB, EDBAC, EDBCA]