I had 45 phone interview round, I was asked very breif intro and two DS questions -
Interviewer was super nice.
I was able to complete both questions and now on the Virtual Onsite stage.
/**
DS question 1 ::
- This function determines if the braces '(' and ')' in a string are properly matched.
- it ignores non-brace characters.
- Some examples:
- "()()()()" -> true
- "((45+)*a3)" -> true
- "(((())())" -> false )))(((
"(())))))))"
*/
public boolean matched(String s) {
// Implementation here
int braces = 0;
// O(N) Time
// O(1) space
for(int i=0;i<s.length();i++) {
char c = s.charAt(i);
// if(stack.isEmpty()) []
switch(c){
case '(':
braces++; // 4 -2 + 1 -2
break;
case ')':
braces--;
if(braces<0) {return false;}
break;
default:
// do nothing
break;
}
return braces ==0;
}
}
/*
DS Question 2:
This class will be given a list of words (such as might be tokenized
-
from a paragraph of text), and will provide a method that takes two
-
words and returns the shortest distance (in words) between those two
-
words in the provided text.
-
Example:
-
SentenceDistanceFinder finder = new SentenceDistanceFinder(Arrays.asList("the", "quick", "brown", "foxi", "quick"));
-
assert(finder.distance("fox", "the") == 3);
-
assert(finder.distance("quick", "fox") == 1);
-
"quick" appears twice in the input. There are two possible distance values for "quick" and "fox":
-
(3 - 1) = 2 and (4 - 3) = 1. -
Since we have to return the shortest distance between the two words we return 1.
*/
public class SentenceDistanceFinder {
Map<String, List<Integer>> wordMap;
public SentenceDistanceFinder(List<String> words) { // O(N) Time // Space : O(N)
wordMap = new HashMap<>();
for(int i=0;i<words.size();i++){
List<Integer> list = wordMap.getOrDefault(words.get(i), new ArrayList<Integer>);
list.add(i);
wordMap.put(words.get(i), list);
}
}
public int distance(String wordOne, String wordTwo) { //Time : O(N) // Space : O(N)
int min = Integer.MAX_VALUE;
List<Integer> indexes1 = null;
List<Integer> indexes2 = null;
if(wordMap.containsKey(wordOne)) {
indexes1 = wordMap.get(wordOne); // ArrayList({1,4}) >2
}
if(wordMap.containsKey(wordTwo)) {
indexes2 = wordMap.get(wordTwo);// ArrayList({3}) >1
}
if(indexes1 != null && indexes2 != null) {
int i1 =0;
int i2 =0;
while (i1<indexes1.size() && i2.indexes2.size()) {
min = Math.min(min, Math.abs(indexes1.get(i1)-indexes2.get(i2)));
if(indexes1.get(i1) < indexes2.get(i2)) {
i1++;
} else {
i2++;
}
}
}
return min;
}
}