I need an help for graph representation [JusPay Coding Interview Question]

help
,
1

This question that I posted below is asked in one of a coding interview in JusPay

The question state that

About · Juspay

You are given a maze with N-cells. Each cell may have multiple entry points but not more than one exit (i.e. entry/exit points are unidirectional doors like valves).

The cells are named with an integer value from 0 to N-1.

You have to find: find the node number of maximum weigth node (Weight of a node is the sum of node numbers of all nodes pointing to that node)

INPUT FORMAT

An integer T, denoting the number of test cases, followed by 2T lines as the test case will contain 2 lines. The first line of each test case has the number of cells N. The second line of each test case has a list of N values of edge[] array.edge[] array.edge[i] contains the cell number that can be reached from cell “i” in one step. edge[i] is -1 if the "i"th cell doesn’t have an exit.

OUTPUT FORMAT

First-line denotes the node number with the maximum wight node.

Sample Input

1

23

4 4 1 4 13 8 8 8 0 8 14 9 15 11 -1 10 15 22 22 22 22 22 21

Sample output

22

But I don’t understand how to represent these inputs array into a graph-like structure?

Is there anyone who previously solved a question like that? can you help me out?

image1
image1814×336 23.5 KB

Program in Java

static int solution(int[] array) {
    //solution here
}

public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    int testCases = scanner.nextInt();
    for (int loop=0; loop<testCases; loop++) {
        int numOfBlocks = scanner.nextInt();
        int array[] = new int[numOfBlocks];
        int src, des;
        for (int i=0; i<numOfBlocks; i++) {
            array[i] = scanner.nextInt();
        }
        System.out.println(solution(array));
    }
    scanner.close();
}
2 Likes
2

There is no need to represent the given input as a graph. See the following code:

static int solution(int[] array) {
    int n = array.length;
    int count[] = new int[n];
    Arrays.fill(count, 0);
    for(int i = 0; i < n; i++) {
        if(array[i] != -1)
            count[array[i]] += i;
    }
    int maxWeight = 0;
    int nodeNumber = 0;
    for(int i = 0; i < n; i++) {
        if(count[i] > maxWeight) {
            maxWeight = count[i];
            nodeNumber = i;
        }
    }
    return nodeNumber;
}
4 Likes
3

Well its not actually graph question as such that we need to represent it still if you want to know how to represent directed graphs you can refer this link:
Graph Representation

5

thanks for posting your solution but may I know the logic behind the arrangement? or which type of problem it is related to? because I have similar-like questions ig: Finding Largest Sum Cycle, Nearest Meeting cell, etc from JusPay

6

You’re going to find it out yourself, with the following hints.

  • Know about Indegree and Outdegree - (major hint to solve the problem)
  • The given array represents a graph indeed, with the number of edges being N.
  • Find what data is given in the array?
  • Relate the image with the example.
    There is an edge from i to a[i] for each i\isin[0, N - 1].
1 Like
7

can you solve one more, please. it will help me to build an understanding cause its still confusing for me. I was unable to approach this problem or failed to build relationship from array to graph shown in image.

Largest Sum Cycle
You have to find the sum of the largest sum cycle in the maze. Return -1 if there are no cycles. The Sum of a cycle is the sum of node numbers of all nodes in that cycle.

Inputs are same

Output
45

8

And how are you relating or detecting entry /exit points?

9

How did you determine, which node is pointing to a node?

10

I don’t think so anyone have solved the 2nd question ( length of largest circle) completely
because some of the test cases were wrong. The question mentions, there are N nodes and the values are from 0 to N-1. but in one of the visible test case N was also included, so i was getting “null pointer exception”. Anyone who passed all the test cases for this question?

I gave the test 2nd time and this time also same questions and same test cases :frowning:
The assessment was taken on talescale’s website.

11

Thank you for the clear explanations, because it caused some difficulties for me