## 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 India`public 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 India`public 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**CareerCup**is the world's biggest and best source for software engineering interview preparation. See all our resources.

Open Chat in New Window

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.