The Social Network

Problem Statement

A student in a college is planning to start a new social networking website for his college community. In this social network, initially, all people belong to different communities. Then, if X connects with Y, the result is the merger of the communities to which X and Y belong to. Suppose, person X and Y connected and later Y and Z connected, then X,Y and Z will belong to the same community.

Input Format

The first line will contain 2 integers U and V, separated by single space denoting number of persons and number of queries respectively. The next U lines will denote each person's details with each detail separated by a single space. The details are : "id of the person" "name of the person" "age of the person". The next V lines will contain V queries. There are 4 types of queries for this problem:-

1. M id1 id2 : This query will merge the 2 communities to which person with id1 and id2 belong to. If both of them belong to same community, then no need to merge.
2. F id1 id2 : This query will find whether person with id1 and person with id2 belong to the same community or not. Your answer has to be “YES” or “NO”.
3. W id1 : This query will return the number of persons in a community to which a person with id1 belongs to.
4. P id1 : This query will print the details of the person with id1.

Output Format

The output of the queries.

Sample Input

6 12
1 Harish 25
2 Anurag 24
3 Gaurav 25
4 Shaifali 22
5 Ranjana 23
6 Krishana 29
F 3 6
M 1 2
M 4 6
W 4
P 4
M 3 5
M 5 4
M 3 6
F 1 6
M 1 6
F 1 6
W 5

Sample Output

NO
2
4 Shaifali 22
NO
YES
6

Solution

	import java.util.*;
	import java.util.concurrent.LinkedBlockingDeque;
	class Person {
	private int id;
	private String name;
	private int age;
	private int parent;
	Person(Scanner input){
	this.id = input.nextInt();
	this.name = input.next();
	this.age = input.nextInt();
	this.parent = this.id;
	}
	public int getParent() {
	return parent;
	}
	public void setParent(int parent) {
	this.parent = parent;
	}
	public int getId() {
	return id;
	}
	public void setId(int id) {
	this.id = id;
	}
	public String getName() {
	return name;
	}
	public void setName(String name) {
	this.name = name;
	}
	public int getAge() {
	return age;
	}
	public void setAge(int age) {
	this.age = age;
	}
	}
	public class Solution {
	public static TreeMap<Integer, Person> trMapPerson
	= new TreeMap<Integer, Person>();
	public static TreeMap<Integer, LinkedList<Person>> trMapSet =
	new TreeMap<Integer, LinkedList<Person>>();
	enum option {M, F, W, P};
	public static void main(String[] args){
	Scanner input = new Scanner(System.in);
	int u = input.nextInt();
	int v = input.nextInt();
	for(int i = 1; i <= u ; i ++){
	trMapPerson.put(i, new Person(input));
	trMapSet.put(i, new LinkedList<Person>());
	trMapSet.get(i).add(trMapPerson.get(i));
	}
	// System.out.println(trMapPerson.toString());
	// System.out.println(trMapSet.toString());
	while(v != 0){
	performQuery(input);
	v--;
	}
	}
	public static void performQuery(Scanner input){
	option userOption;
	userOption = option.valueOf(input.next());
	switch(userOption){
	case M : merge(input);
	break;
	case F : find(input);
	break;
	case W : length(input);
	break;
	case P : printDetail(input);
	break;
	}
	}
	public static void length(Scanner input){
	int id = input.nextInt();
	int community = trMapPerson.get(id).getParent();
	System.out.println(trMapSet.get(community).size());
	}
	public static void merge(Scanner input){
	int id1 = input.nextInt();
	int id2 = input.nextInt();
	if(trMapPerson.get(id1).getParent()!=
	trMapPerson.get(id2).getParent())
	{
	if(trMapSet.get(trMapPerson.get(id1).getParent()).size()
	<= trMapSet.get(trMapPerson.get(id2).getParent()).size()){
	for(Person j : trMapSet.get(trMapPerson.get(id2).getParent())){
	trMapSet.get(trMapPerson.get(id1).getParent()).add(j);
	j.setParent(trMapPerson.get(id1).getParent());
	}
	} else
	{
	for(Person j : trMapSet.get(trMapPerson.get(id1).getParent())){
	trMapSet.get(trMapPerson.get(id2).getParent()).add(j);
	j.setParent(trMapPerson.get(id2).getParent());
	}
	}
	}
	if(trMapPerson.get(id1).getParent()!=trMapPerson.get(id2).getParent())
	{
	if(trMapSet.keySet().contains(id2)){
	trMapSet.remove(id2);
	}
	}
	}
	public static void printDetail(Scanner input){
	int id = input.nextInt();
	System.out.print(id);
	System.out.print(" " + trMapPerson.get(id).getName());
	System.out.println(" " + trMapPerson.get(id).getAge());
	}
	public static void find(Scanner input){
	int id1 = input.nextInt();
	int id2 = input.nextInt();
	if(trMapPerson.get(id1).getParent() ==
	trMapPerson.get(id2).getParent()){
	System.out.println("YES");
	}
	else System.out.println("NO");
	}
	}

view raw socialNetwork.java hosted with ❤ by GitHub

Greedy Algorithms : Implementing Lecture Scheduling : Coding Interview

Problem Statement

In a conference, N people from a company XYZ are present to attend maximum number of presentations. Each presentation is scheduled between 8:00 and 8:00. Here the second 8:00 means 8:00 pm. Our task is to assign people to presentations such that the number of unique presentations attended by XYZ as a company is maximised.

