koeber99
BAN USERComments Welcome!!
Input: xxxxxyabcdefg Output: abcdefg
Input: aaaaXXXbba Output: aaaaxxxb
1) all Input put to lowercase
2) aaaaXXXbb > aaaaXXXbba
Time: O(n) and Space: O(1)
public static String getLongestSubstringLex (String input ){
if ( (input== null) || (input.length()==1) || (input.equals("")))
return input;
String inputString = input.toLowerCase();
char [] arrChar = inputString.toCharArray();
int firstVal = inputString.charAt(0);
int length = arrChar.length;
for( int i =1; i < length;i++){
int currentVal=inputString.charAt(i);
if(currentVal < firstVal)
return inputString.substring(i,length);
if ( i== (length-1))
return inputString.substring(0,length-2);
}
return input;
}
Below is my Java code for this problem:
I used a HashMap. I would ask the interview does Capitalization matter? (Ex. Is Cat the same as CaT?)
If Capitalization matters, use the code below. If not, add
eachString = eachString.toLowerCase(); to the for loop.
public static int distinctString ( String [] inputArray){
Map <String, Integer > hashMapOfString = new HashMap <String, Integer > ();
int distinctCount =0;
for ( String eachString : inputArray){
if ( ! hashMapOfString.containsKey(eachString) ){
hashMapOfString.put(eachString,1);
distinctCount++;
}
}
return distinctCount;
}
My solution has a big O of (n*logn). Where Arrays.sort has a big O of n*logn and swapping the array values has a big O of (n). Since the solution is O( (n*logn) + n), it is reduce to (n*logn).
Note: Arrays.sort is java built in Merge sort.
import java.util.Arrays;
public static void rearrangeArray( int [] arrayA, int [] newIndexOrder){
Arrays.sort(arrayA ); //O (n*log n)
for (int i= 0; i < arrayA.length-1;i++ ){
int tempValue= arrayA[i];
arrayA[i]= arrayA [newIndexOrder[i]-1];
arrayA [newIndexOrder[i]-1]=tempValue;
}
}
Alisovenko,
Again, Thank you for leaving feedback. You are correct, my solution is incorrect!! (See below). So this means my Java algorithm finds a suboptimal solution. Is it best to find all suboptimal solutions, then select the best solution from there?
Output:
In M is 8799, K is 2
Output: 9987
In M is 7899, K is 2
Output: 9978
Below is my java solution to the problem. The time complexity of my solution is O(M*K), where M is equal to the number of digits of M and K is k. What do you think? Please leave feedBack.
public int maxPossibleInteger ( int m, int k){
//Turn M into charArray
char [] charArrayOfM = String.valueOf(m).toCharArray();
int j =0;
while ( k > 0) {
int max = charArrayOfM[j];
int tempIndexID =0;
//Loop through Char array to find largest digit
//Start at index j+1
for ( int i=(j+1); i< (charArrayOfM.length ); i++){
if ( charArrayOfM[i] > max){
tempIndexID=i;
max = charArrayOfM[i];
}}
//Swap Char if Necessary
if ( charArrayOfM[j] < max){
char tempChar = charArrayOfM[tempIndexID];
charArrayOfM[tempIndexID] =charArrayOfM[j];
charArrayOfM[j]= tempChar;
}
k--;
j++;
}
int maxInteger= Integer.parseInt(String.valueOf(charArrayOfM));
return maxInteger;
}
Below are two different Java methods to reverse the input of int:
public void reverseNumbers ( int input){
StringBuilder stringInput = new StringBuilder ( String.valueOf(input));
System.out.println(stringInput.reverse().toString());
}
public void reverseNumbersTwo ( int input){
String StringInput = String.valueOf(input);
char [] charArrayOfInput = StringInput.toCharArray();
for (int i =(charArrayOfInput.length-1); i>=0;i-- ){
System.out.print(charArrayOfInput[i]);
}
What do you guys think about the code below? It uses a red and black tree using the integers as keys. I believe the space complexity is O (n * log n) while the time complexity is the same. I'm not sure... Feed back please!!!
import java.util.TreeMap;
import java.util.Collection;
public class SortTuple {
public void createSingleTuple (String [] arrayTuple){
String [] finalArray = new String [arrayTuple.length*2 ];
TreeMap <Integer,String> redBlackTree = new TreeMap<Integer,String>();
for ( int i =0; i <arrayTuple.length;i++){
String [] tokens = arrayTuple[i].split("[,]");
StringBuffer first = new StringBuffer ();
StringBuffer second = new StringBuffer ();
first.append(tokens[0]).append(tokens[1]);
second.append(tokens[0]).append(tokens[2]);
redBlackTree.put(Integer.parseInt(tokens[1]), first.toString());
redBlackTree.put(Integer.parseInt(tokens[2]), second.toString());
}
Collection <String> coll= redBlackTree.values();
coll.toArray(finalArray);
System.out.println("Print out of array");
for ( int i = 0; i < finalArray.length; i ++ ){
System.out.print(finalArray[i] + " ");
}} }
I'll ask the interviewer if the array contains negative numbers in the array.
No lead zeros are created from my code below. However, I don't check if lead zero exists in the income array.
- koeber99 July 16, 2016