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.