Input Format

Input is provided in the form a file (taken as command line argument). The first line contains N i.e # of people. Second line contains M i.e # of presentation on that day. M lines follow each containing start and end time of presentation. Time will be in format of HH:MM.

Output Format

Output : The maximum number of presentations that can be attended.

Sample Input

3 
5 
08:00 08:00 
08:00 08:00 
08:00 08:00 
08:00 08:00 
08:00 08:00

Sample Output

3

Explanation

3 people can attend max 3 presentations for the given timings.

Solution

	import java.util.ArrayList;
	import java.util.Collections;
	import java.util.Comparator;
	import java.util.Scanner;
	import java.util.TreeMap;
	class Person{
	int name;
	int startTime = 0;
	int endTime = 0;
	ArrayList<Integer> presentationsAttended = new ArrayList<>();
	Person(int n){
	this.name = n;
	}
	public int getStartTime() {
	return startTime;
	}
	public int getEndTime() {
	return endTime;
	}
	public void setStartTime(int startTime) {
	this.startTime = startTime;
	}
	public void setEndTime(int endTime) {
	this.endTime = endTime;
	}
	}
	class Presentation{
	int name;
	int startTime;
	int endTime;
	ArrayList<Integer> clashesWith = new ArrayList<Integer>();
	boolean attended;
	public Presentation() {
	}
	Presentation(int n, String sTime, String eTime){
	this.name = n;
	this.attended = false;
	this.startTime = convertStime(sTime);
	this.endTime = convertEtime(eTime);
	}
	int convertStime(String sTime){
	int timeInMins = 0;
	String[] strArr = sTime.split(":");
	int hour = Integer.parseInt(strArr[0]);
	int min = Integer.parseInt(strArr[1]);
	if(hour < 8){
	timeInMins = ((12+hour) * 60) + min ;
	} else {
	timeInMins = (hour * 60) + min;
	}
	return timeInMins;
	}
	int convertEtime(String eTime){
	int timeInMins = 0;
	String[] strArr = eTime.split(":");
	int hour = Integer.parseInt(strArr[0]);
	int min = Integer.parseInt(strArr[1]);
	if(hour == 8 && min != 0){
	timeInMins = (hour * 60) + min;
	} else if( hour <= 8){
	timeInMins = ((12+hour) * 60) + min;
	}else {
	timeInMins = (hour * 60) + min;
	}
	return timeInMins;
	}
	public void setName(int name) {
	this.name = name;
	}
	public int getName() {
	return name;
	}
	public int getStartTime() {
	return startTime;
	}
	public int getEndTime() {
	return endTime;
	}
	public ArrayList<Integer> getClashesWith() {
	return clashesWith;
	}
	public boolean isAttended() {
	return attended;
	}
	public void setAttended(boolean attended) {
	this.attended = attended;
	}
	}
	public class SchedulingFinal {
	public static ArrayList<Presentation> alPrez = new ArrayList<Presentation>();
	public static ArrayList<Person> alPerson = new ArrayList<Person>();
	public static ArrayList<Presentation> attended = new ArrayList<Presentation>();
	public static void main(String[] args) {
	Scanner input = new Scanner(System.in);
	int noOfPeople = input.nextInt();
	int noOfPrez = input.nextInt();
	int count = 0;
	for(int i = 0; i < noOfPrez; i++){
	String startTime = input.next();
	String endTime = input.next();
	Presentation newPrez = new Presentation(i, startTime, endTime);
	alPrez.add(newPrez);
	}
	for(int j = 0; j < noOfPeople; j++){
	Person newPerson = new Person(j);
	alPerson.add(newPerson);
	}
	Collections.sort(alPrez, new sortBystartTime());
	int t = 0;
	for(t = 0; t < noOfPeople ;t ++){
	attended.add(alPrez.get(t));
	count++;
	alPerson.get(t).setStartTime(alPrez.get(t).getStartTime());
	alPerson.get(t).setEndTime(alPrez.get(t).getEndTime());
	}
	for(int d = t; d < alPrez.size(); d++){
	Collections.sort(alPerson, new sortByendTime());
	if(alPrez.get(d).getStartTime() >= alPerson.get(0).getEndTime()){
	count ++;
	alPerson.get(0).setStartTime(alPrez.get(d).getStartTime());
	alPerson.get(0).setEndTime(alPrez.get(d).getEndTime());
	} else if(alPrez.get(d).getEndTime() < alPerson.get(alPerson.size()-1).getEndTime()){
	alPerson.get(alPerson.size()-1).setStartTime(alPrez.get(d).getStartTime());
	alPerson.get(alPerson.size()-1).setEndTime(alPrez.get(d).getEndTime());
	}
	}
	System.out.println(count);
	}
	}
	class sortBystartTime implements Comparator<Presentation>{
	public int compare(Presentation p1, Presentation p2) {
	if(p1.getStartTime()<p2.getStartTime()){
	return -1;
	} else if(p1.getStartTime()>p2.getStartTime()){
	return 1;
	}
	else {
	return 0;
	}
	}
	}
	class sortByendTime implements Comparator<Person>{
	public int compare(Person p1, Person p2) {
	if(p1.getEndTime()< p2.getEndTime()){
	return -1;
	}if(p1.getEndTime()> p2.getEndTime()){
	return 1;
	}else {
	return 0;
	}
	}
	}

view raw lecture-scheduling.java hosted with ❤ by GitHub

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