SDE - 1

Given an array of positive and negative integers, print x if +x and -x are present in the array.

You are given a connected directed acyclic graph of ‘N’ nodes and ‘N’ - 1 edges, such that there is only one edge between any two nodes. You can perform the below operation on the given graph zero or more times:
1) Choose two nodes, ‘X’ and ‘Y’, such that there exists an edge between ‘X’ and ‘Y’.
2) Change the direction of this edge, i.e., if this edge is directed from ‘X’ to ‘Y’, change the direction of this edge to be directed from ‘Y’ to ‘X’ and vice versa.
Your task is to reorder the edges of the given graph in such a way that there exists a directed path from each node to node 0, using the minimum number of operations.

Here the interviewer told me about an app called splitwise which i had used once. In the application each user adds the amount he spends and it’s shared equally among users of the app. The aim is to minimise the number of give and take operations. I initially thought of a very naive approach where I wanted to create classes for each person and expenditure and iterate through the expenditures of other people to find how much a person should give or take. When I took a closer look I got the idea of modelling it as a directed graph and adding directed edges for transactions. With the graph I thought of taking the difference between the pair of edges between two people to reduce a give and take operation to a single give/take operation. There was a catch, if A has to give B Rs.10, B has to give C Rs.10, and A has to give C Rs.10, the minimum operation to do is to give Rs.20 from A to C. B is not involved here as he has to spend all he gets. So I said we could preprocess the graph with the numbers on the incoming and outgoing edges. If the total flow is 0, we could remove that node. He seemed convinced with the approach. He gave me a graph after all the preprocessing done and finally asked me how to minimise it. So I used a greedy method. I was settling the amount of the person who has to get the largest amount by giving the amount of the people who has to give lesser amounts and he said that’ll work.