kamrultopu
BAN USERsorting and then using a stack
public ArrayList<Integer> MergeRangeArray(int[] arr1, int[] arr2){
ArrayList<Integer> list = new ArrayList<Integer>();
ArrayList<Info> arrInfo = new ArrayList<Info>();
Stack<Info> stack = new Stack<Info>();
for( int i = 0 ; i < arr1.length - 1;i+=2){
Info tempstart = new Info(arr1[i],'S');
Info tempEnd = new Info(arr1[i+1],'E');
arrInfo.add(tempstart);
arrInfo.add(tempEnd);
//System.out.println(tempstart + " " + tempEnd);
}
for( int i = 0 ; i < arr2.length - 1;i+=2){
Info tempstart = new Info(arr2[i],'S');
Info tempEnd = new Info(arr2[i+1],'E');
arrInfo.add(tempstart);
arrInfo.add(tempEnd);
}
Collections.sort(arrInfo);
//System.out.println(arrInfo.toString());
for( int i = 0 ; i < arrInfo.size();i++){
if( arrInfo.get(i).type == 'S'){
stack.push(arrInfo.get(i));
}
else{
Info temp = stack.pop();
if( stack.isEmpty()){
list.add(temp.val);
list.add(arrInfo.get(i).val);
}
}
}
return list;
}
Here is my solution. It is lengthy but i think in interview they want to see your design also not only the code that only solve.
public class CareerCup {
public String maxNumber(int[] arr1, int[] arr2, int k){
HashMap<Integer,ArrayList<Integer>> procMapArr1 = GetProcessingMap(arr1,k);
HashMap<Integer,ArrayList<Integer>> procMapArr2 = GetProcessingMap(arr2,k);
int mid = (k+1)/2;
//System.out.println(mid);
int[] result = new int[k];
for(int i = 1 ; i <= k;i++){
//System.out.println(" check: " + procMapArr1.get(i).toString());
//System.out.println(" check: " + procMapArr2.get(k-i).toString());
int[] temp = findMaxNumber(procMapArr1.get(i),procMapArr2.get(k-i));
if( IsBigger(temp,result)){
for(int j = 0 ; j<temp.length;j++){
result[j] = temp[j];
}
}
}
return Arrays.toString(result);
}
private boolean IsBigger(int[] temp, int[] result) {
int size1 = temp.length;
int size2 = temp.length;
if( size1 == size2){
int i = 0;
while( i<size1 && temp[i] == result[i]){
i++;
}
if( i == size1)
return false;
return temp[i] > result[i];
}
return size1 > size2;
}
private int[] findMaxNumber(ArrayList<Integer> arrayList1,ArrayList<Integer> arrayList2) {
//System.out.println("hi");
int size1 = 0;
int size2 = 0;
if( arrayList1 != null)
size1 = arrayList1.size();
if( arrayList2 != null)
size2 = arrayList2.size();
int[] retArray = new int[size1+size2];
int indexArr1 = 0 ;
int indexArr2 = 0 ;
int currentIndex = 0 ;
while(true){
if( indexArr1 < size1 && indexArr2 < size2 ){
if( arrayList1.get(indexArr1) > arrayList2.get(indexArr2)){
retArray[currentIndex++]= arrayList1.get(indexArr1);
indexArr1++;
}
else {
retArray[currentIndex++]= arrayList2.get(indexArr2);
indexArr2++;
}
}
else if ( indexArr1 < size1){
retArray[currentIndex++]= arrayList1.get(indexArr1);
indexArr1++;
}
else if ( indexArr2 < size2 ){
retArray[currentIndex++]= arrayList2.get(indexArr2);
indexArr2++;
}
else {
break;
}
}
//System.out.println(Arrays.toString(retArray));
return retArray;
}
private HashMap<Integer, ArrayList<Integer>> GetProcessingMap(int[] arr,int k) {
HashMap<Integer,ArrayList<Integer>> hmap = new HashMap<Integer,ArrayList<Integer>>();
for( int i = 1 ; i <= k;i++){
ArrayList<Integer> temp = GetArrayNumber(arr,i);
hmap.put(i, temp);
}
System.out.println(hmap.toString());
return hmap;
}
private ArrayList<Integer> GetArrayNumber(int[] arr, int k) {
//System.out.println(Arrays.toString(arr) + " k: " + k);
ArrayList<Integer> numberList = new ArrayList<Integer>();
int size = arr.length;
if( size < k )
return null;
//int currentSize = 0;
if( size == k ){
for(int i = 0 ; i < size;i++){
numberList.add(arr[i]);
}
}
else{
int maxIndex = 0;
int maxVal = arr[0];
for( int i = 0 ; i < size- k + 1 ; i++){
if( arr[i] > maxVal){
maxIndex = i;
maxVal = arr[i];
}
}
numberList.add(arr[maxIndex]);
int[] rightArray = Arrays.copyOfRange(arr, maxIndex+1, size);
//System.out.println(numberList.toString());
if( k > 1)
numberList.addAll(GetArrayNumber(rightArray,k-1));
//System.out.println(numberList.toString());
}
return numberList;
}
}
can you check your answer for this example? I got zdxrabca as a final output , if we swap (2,7) , (0,2) and (1,6) we got d in the position 1. so zd in the first two position seem lexicographical bigger.
- kamrultopu March 24, 2016