Kodr

Kodr

  • Content
  • Blog
  • About
  • Languages iconEnglish
    • Español

›Problems: Binary Search Trees & Graphs

Technical Interviews

  • What are technical interviews based on?
  • Essential content & how to solve algorithms

Big-O Notation

  • Big-O Notation
  • Big-O Examples
  • Big-O Exercises

Optimisation Techniques

  • BUD optimisation
  • DIY Optimisation

Key Concepts

  • Linked Lists
  • Stack & Queues
  • Trees
  • Graphs
  • Tries
  • Sorting
  • Searching
  • Recursion
  • Dynamic Programming

Problems: Arrays & Strings

  • Is Unique
  • String Rotation
  • Check Permutation
  • URLify
  • One Edit Away
  • String Compression
  • Rotate Matrix
  • Zero Matrix
  • Valid Parenthesis

Problems: Linked Lists

  • Remove duplicates
  • Kth to last node
  • Delete Middle Node
  • Partition
  • Sum List
  • Palindrome
  • Intersection
  • Loop Detection

Problems: Stacks & Queues

  • Stack Min
  • Stack Of Plates
  • Queue via Stacks
  • Sort Stack
  • Animal Shelter

Problems: Trees

  • Path Sum
  • Construct Binary Tree from Inorder and Postorder Traversal

Problems: Binary Search Trees & Graphs

  • Route Between Two Nodes
  • Minimal Tree
  • List of Depths
  • Check Balanced
  • Validate BST
  • Successor
  • Build Order
  • First Common Ancestor
  • Check Sub-Tree
  • (Harder) Random Node

Problems: Sorting & Searching

  • Merge Sorted Array
  • First Bad Version

Problems: Dynamic Programming

  • Triple Step
  • Magic Index
  • (Hard) Towers Of Hanoi

Build Order

Build Order: You are given a list of projects and a list of dependencies (which is a list of pairs of projects, where the second project is dependent on the first project). All of a project's dependencies must be built before the project is. Find a build order that will allow the projects to be built. If there is no valid build order, return an error.

For Example:

projects: a, b, c, d, e, f
dependencies: (a, d), (f, b), (b, d), (f, a), (d, c)

Output: f, e, a, b, d, c

👉 Link here to the repo to solve the problem

imagen

👌 Tips

Build a directed graph representing the dependencies. Each node is a project and an edge exists from A to B if B depends on A (A must be built before B). You can also build it the other way if it's easier for you.

Look at this graph. Is there any node you can identify that will definitely be okay to build first?

If you identify a node without any incoming edges, then it can definitely be built. Find this node (there could be multiple) and add it to the build order.Then, what does this mean for its outgoing edges?

Once you decide to build a node, its outgoing edge can be deleted. After you've done this, can you find other nodes that are free and clear to build?

As a totally different approach: Consider doing a depth-first search starting from an arbi- trary node. What is the relationship between this depth-first search and a valid build order?

Pick an arbitrary node and do a depth-first search on it. Once we get to the end of a path, we know that this node can be the last one built, since no nodes depend on it. What does this mean about the nodes right before it?

👊 Solution 1

This approach works by creating the adjacency list, then creating the graph with all the nodes. Then we take an approach in which I start emptying the graphNodes, first checking if it doesn't has any adjacent nodes, then by removing the nodes who's adjacent nodes are in the final result array.

ArrayList<GraphNode<String>> getOrder(GraphNode<String>[] projects, GraphNode<String>[][] dependencies) {
    ArrayList<GraphNode<String>> result = new ArrayList<>();

    Graph<String> graph = generateGraph(projects, dependencies);

    ArrayList<GraphNode<String>> graphNodes = graph.getNodes();


    while (!graphNodes.isEmpty()) {
        for (int i = 0; i < graphNodes.size(); i++) {
            GraphNode node = graphNodes.get(i);
            if (node.getAdjacentNodes().isEmpty()) {
                result.add(graphNodes.remove(i));
            } else {
                ArrayList<GraphNode<GraphNode>> adjacents = node.getAdjacentNodes();
                boolean adjacentsInResults = areAdjacentsInResults(adjacents, result);
                if (adjacentsInResults) result.add(graphNodes.remove(i));
            }
        }
    }

    Collections.reverse(result);
    return result;
}

private Graph<String> generateGraph(GraphNode<String>[] projects, GraphNode<String>[][] dependencies) {
    // create dependency list
    for (GraphNode<String>[] dependency : dependencies) {
        dependency[0].insertAdjacent(dependency[1]);
    }

    Graph<String> graph = new Graph<>();

    for (GraphNode<String> project : projects) {
        graph.insertNode(project);
    }
    return graph;
}

private boolean areAdjacentsInResults(ArrayList<GraphNode<GraphNode>> adjacents, ArrayList<GraphNode<String>> result) {
    for (GraphNode<GraphNode> adjacent : adjacents) {
        if (!result.contains(adjacent)) return false;
    }
    return true;
}

As we can see, this solution is not the most efficient as we have to iterate through every node's adjacency list multiple times, until all of them are empty.

This will give us an also valid result - which is:

Output: f, b, a, b, e, c

👊 Solution 2

I haven't had time to add this solution yet, but if you do please feel free to email it to me


Question borrowed from “Cracking the coding interview”

Last updated on 3/19/2020
← SuccessorFirst Common Ancestor →
  • 👉 Link here to the repo to solve the problem
  • 👌 Tips
  • 👊 Solution 1
  • 👊 Solution 2
Kodr
Content
IntroBig O NotationOptimisation
Coding Problems
Check PermutationIsUniqueURLify
Blogs
Tecnica Pomodoro
Social
About MeGitHub
Follow @diego_romero_x
Copyright © 2021 Kodr