rajanikant.malviya
BAN USERCan construct "A Tree" but not the same tree for which the pre-order traversal is given.
Atleast two kinds of traversals are required to construct back the tree, reason?
---- Each node has two nodes "letf" and "right" ie, two unknowns thus atleast two expression / fittings required to find them :)
what is the gaming pattern - round robin matches? or knock out? and to which level
- rajanikant.malviya September 26, 2012Sorting would not work for negative numbers :(
- rajanikant.malviya September 26, 2012* Complexity O(n)
public class BinarySearchTree {
static class Node{
Node left, right;
Node parent;
int data;
@Override
public String toString() {
return ""+data;
}
}
public static void main(String[] args) {
final Node node4 = new Node(){{left=null; right=null; parent=null; data=4;}};
final Node node8 = new Node(){{left=null; right=null; parent=null; data=8;}};
final Node node7 = new Node(){{left=node4; right=node8; parent=null; data=7;}};
node4.parent=node8.parent=node7;
final Node node18 = new Node(){{left=null; right=null; parent=null; data=18;}};
final Node node15 = new Node(){{left=null; right=node18; parent=null; data=15;}};
node18.parent=node15;
final Node root = new Node(){{left=node7; right=node15; parent=null; data=10;}};
node7.parent=node15.parent=root;
System.out.println(node4 + " : " + getInorderSuccessor(node4));
System.out.println(node8 + " : " + getInorderSuccessor(node8));
System.out.println(node7 + " : " + getInorderSuccessor(node7));
System.out.println(root + " : " + getInorderSuccessor(root));
System.out.println(node18 + " : " + getInorderSuccessor(node18));
System.out.println(node15 + " : " + getInorderSuccessor(node15));
}
public static Node getInorderSuccessor(Node node){
assert(node!=null);
if (node.right!=null){
return getLeftMost(node.right);
}
//node is left of parent
if (node == node.parent.left)
return node.parent;
//node is right of parent
return getParentWithRightBranch(node.parent);
}
private static Node getParentWithRightBranch(Node node) {
if (node.parent==null)
return null;
if (node.parent.left==node){
return node.parent;
}
return getParentWithRightBranch(node.parent);
}
private static Node getLeftMost(Node node) {
if (node.left==null)
return node;
return getLeftMost(node.left);
}
}
* Java
* Complexity O(n*(2^n))
public class SumMatchCombinationsFromArray {
public static void main(String[] args) {
int[] array = new int[]{-1,4,5,4,0,6,7,9,1};
printAllCombination(0, array);
}
public static void printAllCombination(int requiredSum, int... array) {
assert (array.length < 32);
for (int i = 1, sum = 0; i < (1 << array.length); i++, sum=0) {
for (int j = 0; j < array.length; j++) {
if ((i & (1 << j)) != 0) {
sum += array[j];
}
}
if (sum == requiredSum) {
System.out.print("{");
for (int k = 0; k < array.length; k++) {
if ((i & (1 << k)) != 0) {
System.out.print(array[k] + " ");
}
}
System.out.print("}");
System.out.println();
}
}
}
}
*Bit operation
*Complexity O(nx2^n) - Can we get better than this?
is size of array given? I assume being combination related it should be safely below 32 :)
Step 1: get combinations (limit to 3 selections only)
Step 2: print if sum is zero
public class SumZeroThreeNumbersFromArray {
public static void main(String[] args) {
int[] array = new int[]{-1,4,5,4,0,6,7,9,1};
printAllCombination(0, 3, array);
}
public static void printAllCombination(int requiredSum, int requiredNumbers, int... array) {
assert (array.length < 32);
for (int i = 1, bitCount = 0, sum = 0; i <(1<< array.length); i++, sum=0, bitCount=0) {
for (int j = 0; j < array.length; j++) {
if ((i & (1 << j)) != 0) {
sum += array[j];
bitCount++;
}
}
if (sum == requiredSum && bitCount==requiredNumbers) {
System.out.print("{");
for (int k = 0; k < array.length; k++) {
if ((i & (1 << k)) != 0) {
System.out.print(array[k] + " ");
}
}
System.out.print("}");
System.out.println();
}
}
}
}
Keep single 9 bit number for each player
Winning bit combinations
a. 111000000
b. 000111000
c. 000000111
d. 100100100
e. 010010010
f. 001001001
g. 100010001
h. 001010100
for any player
if there exists a winningCombination (from a to h) such that
boardMatrix AND winningCombination = winningCombination
we have a winner :)
if we have lesser domain set - say hours (24 slots) we could also use bit manipulation
- rajanikant.malviya September 24, 2012find maximum overlap count that is the answer.
Trick is to think of a domain set for time - lets say hour or minute or seconds. Below logic is for domain set "mins"
public class BusStandArrivalTimeMinPlatforms {
public static void main(String[] args) {
BusDetail[] busDetails = new BusDetail[5];
busDetails[0]=new BusDetail(){{
arrivalTime=10*60; //10 AM
haltTime=20; //20 mins
}};
busDetails[1]=new BusDetail(){{
arrivalTime=(int) ((10.5)*60); //10:30 AM
haltTime=30; //30 mins
}};
busDetails[2]=new BusDetail(){{
arrivalTime=11*60; //11 AM
haltTime=15; //15 mins
}};
busDetails[3]=new BusDetail(){{
arrivalTime=(int) (10.5*60); //10:30 AM
haltTime=35; //35 mins
}};
busDetails[4]=new BusDetail(){{
arrivalTime=10*60+40; //10:40 AM
haltTime=5; //5 mins
}};
System.out.println("Min platforms: "+getMinPlatfoms(busDetails));
}
public static int getMinPlatfoms(BusDetail[] busDetails) {
int domain=24*60;
int [] slots = new int[domain];
for (BusDetail busDetail : busDetails) {
for(int i=busDetail.arrivalTime; i<busDetail.arrivalTime+busDetail.haltTime;i++){
slots[i]++;
}
}
return findMaxValue(slots);
}
public static int findMaxValue(int... array){
assert(array.length>0);
int max=array[0];
for (int i : array) {
if(max<i){
max=i;
}
}
return max;
}
}
class BusDetail {
public int arrivalTime;
public int haltTime;
}
oh boy! lotta-code!
1. Implement List<E>, Serializable, Cloneable, RandomAccess
2. Make sure that iterators are fail-fast (can be done using a single modification counter)
3. Finally make sure that sequential access with myList[i] is faster than myList.listIterator().next
count sort can help for domain D and number of integers n complexity will be speed O(n) Space O(D)
- rajanikant.malviya April 05, 2010Algo
required = 25;
i = 0;
j = 0;
count = 0;
while(j<arr.length)
{
sum+=arr[j];
if(sum>=required)
{
if(sum==required)
{
count++;
}
sum-=arr[i];
i++;
}else{
j++;
}
}
print(count);
multiply each point in UI with
| -1 0 |
| 0 -1 |
merge sort on first column and add second column value each time. O(n+m) ie.. O(N)
- rajanikant.malviya September 12, 2013