What will "eventually" happen ?

I have been back to college for past one year. Away from the day to day chores of professional life is a bliss. But now that I have completed one year and the end of this course is in sight, I think I have started getting some pointers as to where my next assignment is going to be. May be it is just wishful thinking. So I put my sixth sense to test today. I am jotting this down to come back here later and see if what I thought would happen, eventually happened or not?

I meet a lot of people who keep guessing themselves and telling me as to what are precedence and how and where should I expect to go next. To be honest, its not always free advice, I poke them a number of times to find out what they think. Whatever their suggestions and whatever the intent of those suggestions, one thing is for certain. Not even a single person, has ever tried to convince me that I might land up where I want to go or should I say where I think I will go. Their analysis is based on scrutiny of empirical facts. Thats where I think differently.

Going by their logic, they are absolutely correct. I will land up middle of nowhere. Not that I do not like "middle of nowhere", but I think I can be better utilized where my skill is put to test. And I have already got some calls, had some conversations that make me feel that I might land up at the right place. As in every bollywood movie there is a villain, there is one problem though. Its the big daddy's office who has to make the all important decision. I know this office rubs its nastiness on anyone who serves their even one day. But still I have confidence in the training my organisation has provided these chameleonistic breed of men, that better judgement will prevail. 

After all if all that has already happened, happened again, would their be any excitement left ? Would history be rewritten ever again ? So every time we defy logic, we create new stuff. Every individuals path which he treads is always different. Unless, the individual himself wants to make the journey easy and comfortable and keep following the herd. 

There are two forces which are responsible for you deciding your path. One is ofcourse you. And the "you" in my case has spoken ... err.rr.. written too (in this blog) ... now the second and all important force, the big daddy's office men have to take theirs. 

So I think I will go where I want to, "junta" says, do not even think that you can land up their. As always, I like fighting the odds. Big Daddy's men say if you happen to reach where you want to, you will suffer in your carrier later. I want to advice these men to try and look where they will land themselves, because if they are not so sure about themselves, which they will realize if they honestly think about themselves (honesty btw is rare) , they how can you give me my destiny ?? 

**************************************************************************************************************

Hindi quote : "Nai  nai, mere sir pe baal kitne ? Ghabrao nahi jajman, abhi samne aate hain "

English Translation : "barber barber, how many hair do I have on my head ? Don't worry sir, they will soon be in front of you to count "

**************************************************************************************************************

Shifting Focus

Over the period of past two years I have not been able to post regularly because of my academic commitments. I however will be more regular in posting to this blog. I am shifting the focus of the blog from being a knowledge sharing platform to a technical diary. I keep doing some experiment or other with what is available online or do something which interests me, I wish to jot down everything I do on this page so that it becomes a quick reference for me in the future.

Also since it will all be public it might help those who are trying to get their hands dirty with similar stuff. For queries in case you face difficulty of understanding please feel free to contact.

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

How to Decrypt rom-0 file

Download the  lzs compress and decompress tools from http://git.kopf-tisch.de/?p=zyxel-revert;a=summary

After clicking on the link given above, click on snapshot link in front of support firmwareupdate master  

 Once you have down loaded the zyxel-revert-779bfd5.tar.gz  file to your Desktop, perform the following steps

root@kali1:~/Desktop# tar -xzf zyxel-revert-779bfd5.tar.gz
root@kali1:~/Desktop# cd zyxel-revert-779bfd5/
root@kali1:~/Desktop/zyxel-revert-779bfd5# ls

Compile the source code with makefile.

root@kali1:~/Desktop/zyxel-revert-779bfd5# make -f Makefile

To decompress rom-0 file

root@kali1:~/Desktop/zyxel-revert-779bfd5# ./decompress /root/Desktop/rom-0

The result of decompressed file is rom-0.decomp (original-filename.decomp).

Show printable strings from decompressed file.

root@kali1:~/Desktop/zyxel-revert-779bfd5# strings /root/Desktop/rom-0.decomp

Password usually on first line