Amazon Interview Question Software Developers
Country: India
Interview Type: Phone Interview
package com.lokesh.cc.amazon;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
public class FindQualifyingSubString {
public static void main(String[] args) throws Exception {
ResultHolder resultHolder = new ResultHolder();
getMatchingPattern("111138984324", new ArrayList<>(), 2, 2, resultHolder);
System.out.println(resultHolder.lst);
}
public static class ResultHolder {
boolean isResultFound = false;
List<Integer> lst = new ArrayList<>();
}
public static List<Integer> getMatchingPattern(String input, List<Integer> prevResult, int beginindex, int endIndex,
ResultHolder resultHolder) throws Exception {
if (endIndex == input.length()) {
return (resultHolder.isResultFound) ? prevResult : new ArrayList<Integer>();
}
if (resultHolder.isResultFound) {
return prevResult;
}
if (input == null || input.length() < 1) {
throw new Exception("input can't be null");
}
int currentPosData = Integer.parseInt(input.substring(beginindex, endIndex + 1));
if (!prevResult.isEmpty()) {
if (currentPosData == prevResult.get(prevResult.size() - 1) + prevResult.get(prevResult.size() - 2)) {
prevResult.add(currentPosData);
if (endIndex == input.length() - 1) {
resultHolder.isResultFound = true;
resultHolder.lst= prevResult;
}
getMatchingPattern(input, prevResult, endIndex + 1, endIndex + 1, resultHolder);
} else if (currentPosData < prevResult.get(prevResult.size() - 1) + prevResult.get(prevResult.size() - 2)) {
// add next char into the current number
getMatchingPattern(input, prevResult, beginindex, endIndex + 1, resultHolder);
} else {
prevResult = new ArrayList<>();
// left shift the number and check combination
getMatchingPattern(input, prevResult, endIndex + 1, endIndex + 1, resultHolder);
}
} else {
if (!resultHolder.isResultFound) {
Map<Integer, Integer> prevCombination = getAllPossiblePreviousSequence(input.substring(0, beginindex));
for (Entry<Integer, Integer> e : prevCombination.entrySet()) {
if (!resultHolder.isResultFound && e.getKey() + e.getValue() == currentPosData) {
// include it in result set
prevResult.add(e.getKey());
prevResult.add(e.getValue());
prevResult.add(currentPosData);
if (endIndex == input.length() - 1) {
resultHolder.isResultFound = true;
resultHolder.lst = prevResult;
}
if (getMatchingPattern(input, prevResult, endIndex + 1, endIndex + 1,
resultHolder).isEmpty()) {
prevResult = new ArrayList<>();
prevResult.add(e.getValue());
prevResult.add(e.getKey());
prevResult.add(currentPosData);
if (getMatchingPattern(input, prevResult, endIndex + 1, endIndex + 1,
resultHolder).isEmpty()) {
getMatchingPattern(input, new ArrayList<Integer>(), beginindex + 1, endIndex + 1,
resultHolder);
}
}
} else if (e.getKey() + e.getValue() < currentPosData) {
// left shift data and call same function again
getMatchingPattern(input, new ArrayList<Integer>(), beginindex + 1, endIndex + 1,
resultHolder);
} else {
getMatchingPattern(input, new ArrayList<Integer>(), beginindex, endIndex + 1, resultHolder);
}
}
}
}
return resultHolder.isResultFound ? prevResult : new ArrayList<>();
}
public static Map<Integer, Integer> getAllPossiblePreviousSequence(String input) {
Map<Integer, Integer> prevCombination = new HashMap<>();
for (int i = 1; i < input.length(); i++) {
prevCombination.put(Integer.parseInt(input.substring(0, i)),
Integer.parseInt(input.substring(i, input.length())));
}
return prevCombination;
}
}
public class SumArray {
private static TreeSet<Integer> resultList = new TreeSet<>();
private static boolean check(char[] chars, int offset1, int offset2, int offset3) {
int first = intOf(subArr(chars, 0, offset1));
int second = intOf(subArr(chars, offset1, offset2));
int third = intOf(subArr(chars, offset1 + offset2, offset3));
boolean result;
if (first + second == third) {
if (offset1 + offset2 + offset3 >= chars.length) {
addIntermediateResults(first, second, third);
return true;
}
return check(subArr(chars, offset1, chars.length - offset1),
offset2, offset3, Math.max(offset2, offset3));
}
if (isValidOffSet(offset1, offset2, 1 + offset3, chars.length)) {
result = check(chars, offset1, offset2, 1 + offset3);
if (result) {
addIntermediateResults(first, second, third);
return true;
}
}
if (isValidOffSet(offset1, 1 + offset2, Math.max(offset1, 1 + offset2), chars.length)) {
result = check(chars, offset1, 1 + offset2, Math.max(offset1, 1 + offset2));
if (result) {
addIntermediateResults(first, second, third);
return true;
}
}
if (isValidOffSet(1 + offset1, offset2, Math.max(1 + offset1, offset2), chars.length)) {
result = check(chars, 1 + offset1, offset2, Math.max(1 + offset1, offset2));
if (result) {
addIntermediateResults(first, second, third);
return true;
}
}
return false;
}
private static void addIntermediateResults(int first, int second, int third) {
resultList.add(first);
resultList.add(second);
resultList.add(third);
}
public static void main(String[] args) {
String numStr = "1111223";
char[] chars = numStr.toCharArray();
System.out.println(check(chars, 1, 1, 1));
System.out.println(resultList);
}
private static boolean isValidOffSet(int offset1, int offset2, int offset3, int length) {
return (offset1 + offset2 + offset3 <= length &&
(offset3 == Math.max(offset1, offset2) || offset3 == 1 + Math.max(offset1, offset2)));
}
private static char[] subArr(char[] chars, int index, int offset) {
int trueOffset = Math.min(chars.length - index, offset);
char[] destArr = new char[trueOffset];
System.arraycopy(chars, index, destArr, 0, trueOffset);
return destArr;
}
private static int intOf(char... chars) {
return Integer.valueOf(new String(chars));
}
}
public class SumArray {
private static TreeSet<Integer> resultList = new TreeSet<>();
private static boolean check(char[] chars, int offset1, int offset2, int offset3) {
int first = intOf(subArr(chars, 0, offset1));
int second = intOf(subArr(chars, offset1, offset2));
int third = intOf(subArr(chars, offset1 + offset2, offset3));
boolean result;
if (first + second == third) {
if (offset1 + offset2 + offset3 >= chars.length) {
addIntermediateResults(first, second, third);
return true;
}
return check(subArr(chars, offset1, chars.length - offset1),
offset2, offset3, Math.max(offset2, offset3));
}
if (isValidOffSet(offset1, offset2, 1 + offset3, chars.length)) {
result = check(chars, offset1, offset2, 1 + offset3);
if (result) {
addIntermediateResults(first, second, third);
return true;
}
}
if (isValidOffSet(offset1, 1 + offset2, Math.max(offset1, 1 + offset2), chars.length)) {
result = check(chars, offset1, 1 + offset2, Math.max(offset1, 1 + offset2));
if (result) {
addIntermediateResults(first, second, third);
return true;
}
}
if (isValidOffSet(1 + offset1, offset2, Math.max(1 + offset1, offset2), chars.length)) {
result = check(chars, 1 + offset1, offset2, Math.max(1 + offset1, offset2));
if (result) {
addIntermediateResults(first, second, third);
return true;
}
}
return false;
}
private static void addIntermediateResults(int first, int second, int third) {
resultList.add(first);
resultList.add(second);
resultList.add(third);
}
public static void main(String[] args) {
String numStr = "1111223";
char[] chars = numStr.toCharArray();
System.out.println(check(chars, 1, 1, 1));
System.out.println(resultList);
}
private static boolean isValidOffSet(int offset1, int offset2, int offset3, int length) {
return (offset1 + offset2 + offset3 <= length &&
(offset3 == Math.max(offset1, offset2) || offset3 == 1 + Math.max(offset1, offset2)));
}
private static char[] subArr(char[] chars, int index, int offset) {
int trueOffset = Math.min(chars.length - index, offset);
char[] destArr = new char[trueOffset];
System.arraycopy(chars, index, destArr, 0, trueOffset);
return destArr;
}
private static int intOf(char... chars) {
return Integer.valueOf(new String(chars));
}
}
bool partistr(string input, vector<string> res, vector<vector<string>> & out) {
if (res.size() == 3) {
if (stoi(res[0]) == stoi(res[1]) + stoi(res[2])) {
out.push_back(res);
res.erase(res.begin());
} else {
res.clear();
}
}
if (input.size() == 1) {
if (res.size() == 2 && stoi(res[0]) == stoi(res[1]) + stoi(input)) {
return true;
}
}
for (int i = 1; i < input.size(); i++) {
string curr = input.substr(input.length() - i, i);
res.push_back(curr);
auto rem = input.substr(0, input.length() - i);
if (partistr(rem, res, out))
return true;
res.pop_back();
}
return false;
}
Are we assuming that there's a unique solution ? if not, how are branching solutions resolved?
- CrazyDiamondu February 06, 2018