Amazon Interview Question
Software Engineer / DevelopersTeam: Tax Systems
Country: United States
Interview Type: Written Test
I tried and came up with this answer. I was able to get a majority of the test results to pass, however, there were a few that didn't pass because they took longer than 4 seconds. Still trying to figure out a solution that is faster than this....
public static List<Integer> calculateContainerCount(String str, List<Integer> startIndexInclusive, List<Integer> endIndexInclusive) {
List<Integer> result = new ArrayList<>();
int size = startIndexInclusive.size() < endIndexInclusive.size() ? startIndexInclusive.size() : endIndexInclusive.size();
for (int i = 0; i < size; i++) {
int count = 0;
String subString = str.substring(startIndexInclusive.get(i), endIndexInclusive.get(i) + 1);
int firstPipe = subString.indexOf("|");
int lastPipe = subString.lastIndexOf("|");
if (firstPipe >= 0 && lastPipe >= 0) {
String subSubString = subString.substring(firstPipe, lastPipe);
for (char c : subSubString.toCharArray()) {
if (c == '*') {
count++;
}
}
}
result.add(count);
}
return result;
}
public static List<Integer> numberOfItems(String s, List<Integer> startIndices, List<Integer> endIndices) {
String items = "";
List<Integer> itemList = new ArrayList<>();
for(int i=0;i<Math.min(startIndices.size(), endIndices.size());i++) {
items = s.substring(startIndices.get(i)-1,endIndices.get(i));
char[] itemChars = items.toCharArray();
int pair = 0;
int compCount = 0;
int cumComCount = 0;
for(char itemChar: itemChars) {
if(itemChar == '|' && pair == 0) {
pair++;
compCount = 0;
} else if(itemChar == '|' && pair == 1) {
if(compCount>0) {
cumComCount += compCount;
}
compCount = 0;
} else if(itemChar == '*' && pair == 1) {
compCount += 1;
}
}
itemList.add(cumComCount);
}
return itemList;
}
int computeItemCount(String str, int start, int end) {
boolean compStart = false;
int itemCount = 0;
int compartmentCount = 0;
for (int i = start - 1; i < end; i++) {
char c = str.charAt(i);
if( !(c == '|' || c == '*')) {
throw new IllegalArgumentException("Invalid character '" + c + "'." +
"Accepted characterd are '|' and '*'");
}
if ( c == '|' && !compStart) {
compStart = true;
}
if(compStart && c == '*') {
itemCount++;
}else if(compStart && c == '|'){
compartmentCount += itemCount;
//reset itemCount. Restart
itemCount = 0;
}
}
return compartmentCount;
}
public int[] getAllItems(String str, int[] startIndices, int[] endIndices) {
assert startIndices.length == endIndices.length;
int[] result = new int[startIndices.length];
for(int i = 0 ; i < startIndices.length; i++){
result[i] = computeItemCount(str, startIndices[i], endIndices[i]);
}
return result;
}
void testGetAllItems() {
String str = "|****|**|*|*****|**";
// Find total number of items in closed compartments in the given range for the string.
int[] startIndices = {1, 3, 5, 6};
int[] endIndices = {18, 5, 10, 11};
int[] result = getAllItems(str, startIndices, endIndices);
Arrays.stream(result).forEach(e -> System.out.printf("%d, ", e));
}
public static void main(String... args){
ItemCompartments app = new ItemCompartments();
app.testGetAllItems();
}
- Sahil May 26, 2021