CareerCup

O(n) time and O(1) space

import org.junit.Assert;
import org.junit.Test;

public class LexicographicalLongestSubstring {
    @Test
    public void testLexicographicalLongestSubstring() {
	Assert.assertEquals("x", getLexicographicalLongestSubstring("bandix"));
	Assert.assertEquals("dacdac", getLexicographicalLongestSubstring("bdacdac"));
	Assert.assertEquals("ddac", getLexicographicalLongestSubstring("bdacddac"));
	Assert.assertEquals("xia", getLexicographicalLongestSubstring("bdacdacxia"));
    }

    public String getLexicographicalLongestSubstring(String str) {
	char[] charArray = str.toCharArray();
	int i = 1;
	int n = str.length();
	int rstart = 0;
	while (i < n) {
	    if (charArray[i] > charArray[rstart]) {
		// Reset
		rstart = i;
	    } else if (charArray[i] == charArray[rstart]) {
		// compare
		int j = i;
		int k = rstart;
		while (j < n) {
		    if (charArray[k] < charArray[j]) {
			if (charArray[j] > charArray[rstart]) {
			    // reset
			    rstart = j;
			} else {
			    rstart = i;
			}
			i = j + 1;
			break;
		    } else if (charArray[k] > charArray[j]) {
			i = j + 1;
			break;
		    }
		    k++;
		    j++;
		}
	    }
	    i++;
	}
	return str.substring(rstart);
    }

}

Time complexity - O(n) Space complexity O(n)

import org.junit.Assert;
import org.junit.Test;

public class LexicographicalLongestSubstring {
    @Test
    public void testLexicographicalLongestSubstring() {
	Assert.assertEquals("x", getLexicographicalLongestSubstring("bandix"));
	Assert.assertEquals("dacdac", getLexicographicalLongestSubstring("bdacdac"));
	Assert.assertEquals("ddac", getLexicographicalLongestSubstring("bdacddac"));
	Assert.assertEquals("xia", getLexicographicalLongestSubstring("bdacdacxia"));
    }

    public String getLexicographicalLongestSubstring(String str) {
	char[] charArray = str.toCharArray();
	int i = 1;
	int n = str.length();
	int rstart = 0;
	while (i < n) {
	    if (charArray[i] > charArray[rstart]) {
		// Reset
		rstart = i;
	    } else if (charArray[i] == charArray[rstart]) {
		// compare
		int j = i;
		int k = rstart;
		while (j < n) {
		    if (charArray[k] < charArray[j]) {
			if (charArray[j] > charArray[rstart]) {
			    // reset
			    rstart = j;
			} else {
			    rstart = i;
			}
			i = j + 1;
			break;
		    } else if (charArray[k] > charArray[j]) {
			i = j + 1;
			break;
		    }
		    k++;
		    j++;
		}
	    }
	    i++;
	}
	return str.substring(rstart);
    }

}

Time complexity Min{ mlogm, n} where m in number of ranges and n is the end range

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

public class MinimumCost {
    private int INT_MAX = 999999999;

    public static void main(String[] args) {
	MinimumCost obj = new MinimumCost();
	List<Range> ranges = new ArrayList<>();
	ranges.add(obj.createRange(0, 1, 1.0));
	ranges.add(obj.createRange(1, 2, 1.0));
	ranges.add(obj.createRange(2, 4, 2.0));
	ranges.add(obj.createRange(2, 5, 3.0));
	ranges.add(obj.createRange(1, 3, 1.0));
	ranges.add(obj.createRange(0, 2, 2.0));
	ranges.add(obj.createRange(3, 5, 2.0));
	System.out.println(obj.findMinimumCostToPaint(5, ranges));
    }

    public Range createRange(int start, int end, double cost) {
	return new Range(start, end, cost);
    }

    public class Range {
	private int start;
	private int end;
	private double cost;

	public Range(int start, int end, double cost) {
	    this.start = start;
	    this.end = end;
	    this.cost = cost;
	}

	public int getStart() {
	    return start;
	}

	public int getEnd() {
	    return end;
	}

	public double getCost() {
	    return cost;
	}

    }

    public class RangeComparator implements Comparator<Range> {

	@Override
	public int compare(Range o1, Range o2) {
	    if (o1.getStart() == o2.getStart()) {
		return Integer.compare(o1.getEnd(), o2.getEnd());
	    }
	    return Integer.compare(o1.getStart(), o2.getEnd());
	}

    }

    public double findMinimumCostToPaint(int n, List<Range> ranges) {
	double[] result = new double[n + 1];
	for (int i = 1; i <= n; i++) {
	    result[i] = INT_MAX;
	}
	result[0] = 0;
	Collections.sort(ranges, new RangeComparator());
	for (Range r : ranges) {
	    double temp = result[r.getStart()] + r.getCost();
	    if (temp < result[r.getEnd()]) {
		result[r.getEnd()] = temp;
	    }
	}
	if (result[n] == INT_MAX) {
	    return -1;
	}
	return result[n];
    }

}

public class BitSet {

    public static void main(String[] args) {
	BitSet b = new BitSet();
	b.generateBit(3);
    }

    public void generateBit(int k) {
	for (int i = 0; i <= k; i++) {
	    generateBitSet(k, i, "");
	}
    }

    public void generateBitSet(int size, int d, String suffix) {
	if (d < 0) {
	    return;
	}
	if (size <= 0) {
	    System.out.println(suffix);
	} else if (size == d) {
	    generateBitSet(size - 1, d - 1, "1" + suffix);
	} else {
	    generateBitSet(size - 1, d - 1, "1" + suffix);
	    generateBitSet(size - 1, d, "0" + suffix);
	}
    }

}

public void getGoodNumbers(int limit) {
List<String> output = new ArrayList<>();
int i = 1;
int jMax = (int) Math.cbrt(limit);
while (i < jMax - 3) {
int j = i + 3;
while (j <= jMax) {
long iCube = i * i * i;
long jCube = j * j * j;
long n = iCube + jCube;
if (n > limit) {
break;
}
// System.out.println("****i,j******");
// System.out.println(i + "\t" + j);
int start = i + 1;
int end = j - 1;
while (start < end) {
// System.out.println("****start,end******");
// System.out.println(start + "\t" + end);
long res = (start * start * start) + (end * end * end);
if (res == n) {
output.add(start + " & " + end + " AND " + i + " & " + j);
break;
} else if (res < n) {
start++;
} else {
end--;
}
}
j++;
}
i++;
}
System.out.println(output);
}

Why are checking if (s.charAt(i)==s.charAt(i+1)) and if (s.charAt(i)==s.charAt(i+2))? Does not look like a correct solution

Python code

def recur(i,j,n,arr):
    if i < j: 
        display(arr, i,j)
        y = int(n/2)
        for x in xrange(i,y+1):
            if x <= j-x:
                arr.append(i)
                if j-x >= i:
                    recur(x,j-x,j,arr[:])
        
                arr.remove(i)


    elif i == j:
        display(arr,i,j)

    
def compute(n):
    print "Combination sum for ",n
    if (n<=1):
        return

    y = int(n/2)
    for x in xrange(1,y+1):
        arr = []
        recur(x,n-x,n,arr)

def display(arr, i, j):
    newarr = arr[:]
    newarr.append(i)
    newarr.append(j)
    print newarr


input = int(raw_input())
compute(input)

lookup does takes key and gives back value
rangeLookup takes two keys key1 and key2 and returns all the key value pair which lies between key1 and key2 in lexicographically order