just_do_it
BAN USERonly considering quadruplets involving arr[0]
- just_do_it October 15, 2014array could be sorted in decreasing order, may have to repeat the same starting from the end of array and pick min of two kth elements from end-points
- just_do_it August 06, 2014public class CoverWithMinimumWindowSize {
protected static class Element implements Comparator<Element>{
int value;
int listIndex;
int positionInList;
Element(){
}
Element(int value, int listIndex,int positionInList){
this.value = value;
this.listIndex = listIndex;
this.positionInList = positionInList;
}
public int compare(Element e1, Element e2){
return e1.value-e2.value;
}
}
public static int findCoverWithMinimumWindowSize(List<int[]> lists) throws Exception{
int numLists = lists.size();
if(numLists == 1){
throw new Exception("Only one list");
}
int index[] = new int[numLists];
int listSize[] = new int[numLists];
for(int i = 0; i < numLists; i++){
int[] listi = lists.get(i);
Arrays.sort(listi);
listSize[i] = listi.length;
if(listSize[i] == 0){
throw new Exception("Empty list " + i);
}
}
boolean done=false;
Arrays.fill(index, 0);
int windowStart,windowEnd;
PriorityQueue<Element> minHeap = new PriorityQueue<Element>(numLists,new Element(0,0,0));
PriorityQueue<Element> maxHeap = new PriorityQueue<Element>(numLists,Collections.reverseOrder(new Element(0,0,0)));
for(int i = 0; i < numLists; i++){
int[] listi = lists.get(i);
Element elem = new Element(listi[0],i,0);
minHeap.add(elem);
maxHeap.add(elem);
}
Element minElement = minHeap.peek();
Element maxElement = maxHeap.peek();
int maxWindowSize = -1;
while(!done){
minElement = minHeap.peek();
windowStart = minElement.value;
int minElementSource = minElement.listIndex;
int positionInList = minElement.positionInList;
maxElement = maxHeap.peek();
windowEnd = maxElement.value;
int windowSize=windowEnd-windowStart;
if(maxWindowSize == -1){
maxWindowSize = windowSize;
} else if(windowSize < maxWindowSize){
maxWindowSize = windowSize;
}
minHeap.poll();
maxHeap.remove(minElement);
if(positionInList+1 < listSize[minElementSource]){
int[] listi = lists.get(minElementSource);
int value = listi[positionInList+1];
Element elem = new Element(value,minElementSource,positionInList+1);
minHeap.add(elem);
maxHeap.add(elem);
positionInList++;
} else {
done = true;
}
}
return maxWindowSize;
}
public static void main(String[] args) throws Exception{
int list1[] = {4, 10, 15, 20};
int list2[] = {1, 13, 29};
int list3[] = {5, 14, 28};
List<int[]> testcase = new LinkedList<int[]>();
testcase.add(list1);
testcase.add(list2);
testcase.add(list3);
int result = findCoverWithMinimumWindowSize(testcase);
System.out.println(result);
}
}
If we assume that pair sums should not repeat, this could be little more involved that the matching algorithm
1 , 3 , 5 , 7 , 9 , 11 and k=12
#distinct sums = 1
The conditions listed earlier are necessary but not sufficient. You may want to look at
> find (i,j) such that xi+xj %k = 0, add a node for the sum and add a directed edge from (i,j) to sum, assume edge capacity 2
> add directed edges from sums to a sink node, assume edge capacity 2
> add directed edges from i to (i,j) and j to (i,j) assume edge capacity 1
> add directed edges of capacity 1 from a source node to i
Check if max flow from source to sink = n
public class MinSequenceSumAboveTarget {
static void identifyMinSequenceSumAboveTarget(int arr[], int target){
int size = arr.length;
int currSum=0;
int currWindowStart=0;
int currSolnStart=-1, currSolnEnd=-1;
int begin=0;
while(begin < size){
int x = arr[begin]+currSum;
if(x > 0){
if(x<target){
currSum = x;
} else {
// keep moving start if sum keeps above target
while(x-arr[currWindowStart] >= target){
x -= arr[currWindowStart];
currWindowStart++;
}
if((currSolnStart==-1) || ((begin-currWindowStart) < (currSolnEnd - currSolnStart))){
currSolnStart=currWindowStart;
currSolnEnd=begin;
}
currSum = x;
}
}
begin++;
}
if(currSolnStart>=0){
System.out.println("Best solution\t"+currSolnStart + " -> " + currSolnEnd);
}
}
public static void main(String[] args) throws Exception{
int testcase[] = { 1,2,1,1,4,3,6 };
int target = 8;
System.out.println(Arrays.toString(testcase));
identifyMinSequenceSumAboveTarget(testcase, target);
int testcase2[] = { 1,2,9,1,1,4,3,6 };
int target2 = 9;
System.out.println(Arrays.toString(testcase2));
identifyMinSequenceSumAboveTarget(testcase2, target2);
}
}
public class IslandWanderSurvivalProbability {
static double survivalProbability(int x, int y, int N, int n){
if(x < 0 || x >= N || y < 0 || y >= N){
return 0;
}
double p[][] = new double[N][N];
for(int i = 0; i < N; i++){
for(int j = 0; j < N; j++){
p[i][j] = 0.0;
}
}
p[x][y] = 1.0;
p = computeStateSurvivalProbabilities(p, N, n);
double pSum = 0;
for(int i = 0; i < N; i++){
for(int j = 0; j < N; j++){
pSum += p[i][j];
}
}
if(n < 3){
for(int i = 0; i < N; i++)
System.out.println(Arrays.toString(p[i]));
}
return pSum;
}
static double[][] computeStateSurvivalProbabilities(double p[][], int N, int n){
double pUptoNMinus1[][] = p;
if(n == 0){
return p;
} else if(n > 1){
pUptoNMinus1 = computeStateSurvivalProbabilities(p,N,n-1);
}
double pNextStep[][] = new double[N][N];
for(int i = 0; i < N; i++){
for(int j = 0; j < N; j++){
pNextStep[i][j] = 0.0;
}
}
for(int i = 0; i < N; i++){
for(int j = 0; j < N; j++){
if(i+1 < N){
pNextStep[i+1][j] += 0.25*pUptoNMinus1[i][j];
}
if(j+1 < N){
pNextStep[i][j+1] += 0.25*pUptoNMinus1[i][j];
}
if(i-1 >=0){
pNextStep[i-1][j] += 0.25*pUptoNMinus1[i][j];
}
if(j-1 >=0){
pNextStep[i][j-1] += 0.25*pUptoNMinus1[i][j];
}
}
}
return pNextStep;
}
public static void main(String[] args) throws Exception{
for(int n = 0; n < 20; n++){
double pSurvival = survivalProbability(1,1,3,n);
System.out.println(n + "\t" + pSurvival);
}
}
}
public class MinPairSumFromDigits {
static long minPairSumFromNumbersBuiltFromDigits(int digits[]) throws Exception{
if(digits == null){
throw new Exception("Invalid argument " + digits);
} else {
for(int i : digits){
if(i < 0 || i > 9){
throw new Exception("Invalid argument " + i);
}
}
}
Arrays.sort(digits);
int n = digits.length;
List<Integer> digitsOfNum1 = new LinkedList<Integer>();
List<Integer> digitsOfNum2 = new LinkedList<Integer>();
int leadingDigitNum1 = 0;
int begin = 0;
if(n%2 == 1){
leadingDigitNum1 = digits[begin++];
}
for(int i = n-1; i >= begin; i--){
if(i%2 == 0){
digitsOfNum2.add(digits[i]);
} else {
digitsOfNum1.add(digits[i]);
}
}
digitsOfNum1.add(leadingDigitNum1);
String num1Str = "";
String num2Str = "";
for(int i : digitsOfNum1){
num1Str = i + num1Str;
}
for(int i : digitsOfNum2){
num2Str = i + num2Str;
}
long num1 = Long.parseLong(num1Str);
long num2 = Long.parseLong(num2Str);
System.out.println("num1\t"+num1 + "\tnum2\t" + num2);
return num1+num2;
}
public static void main(String[] args) throws Exception{
int testcase1[] = { 1 , 2 , 7 , 8 , 9 };
int result1 = 207;
int testcase2[] = { 1 , 2 , 5 , 7 , 8 , 9 };
int result2 = 437;
System.out.println(Arrays.toString(testcase1));
long x = minPairSumFromNumbersBuiltFromDigits(testcase1);
System.out.println(result1 + "\t" + x);
System.out.println(Arrays.toString(testcase2));
x = minPairSumFromNumbersBuiltFromDigits(testcase2);
System.out.println(result2 + "\t" + x);
}
}
//Simpler recursive version
static void printAllPathsSumToValue(Node root, int targetSum){
if(root == null) return;
LinkedList<Node> currentPath = new LinkedList<Node>();
Map<Node,Integer> pathSums = new HashMap<Node,Integer>();
Map<Node,Integer> nodeHeight = new HashMap<Node, Integer>();
printAllPathsSumToValue(currentPath, root, targetSum, pathSums, nodeHeight, 0 );
}
static void printAllPathsSumToValue(LinkedList<Node> currentPath, Node currNode, int targetSum,
Map<Node,Integer> pathSums, Map<Node,Integer> nodeHeight, int currNodeHeight){
currentPath.push(currNode);
int currNodeValue = currNode.value;
pathSums.put(currNode, currNodeValue);
nodeHeight.put(currNode, currNodeHeight);
for(Node ancestor : pathSums.keySet()){
int sumTillParentCurrNode = pathSums.get(ancestor);
if(sumTillParentCurrNode + currNodeValue == targetSum){
printPath(currentPath, ancestor, nodeHeight.get(ancestor));
}
}
pathSums.put(currNode, currNodeValue);
if(currNodeValue == targetSum){
printPath(currentPath, currNode, nodeHeight.get(currNode));
}
if(currNode.leftChild != null){
printAllPathsSumToValue(currentPath, currNode.leftChild, targetSum, pathSums, nodeHeight, currNodeHeight+1);
}
if(currNode.rightChild != null){
printAllPathsSumToValue(currentPath, currNode.rightChild, targetSum, pathSums, nodeHeight, currNodeHeight+1);
}
currentPath.pop();
pathSums.remove(currNode);
nodeHeight.remove(currNode);
}
static void printPath(LinkedList<Node> currentPath, Node startAncestor, int startAncestorHeight){
for(int h = startAncestorHeight; h < currentPath.size(); h++){
Node currNode = currentPath.get(h);
System.out.print(currNode + "\t->\t");
}
System.out.println();
}
public class AllPathsSumToValue {
class Node {
int value;
Node leftChild, rightChild;
}
/**
* DFS on the tree, maintain sums upto current that start at every node in the stack
* @param root
* @param targetSum
*/
static void printAllPathsSumToValue(Node root, int targetSum){
if(root == null) return;
LinkedList<Node> currentPath = new LinkedList<Node>();
// use a AVL tree / RB tree for faster lookup later
Map<Node,Integer> pathSums = new HashMap<Node,Integer>();
Map<Node,Integer> nodeHeight = new HashMap<Node, Integer>();
currentPath.push(root);
int currNodeValue = root.value;
if(currNodeValue == targetSum){
printPath(currentPath, root , 0);
}
pathSums.put(root, currNodeValue);
nodeHeight.put(root, 0);
while(!currentPath.isEmpty()){
Node currNode = currentPath.peek();
int currNodeHeight = nodeHeight.get(currNode);
Node nextNode = null;
int nextNodeHeight = currNodeHeight;
if(currNode.leftChild != null){
nextNode = currNode.leftChild;
nextNodeHeight++;
} else if(currNode.rightChild != null){
nextNode = currNode.rightChild;
nextNodeHeight++;
} else {
while(nextNode == null){
currentPath.pop();
pathSums.remove(currNode);
nodeHeight.remove(currNode);
if(currentPath.isEmpty()){
break;
}
Node parentNode = currentPath.peek();
if(currNode == parentNode.leftChild && parentNode.rightChild != null){
nextNode = parentNode.rightChild;
} else {
pathSums.remove(currNode);
currNodeValue = currNode.value;
for(Node ancestor : pathSums.keySet()){
int sumTillParentCurrNode = pathSums.get(ancestor);
pathSums.put(ancestor, sumTillParentCurrNode-currNodeValue);
}
currNode = parentNode;
nextNodeHeight--;
}
}
}
if(nextNode != null){
currNode = nextNode;
currentPath.push(currNode);
nodeHeight.put(nextNode, nextNodeHeight);
currNodeValue = currNode.value;
for(Node ancestor : pathSums.keySet()){
int sumTillParentCurrNode = pathSums.get(ancestor);
if(sumTillParentCurrNode + currNodeValue == targetSum){
printPath(currentPath, ancestor, nodeHeight.get(ancestor));
}
}
pathSums.put(currNode, currNodeValue);
if(currNodeValue == targetSum){
printPath(currentPath, currNode, nodeHeight.get(currNode));
}
}
}
}
static void printPath(LinkedList<Node> currentPath, Node startAncestor, int startAncestorHeight){
for(int h = startAncestorHeight; h < currentPath.size(); h++){
Node currNode = currentPath.get(h);
System.out.print(currNode + "\t->\t");
}
System.out.println();
}
}
public class ArrangeInCustomOrder {
/**
* target order provided in the form which indicates the index of sorted(a[i]) that occurs at a particular position
* would be nice if targetOrder[i] indicated where sorted(a)[i] should go to
*/
static void rearrange(int a[] , int targetOrder[]){
invertPermutation(targetOrder);
Arrays.sort(a);
for(int i = 0; i < a.length; i++){
if(targetOrder[i] > 0){
int targetLocation = targetOrder[i]-1;
// flip signs to track which positions are already processed
targetOrder[i] = 0-targetOrder[i];
if(targetLocation != i){
int temp = a[targetLocation];
int locationOfHole = i;
a[targetLocation] = a[i];
int j = targetLocation;
int elementAtJOriginal = temp;
//System.out.println((j+1) + "\t" + Arrays.toString(a) + "\t" + elementAtJOriginal);
boolean done = false;
while(!done){
int targetLocationPrev = targetLocation;
targetLocation = targetOrder[j]-1;
targetOrder[j] = 0-targetOrder[j];
if(targetLocationPrev == locationOfHole){
done = true;
} else{
int temp2 = a[targetLocation];
a[targetLocation] = elementAtJOriginal;
j = targetLocation;
elementAtJOriginal = temp2;
//System.out.println((j+1) + "\t" + Arrays.toString(a) + "\t" + elementAtJOriginal);
}
}
}
}
}
for(int i = 0; i < a.length; i++){
if(targetOrder[i] < 0)
targetOrder[i] = 0-targetOrder[i];
}
invertPermutation(targetOrder);
}
/**
* example input: 3 , 2 , 4 , 1
* output: 4 , 2 , 1 , 3
*/
static void invertPermutation(int ordering[]){
for(int i = 0; i < ordering.length; i++){
if(ordering[i] > 0){
int elementAtIOriginal = ordering[i]-1;
// flip signs to track which positions are already processed
ordering[i] = 0-ordering[i];
if(elementAtIOriginal != i){
int temp = ordering[elementAtIOriginal];
int locationOfHole = i;
ordering[elementAtIOriginal] = i+1;
int j = elementAtIOriginal;
int elementAtJOriginal = temp-1;
boolean done = false;
//System.out.println((j+1) + "\t" + Arrays.toString(ordering) + "\t" + (elementAtJOriginal+1));
while(!done){
ordering[elementAtIOriginal] = 0-ordering[elementAtIOriginal];
if(elementAtIOriginal == locationOfHole){
done = true;
} else{
int temp2 = ordering[elementAtJOriginal];
ordering[elementAtJOriginal] = j+1;
elementAtIOriginal = elementAtJOriginal;
elementAtJOriginal = temp2-1;
j = elementAtIOriginal;
//locationOfHole = elementAtIOriginal;
}
//System.out.println((j+1) + "\t" + Arrays.toString(ordering) + "\t" + (elementAtJOriginal+1));
}
}
}
}
for(int i = 0; i < ordering.length; i++){
if(ordering[i] < 0)
ordering[i] = 0-ordering[i];
}
}
public static void main(String[] args){
int customOrdering[] = { 3 , 2 , 4 , 1 };
System.out.println(Arrays.toString(customOrdering));
invertPermutation(customOrdering);
System.out.println(Arrays.toString(customOrdering));
invertPermutation(customOrdering);
System.out.println(Arrays.toString(customOrdering));
int a[] = { 17, 5 , 1 , 9};
System.out.println(Arrays.toString(a));
rearrange(a,customOrdering);
System.out.println(Arrays.toString(a));
}
}
// was not easily solvable in 45 minutes / 1 hour
/**
*
* @author just_do_it
*
* Check if there exists positive integral solution to
* 6a + 9b + 20c = n
*
* you can assume n < 60
since for n>60, one of n-60, n-20 or n-40 is divisible by 3 and can be assembled from 6 and 9
*/
public class McDonaldPurchaseProblem {
/*static boolean solvable[] = new boolean[60];
static void precomputeSolvableNumbersLessThan60(){
}*/
static boolean solvable(int n){
if(n>=60) return true;
int m = n%60;
if(m == 0){
return true;
} else {
if(m %3 == 0){
if(m >=6){
return true;
}
} else if (m < 20){
return false;
}
if(m %20 == 0){
return true;
} else {
if(m>20 && (m-20) %3 == 0 && m-20 >= 6){
return true;
}
if(m>40 && (m-40) %3 == 0 && m-40 >= 6){
return true;
}
}
}
return false;
}
public static void main(String[] args){
for(int i = 1; i < 60; i++){
System.out.println(i + "\t" + solvable(i));
}
}
}
public class MinDeletionsToMakePalindrome {
static boolean isKPalindrome(String s, int K){
if(s == null){
return false;
}
int m = minDeletionsToMakePalindrome(s);
if(m <= K){
return true;
} else {
return false;
}
}
static int minDeletionsToMakePalindrome(String s){
char[] sChar = s.toCharArray();
int n = sChar.length;
char sInvChar[] = new char[n];
for(int i = 0; i < n; i++){
sInvChar[i] = sChar[n-1-i];
}
String sInv = new String(sInvChar);
int m = computeEditDistance(s, sInv);
return (int) Math.ceil((float)m/2.0);
}
static int computeEditDistance(String s1, String s2){
int n1 = s1.length();
int n2 = s2.length();
char[] s1_c = s1.toCharArray();
char[] s2_c = s2.toCharArray();
int[][] d = new int[n1+1][n2+1];
for(int i1 = 0; i1 <= n1; i1++){
d[i1][0] = i1;
}
for(int i2 = 0; i2 <= n2; i2++){
d[0][i2] = i2;
}
for(int i1 = 1; i1 <= n1; i1++){
for(int i2 = 1; i2 <= n2; i2++){
int d10 = d[i1-1][i2]+1;
int d01 = d[i1][i2-1]+1;
int dmin = Math.min(d10, d01);
if(s1_c[i1-1] == s2_c[i2-1]){
int d00 = d[i1-1][i2-1];
dmin = Math.min(dmin, d00);
}
d[i1][i2] = dmin;
}
}
return d[n1][n2];
}
public static void main(String[] args){
System.out.println("test edit distance calc:\t" + computeEditDistance("bb","cbb"));
String[] testcases = {"a" , "aa", "abxa" , "abdxa" , "dbaacbd" , "bdaacbd"};
int[] results = {0 , 0 , 1 , 2 , 1 , 3 };
for(int i = 0; i < testcases.length; i++){
String s = testcases[i];
int n = minDeletionsToMakePalindrome(s);
System.out.println(s + "\t" + n + "\t" + results[i]);
}
}
}
public class MinPositiveNotInArray {
static int minPositiveNotInArray(int a[]){
int n = a.length;
// need to keep track of the end points of ranges for the endpoints only
Map<Integer,Integer> rangeMinWithElement = new HashMap<Integer,Integer>();
Map<Integer,Integer> rangeMaxWithElement = new HashMap<Integer,Integer>();
for(int i = 0; i < n; i++){
if(a[i] > 0){
int min = a[i], max = a[i];
if(!rangeMinWithElement.containsKey(a[i])){
rangeMinWithElement.put(a[i], a[i]);
}
if(!rangeMaxWithElement.containsKey(a[i])){
rangeMaxWithElement.put(a[i], a[i]);
}
if(rangeMinWithElement.containsKey(a[i]-1)){
min = rangeMinWithElement.get(a[i]-1);
}
if(rangeMaxWithElement.containsKey(a[i]+1)){
max = rangeMaxWithElement.get(a[i]+1);
}
//System.out.println(a[i] + "\t" + min + "\t" + max);
rangeMaxWithElement.put(min, max);
rangeMinWithElement.put(max, min);
}
}
if(!rangeMinWithElement.containsKey(1)){
return 1;
} else {
int max = rangeMaxWithElement.get(1);
return max+1;
}
}
public static void main(String[] args){
int[] testcase1 = {-2 , 1 , 5 , 8 , -8 , -6 , 0 , 2};
int res1 = 3;
int[] testcase2 = {-2 , 1 , 5 , 8 , -8 , -6 , 0 , 2 , 3 , 4};
int res2 = 6;
System.out.println(Arrays.toString(testcase1));
System.out.println(minPositiveNotInArray(testcase1)+ "\t" + res1);
System.out.println(Arrays.toString(testcase2));
System.out.println(minPositiveNotInArray(testcase2)+ "\t" + res2);
}
}
public class GoogleHireProblem {
static boolean validWordInLanguage(String s){
if(s.length() == 0){
return false;
}
// check if concatenated by two valid words
char[] sChars = s.toCharArray();
int numOccurencesOfHInWord1=0;
boolean done=false;
int i = 0;
while(!done && i < sChars.length){
if(sChars[i] == 'h'){
i++;
numOccurencesOfHInWord1++;
} else if(sChars[i] == 'i') {
done = true;
break;
} else {
return false;
}
}
int numOccurencesOfIInWord1 = 0;
done = false;
while(!done && i < sChars.length){
if(sChars[i] == 'i'){
i++;
numOccurencesOfIInWord1++;
} else if(sChars[i] == 'r') {
done = true;
break;
} else {
return false;
}
}
if(numOccurencesOfHInWord1 != numOccurencesOfIInWord1){
return false;
}
int numOccurencesOfRInWord1 = 0;
done = false;
while(!done && i < sChars.length){
if(sChars[i] == 'r'){
i++;
numOccurencesOfRInWord1++;
} else if(sChars[i] == 'e'){
done = true;
break;
} else {
return false;
}
}
if(numOccurencesOfIInWord1 != numOccurencesOfRInWord1){
return false;
}
int numOccurencesOfEInWord1 = 0;
done = false;
while(!done && i < sChars.length){
if(sChars[i] == 'e'){
i++;
numOccurencesOfEInWord1++;
} else if(sChars[i] == 'h'){
done = true;
break;
} else {
return false;
}
}
if(numOccurencesOfRInWord1 != numOccurencesOfEInWord1){
return false;
}
if(i < sChars.length-1){
String word2 = s.substring(i);
//System.out.println(word2);
return(validWordInLanguage(word2));
} else {
return true;
}
}
public static void main(String[] args){
String[] testcases = {"hire" , "", "hhiirree" , "hhiirreehire"};
for(String s : testcases){
boolean isValidWord = validWordInLanguage(s);
System.out.println(s + "\t" + isValidWord);
}
}
}
public class DeepestOneInBinaryTree {
class Node{
int value;
Node leftChild, rightChild;
boolean isLeftChildOfRoot;
}
static int deepestOneInTree(Node root){
if(root == null){
return 0;
}
Stack<Node> pathFromRoot = new Stack<Node>();
pathFromRoot.add(root);
Node longestPathEndPoint;
int maxLengthOfValidPath=0;
int currentLengthOfValidPath=0;
while(!pathFromRoot.empty()){
Node currNode = pathFromRoot.peek();
boolean doneProcessingNode = false;
if(currNode.value == 1){
currentLengthOfValidPath = pathFromRoot.size();
if(currentLengthOfValidPath > maxLengthOfValidPath){
maxLengthOfValidPath = currentLengthOfValidPath;
longestPathEndPoint = currNode;
}
if(currNode.leftChild != null){
pathFromRoot.push(currNode.leftChild);
currNode.leftChild.isLeftChildOfRoot = true;
} else if(currNode.rightChild != null){
pathFromRoot.push(currNode.rightChild);
currNode.rightChild.isLeftChildOfRoot = false;
} else {
doneProcessingNode = true;
}
} else {
doneProcessingNode = true;
}
if(doneProcessingNode){
pathFromRoot.pop();
boolean stackInValidState = false;
while(!stackInValidState){
if(pathFromRoot.empty()){
break;
}
Node parentOfCurrNode = pathFromRoot.peek();
if(currNode.isLeftChildOfRoot){
if(parentOfCurrNode.rightChild != null){
pathFromRoot.push(parentOfCurrNode.rightChild);
stackInValidState = true;
} else {
currNode = pathFromRoot.pop();
}
}
}
}
}
return maxLengthOfValidPath;
}
}
public class FindLargestUniformWindow {
// false = 0, true = 1
static int findLargestUniformWindow(Boolean a[]){
int n = a.length;
if(n<=1){
return 0;
}
//int numZerosMinusNumOnes[] = new int[n];
int numZerosMinusNumOnesCurr = 0;
Map<Integer,Integer> valVsLowestIndexWhereOccured = new HashMap<Integer,Integer>();
valVsLowestIndexWhereOccured.put(0, -1);
int maxWindowLength = 0;
for(int i = 0; i < n; i++){
//numZerosMinusNumOnes[i] = numZerosMinusNumOnesCurr;
boolean val = a[i];
if(!val){
numZerosMinusNumOnesCurr++;
} else {
numZerosMinusNumOnesCurr--;
}
if(!valVsLowestIndexWhereOccured.containsKey(numZerosMinusNumOnesCurr)){
valVsLowestIndexWhereOccured.put(numZerosMinusNumOnesCurr, i);
} else {
int windowLengthCur = i - valVsLowestIndexWhereOccured.get(numZerosMinusNumOnesCurr);
if(windowLengthCur > maxWindowLength){
maxWindowLength = windowLengthCur;
}
}
//System.out.println(i + "\t" + numZerosMinusNumOnesCurr + "\t" + valVsLowestIndexWhereOccured.get(numZerosMinusNumOnesCurr));
}
return maxWindowLength;
}
public static void main(String[] args){
Boolean[] testcase = {false, false, true,true, false, true, false, false, false, false, true};
int result = 6;
System.out.println(Arrays.toString(testcase));
int m = findLargestUniformWindow(testcase);
System.out.println(m + "\t" + result);
}
}
example: -1 , 1 , 3 , -2 , 2, -4 , 4 , 5 , -5
O(n) time O(1) space solution
Count the number of negative elements (k = 4 here) , as a first step try to get first 4 elements in correct order, every time you swap an element out record its index, let f be the encoding function for negatives and g for positives.
Step1.1 : -1 , 1 , -4 , -5 , 2 , g(3,3), 4 , 5 , f(-2,4)
Step1.2 ( f(x,y) will be in the order f(x1, y1), f(x2, y2), f(x3, y3) , ..., where y1 < y2 < y3 < .. , same property holds for g). But you have the rest of the negative elements in their final destinations, freeze these elements. Treat f(x,y) as your new negatives on an array, perform swaps similar to step1, let h be the encoding function for positives dislocated in this step:
-1 , f(-2,4) , -4 , -5 , 2 , g(3,3) , 4 , 5 , h(1,2)
Step2: Stable sort the unfrozen negative elements
Step3: Now you are done with all the negatives. You have the property max(y / h(x,y)) < max(y / g(x,y)), again h(x,y) will appear in increasing order of y. Stable sort h union g relative to the other positives:
<all negatives> , h(1,2) , g(3,3), 2 , 4 , 5
You can always pick to work on the positives first / negatives first based on the sizes of arrays appearing in the recursive step. So you would have
T(n) = O(n) + T(a) + T(b) ( where a+b < 3n/4)
so T(n) = O(n)
It is unreasonable to expect someone to solve this within 1 hour
need clarification:
input: 121221312
output: 1 , 2 , 12 with tokenization 1 2 12 2 1 3 12 ??
input: 1212213
output: 1 , 2 , 3 with tokenization 1 2 1 2 2 1 3 ??
package interview_questions;
/**
*
* @author just_do_it
*
*/
public class CountBinaryHeaps {
/*
* f(38) = 37C22 * f(15) * f(22)
*/
static long numBinaryHeaps(int n){
if(n == 1 || n == 2) {
return 1;
} else if (n == 3){
return 2;
}
int numElementsChild1, numElementsChild2;
int n1 = largestPowerOf2LessOrEqual(n);
if(n1 - 1 + n1/2 >= n){
numElementsChild1 = n1/2 - 1;
numElementsChild2 = n - n1/2;
} else {
numElementsChild1 = n1 -1;
numElementsChild2 = n - n1;
}
long res = choose(n-1,numElementsChild1) * numBinaryHeaps(numElementsChild1) * numBinaryHeaps(numElementsChild2);
return res;
}
public static int choose(int n, int m){
if(n < m)
return 0;
if(m == 0 || n == m)
return 1;
return choose(n-1,m-1)+choose(n-1,m);
}
static int largestPowerOf2LessOrEqual(int n){
int pow2 = 1;
while(pow2*2 < n){
pow2 *= 2;
}
return pow2;
}
public static void main(String[] args){
int[] testcases = {1 , 2 , 3 , 4 , 5 , 6};
long[] results = {1 , 1 , 2 , 3 , 4*2, 10*2 };
for(int i = 0; i < testcases.length; i++){
int n = testcases[i];
long res = numBinaryHeaps(n);
System.out.println(n + "\t" + res + "\t" + results[i]);
}
}
}
- just_do_it October 15, 2014