naren
BAN USERWhen you map the nodes to a coordinate system and sort the nodes by X-Coordinate (if X coordinate is equal, sort it by Y-coordinate), then you will get the answer in the right order.
Root will (0,0).
Left turn will be (x-1,y+1) and right turn will be (x+1,y+1)
In the above example, 6 is mapped to (0,0) , 3 is mapped to (-1,1) and 1 is mapped to (0,2).
Time complexity O(NLOGN) using priority queues
space complexity is O(N).
public Node(Node left, Node right, int value) {
this.left = left;
this.right = right;
this.value = value;
}
class NodePriority implements Comparable<NodePriority>{
private final Node node;
private final int x;
private final int y;
public NodePriority(Node n, int x,int y) {
this.node = n;
this.x = x;
this.y = y;
}
@Override
public int compareTo(NodePriority o) {
if(this.x == o.x) return this.y - o.y;
return this.x - o.x;
}
public Node getNode(){
return node;
}
}
static PriorityQueue<NodePriority> pq4Nodes = new PriorityQueue<>();
public static void processNodesByColumns(Node node, int x,int y) {
if(node == null) return;
pq4Nodes.add(new NodePriority(node, x,y));
processNodesByColumns(node.left,x-1,y+1);
processNodesByColumns(node.right,x+1,y+1);
}
public static void main(String[] args) {
Node n9 = new Node(null,null,9);
Node n7 = new Node(null,null,7);
Node n1 = new Node(null,null,1);
Node n8 = new Node(null,null,8);
Node n2 = new Node(null,n7,2);
Node n5 = new Node(n9,n2,5);
Node n3 = new Node(n5,n1,3);
Node n0 = new Node(n8,null,0);
Node n4 = new Node(null,n0,4);
Node n6 = new Node(n3,n4,6);
processNodesByColumns(n6, 0,0);
while(!pq4Nodes.isEmpty()) {
NodePriority head = pq4Nodes.poll();
System.out.println(head.getNode().value);
}
}
I am going to make the java Regex do the work for me:
public static void main(String[] args) {
String pattern = "xyz";
String text = "xyzxyzxyz";
String [] delimitingStrs = text.split("("+pattern+")+");
if(delimitingStrs.length == 0)
System.out.println("Contains the pattern");
else
System.out.println("Does not contain the pattern");
}
Recently found that Prof Skiena has a nice Java Class for any backtracking problem. Here is my attempt at doing this: All of you have to do overwrite a few methods and you are good with any backtracking problem.. For more info on this, check youtube "skiena backtracking"
class BackTracking {
static boolean finished = false;
static final int MAXCANDIDATES = 100;
static final int NMAX = 100;
static void backtrack(char a[], int k, int input) {
char c[] = new char[MAXCANDIDATES];
int ncandidates, i;
if (is_a_solution(a, k, input))
process_solution(a, k, input);
else {
k++;
ncandidates = construct_candidates(a, k, input, c);
for (i = 0; i < ncandidates; i++) {
a[k] = c[i];
make_move(a, k, input);
backtrack(a, k, input);
if (finished)
return;
unmake_move(a, k, input);
}
if(ncandidates > 1) a[k] = '?';
}
}
static void make_move(char a[], int k, int n) {
}
static void unmake_move(char a[], int k, int n) {
}
static void process_solution(char a[], int k, int n) {
System.out.println(new String(a));
}
static boolean is_a_solution(char a[], int k, int n) {
return k == n;
}
static int construct_candidates(char a[], int k, int n, char c[]) {
if(a[k] == '?') {
c[0] = '0';
c[1] = '1';
return 2;
}
c[0] = a[k];
return 1;
}
static public void main(String[] args) {
char a[] = "0?1?".toCharArray();
backtrack(a, 0, a.length-1);
}
}
Ok for design purists, this class can be declared abstract and all methods can be designed as generic but more starters, this is good enough..
- naren December 20, 2014First one:
Check for Zero in the matrix and whether it is surrounded by 1's.
M[i][j] ==0 && M[i+1][j] == 1 && M[i-1][j] == 1 && M[i-1]j-1] == 1 && M[i+1][j+1] == 0 && M[i][j-1] == 0 && M[i][j+1] ==0. // Ofcourse take care of corner cases such as edges etc
Second one: As per my understanding, if it takes one change from 1 to zero, then changes required to make 1 pond: (#no of ponds -1 ) provided #noOfPonds > 1
@rizhang. you are right. There was one glitch in the code which is corrected. Now it works for any length of digits(+ve integers ofcourse). Revised code here with updated inputs for the program
public class DictionarySort {
public static void main(String[] args) {
Integer[] array = new Integer[] { 1, 2, 2222, 222222, 10, 20, 100, 110,
3333, 332,111111111,2222222,233332,66666666,1111111,9090,8880 };
System.out.println(Arrays.toString(array));
Arrays.sort(array, new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
int quotient1 = o1 / 10;
int reminder1 = o1 % 10;
int quotient2 = o2 / 10;
int reminder2 = o2 % 10;
if (quotient1 != 0 && quotient2 != 0) {
if (quotient1 == quotient2)
return reminder1 - reminder2;
int msd1 = 0;
int msd2 = 0;
if (quotient1 >= 10) {
msd1 = quotient1 / 10;
while (msd1 >= 10)
msd1 = msd1 / 10;
} else
msd1 = quotient1;
if (quotient2 >= 10) {
msd2 = quotient2 / 10;
while (msd2 >= 10)
msd2 = msd2 / 10;
} else
msd2 = quotient2;
if (msd1 == msd2)
return quotient1 - quotient2;
if (msd1 != msd2)
return msd1 - msd2;
}
if (quotient1 == 0 && quotient2 == 0)
return reminder1 - reminder2;
if (quotient2 != 0 && quotient1 == 0) {
while (quotient2 >= 10)
quotient2 /= 10;
return reminder1 - quotient2;
}
if (quotient1 != 0 && quotient2 == 0) {
while (quotient1 >= 10)
quotient1 /= 10;
return quotient1 - reminder2;
}
return 1;
}
});
System.out.println(Arrays.toString(array));
}
}
I also have the same hashmap idea but anoynous put forth almost the code out here. So, the rub is the hash function.
My idea here for the hash function is run length encoding with a twist of course: "ABCAGR" MAPS to "A2B1C1G1R1" and so is "RABCAG". Order of the letters does not matter. The way to approach to this is to use a temporary character counter array and use that counter to generate the hash.
private static String computeHash(String string) {
//This array needs to be increased if we consider the numbers as well as other characters
long [] charCtr = new long [52]; // Radix
char[] chrArray = string.toCharArray();
for (int i = 0; i < chrArray.length; i++) {
charCtr[chrArray[i]-'A']++;
}
StringBuffer strBuff = new StringBuffer();
for (int i = 0; i < charCtr.length; i++) {
if(charCtr[i]!=0) {
strBuff.append( (char) (i+'A')+ "" + charCtr[i] );
}
}
return strBuff.toString();
}
Algorithm: Compare quotients and reminders
import java.util.Arrays;
import java.util.Comparator;
public class DictionarySort {
public static void main(String[] args) {
Integer[] array = new Integer[] { 1, 2, 10, 20, 100, 110 };
Arrays.sort(array, new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
// TODO Auto-generated method stub
int quotient1 = o1 / 10;
int reminder1 = o1 % 10;
int quotient2 = o2 / 10;
int reminder2 = o2 % 10;
if (quotient1 != 0 && quotient2 != 0) {
if (quotient1 == quotient2)
return 0;
int msd1 = 0;
int msd2 = 0;
if (quotient1 >= 10)
msd1 = quotient1 / 10;
else
msd1 = quotient1;
if (quotient2 >= 10)
msd2 = quotient2 / 10;
else
msd2 = quotient2;
if (msd1 == msd2)
return quotient1 - quotient2;
if (msd1 != msd2)
return msd1 - msd2;
}
if (quotient1 == 0 && quotient2 == 0)
return reminder1 - reminder2;
if (quotient2 != 0 && quotient1 == 0) {
while (quotient2 >= 10)
quotient2 /= 10;
return reminder1 - quotient2;
}
if (quotient1 != 0 && quotient2 == 0) {
while (quotient1 >= 10)
quotient1 /= 10;
return quotient1 - reminder2;
}
return 1;
}
});
System.out.println(Arrays.toString(array));
}
}
This can be further improved. In the second step, you can start from 12(largest doubled value which is less than 16) onwards and not from 3 again.
40/3-> 40/6->40/12->40/24 : Keep track of doubling: 2 power 3 = 8
16/12: Keep track of doubling 2 Power 2 = 4
4/3-> 1 Stop here because 1 less than 3: Keep track of doubling i.e. 2 power of zero: 1
Total steps: 5
Double the divisor everytime until it is greater than numerator.Keep track of the doubling. Apply this recursively until the subtraction is less than divisor.
E.g.
40/3-> 40/6->40/12->40/24 : Keep track of doubling: 2 power 3 = 8
16/3 - > 16/6->16/12: Keep track of doubling 2 Power 2 = 4
4/3-> 1 Stop here because 1 less than 3: Keep track of doubling i.e. 2 power of zero: 1
8 + 4 +1 =13 factor remainder = 1
yes you are right except for the major 5 GB data, the idea is to use the stream reader like BufferedReader or something like that, you don't load everything into the main memory and load line or line or chunks of data and apply this logic. The assumption each line is self contained i.e. it does not have any dependencies on other lines..
- naren December 12, 2014//Assumption: Intervals seems like month and day to me.
//Algorithm store all the half intervals into the priority Queue and assemble them by retrieving one by one appending start one to the previous one as end date afterwards incrementing the start interval
public class SplitIntervals {
final static int [] MONTH_DAYS = new int [] { 31,27,31,30,31,30,31,31,30,31,30,31};
private static class Interval {
int startDay;
int startMonth;
int endDay;
int endMonth;
Interval(int startMonth,int startDay,int endDay,int endMonth) {
this.startDay = startDay;
this.startMonth = startMonth;
this.endDay = endDay;
this.endMonth = endMonth;
}
@Override
public String toString() {
return String.format("%d/%d - %d/%d",startMonth,startDay,endMonth,endDay);
}
}
public static void main(String[] args) {
PriorityQueue<Interval> intervalQueue = new PriorityQueue<>(10,new Comparator<Interval>() {
@Override
public int compare(Interval o1, Interval o2) {
// sort by start interval
int diff = o1.startMonth - o2.startMonth;
if(diff!=0) return diff;
diff = o1.startDay - o2.startDay;
if(diff!=0) return diff;
return 0;
}
});
intervalQueue.add(new Interval(2,3,-1,-1));
intervalQueue.add(new Interval(2,20,-1,-1));
intervalQueue.add(new Interval(2,6,-1,-1));
intervalQueue.add(new Interval(3,5,-1,-1));
Interval currentInterval = intervalQueue.poll();
List<Interval> splitIntervals = new ArrayList<>();
while(!intervalQueue.isEmpty()) {
Interval nextInterval = intervalQueue.poll();
//set this interval start day and end Month to be end day and end Month
currentInterval.endDay = nextInterval.startDay;
currentInterval.endMonth = nextInterval.startMonth;
splitIntervals.add(currentInterval);
currentInterval = nextInterval;
currentInterval.startDay++;
if(currentInterval.startDay > MONTH_DAYS[currentInterval.startMonth-1]) {
currentInterval.startMonth++;
currentInterval.startDay = 1;
}
if(currentInterval.startMonth > 12) {
currentInterval.startMonth = 1;
}
}
System.out.println(splitIntervals);
As already mentioned,XOR each invidividual bits: Java solution my attempt: Optimization can be done not to through all the 32 bits of integer.. Time Complexity :O(32N) Space: O(1)
private static int findOddOccurenceNum(int [] integers) {
//get the ith bit
int missingNum = 0;
for (int i = 0; i < 32; i++) {
int missingBit = 0;
for (int j = 0; j < integers.length; j++) {
missingBit = missingBit ^ (integers[j] & (1<<i) );
}
if(missingBit!=0) {
missingNum |= (1<<i);
}
}
return missingNum;
}
public static void main(String[] args) {
int [] integers = new int [] {-2,2,2,3,3};
System.out.println(findOddOccurenceNum(integers));
}
Approach: Create the sort order using the second array using the map which stores map->index map. Then look up this order during the sorting. Entry in the map is given higher order. If the entries are not there in the order use the natural order.Code here in Java
private static void sortArrayBasedOnAnother(Integer [] array,Integer [] sortOrderArray ) {
//create a hashmap which stores the index of element as the value : value->index map
//from the sortOrderArray
final Map<Integer,Integer> sortOrderMap = new HashMap<Integer, Integer>();
for (int i = 0; i < sortOrderArray.length; i++) {
sortOrderMap.put(sortOrderArray[i],i);
}
Arrays.sort(array, new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
// TODO Auto-generated method stub
Integer order1 = sortOrderMap.get(o1);
Integer order2 = sortOrderMap.get(o2);
if(order1!=null && order2!=null) return order1-order2;
if(order1!=null && order2==null) return -1;
if(order1 ==null && order2!=null) return 1;
return o1-o2;
}
});
}
public static void main(String[] args) {
//A = {4,2,7,6,8,9,1,3,2,5,6}
//B = {6,3,4,1}
Integer [] A = new Integer [] {4,2,7,6,8,9,1,3,2,5,6};
Integer [] B = new Integer [] {6,3,4,1};
sortArrayBasedOnAnother(A, B);
System.out.println(Arrays.toString(A));
}
//Another Java solution. Function takes the # of missing elements as the parameter
private static void findMissingElements(int [] array, int lo, int hi,int missingElements,List<Integer> missingList) {
//boundary condition
if(missingList.size() == missingElements) return;
if(lo>=hi) return;
int mid = lo +(hi-lo)/2;
//search for neighborhood of lo,hi and mid and see if there are missing elements
if(array[lo+1] - array[lo]!=1) {
missingList.add(array[lo]+1);
if(missingList.size() == missingElements) return;
}
if(array[mid+1] - array[mid]!=1) {
missingList.add(array[mid]+1);
if(missingList.size() == missingElements) return;
}
if(array[mid] - array[mid-1]!=1) {
missingList.add(array[mid-1]+1);
if(missingList.size() == missingElements) return;
}
if(array[hi] - array[hi-1]!=1) {
missingList.add(array[hi-1]+1);
if(missingList.size() == missingElements) return;
}
//search both in halves
findMissingElements(array,lo,mid,missingElements,missingList);
findMissingElements(array,mid+1,hi,missingElements,missingList);
}
public static void main(String[] args) {
//arr = [1,2,4,5,6,8]
int [] array = new int [] {1,2,4,5,6,8};
List<Integer> missingList = new ArrayList<Integer>();
findMissingElements(array, 0,array.length-1, 2, missingList);
System.out.println(missingList);
}
//My turn: Scan through each of the intervals and search for the gaps in each of the intervals starting with 1. Time complexity is O(m+n)
private static class Interval {
public Interval(int start, int end) {
this.start = start;
this.end = end;
}
int start, end;
@Override
public String toString() {
return String.format("(%d,%d)", start, end);
}
}
// This method is useful to extract the interval from the list
// if the index exceeds size, backupInterval
public static Interval getInterval(List<Interval> list, int index,
Interval backUpInterval) {
if (list.size() - 1 < index)
return backUpInterval;
return list.get(index);
}
// Time complexity is O(m+n)
public static List<Interval> findFreeIntervals(List<Interval> list1,
List<Interval> list2) {
int currentStart = 0;
int currentEnd = 0;
List<Interval> freeIntervals = new ArrayList<Interval>();
Interval first = null;
Interval second = null;
// Loop through the max of the intervals
for (int i = 0; i < Math.max(list1.size(), list2.size()); i++) {
currentStart = currentEnd + 1;
// get the next interval from each of the lists
first = getInterval(list1, i, first);
second = getInterval(list2, i, second);
// get minimum and maximum of both intervals
int minStart = Math.min(first.start, second.start);
int maxEnd = Math.max(first.end, second.end);
// End of the current busy interval
currentEnd = maxEnd;
// if there is a difference between one start interval start time
// and another end time
// then that is one free interval
if (minStart > currentStart) {
Interval freeInterval = new Interval(currentStart, minStart - 1);
freeIntervals.add(freeInterval);
}
if (first.start > second.end) {
Interval freeInterval = new Interval(second.end + 1,
first.start - 1);
freeIntervals.add(freeInterval);
}
if (second.start > first.end) {
Interval freeInterval = new Interval(first.end + 1,
first.start - 1);
freeIntervals.add(freeInterval);
}
// If the size exceeds size, then take the previous of the other
// intervals
// for future consideration
if (i == list1.size()) {
first = second;
}
if (i == list2.size()) {
second = first;
}
}
return freeIntervals;
}
public static void main(String[] args) {
// per1: (1,5) (10, 14) (19,20) (21,24) (27,30)
// per2: (3,5) (12,15) (18, 21) (23, 24)
Interval[] intervals = new Interval[] { new Interval(1, 5),
new Interval(10, 14), new Interval(19, 20),
new Interval(21, 24), new Interval(27, 30) };
Interval[] intervals2 = new Interval[] { new Interval(3, 5),
new Interval(12, 15), new Interval(18, 21),
new Interval(23, 24) };
System.out.println(findFreeIntervals(Arrays.asList(intervals), Arrays.asList(intervals2)));
}
//I am going to take a graph approach. Construct a DAG with the hops and using the BFS find out if the path to the last index(or node is possible). Sedgewick has the java implemenations available on the web and you can get the source for Digraph and DepthFirstDirectedPaths. Granted time complexity may be N2 (just for construction of Digraph) but one more creative exercise using graphs for me.
private static boolean isHopPossible(int [] hopArray) {
int hopArrayLength = hopArray.length;
Digraph digraph = new Digraph(hopArrayLength);
// convert hopArray into DAG
for(int i =0;i<hopArrayLength-1;i++) {
for (int j = 1; j <= hopArray[i]; j++) {
digraph.addEdge(i, i+j);
}
}
DepthFirstDirectedPaths depthFirstDirectedPath = new DepthFirstDirectedPaths(digraph, 0);
return depthFirstDirectedPath.hasPathTo(hopArrayLength-1);
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] hopArray = new int [] {1, 2, 0, 1, 1, 1};
System.out.println(isHopPossible(hopArray));
}
//Wow So many solutions already. Let me add my two cents. The java version
//I think 0(1) for finding the sorting type unless I missed something in the question
//Finding max element is 0(LOGN) only for INCR/DECR case. Everything else is O(1)
//Code in its entirety
public enum SortType {
INCREASING, DECREASING, INCREASEANDDECREASE, DECREASEANDINCREASE
}
private static SortType findArraySortType(int[] intArray) {
if (intArray.length == 1)
return SortType.INCREASING;// arbitary
boolean firstIncrease = false;
boolean secondIncrease = false;
// check the first two elements
if (intArray[1] > intArray[0])
firstIncrease = true;
else
firstIncrease = false;
int arrayLength = intArray.length;
if (intArray[arrayLength - 1] > intArray[arrayLength - 2])
secondIncrease = true;
else
secondIncrease = false;
if (firstIncrease && secondIncrease)
return SortType.INCREASING;
if (firstIncrease && !secondIncrease)
return SortType.INCREASEANDDECREASE;
if (!firstIncrease && !secondIncrease)
return SortType.DECREASING;
if (!firstIncrease && secondIncrease)
return SortType.DECREASEANDINCREASE;
throw new RuntimeException("Should not happen this way.Cannot determine the sort type for this array!!");
// check the last two elements
}
private static int getMaxElement(SortType sortType, int[] intArray) {
if(sortType == SortType.DECREASING) return intArray[intArray.length-1];
if(sortType == SortType.INCREASING) return intArray[0];
//Compare the last and first for the decrease and increase and return the max one
if(sortType == SortType.DECREASEANDINCREASE)
return intArray[0] > intArray[intArray.length-1]?intArray[0]:intArray[intArray.length-1];
if(sortType == SortType.INCREASEANDDECREASE) {
//Get the transition element and return that one.Done!!
int lo = 0;
int hi = intArray.length-1;
while(true) {
int mid = lo + (hi-lo) /2;
if(intArray[mid] > intArray[lo]) {
if(intArray[mid+1] < intArray[mid]) return intArray[mid];
//still decreasing. change the lo
lo = mid+1;
continue;
}
if(intArray[mid] < intArray[lo]) {
hi = mid+1;
}
}
}
return -1;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int [] incArray = new int [] {1,2,3,4};
SortType sortType = findArraySortType(incArray);
int maxElement = getMaxElement(sortType, incArray);
System.out.format("%s %d \n",sortType,maxElement );
int [] decArray = new int [] {-1,-2,-3,-4};
sortType = findArraySortType(decArray);
maxElement = getMaxElement(sortType, decArray);
System.out.format("%s %d \n",sortType,maxElement );
int [] incrAndDecArray = new int [] {1,2,3,4,-1,-2,-3,-4};
sortType = findArraySortType(incrAndDecArray);
maxElement = getMaxElement(sortType, incrAndDecArray);
System.out.format("%s %d \n",sortType,maxElement );
int [] decAndIncArray = new int [] {-1,-2,-3,-4,-1,1,2};
sortType = findArraySortType(decAndIncArray);
maxElement = getMaxElement(sortType, decAndIncArray);
System.out.format("%s %d \n",sortType,maxElement );
}
//Here's my two cents with o(1) space with recursion!!
//printing algo. Take any root and combine its left->right and right->left value
//ofcourse excluding those values from printing again by this condition
//if it is not root node or if it's on the root left and it is left node itself, then print it.
//if it is not root node and if it's on the root right and it is right node itself, then print it.
private static void printTreeVOrder(Node node,boolean root,boolean left,boolean rootLeft){
if(node == null) return;
if(root) {
rootLeft = true;
}
if(node.left!=null) printTreeVOrder(node.left,false,true,rootLeft);
if(root || ((left && rootLeft ) || (!left && !rootLeft)))
System.out.print(node.value);
if(node.left!=null && node.left.right!=null) System.out.print(" " + node.left.right.value);
if(node.right!=null && node.right.left!=null) System.out.print(" " + node.right.left.value);
if(root || ((left && rootLeft ) || (!left && !rootLeft)))
System.out.println();
if(node.left!=null) printTreeVOrder(node.right,false,false,(root?!rootLeft:rootLeft));
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Node root = add(null, 8, false);
//level 1 nodes
Node l11 = add(root,6,true);
Node l12 = add(root,10,false);
//level 2 nodes
Node l21 = add(l11,4,true);
Node l22 = add(l11,7,false);
Node l23 = add(l12,9,true);
Node l24 = add(l12,12,false);
//level 3 nodes
Node l31 = add(l21,3,true);
Node l32 = add(l21,5,false);
printTreeVOrder(root,true,false,false);
}
private static Node add(Node parentNode,int value,boolean left) {
Node returnNode = new Node();
if(parentNode != null) {
if(left) parentNode.left = returnNode;
else parentNode.right = returnNode;
}
returnNode.value = value;
return returnNode;
}
//Java solution using recursion
private static void computeSum(Node node, long parentNodeValue,long[] runnningTotal) {
if(node == null) return ;
long currentNodeValue = parentNodeValue*10 + node.value;
if(node.left == null && node.right==null) {
runnningTotal[0] += currentNodeValue;
return ;
}
computeSum(node.left,currentNodeValue,runnningTotal);
computeSum(node.right,currentNodeValue,runnningTotal);
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Node root = new Node();
root.value = 6;
Node left = new Node();
left.value = 3;
Node right = new Node();
right.value = 5;
root.left = left;
root.right = right;
left.left = new Node();
left.left.value = 2;
left.right = new Node();
left.right.value = 5;
left.right.left = new Node();
left.right.left.value = 7;
left.right.right = new Node();
left.right.right.value = 4;
right.right = new Node();
right.right.value = 4;
long [] runningTotal = new long[1];
computeSum(root,0,runningTotal);
System.out.println(runningTotal[0]);
}
static class Node {
public Node left;
public Node right;
public int value;
}
/**
* This method divides the array into halves and calls recursively
* for the count. countZeros will count the zeros that go
* across left and right
*/
private static int getConsecutiveZeroCount(int [] inputArray,int lo,int hi) {
int mid = lo + (hi-lo)/2;
if (hi <= lo) return 0;
int count = getConsecutiveZeroCount(inputArray, lo, mid);
count +=getConsecutiveZeroCount(inputArray, mid+1, hi);
return count+countZeros(inputArray,lo,hi,mid);
}
/**
* This method will count any zeros between left and right array
* @return
*/
private static int countZeros(int [] inputArray,int lo, int hi,int mid) {
if(inputArray[mid+1] == 0 && inputArray[mid] == 0) return 1;
return 0;
}
public static void main(String[] args) {
int [] inputArray = new int[]{3, 0, 0, 1, 0, 1, 3, 2, 0, 0, 0, 1, 2};
System.out.println(getConsecutiveZeroCount(inputArray, 0, inputArray.length-1));
}
//simple o(nlogn) solution and o(n) space
private static Map<String,String> getPrefixes(String [] str) {
Map<String,String> word2PrefixMap = new HashMap<String, String>();
int [] lcps = new int[str.length];
Arrays.sort(str);
for(int i =0;i<str.length-1;i++) {
int lcp = lcp(str[i],str[i+1]);
lcps[i] = Math.max(lcps[i], lcp);
lcps[i+1] = Math.max(lcps[i+1], lcp);
}
for (int i = 0; i < lcps.length; i++) {
String prefix;
if(lcps[i] == str[i].length()) {
prefix = "";
}
else {
prefix = str[i].substring(0,lcps[i]+1);
}
word2PrefixMap.put(str[i], prefix);
}
return word2PrefixMap;
}
private static int lcp(String str1, String str2) {
int j = -1;
for( int i= 0;i<Math.min(str1.length(),str2.length());i++) {
if(str1.charAt(i)!=str2.charAt(i)) break;
j = i;
}
return j+1;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
String [] words = new String[] {"zebra", "dog", "duck","dot"};
// String [] words = new String[] {"bearcat", "bear"};
System.out.println(getPrefixes(words));
}
/**
* Algorithm
* Build up the original stack in sorted order slowly and process only unsorted items
* in each loop in the stack and you copy back all the elements from
* additional Stack to the originalStack in each loop.
* One extra method that was used to process was the peek()
* but this can easily replaced if this is not allowed
* @param stackToIterate
* TODO There is a room for improvement in this algorithm in terms of time complexity
*/
public static void sort(Stack<Integer> originalStack) {
//Only allowed one more additional stack
Stack<Integer> additionalStack = new Stack<Integer>();
boolean notSorted = true;
int sortedElements = -1;
while(notSorted) {
int currentInt = originalStack.pop();
sortedElements++;
notSorted = false;
while(!originalStack.isEmpty() && originalStack.size() -sortedElements >0 ) {
int nextInt = originalStack.pop();
if(nextInt > currentInt) {
if(!additionalStack.isEmpty() && additionalStack.peek() > currentInt) notSorted = true;
additionalStack.push(currentInt);
currentInt = nextInt;
}
else {
if(!additionalStack.isEmpty() && additionalStack.peek() > nextInt) notSorted = true;
additionalStack.push(nextInt);
}
}
originalStack.push(currentInt);
while(!additionalStack.isEmpty()) {
originalStack.push(additionalStack.pop());
}
}
}
public static void main(String [] args) {
Stack<Integer> inputStack = new Stack<>();
inputStack.push(10);
inputStack.push(11);
inputStack.push(23);
inputStack.push(90);
inputStack.push(1);
inputStack.push(2);
inputStack.push(3);
inputStack.push(4);
sort(inputStack);
System.out.println(inputStack);
}
Ok I got the partial solution by not using backtracking.
Let A1,A2,A3 be the positions of 3 numbers(i.e. A1 for 1,A2 for 2 and A3 for 3) in the 6 slots.
Sum of 6 slots indexes(starting with 1) = 6*7/2=21 (geometric series sum problem)
Based on the position of slots of the numbers, the sum should be
A1+(A1+2)+A2+(A2+3)+A3+A3+4 = 21 There is A1+2 because the second '1' will be 2 indexes after the first '1'. similarly for 2 and 3
2(A1+A2+A3) = 21 -9 i.e. A1+A2+A3 = 6
Had the sum of the numbers been contains decimals, there is no possible solution. i.e. try for 5.
If we choose the highest number in the first slot, then
equation will be A1+A2 = 5. 5 is possible with 2 numbers (remaining) with the following either (4,1) (1 is already taken) and so the other (2,3) is the only place where we can put either 2 or 1. Trying these two cases, will yield A2 = 3 and A1=2
I think this can be further improved. Feel free to jump in with your improvements...
Java solution
- naren November 12, 2017