Swiggy Interview Question
SDE-3sCountry: United States
public static void main(String[] args) throws Exception {
System.out.print(swiggySDE3(Arrays.asList("(A,B)", "(B,C)", "(A,D)", "(C,E)", "(A,F)")));
}
public static String swiggySDE3(List<String> str) {
Map<String, List<String>> map = new HashMap<>();
for (String t : str) {
String[] pair = t.substring(1, t.length() - 1).split(",");
final List<String> orDefault = map.getOrDefault(String.valueOf(pair[0]), new ArrayList<>());
orDefault.add(pair[1]);
map.put(pair[0], orDefault);
}
StringBuffer stringBuffer = new StringBuffer();
swiggySDE3UTIL("A", map, stringBuffer);
return stringBuffer.toString().substring(0, stringBuffer.length()-1);
}
private static void swiggySDE3UTIL(String start, Map<String, List<String>> map, StringBuffer stringBuffer) {
final List<String> values = map.get(start);
if (values == null || values.isEmpty()) {
stringBuffer.append(start + ")");
return;
}
stringBuffer.append(start+"(");
values.forEach(t->swiggySDE3UTIL(t,map,stringBuffer));
stringBuffer.append(")");
}
Simply, maintain two HashMap. Parent Map and child map. In parent map keep a child count. In child map keep a parent info. When inserting new tuple check.
1. parent map already has more than 2 child count.
2. child already has same parent as in tuple
3. child already has a parent.
4. After all tuples are entered run through the parent table and count entries with 0 child if more than 1 flag error.
- NoOne June 01, 2019