In the coding round of this company, question was to find the longest substring having distinct characters.
Below is my solution for this problem, though I was not able to complete this in the given time frame, as I was having around 35 mins remaining for this, you can also check the related code given in Interview2
But may be it can help you to crack this or other such interview -
import java.util.HashMap;
/**
* Below question was asked to code in interview for BlueOptima.
* Question was to find the largest substring with distinct characters.
* Below is my solution, which I can think of for now with my a few below test cases.
* Please let me know the case for which it doesn't work.
* @author nitin
*
*/
public class BlueOptima {
public static void main(String args[]) {
System.out.println(LargestSubString("abcda")); // 4
System.out.println(LargestSubString("abadc")); // 4
System.out.println(LargestSubString("abadcbefg")); // 7
System.out.println(LargestSubString("abadcbeag")); // 6
System.out.println(LargestSubString("abadcbeagb")); // 6
System.out.println(LargestSubString("aaaaaaaaaa")); // 1
System.out.println(LargestSubString("abcddceaghi")); // 7
System.out.println(LargestSubString("abclmceaghi")); // 8
System.out.println(LargestSubString("abcddceag")); // 5
System.out.println(LargestSubString("abadcbeagbklmnop")); // 10
System.out.println(LargestSubString("abcdefghijklmf")); // 13
}
static int LargestSubString(String S){
int max = 0;
HashMap<Character, Integer> hm = new HashMap<>();
char[] chars = S.toCharArray();
int len = chars.length;
int start = 0;
for(int i = 0; i < len; i++) {
char ch = chars[i];
if(!hm.containsKey(ch)) {
hm.put(ch, i);
} else {
int pos = hm.get(ch);
if(pos != start) {
if(hm.size() > max)
max = hm.size();
int k = hm.get(chars[i]) + 1;
hm.clear();
start = k;
while(k < i) {
hm.put(chars[k], k);
k++;
}
} else {
start = pos + 1;
int k = pos;
while(k >= 0) {
if(hm.containsKey(chars[k]) && hm.get(chars[k]) == k)
hm.remove(chars[k]);
k--;
}
}
hm.put(ch, i);
}
}
if(hm.size() > max)
max = hm.size();
return max;
}
}
Below is my solution for this problem, though I was not able to complete this in the given time frame, as I was having around 35 mins remaining for this, you can also check the related code given in Interview2
But may be it can help you to crack this or other such interview -
import java.util.HashMap;
/**
* Below question was asked to code in interview for BlueOptima.
* Question was to find the largest substring with distinct characters.
* Below is my solution, which I can think of for now with my a few below test cases.
* Please let me know the case for which it doesn't work.
* @author nitin
*
*/
public class BlueOptima {
public static void main(String args[]) {
System.out.println(LargestSubString("abcda")); // 4
System.out.println(LargestSubString("abadc")); // 4
System.out.println(LargestSubString("abadcbefg")); // 7
System.out.println(LargestSubString("abadcbeag")); // 6
System.out.println(LargestSubString("abadcbeagb")); // 6
System.out.println(LargestSubString("aaaaaaaaaa")); // 1
System.out.println(LargestSubString("abcddceaghi")); // 7
System.out.println(LargestSubString("abclmceaghi")); // 8
System.out.println(LargestSubString("abcddceag")); // 5
System.out.println(LargestSubString("abadcbeagbklmnop")); // 10
System.out.println(LargestSubString("abcdefghijklmf")); // 13
}
static int LargestSubString(String S){
int max = 0;
HashMap<Character, Integer> hm = new HashMap<>();
char[] chars = S.toCharArray();
int len = chars.length;
int start = 0;
for(int i = 0; i < len; i++) {
char ch = chars[i];
if(!hm.containsKey(ch)) {
hm.put(ch, i);
} else {
int pos = hm.get(ch);
if(pos != start) {
if(hm.size() > max)
max = hm.size();
int k = hm.get(chars[i]) + 1;
hm.clear();
start = k;
while(k < i) {
hm.put(chars[k], k);
k++;
}
} else {
start = pos + 1;
int k = pos;
while(k >= 0) {
if(hm.containsKey(chars[k]) && hm.get(chars[k]) == k)
hm.remove(chars[k]);
k--;
}
}
hm.put(ch, i);
}
}
if(hm.size() > max)
max = hm.size();
return max;
}
}
This question was asked in MyMoneyKarma also & using HashSet, concern about runtime complexity was raised & was suggested to use HashMap instead.
I am not sure how much performance improvement will be there but surely it will be better to use HashMap. And as per my understanding its implementation will look like -
I am not sure how much performance improvement will be there but surely it will be better to use HashMap. And as per my understanding its implementation will look like -