jimmy.sjsu
BAN USER//Complexity is -- O(nlogn) + O(n)
public static int minimumIntegerWhichCannotBeFormed(int[] arr){
//first sort it
Arrays.sort(arr);
int result = 1;
for(int i=0;i<arr.length;i++){
if(arr[i] <= result){
result = result + arr[i];
}else{
break;
}
}
return result;
}
public static void removeDuplicatedByReplacingNextNumbers(int[] arr){
HashMap<Integer, Boolean> map = new HashMap<Integer, Boolean>();
int maxValue=0;
for(int i=0;i<arr.length;i++){
if(!map.containsKey(arr[i])){
map.put(arr[i],false);
}
if(arr[i] > maxValue){
maxValue = arr[i];
}
}
for(int j=0;j<arr.length;j++){
if(!map.get(arr[j])){
map.put(arr[j], true);
}else{
maxValue = maxValue+1;
arr[j] = maxValue;
}
}
}
public static int[] mergeTwoSortedArraysWithoutAdditionalArray(int[] arr1, int[] arr2){
if((arr1 == null || arr1.length == 0 ) && (arr2 == null || arr2.length == 0)){
return null;
}
int a1Index = arr1.length-1;
int a2Index = arr2.length-1;
int a2mIndex = arr2.length-arr1.length-1;
while(a1Index >=0 && a2Index >=0 && a2mIndex >=0){
if(arr1[a1Index] > arr2[a2mIndex]){
arr2[a2Index] = arr1[a1Index];
a2Index--;
a1Index--;
}else{
arr2[a2Index] = arr2[a2mIndex];
a2Index--;
a2mIndex--;
}
}
while(a1Index > 0){
arr2[a2Index] = arr1[a1Index];
a2Index--;
a1Index--;
}
while(a2mIndex > 0){
arr2[a2Index] = arr2[a2mIndex];
a2Index--;
a2mIndex--;
}
return arr2;
}
I was giving an interview today and asked this question. I struggled during an interview but after that I gave it a try and did implement it. here is the Solution in Java.
public static List<String> deriveWordCombinations(String number){
List<String> finalWord = new ArrayList<String>();
List<String> iterative = new ArrayList<String>();
finalWord.add("");
for(int i=0;i<number.length();i++){
char c = number.charAt(i);
String stringForNumber = map.get(c);
for(String s:finalWord){
for(char cs: stringForNumber.toCharArray()){
iterative.add(s+cs);
}
}
finalWord = iterative;
iterative = new ArrayList<String>();
}
return finalWord;
}
static final HashMap<Character,String> map = new HashMap<Character,String>(){
{
put('2',"abc");
put('3',"def");
put('4',"ghi");
put('5',"jkl");
put('6',"mno");
put('7',"pqrs");
put('8',"tuv");
put('9',"wxyz");
}
};
here is my solution::
- jimmy.sjsu January 26, 2015