banerjees36
BAN USER- -1of 1 vote
AnswersWithout using extra space place all zeroes to left and 1's to right from an array of Zero's and 1's as below
011001 ans. 000111
- banerjees36 in Indiapublic class Zeros_ones_New { /** * @param args */ public static void main(String[] args) { int[] arrZerosOnes = { 0,1,0,1,0,1,1 }; int len = arrZerosOnes.length; int firstOne = -1; int lastZero = len; for (int i = 0; i < len; i++) { if (arrZerosOnes[i] == 1) { firstOne = i; break; } } for (int u = len - 1; u > -1; u--) { if (arrZerosOnes[u] == 0) { lastZero = u; break; } } if (firstOne > -1 && lastZero<len) { while (firstOne<lastZero) { for (int j = firstOne; j < lastZero; j++) { if (((j + 1) <= lastZero) && (j == firstOne) && (arrZerosOnes[j + 1] == 0)) { arrZerosOnes[j] = 0; arrZerosOnes[j + 1] = 1; firstOne++; /*if ((j + 1) == lastZero) { break; }*/ } else if (((j + 1) <= lastZero) && (arrZerosOnes[j] == 1) && (arrZerosOnes[j + 1] == 0)) { arrZerosOnes[j] = 0; arrZerosOnes[j + 1] = 1; if ((j + 1) == lastZero) { lastZero--; } } } } } for (int t = 0; t < len; t++) { System.out.print(arrZerosOnes[t]); } } }
| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer - 0of 0 votes
AnswersHow to most efficiently find duplicates/commons in two sorted arrays of integers. No extra space should be used. My answer as below
- banerjees36 in Indiapublic class Duplicate { //private HashSet<Integer> duplicates = new HashSet<Integer>(); /** * @param args */ public static void main(String[] args) { int a[] = {0,2,2,4,6,8,8,9,9,10}; int b[] = {0,3,3,4,8,8,10,12}; new Duplicate().mergeAndCheck(a, b); } private void mergeAndCheck(int[] arr1, int[] arr2){ int len1 = arr1.length; int len2 = arr2.length; int pointArr1 = 0; int pointArr2 = 0; while((pointArr1<len1)&&(pointArr2<len2)){ if(arr1[pointArr1]<=arr2[pointArr2]){ if((arr1[pointArr1]==arr2[pointArr2])){ if(pointArr1==0){ System.out.print(" "+arr1[pointArr1]); }else if(arr1[pointArr1]!=arr1[pointArr1-1]){ System.out.print(" "+arr1[pointArr1]); } //duplicates.add(arr1[pointArr1]); } pointArr1++; }else{ pointArr2++; } } /*for(Integer iNT:duplicates){ //System.out.print(" "+iNT); }*/ } }
| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer
Please follow my post on 23rd July 2012
2 has subsets as {{2}}
3 has subsets as {{1,2},{3}}
4 has subsets {{1,3}, {4}}
8 has subsets {{1,2,5},{1,3,4},{1,7},{2,6},{3,5},{8}}
So there should be a set {x,y,z} where at least one subset will be found for each 2, 3, 4 and 8.
As there is 2 as one of the numbers it is evident that the set must be {2,y,z}
As there is 3 as one of the numbers the set must be one amongst the below
{2,1,z} or {2,3,z}
As there is 4 as one of the numbers the set now must be either {2,1,4} or {2,3,1}
But as there is 8, none of the above 2 sets satisfy it because we cannot find a summation which is 8.
So there is no solution
There may be 3 kind of sets
Set 1 will have subsets as{ {1,2,3},.....{1,2,7},{1,3,4},.....,{1,3,6},{1,4,5},{2,3,4},....{2,3,5}}
Set 2 will have subsets as{{1,2},.....,{1,9},{2,3}.....,{2,8},{3,4},....,{3,7},{4,5},{4,6}}
Set 3 will have subsets {1,2,3,4,5,6,7,8,9,10}
Each number may have a set of subsets which add up the number.
Like number 6 will have set as {{1,2,3},{1,5},{2,4},{6}}
3 will have set as {{1,2},{3}}
5 will have set as {{1,4},{2,3},{5}}
This may be the approach.... This way the logic may be designed....
Quicksort interchange far away elements... Not only adjacents
- banerjees36 June 22, 2012st and end should be adjacent while being interchanged
- banerjees36 June 22, 2012Cannot use any predefined function
- banerjees36 June 22, 2012You are not checking whether i and j are adjacent
- banerjees36 June 22, 2012No it's n to the power n i.e. n^n Example
3^3 = 27 true
2^2 = 5 false
Sorry... Apologies.... You can only interchange the adjacent numbers... I forgot this
- banerjees36 June 22, 2012all are +ve integers
- banerjees36 June 22, 2012
Algo
- banerjees36 April 14, 20131> Create a stack to hold the references of the BST nodes. Set the counter variable to 0. Start from root. Make it the "current node".
2> Start from the "current node". Go on traversing the right child until the node which does not have a right child. en-stack it. Increase the counter variable by 1.
2a> If the value of counter is k, return the value of the node at the top of the stack.
2b> Else check whether the top node has left child. if yes make the left child the
current node. Again execute step 2.
2c> Else if the top node does not have a left child, destack the stack node by node till
it is empty. With every de-stack operation hold the reference of the node in a single
variable. So when the stack is empty the variable holds the lowest reference of the stck.
If this is the root node throw error. Because k>n. Else make the parent of this node
the "current node" and execute step 2.