Question

Google | Interview experiences | L3 | 2022 | Set-36

Answer 1

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.

Answer 2

Third one is https://leetcode.com/problems/remove-invalid-parentheses/

Answer 3

First question is exactly similar to Course Schedule II.

 

Second Question
Insights :-

 

1. A tree in the beginning will always have one connected component. When you remove an edge, it is divided into two parts. Between a and b, one will be parent and the other will be the child. We just need to calculate the number of nodes beginning at the subtree rooted at that child and subtract from the total number of vertices.

 

Second question can be solved using DFS. Some assumptions are required here, though.

 

1. The values of the nodes should be unique (Why ?).
2. a and b are given as ints.
3. We assume that a is the parent of b to make our code simpler.
4. We also assume that the graph is directed that the edge from a to b is directed. The code can be easily adjusted to make this work for undirected tree.

 

Algorithm:-
Calculate the number of nodes on each subtree and store that in a map. To get the reference of the node from a or b, build another map again. You can get both the maps and the total counts in one single DFS traversal.

 

Java Code
Time Complexity :- O(N)
Space Complexity :- O(N)

 

import java.util.*;

class Tree {
  public TreeNode root;
  Map<Integer, Integer> numbersMap;
  Map<Integer, TreeNode> nodesMap;
  public int totalCount = 0;
  public Tree(TreeNode node){
    root = node;
    numbersMap = new HashMap<>();
    nodesMap = new HashMap<>();
    totalCount = dfs(root);
  }

  public int dfs(TreeNode root) {
    if (root == null) {
      return 0;
    }

    int count = 1;

    for(TreeNode child : root.children) {
      count += dfs(child);
    }

    numbersMap.put(root.val, count);
    nodesMap.put(root.val, root);

    return count;
  }

  public int[] GetNumberOfVertices(int a, int b) {
    return new int[]{numbersMap.get(b), totalCount - numbersMap.get(b)};
  }

  public int[][] GetNumberOfVertices(int[][] queries) {
    int[][] result = new int[queries.length][2];
    for (int i = 0; i < queries.length; i++) {
      result[i] = GetNumberOfVertices(queries[i][0], queries[i][1]);
    }
    return result;
  }
}

class TreeNode {
  public int val;
  public List<TreeNode> children;

  public TreeNode(int value) {
    val = value;
    children = new ArrayList<>();
  }
}

class Main {

  
  public static void main(String[] args) {
    System.out.println("Hello world!");
    TreeNode zero = new TreeNode(0);
    TreeNode one = new TreeNode(1);
    TreeNode two = new TreeNode(2);
    TreeNode three = new TreeNode(3);
    TreeNode four = new TreeNode(4);
    TreeNode five = new TreeNode(5);
    TreeNode six = new TreeNode(6);
    TreeNode seven = new TreeNode(7);
    TreeNode eight = new TreeNode(8);
    TreeNode nine = new TreeNode(9);
    TreeNode ten = new TreeNode(10);

    zero.children.add(one);
    zero.children.add(two);
    zero.children.add(ten);

    one.children.add(three);
    one.children.add(four);

    two.children.add(five);
    two.children.add(six);

    three.children.add(seven);
    three.children.add(eight);

    five.children.add(nine);

    Tree tree = new Tree(zero);
    

    printArray(tree.GetNumberOfVertices(1, 3));  // prints 3 8
    printArray(tree.GetNumberOfVertices(3, 8));  // prints 1 10
    printArray(tree.GetNumberOfVertices(0, 1));  // prints 5 6

    int[][] queries = new int[3][2];
    queries[0][0] = 1;
    queries[0][1] = 3;
    queries[1][0] = 3;
    queries[1][1] = 8;
    queries[2][0] = 0;
    queries[2][1] = 1;

    printArray(tree.GetNumberOfVertices(queries));
    
  }

  static void printArray(int[] arr) {
    System.out.println(arr[0] + " " + arr[1]);
  }

  static void printArray(int[][] arr) {
    for(int[] ar : arr){
        printArray(ar);
    }
  } 
}