I had my interview at the end of september and here are coding questions that i had.
Level: L3, L4
#Coding Interview 1
I didn't copy first question, so i wrote description by myself.
There N runners and M reports. report i says that runner A beats runner B. Return the order of runners and how they finished
There can be test cases like this: a->b, b->a
Example 1:
A->B
B->C
A->C
C->D
E->D
Result: A,B,C,E,D
Example 2:
a->b
b->a
Result: Impossible
I solved this questions with dfs.
#Coding Interview 2
Given a tree of N vertices and an edge E, calculate the number of vertices in each of the connected components remaining after removal of the edge.
Test case:
image
1,3
Result: 3,8
He asked me how to solve this. I found solution with dfs and he asked me to write only the Tree Structure and prepare method to do this.
class TreeStructure {
public:
int id;
vector<TreeStructure*>edges;
};
pair<int,int> getNumberOfVerticesAfterEdgeDelete(TreeStructure* root, pair<int,int>edge) {
//implementation
}
After he gave follow up question:
Given a tree of N vertices and a list of M edges E, calculate number of vertices in each of the connected components remaining after removal of each edge Ei independently.
Test case:
image
1,3
5,2
1,3
Result:
3,8
2,9
3,8
#Coding Interview 3
Question:
Given a string containing only parentheses, scan it to see if the parentheses are well-nested, then:
If they are, return the string as-is.
If they are not, repair the string so that the parentheses are well nested and return the result
action can be:
deleting, adding, changing
You must do string well-nested with minimum number of actions
Example:
Input: (()
Output: (()), or () or ()()
Input: (())))
Output: ((()))
My solution:
string minActionToMakeWellNested(string s) {
string ans;
//Find not matching indexes
vector<int>v;
for (int i=0;i<s.size();i++) {
if (s[i] == '(') {
v.push_back(i);
} else {
if (!v.empty() && s[v[v.size()-1]] == '(') {
v.pop_back();
} else {
v.push_back(i);
}
}
}
//For every not matching index make actions to change
for (int i=0;i<v.size();i++) {
if (s[v[i]] == '(') {
if (i+1 < v.size() && s[v[i+1]] == '(') {
s[v[i+1]] = ')';
i++;
} else (i+1 >= v.size()) {
s[v[i]] = '_';
}
} else if (s[v[i]] == ')') {
if (i+1 < v.size() && s[v[i+1]] == ')') {
s[v[i]] = '(';
i++;
} else if (i+1 >= v.size() || s[v[i+1]] == '(') {
s[v[i]] = '_';
}
}
}
//Create ans string
ans="";
for (int i=0;i<s.size();i++) {
if (s[i] != '_') {
ans += s[i];
}
}
return ans;
}
After I wrote she said it's good solution and asked how we can do this with one for without vector.
Now I'm waiting for the results.