Related Strings : Interview Coding

Problem Statement

Two strings S1 and S2 are "Related" if one of the condition holds true: 
1) They are equal 
2) If we divide string S1 into two halves of the same size S11 and S12, and string S2 into two halves of the same size S21 and S22, then one of the following is correct:
A: S11 is Related to S21 and S12 is Related to S22.
B: S11 is Related to S22 and S12 is Related to S21.
You are given a two strings S1 and S2 print "YES" if they are related otherwise Print "NO".

Input Format

Two space separated strings.

Output Format

Print "YES" if given two string are related otherwise print "NO".

Sample Input

aaba abaa

Sample Output

YES

Solution

	import java.util.*;
	public class Solution {
	public static void main(String[] agrs){
	Scanner input = new Scanner(System.in);
	String str1 = input.next();
	String str2 = input.next();
	if(strComp(str1, str2))
	System.out.println("YES");
	else
	System.out.println("NO");
	}
	public static boolean strComp(String str1, String str2){
	if(str1.equals(str2))
	{
	return true;
	}
	else {
	if(str1.length()==0 || str2.length()==0)
	{ return false;
	}
	if(str1.length()%2!=0 || str2.length()%2!=0)
	return false;
	String str11 = str1.substring(0, str1.length()/2);
	String str12 = str1.substring((str1.length()/2), str1.length());
	String str21 = str2.substring(0, str2.length()/2);
	String str22 = str2.substring((str2.length()/2), str2.length());
	if((strComp(str11, str21)&&strComp(str12, str22)) ||
	(strComp(str11, str22) && strComp(str12, str21)))
	return true;
	}
	return false;
	}
	}

view raw relatedString.java hosted with ❤ by GitHub

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