Amazon Interview Question
Backend DevelopersCountry: United States
Here is also a recursion version of the same idea in Python.
Solution (Recursive):
def printFunctionRecursive(functions):
def recursiveHelper(functions, indendationLevel = 1, hasSubFunction = False):
if '->' not in functions:
print(' ' * indendationLevel + functions + ' start')
if not hasSubFunction: # Single function
print(' ' * indendationLevel + functions + ' end')
else:
stackTrace = functions.split('->')
for sub_funcs in stackTrace:
indendationLevel += 2
recursiveHelper(sub_funcs, indendationLevel, True)
print(' ' * indendationLevel + sub_funcs + ' end')
for stackTrace in functions:
recursiveHelper(stackTrace)
Test code:
printFunctionRecursive(['main->foo->bar', 'main2'])
'''
Output:
main start
main end
foo start
foo end
bar start
bar end
main2 start
main2 end
public static void printStackHireachy(String[] funcs)
{
Vector<String> h = new Vector<>();
for(String v:funcs)
{
h.add(v);
}
boolean previousStart = false;
int numOfSpaces = 2;
for(String v:h)
{
if(v.contains("start"))
{
if(previousStart)
{
numOfSpaces = numOfSpaces * 2;
}
previousStart = true;
PrintSpaces(v, numOfSpaces);
}
else
{
previousStart = false;
PrintSpaces(v, numOfSpaces);
numOfSpaces = numOfSpaces / 2;
if(numOfSpaces < 2)
{
numOfSpaces = 2;
}
}
}
}
private static void PrintSpaces(String h, int numOfSpaces) {
for(int i = 0; i < numOfSpaces; i++)
{
System.out.print(" ");
}
System.out.println(h);
}
public static void main(String[] args)
{
String[] in =new String[] {"main start", "foo start", "bar start", "bar end", "foo end","main end", "main2 start", "main2 end"};
printStackHireachy(in);
}
bool startParse(string input) {
string start = input.substr(input.find_last_of(',') + 1);
return start == "start";
}
void callOrder(vector<string> input, int index, vector<vector<string>>& values, int depth) {
if (index >= input.size())
return;
if (startParse(input[index])) {
values[depth].push_back(input[index]);
callOrder(input, index + 1, values, depth + 1);
} else {
callOrder(input, index + 1, values, depth - 1);
}
}
bool startParse(string input) {
string start = input.substr(input.find_last_of(',') + 1);
return start == "start";
}
void callOrder(vector<string> input, int index, vector<vector<string>>& values, int depth) {
if (index >= input.size())
return;
if (startParse(input[index])) {
values[depth].push_back(input[index]);
callOrder(input, index + 1, values, depth + 1);
} else {
callOrder(input, index + 1, values, depth - 1);
}
}
bool startParse(const string& input, string& method) {
int pos = input.find_last_of(',');
string start = input.substr(pos + 1);
method = input.substr(0, pos);
return start == "start";
}
void callOrder(const vector<string>& input, int index, vector<vector<string>>& values, int depth) {
if (index >= input.size())
return;
string methodName;
if (startParse(input[index], methodName)) {
values[depth].push_back(methodName);
callOrder(input, index + 1, values, depth + 1);
} else {
callOrder(input, index + 1, values, depth - 1);
}
}
int main(int argc, const char * argv[]) {
vector<string> input = {"main,start", "foo,start", "foo,end", "boo,start", "boo,end", "main,end"};
vector<vector<string>> methods;
callOrder(input, 0, methods, 0);
for (int i = 0; i < methods.size(); i++) {
for (auto method : methods[i]) {
cout << setfill(' ') << setw(i) << method << std::endl;
}
}
}
public void StackTrace(string [] ar)
{
Stack<string> st = new Stack<string>();
for (int i = 0; i < ar.Length; i++)
{
var str = ar[i];
if(str.EndsWith("start"))
st.Push(ar[0]);
var s = string.Empty;
for (int j = 0; j < st.Count; j++)
{
s += " ";
}
if (str.EndsWith("end"))
st.Pop();
Console.WriteLine(s + str);
}
}
public void StackTrace(string [] ar)
{
Stack<string> st = new Stack<string>();
for (int i = 0; i < ar.Length; i++)
{
var str = ar[i];
if(str.EndsWith("start"))
st.Push(ar[0]);
var s = string.Empty;
for (int j = 0; j < st.Count; j++)
{
s += " ";
}
if (str.EndsWith("end"))
st.Pop();
Console.WriteLine(s + str);
}
}
public void StackTrace(string [] ar)
{
Stack<string> st = new Stack<string>();
for (int i = 0; i < ar.Length; i++)
{
var str = ar[i];
if(str.EndsWith("start"))
st.Push(ar[0]);
var s = string.Empty;
for (int j = 0; j < st.Count; j++)
{
s += " ";
}
if (str.EndsWith("end"))
st.Pop();
Console.WriteLine(s + str);
}
}
Use a stack or recursion to keep track of the function calls. This is very similar to printing the directory structure of a folder. I assume we are given a string which represents the function and I assume we are also given a marker which denotes whether this function calls other functions or is just a standalone function. For the sake of assumption, I assume '->' is the marker which denotes that this function will call other functions. I present my solution in Python below using an explicit stack.
Solution:
Test code:
- prudent_programmer March 28, 2018