Interview Coding Problems : Solved

Hereon afterwards, I will be posting Java Code, for various problem sets, which are generally given during placement exams and interviews. These problems are well known and I certainly do not claim that these are most optimum, but I in the spirit of open source want to make my code available to those who might benefit from it.

If you feel this code helped you at all, just drop me a mail or comment, so that it keeps me motivated to keep doing it for more and more problem sets.

Thank you.

Today's problem : Based on Maxflow. 

Problem Statement

After succeeding to the British crown, you inherit a 16th-century Scottish castle with an elaborate plumbing system that has accumulated pipes and junctions over four centuries. You'd like to know if it is safe to install a modern American overHead Tank , or if this will eventually overflow the historic bathtub of James VI/James I.

Input Format

The first line of input consist of two integers N (no of junctions) and M (no of pipes) , separated by a single space.

Then, M lines follow. Each of these lines consist of three integers X, Y, Cxy separated by a single space. It means that there is a pipe between the junction X and the junction Y with a capacity of pipe equal to Cxy.

Assume junction 1 will be Source and junction N represents Sink.

Constraints:

3≤N≤500

3≤M≤500

1≤capacity of pipe ≤100

The junctions are indexed from 1 to N. its implicit that 1 is source and N is sink

Output Format

A yes or no, that represent to install new American overhead tank or not. A Integer representing maximum flow allowed my network into sink.

Sample Input

6 10

1 2 16

1 3 13

2 3 10

3 2 4

2 4 12

3 5 14

4 3 9

5 4 7

4 6 20

5 6 4

Sample Output

Yes

23

Explanation

The max flow of the network is 23 which is lesser than maximum input capacity of sink(bathtub) i.e 24.

