Mritunjay Kumar
BAN USERpublic class SingleLinkedList {
private String value;
private SingleLinkedList next;
public SingleLinkedList(String value, SingleLinkedList next){
this.value = value;
this.next = next;
}
public String getValue() {
return value;
}
public void setValue(String value) {
this.value = value;
}
public SingleLinkedList getNext() {
return next;
}
public void setNext(SingleLinkedList next) {
this.next = next;
}
}
public class ListOperations {
/* print the single linked list */
private void printLinkedlist(SingleLinkedList root){
while(root!=null){
System.out.println(root.getValue());
root= root.getNext();
}
}
/* reverse a linked list */
private SingleLinkedList reverseLinkedList(SingleLinkedList root){
SingleLinkedList prev = null;
SingleLinkedList current = root;
SingleLinkedList next = null;
while (current !=null){
next = current.getNext();
current.setNext(prev);
prev = current;
current = next;
}
return prev;
}
/* get middle node */
private SingleLinkedList getMiddleNode(SingleLinkedList root){
SingleLinkedList fast = root;
SingleLinkedList slow = root;
while(fast !=null && fast.getNext()!=null && fast.getNext().getNext()!= null){
fast = fast.getNext().getNext();
slow = slow.getNext();
}
return slow;
}
/*Given a singly linked list: 1->2->3->4->5
Change it to 1->5->2->4->3 using O(1) space*/
private SingleLinkedList shuffleLinkedList(SingleLinkedList root){
SingleLinkedList middle = getMiddleNode(root);
/* get location of middle element */
if (middle !=null) {
//reverse the list after middle position
SingleLinkedList secondList = reverseLinkedList(middle.getNext());
// get the linked list till middle
middle.setNext(null);
SingleLinkedList firstList = root;
// merge first and second list
SingleLinkedList shuffledRoot = firstList;
SingleLinkedList shuffledPtr = null;
boolean fromFirst = true;
SingleLinkedList firstPtr = firstList;
SingleLinkedList secondPtr = secondList;
while (firstPtr != null && secondPtr!=null){
if (fromFirst){
if (shuffledPtr == null){
shuffledPtr = firstList;
firstPtr = firstPtr.getNext();
}
else {
shuffledPtr.setNext(firstPtr);
shuffledPtr = shuffledPtr.getNext();
firstPtr = firstPtr.getNext();
}
}
else {
shuffledPtr.setNext(secondPtr);
shuffledPtr = shuffledPtr.getNext();
secondPtr = secondPtr.getNext();
}
fromFirst = !fromFirst;
}
if (firstPtr == null){
shuffledPtr.setNext(secondPtr);
}
else if(secondPtr == null){
shuffledPtr.setNext(firstPtr);
}
return shuffledRoot;
}
else {
return root;
}
}
public static void main(String args[]){
SingleLinkedList lastNode = new SingleLinkedList("5", null);
SingleLinkedList singleLinkedList = new SingleLinkedList("4", lastNode);
singleLinkedList = new SingleLinkedList("3", singleLinkedList);
singleLinkedList = new SingleLinkedList("2", singleLinkedList);
SingleLinkedList root = new SingleLinkedList("1", singleLinkedList);
ListOperations listOperations = new ListOperations();
//listOperations.printLinkedlist(root);
SingleLinkedList shuffledroot = listOperations.shuffleLinkedList(root);
System.out.println("Shuffled list is ->");
listOperations.printLinkedlist(shuffledroot);
}
}
This problem is same as common ancestor problem.
/*
* Lowest common ancestor of a tree whose two nodes are given
*/
public class LowestCommonAncestor {
private static Tree findLCA(Tree ptr, String n1, String n2){
if(ptr == null){
return null;
}
if (ptr.getValue().equals(n1) || ptr.getValue().equals(n2)){
return ptr;
}
Tree left = findLCA(ptr.getLeft(), n1, n2);
Tree right = findLCA(ptr.getRight(), n1, n2);
if(left !=null && right !=null){
return ptr;
}
else {
if(left == null && right !=null){
return findLCA(ptr.getRight(), n1, n2);
}
else if(right == null && left !=null){
return findLCA(ptr.getLeft(), n1, n2);
}
else {
return null;
}
}
}
public static void main(String args[]){
Tree child11 = new Tree("D", null, null);
Tree child22 = new Tree("E", null, null);
Tree child33 = new Tree("F", null, null);
Tree child44 = new Tree("G", null, null);
Tree child1 = new Tree("B", child11, child22);
Tree child2 = new Tree("C", child33, child44);
Tree root = new Tree("A", child1, child2);
Tree lcaNode = findLCA(root, "D", "F");
System.out.println("LCA(D,F) is ->" + lcaNode!=null?lcaNode.getValue():"No LCA");
}
}
package com.mj.algo.misc;
public class ZeroSumCombination {
void printCombinationZeroSum(int arr[], int n, int r)
{
int [] data= new int[r];
// Print all combination using temprary array 'data[]'
combinationUtilZeroSum(arr, n, r, 0, data, 0);
}
void combinationUtil(int arr[], int n, int r, int index, int data[], int i)
{
if(index == r){
for(int pos = 0; pos<r; pos++){
System.out.print(data[pos] + " ");
}
System.out.println();
return;
}
if(i>=n){
return;
}
data[index]=arr[i];
// current is included, put next at next location
combinationUtil(arr,n, r, index+1, data, i+1);
// current is excluded, replace it with next (Note that
// i+1 is passed, but index is not changed)
combinationUtil(arr,n, r, index, data, i+1);
}
void combinationUtilZeroSum(int arr[], int n, int r, int index, int data[], int i)
{
if(index == r){
if(checkSumtoZero(data)){
System.out.println();
}
return;
}
if(i>=n){
return;
}
data[index]=arr[i];
// current is included, put next at next location
combinationUtil(arr,n, r, index+1, data, i+1);
// current is excluded, replace it with next (Note that
// i+1 is passed, but index is not changed)
combinationUtil(arr,n, r, index, data, i+1);
}
private boolean checkSumtoZero(int[] input){
if(input == null){
return false;
}
int sum = 0;
for(int index = 0; index<input.length; index++){
sum = sum + input[index];
}
if(sum == 0){
return true;
}
return false;
}
private void findSumToZero(int[] input){
for(int index = 0; index<input.length; index++){
printCombinationZeroSum(input, input.length, index);
}
}
public static final void main(String args[]){
ZeroSumCombination zeroSumCombination = new ZeroSumCombination();
int[] input = {2, 3, 1, -2, -1, 0, 2, -3, 0};
zeroSumCombination.findSumToZero(input);
}
}
public class MaxRepeating {
private static final int maxRepeating(int[] input, int k){
int size = input.length;
for(int index =0 ; index<size; index++){
input[input[index]%k] += k;
}
int max = input[0], result = 0;
for (int i = 1; i < size; i++)
{
if (input[i] > max)
{
max = input[i];
result = i;
}
}
return result;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int input[] = {2, 3, 3, 5, 3, 4, 1, 7, 7, 7 };
int result = maxRepeating(input, 8);
System.out.println("Maximun repeating word is -> " + result);
int x = 2%7;
System.out.println(x);
}
}
We can use selection sort. In first iteration, selection sort put smallest element in 1st position, next iteration 2nd smallest element in 2nd position and so on. So to put kth smallest element in its position we need k iteration.
However complexity of this algorithm will be O(k*n)l
I am not sure about the requirement but following programme will solve our purpose:
private void reverseFile(String inputFile, String outputFile){
try {
PrintWriter printWriter = new PrintWriter(outputFile);
FileReader fileReader = new FileReader(new File(inputFile));
BufferedReader bufferedReader = new BufferedReader(fileReader);
String line = null;
while((line = bufferedReader.readLine())!=null){
StringBuffer buffer = new StringBuffer(line);
buffer=buffer.reverse();
String rs=buffer.toString();
printWriter.write(rs);
printWriter.write("\n");
}
bufferedReader.close();
printWriter.flush();
printWriter.close();
} catch (IOException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
public class Tree {
private String value;
private Tree left;
private Tree right;
public Tree(String value, Tree left, Tree right){
this.value = value;
this.left = left;
this.right= right;
}
public String getValue() {
return value;
}
public void setValue(String value) {
this.value = value;
}
public Tree getLeft() {
return left;
}
public void setLeft(Tree left) {
this.left = left;
}
public Tree getRight() {
return right;
}
public void setRight(Tree right) {
this.right = right;
}
}
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import com.mj.algo.tree.modal.Tree;
public class TreeTraversal {
private Map<Integer, String> valuesMap = new HashMap<Integer, String>();
private void printLevelOrder(Tree root, int level){
//print values
if(valuesMap.containsKey(level)){
String value = valuesMap.get(level);
value = value + root.getValue();
valuesMap.put(level, value);
}
else{
String value = root.getValue();
valuesMap.put(level, value);
}
if(root.getLeft()!=null){
printLevelOrder(root.getLeft(), level+1);
}
if(root.getRight()!=null){
printLevelOrder(root.getRight(), level+1);
}
}
private void printValueMap() {
Iterator it = valuesMap.entrySet().iterator();
while (it.hasNext()) {
Map.Entry pairs = (Map.Entry)it.next();
//System.out.println(pairs.getKey() + " = " + pairs.getValue());
System.out.println( pairs.getValue());
it.remove();
}
}
public static void main(String args[]){
Tree child11 = new Tree("D", null, null);
Tree child22 = new Tree("E", null, null);
Tree child33 = new Tree("F", null, null);
Tree child44 = new Tree("G", null, null);
Tree child1 = new Tree("B", child11, child22);
Tree child2 = new Tree("C", child33, child44);
Tree root = new Tree("A", child1, child2);
TreeTraversal treeTraversal = new TreeTraversal();
treeTraversal.printLevelOrder(root,1);
treeTraversal.printValueMap();
}
}
From the name it is clear that suppose we want only one instance of a class in JVM then we will use singleton pattern. One such example:
public class HibernateUtils
{
private HibernateUtils()
{
}
private static SessionFactory seesionFactory = null;
private static final SessionFactory makeSessionFactory()
{
try {
if (sessionFactory==null)
seesionFactory = new Configuration().configure().buildSessionFactory();
} catch (HibernateException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
return seesionFactory;
}
public static SessionFactory getSessionFactory()
{
return makeSessionFactory();
}
}
Agree...rubbish question.
- Mritunjay Kumar August 08, 2014We can use cron scheduler for this. Spring provides a easy way for the integration with cron scheduler.
- Mritunjay Kumar June 09, 2014Here is sample programme to get intersection os two sorted list
private Node getIntersectedLinkedList(Node first, Node second){
Node ptr = first;
Node ptr1 = second;
Node previous = null;
Node firstIntersectedNode = null;
while (ptr != null) {
ptr1=second;
while (ptr1!= null && ptr.getValue() != ptr1.getValue() ) {
ptr1 = ptr1.getNext();
}
if(ptr1 !=null){
Node node = new Node();
if (firstIntersectedNode == null) {
firstIntersectedNode = node;
}
node.setValue(ptr.getValue());
if (previous != null) {
previous.setNext(node);
}
previous = node;
}
ptr = ptr.getNext();
}
return firstIntersectedNode;
}
- Mritunjay Kumar September 15, 2010Nice solution by Neo above.
One other approach. We can use hash set to keep the distinct nodes.
private boolean checkLinkedListForLoop(Node first){
Set nodeSet = new HashSet();
if(first !=null){
Node ptr = first;
while(ptr !=null){
if(nodeSet.contains(ptr)){
return true;
}
else {
nodeSet.add(ptr);
}
ptr= ptr.getNext();
}
}
return false;
}
And Node class is ->
package linkedlist;
public class Node implements Cloneable{
private String value;
private Node next;
public String getValue() {
return value;
}
public void setValue(String value) {
this.value = value;
}
public Node getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
public Object clone(){
try {
Node clonnedNode = (Node)super.clone();
clonnedNode.next= (Node)next.clone();
return clonnedNode;
}
catch(CloneNotSupportedException cnse){
return null;
}
}
}
- Mritunjay Kumar September 15, 2010Solution if i understood question correctly :)
package linkedlist;
public class Node implements Cloneable{ private String value;
private Node next;
public String getValue() {
return value;
}
public void setValue(String value) {
this.value = value;
}
public Node getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
public Object clone(){
try {
Node clonnedNode = (Node)super.clone();
clonnedNode.next= (Node)next.clone();
return clonnedNode;
}
catch(CloneNotSupportedException cnse){
return null;
}
}
}
Since the coefficient of 'Y' is same in both the equations, we can easily get value of X, Y and Z.
- Mritunjay Kumar September 07, 2010Here is sample programme to get the desired result.
package randomTest;
public class LeastDifferenceNumber {
private int[] numberArray = new int[50];
private void sortArray(){
if(numberArray !=null && numberArray.length>0){
for(int i=1;i<numberArray.length; i++){
int pos = i-1;
int temp = numberArray[i];
while(numberArray[pos]>temp){
numberArray[pos+1]= numberArray[pos];
pos--;
}
numberArray[pos+1]=temp;
}
}
}
private int getLeastDifferenceIndex(){
int leastDifferencePos = 1;
int minDiff = -1;
if(numberArray !=null && numberArray.length>0){
for(int i=1;i<numberArray.length; i++){
int diff=numberArray[i]-numberArray[i-1];
if(diff<minDiff){
minDiff = diff;
leastDifferencePos = i;
}
}
}
return leastDifferencePos;
}
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
LeastDifferenceNumber leastDifferenceNumber = new LeastDifferenceNumber();
leastDifferenceNumber.numberArray = new int []{1, 18, 22, 28, 8, 58, 22, 92};
leastDifferenceNumber.sortArray();
int leastDifferencePos = leastDifferenceNumber.getLeastDifferenceIndex();
System.out.println("Least Difference position is ->" + leastDifferenceNumber.numberArray[leastDifferencePos-1] + " and " + leastDifferenceNumber.numberArray[leastDifferencePos]);
}
}
Algorithm:
1) Sort the array.
2) Find the position of the two consecutive digits in array whose difference is lowest.
The solution of this question is given below:
X/72 + Y/64 + Z/56 = 4
Z/72 + Y/64 + X/56 = 14/3
Total distance is X+Y+Z.
Uphill distance while going is same as downhill distance in return and Downhill distance while going is same as uphill distance in return.
Solving this equation, THE TOTAL DISTANCE IS COMING CLOSE TO 273.18km.
Here is sample java programme for level order tree traversal.
package tree;
import java.util.List;
import sun.misc.Queue;
public class NTreeTraversal {
Queue traversalQueue = new Queue();
public void nTreeTraversal(NTreeNode root) throws InterruptedException{
if(root==null){
return;
}
System.out.println("Label Order tree traversal is -> ");
traversalQueue = new Queue();
traversalQueue.enqueue(root);
NTreeNode ptr = (NTreeNode) traversalQueue.dequeue();
while(ptr !=null){
System.out.println(ptr.getValue() + " \n");
addDirectChildInQueue(ptr);
ptr = (NTreeNode) traversalQueue.dequeue();
}
}
private void addDirectChildInQueue(NTreeNode node){
if(node == null){
return;
}
List<NTreeNode> directChildNodes = null;
NTreeNode ptr = node.getChild();
while(ptr !=null){
traversalQueue.enqueue(ptr);
ptr= ptr.getSibling();
}
}
public static void main(String args[]){
NTreeNode treeNode1 = new NTreeNode("1", null, null);
NTreeNode treeNode2 = new NTreeNode("2", null, null);
NTreeNode treeNode3 = new NTreeNode("3", null, null);
NTreeNode treeNode4 = new NTreeNode("4", null, null);
NTreeNode treeNode5 = new NTreeNode("5", null, null);
NTreeNode treeNode6 = new NTreeNode("6", null, null);
NTreeNode treeNode7 = new NTreeNode("7", null, null);
NTreeNode treeNode8 = new NTreeNode("8", null, null);
treeNode1.setChild(treeNode2);
treeNode2.setChild(treeNode5);
treeNode2.setSibling(treeNode3);
treeNode3.setChild(treeNode8);
treeNode3.setSibling(treeNode4);
treeNode5.setSibling(treeNode6);
treeNode6.setSibling(treeNode7);
NTreeTraversal ntreeTraversal = new NTreeTraversal();
try {
ntreeTraversal.nTreeTraversal(treeNode1);
} catch (InterruptedException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
}
- Mritunjay Kumar January 14, 2017