Google Interview Question for SDE1s


Country: India
Interview Type: In-Person




Comment hidden because of low score. Click to expand.
5
of 5 vote

UnionFind.

- Sithis April 01, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Wouldn't merging the intervals also work here?

- aurelien May 11, 2019 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

I believe there are many approaches
1. First build the graph ( like 2d array) of n nodes using edge list
2. Then pick a pair from restricted nodes and recursively check does current node pass through any other node which is restricted, if so, simply remove that edge(s).
Complexity = there can be at most n^2 edges = M size O(m) , You need to pick a pair from k list O(k), and check all possible connections from source to destination of picked pair O(m)
O(nkm^2)

2.
2.1 build hash to set of given k list O(k)
2.2 Rater bulding graph, while building it check the restrictions recursively using 2d matrix,
Complexity = you need to traverse whole matrix to check restrictions O(n^2)
For each pair from edge list O(m) , keeping hash to set of nodes from k list O(1)
O(mn^2)

3. Efficient
Use union find algo, assuming path compression is used.
3.1 union edges from m list one by one if they are not connected, before connecting them see O(m)

a) the parent (s) of pair source does not lies in k list O(logn)
B) child of pair of destinations node not lies in k list O(logn)
If either of its true, then discard

Complexity = O(logn + logn) * O(m)
O(mlogn)

- nitinguptaiit April 12, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

To check in k list use Hash to set map

- nitinguptaiit April 12, 2019 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

isn't it k*m?

- heejae April 16, 2019 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

No, don't check directly to k list (which will be O(k) ) rather build hash to set list; and then check

What is Hash to set List of K?
put a node as key and all node that it connects to as set being value in map
make sure you put in reverse way to
like
1,4
1,5

1 -> (4,5)
4->1
5->1

to check efficiently in k list

- nitinguptaiit April 16, 2019 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Complexity of last code is
O(mklogn) in worst case
as it might possible that single node is connected to all nodes in restricted list

- nitinguptaiit April 16, 2019 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

for approach 2
O(mkn^2)

- nitinguptaiit April 16, 2019 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Other option still using disjoint set is for each edge, before adding it, check the sets for each vertex in the edge (say sets x and y) and for each edge in the K list check also the sets of its vertices (say sets w and z), in case (x == z && y == w) || (x == w && y == z) discard the edge. Complexity is O(mk logn)

public class RestrictedPaths {

    public List<UndirectedGraph.Edge> create(List<UndirectedGraph.Edge> edges, List<UndirectedGraph.Edge> restricted, int n) {

        DisjointSet ds = new DisjointSet(n);

        List<UndirectedGraph.Edge> result = new ArrayList<>();

        for (UndirectedGraph.Edge edge: edges) {

            int x = ds.find(edge.getSrc());
            int y = ds.find(edge.getDest());

            boolean validEdge = true;
            for (UndirectedGraph.Edge r: restricted) {
                int z = ds.find(r.getSrc());
                int w = ds.find(r.getDest());

                if ((x == z && y == w) || (x == w && y == z)) {
                    validEdge = false;
                    break;
                }
            }

            if (validEdge) {
                result.add(edge);
                ds.union(x, y);
            }
        }

        return result;

    }

}

- mmenezes April 26, 2019 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More