Solution

	import java.util.*;
	class Edge{
	String name;
	String revName;
	int capacity;
	int flow;
	int revFlow;
	int fromVertex;
	int toVertex;
	int residualCapacity;
	Edge(){}
	Edge(String n, int capN){
	this.name = n;
	this.revName = reverseFlowName();
	this.capacity = capN;
	this.flow = 0;
	this.revFlow = 0;
	this.fromVertex = fromVertex();
	this.toVertex = toVertex();
	this.residualCapacity = this.capacity - flow;
	}
	public int getResidualCapacity() {
	return residualCapacity;
	}
	public int getFromVertex() {
	return fromVertex;
	}
	public int getToVertex() {
	return toVertex;
	}
	int fromVertex(){
	String[] frmArr = name.split(":");
	int fvert = Integer.parseInt(frmArr[0]);
	return fvert;
	}
	int toVertex(){
	String[] frmArr = name.split(":");
	int tvert = Integer.parseInt(frmArr[1]);
	return tvert;
	}
	String reverseFlowName(){
	char from = name.charAt(0);
	char to = name.charAt(1);
	String revName = Character.toString(to) + Character.toString(from);
	return revName;
	}
	public void updateResiCap(){
	this.residualCapacity = this.capacity - this.flow;
	}
	public String getName() {
	return name;
	}
	public String getRevName() {
	return revName;
	}
	public void setCapacity(int capacity) {
	this.capacity = capacity;
	}
	public int getCapacity() {
	return capacity;
	}
	public int getFlow() {
	return flow;
	}
	public int getRevFlow() {
	return revFlow;
	}
	public void setFlow(int flow) {
	this.flow += flow;
	}
	public void setRevFlow(int revFlow) {
	this.revFlow = revFlow;
	}
	}
	class Vertex{
	int name;
	int distance;
	int parent;
	boolean visited;
	Vertex(int n){
	this.name = n;
	this.distance = -1;
	this.parent = -1;
	this.visited = false;
	}
	public boolean isVisited() {
	return visited;
	}
	public void setVisited(boolean visited) {
	this.visited = visited;
	}
	public int getName() {
	return name;
	}
	public int getDistance() {
	return distance;
	}
	public int getParent() {
	return parent;
	}
	public void setDistance(int distance) {
	this.distance = distance;
	}
	public void setParent(int parent) {
	this.parent = parent;
	}
	}
	class BFS{
	TreeMap<Integer, LinkedList<Integer>> adjList = new TreeMap<Integer, LinkedList<Integer>>();
	ArrayList<Edge> path = new ArrayList<Edge>();
	BFS(){}
	public boolean doBFS(ArrayList<Vertex> vert, ArrayList<Edge> edges, int[] parent){
	for(int i = 1; i<=vert.size(); i++){
	adjList.put(i, new LinkedList<Integer>());
	}
	for(Edge x : edges){
	if(adjList.containsKey(x.getFromVertex())){
	adjList.get(x.getFromVertex()).add(x.toVertex());
	}else{
	LinkedList<Integer> ll = new LinkedList<Integer>();
	adjList.put(x.getFromVertex(), ll);
	adjList.get(x.getFromVertex()).add(x.toVertex());
	}
	}
	// System.out.println(adjList.toString());
	int[] visited = new int[vert.size()+1];
	Queue<Integer> q = new LinkedList<Integer>();
	parent[1] = -1;
	vert.get(0).setDistance(0);
	q.add(vert.get(0).getName());
	// System.out.println(vert.get(0).getName());
	while(!q.isEmpty()){
	int u = q.remove();
	//System.out.println(u);
	Iterator<Integer> itr = adjList.get(u).iterator();
	while(itr.hasNext()){
	int v = itr.next();
	//System.out.println("v " + v);
	for(Edge e : edges){
	if(e.getFromVertex() == u && e.toVertex() == v ){
	if(e.getCapacity()>0 && visited[v] == 0){
	q.add(v);
	visited[v] = 1;
	parent[v] = u;
	}
	}
	}
	}
	}
	return (visited[vert.size()] ==1);
	}
	}
	public class MaxFlowPlumbing {
	public static void main(String[] args) {
	ArrayList<Vertex> vertxList = new ArrayList<Vertex>();
	ArrayList<Edge> edgeList = new ArrayList<Edge>();
	ArrayList<Integer> path = new ArrayList<Integer>();
	Scanner input = new Scanner(System.in);
	int maxCapacity = 0;
	int maxFlow = 0;
	int noOfVertex = input.nextInt();
	int noOfEdges = input.nextInt();
	int lastVertex = noOfVertex;
	for(int i = 1; i <= noOfVertex; i++){
	Vertex newVert = new Vertex(i);
	vertxList.add(newVert);
	}
	for(int i = 0; i < noOfEdges; i++){
	String from = input.next();
	String to = input.next();
	int capacity = input.nextInt();
	if(Integer.parseInt(to) == lastVertex){
	maxCapacity += capacity;
	}
	String edgeName = from +":"+ to;
	Edge newEdge = new Edge(edgeName, capacity);
	edgeList.add(newEdge);
	}
	int[] parent = new int[vertxList.size()+1];
	BFS getPath = new BFS();
	while(getPath.doBFS(vertxList, edgeList, parent)){
	int flow = 1000000;
	for(int i = vertxList.size(); i !=1 ; i = parent[i]){
	int u = parent[i];
	for(Edge x : edgeList){
	if(x.getFromVertex() == u && x.getToVertex() == i){
	if(x.getCapacity()<flow){
	flow = x.getCapacity();
	}
	}
	}
	}
	for(int j = vertxList.size(); j!=1; j=parent[j]){
	int u = parent[j];
	boolean flag = false;
	for(Edge x: edgeList){
	if(x.getFromVertex()== u && x.toVertex() == j){
	x.setCapacity(x.getCapacity()-flow);
	}
	}
	for(Edge y: edgeList){
	if (y.getFromVertex()== j && y.toVertex() == u){
	y.setCapacity(y.getCapacity()+flow);
	flag = true;
	break;
	}
	}
	if(!flag){
	edgeList.add(new Edge(Integer.toString(j)+":"+Integer.toString(u), flow));
	}
	}
	maxFlow += flow;
	}
	if(maxFlow<maxCapacity){
	System.out.println("Yes");
	}else{
	System.out.println("No");
	}
	System.out.println(maxFlow);
	}
	}

view raw plumbing.java hosted with ❤ by GitHub