Represent a graph containing directed and undirected edges using List<Integer>

user_10977529 0
Viewed 119

I was asked this question in one of my google interviews. I couldn't figure it out. If someone can help that would be great :)

The class provided was

class Node{
   int data,
   List<Node> outEdges;
}

if you're provided a Node stream containing both directed and undirected edges you have to encode it in such a way that it return List and and decode again to original graph

List<Integer> encode(Node root){
}

Node decode(List<Integer> graph){
}

The hint provided was you can add your own integers if you want

graph data-structures algorithm java
1 Answers

You could just put the data and all the edges in the list and using null as delimiter:

private class IndexAndEdge {
    public Set<Integer> edges = new HashSet<>();
    public int index;
    public int data;
}

List<Integer> encode(Node root) {
    List<Integer> result = new ArrayList<>();
    Map<Node, IndexAndEdge> lookup = new HashMap<>();
    parse(root, lookup);
    result.add(lookup.size());
    lookup.values().stream()
        .sorted((a, b) -> Integer.compare(a.index, b.index))
        .forEach(iae -> {
            result.add(iae.data);
            result.addAll(iae.edges);
            result.add(null);
        });
    result.remove(result.size() - 1);
    return result;
}

private int parse(Node node, Map<Node, IndexAndEdge> lookup) {
    if (lookup.containsKey(node))
        return lookup.get(node).index;
    IndexAndEdge iae = new IndexAndEdge();
    iae.index = lookup.size();
    iae.data = node.data;
    lookup.put(node, iae);
    for (Node n : node.outEdges)
        iae.edges.add(parse(n, lookup));
    return iae.index;
}

Node decode(List<Integer> graph) {
    Node[] nodes = new Node[graph.get(0)];
    for (int i = 0; i < nodes.length; i++) {
        nodes[i] = new Node();
        nodes[i].outEdges = new ArrayList<>();
    }
    int index = 0;
    for (int i = 1; i < graph.size(); i++) {
        Integer n = graph.get(i);
        if (n == null)
            index++;
        else if (nodes[index].outEdges.isEmpty())
            nodes[index].data = n;
        else
            nodes[index].outEdges.add(nodes[n]);
    }
    return nodes[0];
}
user_47851100
Related