Problem Practice

---

In a given word find the first un-repeated  letter, e.g., in ‘total’ its ‘o’ and in ‘ teeter’ its ‘r’.



import java.util.LinkedHashMap;
import java.util.Map;
import java.util.Map.Entry;

/**
 * @author mohit
 *
 * In a given word find the first un-repeated  letter, e.g., in ‘total’ its ‘o’ and in ‘ teeter’ its ‘r’.
 *
 */
public class FirstUnrepeatedLetter {


	public static void main(String[] args) {

		firstUnrepeatedLetter("total");

		firstUnrepeatedLetter("teeter");

	}


	public static void firstUnrepeatedLetter (String s1) {

		String input = s1;

		Map charOccouranceMap = new LinkedHashMap<>();

		for(Character c : input.toCharArray()) {

			if(charOccouranceMap.containsKey(c)) {
				charOccouranceMap.put(c, true);
			}else {
				charOccouranceMap.put(c, false);
			}

		}

		for (Entry entry : charOccouranceMap.entrySet()) {
			if(entry.getValue()) {
				continue;
			} else {
				System.out.println(entry.getKey());
				break;
			}
		}

	}

}




Reverse the LinkedList


public class ReverseLinkedList {


    private static class SinglyLinkedList {

        Node head;



        // prints content of double linked list
        void printList(Node node) {
            while (node != null) {
                System.out.print(node.data + " ");
                node = node.next;
            }
        }



        Node reverseV2( Node node, Node previous) {

//	    	System.out.println(node.data + "->" + (previous == null ? "null" : previous.data) );

            if ( node.next != null) {

                Node next1 = node.next;

                node.next = previous;

                return reverseV2(next1, node);

            } else {

                node.next = previous;
                return node;

            }


        }

    }


    private static class Node {

        int data;
        Node next;
        Node(int d) {
            data = d;
        }

    }


    public static void main(String[] args) {


        SinglyLinkedList list = new SinglyLinkedList();
        list.head = new Node(1);
        list.head.next = new Node(2);
        list.head.next.next = new Node(3);
        list.head.next.next.next = new Node(4);

        System.out.println("Original Linked list is :");
        list.printList(list.head);
        System.out.println("");
        list.head = list.reverseV2(list.head, null);
        System.out.println("");
        System.out.println("Reversed linked list : ");
        list.printList(list.head);
    }

}

debug points

linklist null->1->2->3->4

reverse(1,null)
next1 2,
1->null
reverse(2, 1)
next1 3,
2->1->null
reverse(3, 2)
next1 4,
3->2->1->null
reverse(4, 3)
4->3->2->1->null
return 4




Shortest Path in Matrix Problem Java solution  


import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class ShortestPathMatrix {

	Set elements = new HashSet<>();

	Map locationMap = new HashMap<>();

	public void createMatrix () {

	  /*	1	2	3
		4	5	6
		7	8	9
		10	11	13	*/


		String matrix = "(0,0)1 \n " +
				"(0,1)2 \n " +
				"(0,2)3 \n " +
				"(1,0)4 \n " +
				"(1,1)5 \n " +
				"(1,2)6 \n " +
				"(2,0)7 \n " +
				"(2,1)8 \n " +
				"(2,2)9 \n " +
				"(3,0)10 \n " +
				"(3,1)11 \n " +
				"(3,2)12 \n " +
				"(4,0)13 \n " +
				"(4,1)14 \n " +
				"(4,2)15 \n " ;

		int id = 0;
		for (String element : matrix.split("\\n")) {

			if(element.trim().length() > 0) {

				MatrixElement matrixElement = new MatrixElement();
				matrixElement.setId(id);
				matrixElement.setValue(element.split("\\)")[1]);
				matrixElement.setCordX(Integer.parseInt(element.split(",")[0].replace("(", "").trim()));
				matrixElement.setCordY(Integer.parseInt(element.split(",")[1].split("\\)")[0]));
				elements.add(matrixElement);
				locationMap.put(matrixElement.getCordX()+","+matrixElement.getCordY(), matrixElement);
				id++;

			}



		}

	}


	public static void main(String[] args) {

		ShortestPathMatrix matrix = new ShortestPathMatrix();

		matrix.createMatrix();

		matrix.findDistanceBetweenPoint("4,1", "0,0");



	}


	private void findDistanceBetweenPoint(String string, String string2) {

		MatrixElement a = locationMap.get(string);
		MatrixElement b = locationMap.get(string2);

		int x, y;

		x = a.getCordX();
		y = a.getCordY();


		locateTheItem(x, y, b);

	}

	private void locateTheItem(int x, int y, MatrixElement b) {

		System.out.println(x + " , " + y);

		int nextX = x;
		int nextY = y;

		boolean locateAgain = false;

		if(b.getCordX() > x) {
			nextX = x + 1;
			locateAgain = true;
		}

		if (b.getCordY() > y ) {
			nextY = y + 1;
			locateAgain = true;
		}

		if(b.getCordX() < x) {
			nextX = x - 1;
			locateAgain = true;
		}

		if (b.getCordY() < y ) {
			nextY = y - 1;
			locateAgain = true;
		}


		if(locateAgain) {
			locateTheItem(nextX, nextY, b);
		} else {

			System.out.println("traced !");

		}


	}

	public class MatrixElement {

		private int id;
		private String value;

		private MatrixElement left;
		private MatrixElement right;
		private MatrixElement top;
		private MatrixElement bottom;

		private int cordX;
		private int cordY;


		public MatrixElement getLeft() {
			return left;
		}
		public void setLeft(MatrixElement left) {
			this.left = left;
		}
		public MatrixElement getRight() {
			return right;
		}
		public void setRight(MatrixElement right) {
			this.right = right;
		}
		public MatrixElement getTop() {
			return top;
		}
		public void setTop(MatrixElement top) {
			this.top = top;
		}
		public MatrixElement getBottom() {
			return bottom;
		}
		public void setBottom(MatrixElement bottom) {
			this.bottom = bottom;
		}
		public int getId() {
			return id;
		}
		public void setId(int id) {
			this.id = id;
		}
		public String getValue() {
			return value;
		}
		public void setValue(String value) {
			this.value = value;
		}
		public int getCordX() {
			return cordX;
		}
		public void setCordX(int cordX) {
			this.cordX = cordX;
		}
		public int getCordY() {
			return cordY;
		}
		public void setCordY(int cordY) {
			this.cordY = cordY;
		}



	}


}






Union Of Two Sorted Array problem or Merge two sorted arrays 



import java.util.Arrays;

public class UnionOfTwoSortedArray {

	public static void main(String[] args) {

		int [] arr1 = {1,3,4,5,7};
		int [] arr2 = {2,3,5,6};

		int i = arr1.length;
		int j = arr2.length;

		int [] unionArray = new int [i + j];

		int x = 0;
		int y = 0;

		int g = 0;

		while (x < i && y < j) {


			if (arr1[x] < arr2[y]) {

				unionArray[g] = arr1[x];
				g++;
				x++;


			} else if (arr1[x] > arr2[y]) {

				unionArray[g] = arr2[y];
				g++;
				y++;


			} else if (arr1[x] == arr2[y]) {

				unionArray[g] = arr1[x];
				x++;
				y++;
				g++;
			}

		}

		while(x < i)
		unionArray[g++] = arr1[x++];
		while(y < j)
		unionArray[g++] = arr1[y++];


		System.out.println(Arrays.toString(unionArray));

	}

}





Untraceable ransom note

A kidnapper wrote a ransom note but is worried it will be traced back to him. He found a magazine and wants to know if he can cut out whole words from it and use them to create an untraceable replica of his ransom note. The words in his note are case-sensitive and he must use whole words available in the magazine, meaning he cannot use substrings or concatenation to create the words he needs.
Given the words in the magazine and the words in the ransom note, print Yes if he can replicate his ransom note exactly using whole words from the magazine; otherwise, print No.

from collections import Counter

def ransom_note(magazine, ransom):
  return not (Counter(rasom) - Counter(magazine))

m, n = map(int, input().strip().split(' '))
magazine = input().strip().split(' ')
ransom = input().strip().split(' ')
answer = ransom_note(magazine, ransom)
if(answer):
    print("Yes")
else:
    print("No")

-----

Sample Input 0

6 4
give me one grand today night
give one grand today

Sample Output 0

Yes

-----

Sample Input 1

6 5
two times three is not four
two times two is four

Sample Output 1

No

-----





Program to print column names of excel eg. a, b ... ab, ac ... az, ba ... azz, caa


def incrementString(str1):
    arr = list(str1)
    arr.reverse()

    if ord(arr[0]) - ord('a') + 1 == 26:
        arr[0] = 'a'
        if str1[:-1] is not '':
            str1 = incrementString(str1[:-1])
        else:
            str1 = 'a'
            str1 = str1 + ''.join(arr[0])
    else:
        arr[0] = chr(ord(arr[0]) + 1)
        str1 = str1[:-1] + ''.join(arr[0])

    return str1


while True:
    val = incrementString(val)
    print(val)




Find Nth Max or Largest element of unsorted array 

	arr = [7,2,1,3,10,4,5,8,9,6]
	nthMax = 2 #specify max element here
	maxArr = arr

	for i in range (0, len(maxArr)):
	    for j in range (i, len(maxArr)):
		if (maxArr[i] < maxArr[j]):
		    maxArr[i],maxArr[j] = maxArr[j],maxArr[i]
		    if i == nthMax:
			break

	print(maxArr)
	print(maxArr[nthMax-1])


-- java solution with Heap

package com.company;

import java.util.PriorityQueue;



class JavaTest {

    public static int findKthLargest(int[] nums, int k) {
        PriorityQueue q = new PriorityQueue(k);
        for(int i: nums){

            q.offer(i);

            if(q.size()>k){
                q.poll();
            }

        }

        return (int)q.peek();
    }

    public static void main (String[] args) throws java.lang.Exception
    {

        int[] arr = new int[]{7, 2, 1, 3, 10, 4, 5, 8, 9, 6};
        int k = 2;

        System.out.println(findKthLargest(arr, k));

    }
}





 Recursively remove all adjacent duplicates 

problem url http://www.geeksforgeeks.org/recursively-remove-adjacent-duplicates-given-string/


Input:  azxxzy
Output: ay
First "azxxzy" is reduced to "azzy".
The string "azzy" contains duplicates,
so it is further reduced to "ay".

Input: geeksforgeeg
Output: gksfor
First "geeksforgeeg" is reduced to
"gksforgg". The string "gksforgg"
contains duplicates, so it is further
reduced to "gksfor".

Input: caaabbbaacdddd
Output: Empty String

Input: acaaabbbacdddd
Output: acac



def removeAdjoints(ipx, start, end):
    if(len(ipx) == 0):
        print("blank")
    else:
        print(ipx)

    if len(ipx) > 0 and end < len(ipx):
        if ipx[start] == ipx[end]:
            if end + 1 < len(ipx):
                removeAdjoints(ipx, start, end + 1)
            elif start < end:
                ipx = ipx[0:start]
                if len(ipx) > 0:
                    removeAdjoints(ipx, 0, 1)
        elif start + 1 < end:
            ipx = ipx[0:start] + ipx[end:len(ipx)]
            removeAdjoints(ipx, 0, 1)
        else:
            if end + 1 < len(ipx):
                removeAdjoints(ipx, start + 1, end + 1)


removeAdjoints("azxxzy", 0, 1)
print("----")
removeAdjoints("geeksforgeeg", 0, 1)
print("----")
removeAdjoints("gksforgg", 0, 1)
print("----")
removeAdjoints("caaabbbaacdddd", 0, 1)
print("----")
removeAdjoints("dddd", 0, 1)
print("----")






Level Order Tree Traversal or breadth first traversal for the tree.


''

input tree

                                1
                2                               3
        4                 5             6               7
      8  9              10 11        12  13          14   15

'''


class Node:
    pass


root = Node()
root.data = 1
root.left = Node()
root.right = Node()

root.left.data = 2
root.left.left = Node()
root.left.right = Node()

root.right.data = 3
root.right.left = Node()
root.right.right = Node()

node2 = root.left
node2.left.data = 4
node2.right.data = 5

node3 = root.right
node3.left.data = 6
node3.right.data = 7

node4 = node2.left
node4.left = Node()
node4.left.data = 8
node4.right = Node()
node4.right.data = 9


node5 = node2.right
node5.left = Node()
node5.left.data = 10
node5.right = Node()
node5.right.data = 11

node6 = node3.left
node6.left = Node()
node6.left.data = 10

# node7 = node3.right
# node7.right = Node()
# node7.right.data = 11


queue = []

def printTree(rootNode, queue):

    if rootNode.data is not None:
        print(rootNode.data)

    t = None
    while len(queue) > 0:
        t = queue[len(queue)-1]
        queue.pop()
        print(t.data)
    if t is not None and hasattr(t, "right"):
        queue.append(t.right)
    if t is not None and hasattr(t, "left"):
        queue.append(t.left)

    if hasattr(rootNode, "right"):
        queue.append(rootNode.right)
    if rootNode is not None and hasattr(rootNode, "left"):
        printTree(rootNode.left, queue)



printTree(root, queue)

# print(root.data)

more about problem at http://www.geeksforgeeks.org/level-order-tree-traversal/




Find height of tree



'''

input tree

                                1
                2                               3
        4                 5             6               7
      8  9              10 11        12  13          14   15

'''


class Node:
    pass


root = Node()
root.data = 1
root.left = Node()
root.right = Node()

root.left.data = 2
root.left.left = Node()
root.left.right = Node()

root.right.data = 3
root.right.left = Node()
root.right.right = Node()

node2 = root.left
node2.left.data = 4
node2.right.data = 5

node3 = root.right
node3.left.data = 6
node3.right.data = 7

node4 = node2.left
node4.left = Node()
node4.left.data = 8
node4.right = Node()
node4.right.data = 9


node5 = node2.right
node5.left = Node()
node5.left.data = 10
node5.right = Node()
node5.right.data = 11

node6 = node3.left
node6.left = Node()
node6.left.data = 10

node10 = node5.left
node10.left = Node()
node10.left.data = 16


# node7 = node3.right
# node7.right = Node()
# node7.right.data = 11


maxLength = 0

def findHightOfTree(head, length):
    if head is None:
        print(length)
        return length
    maxHeight = 0
    if hasattr(head, "left"):
        lhight = findHightOfTree(head.left, length)
        maxHeight = lhight + 1
    if hasattr(head, "right"):
        rhight = findHightOfTree(head.right, length)
        if maxHeight - 1 < rhight:
            maxHeight = rhight+1

    print(maxHeight)
    return maxHeight;

print(findHightOfTree(root, 0))






Producer Consumer Problem


// Java program to implement solution of producer
// consumer problem.
import java.util.LinkedList;

public class Threadexample
{
    public static void main(String[] args)
                        throws InterruptedException
    {
        // Object of a class that has both produce()
        // and consume() methods
        final PC pc = new PC();

        // Create producer thread
        Thread t1 = new Thread(new Runnable()
        {
            @Override
            public void run()
            {
                try
                {
                    pc.produce();
                }
                catch(InterruptedException e)
                {
                    e.printStackTrace();
                }
            }
        });

        // Create consumer thread
        Thread t2 = new Thread(new Runnable()
        {
            @Override
            public void run()
            {
                try
                {
                    pc.consume();
                }
                catch(InterruptedException e)
                {
                    e.printStackTrace();
                }
            }
        });

        // Start both threads
        t1.start();
        t2.start();

        // t1 finishes before t2
        t1.join();
        t2.join();
    }

    // This class has a list, producer (adds items to list
    // and consumber (removes items).
    public static class PC
    {
        // Create a list shared by producer and consumer
        // Size of list is 2.
        LinkedList list = new LinkedList<>();
        int capacity = 2;

        // Function called by producer thread
        public void produce() throws InterruptedException
        {
            int value = 0;
            while (true)
            {
                synchronized (this)
                {
                    // producer thread waits while list
                    // is full
                    while (list.size()==capacity)
                        wait();

                    System.out.println("Producer produced-"
                                                  + value);

                    // to insert the jobs in the list
                    list.add(value++);

                    // notifies the consumer thread that
                    // now it can start consuming
                    notify();

                    // makes the working of program easier
                    // to  understand
                    Thread.sleep(1000);
                }
            }
        }

        // Function called by consumer thread
        public void consume() throws InterruptedException
        {
            while (true)
            {
                synchronized (this)
                {
                    // consumer thread waits while list
                    // is empty
                    while (list.size()==0)
                        wait();

                    //to retrive the ifrst job in the list
                    int val = list.removeFirst();

                    System.out.println("Consumer consumed-"
                                                    + val);

                    // Wake up producer thread
                    notify();

                    // and sleep
                    Thread.sleep(1000);
                }
            }
        }
    }
}


more at http://www.geeksforgeeks.org/producer-consumer-solution-using-threads-java/


Approach 2

import java.util.LinkedList;
import java.util.Queue;
import java.util.Random;

/**
 * Simple Java program to demonstrate How to use wait, notify and notifyAll()
 * method in Java by solving producer consumer problem.
 *
 * @author Javin Paul
 */
public class ProducerConsumerInJava {

    public static void main(String args[]) {
        System.out.println("How to use wait and notify method in Java");
        System.out.println("Solving Producer Consumper Problem");

        Queue buffer = new LinkedList<>();
        int maxSize = 10;

        Thread producer = new Producer(buffer, maxSize, "PRODUCER");
        Thread consumer = new Consumer(buffer, maxSize, "CONSUMER");

        producer.start();
        consumer.start();


    }

}

/**
 * Producer Thread will keep producing values for Consumer
 * to consumer. It will use wait() method when Queue is full
 * and use notify() method to send notification to Consumer
 * Thread.
 *
 *
 */
class Producer extends Thread {
    private Queue queue;
    private int maxSize;

    public Producer(Queue queue, int maxSize, String name){
        super(name);
        this.queue = queue;
        this.maxSize = maxSize;
    }

    @Override
    public void run() {
        while (true) {
            synchronized (queue) {
                while (queue.size() == maxSize) {
                    try {
                        System.out .println("Queue is full, "
                                + "Producer thread waiting for "
                                + "consumer to take something from queue");
                        queue.wait();
                    } catch (Exception ex) {
                        ex.printStackTrace();
                    }
                }

                Random random = new Random();
                int i = random.nextInt();
                System.out.println("Producing value : " + i);
                queue.add(i);
                queue.notifyAll();
            }

        }
    }
}

/**
 * Consumer Thread will consumer values form shared queue.
 * It will also use wait() method to wait if queue is
 * empty. It will also use notify method to send
 * notification to producer thread after consuming values
 * from queue.
 *
 *
 */
class Consumer extends Thread {
    private Queue queue;
    private int maxSize;

    public Consumer(Queue queue, int maxSize, String name){
        super(name);
        this.queue = queue;
        this.maxSize = maxSize;
    }

    @Override
    public void run() {
        while (true) {
            synchronized (queue) {
                while (queue.isEmpty()) {
                    System.out.println("Queue is empty,"
                            + "Consumer thread is waiting"
                            + " for producer thread to put something in queue");
                    try {
                        queue.wait();
                    } catch (Exception ex) {
                        ex.printStackTrace();
                    }

                }
                System.out.println("Consuming value : " + queue.remove());
                queue.notifyAll();
            }

        }
    }
}

Output
How to use wait and notify method in Java
Solving Producer Consumper Problem
Queue is empty,Consumer thread is waiting for producer thread to put something in queue
Producing value : -1692411980
Producing value : 285310787
Producing value : -1045894970
Producing value : 2140997307
Producing value : 1379699468
Producing value : 912077154
Producing value : -1635438928
Producing value : -500696499
Producing value : -1985700664
Producing value : 961945684
Queue is full, Producer thread waiting for consumer to take something from queue
Consuming value : -1692411980
Consuming value : 285310787
Consuming value : -1045894970
Consuming value : 2140997307
Consuming value : 1379699468
Consuming value : 912077154
Consuming value : -1635438928
Consuming value : -500696499
Consuming value : -1985700664
Consuming value : 961945684
Queue is empty,Consumer thread is waiting for producer thread to put something in queue
Producing value : 1182138498


more details at http://javarevisited.blogspot.in/2015/07/how-to-use-wait-notify-and-notifyall-in.html#axzz4hJulc43E

http://javarevisited.blogspot.in/2011/05/wait-notify-and-notifyall-in-java.html#axzz4hJulc43E




Print a Binary Tree in Vertical Order





# method have used hashmap

class Node:
    pass


root = Node()
root.data = 1
root.left = Node()
root.right = Node()

root.left.data = 2
root.left.left = Node()
root.left.right = Node()

root.right.data = 3
root.right.left = Node()
root.right.right = Node()

node2 = root.left
node2.left.data = 4
node2.right.data = 5

node3 = root.right
node3.left.data = 6
node3.right.data = 7

node6 = node3.left
node6.right = Node()
node6.right.data = 8


node7 = node3.right
node7.right = Node()
node7.right.data = 9




def getVerticalOrder(node, hd, m):

    if node is None:
        return
    else:
        try:
            m[hd].append(node.data)
        except:
            m[hd] = [node.data]

    if hasattr(node, "right"):
        getVerticalOrder(node.right, hd+1, m)
    if hasattr(node, "left"):
        getVerticalOrder(node.left, hd-1, m)

dictM = dict()
getVerticalOrder(root, 0 , dictM)


print(sorted(dictM))

for index, value in enumerate(sorted(dictM)):
    for data in dictM[value]:
        print(data, end="")
    print()


more details at http://www.geeksforgeeks.org/print-binary-tree-vertical-order/

http://www.geeksforgeeks.org/print-binary-tree-vertical-order-set-2/



How HashMap / HashTable works





Data Structures: Heaps





Data Structures: Trees





Data Structures: Tries 







Find The Cost (Nested Approch)

Let's say the building has 'n' floors, each fllor has meeting rooms & work-stations, each room has several objects (table, chairs, tv..).
Find the cost of perticular room, complete floor or a building.

Meeting Room 1:

Item
Cost

TV
90000

Chairs
150000

Table
200000

Total:
440000



Floor 1:

Meeting Room1          440000

Meeting Room2          650000

Total: 1090000


class Object:
    name = None
    value = None
    containsObject = None
    pass

def getCostOfMultipleObjects(manyObjectOfBuilding):
    totalCost = 0
    for obj in manyObjectOfBuilding:
        totalCost += getCost(obj)
    return totalCost

def getCost(anyObjectOfBuilding):
    if anyObjectOfBuilding.containsObject is not None and len(anyObjectOfBuilding.containsObject) > 0:
        return anyObjectOfBuilding.value + getCostOfMultipleObjects(anyObjectOfBuilding.containsObject)
    else:
        return anyObjectOfBuilding.value

table1 = Object()
table1.name = 'table_1'
table1.value = 5

lamp1 = Object()
lamp1.name = 'lamp_1'
lamp1.value = 1

tv1 = Object()
tv1.name = 'tv_1'
tv1.value = 3

meetingRoom1 = Object()
meetingRoom1.name = 'meetingRoom_1'
meetingRoom1.value = 10
meetingRoom1.containsObject = [lamp1, table1]

meetingRoom2 = Object()
meetingRoom2.name = 'meetingRoom_2'
meetingRoom2.value = 20
meetingRoom2.containsObject = [lamp1, table1, tv1]

floor1 = Object()
floor1.name = 'floor_1'
floor1.value = 20
floor1.containsObject = [meetingRoom1, meetingRoom2]

builing1 = Object()
builing1.name = 'building_1'
builing1.value = 100
builing1.containsObject = [floor1]

print('t1', getCost(table1))
print('m1', getCost(meetingRoom1))
print('m2', getCost(meetingRoom2))
print('f1', getCost(floor1))
print('b1', getCost(builing1))




A program to check if a binary tree is BST or not

http://www.geeksforgeeks.org/a-program-to-check-if-a-binary-tree-is-bst-or-not/



Tree Traversals (Inorder, Preorder and Postorder)

http://www.geeksforgeeks.org/tree-traversals-inorder-preorder-and-postorder/



Search in a row wise and column wise sorted matrix

www.geeksforgeeks.org/search-in-row-wise-and-column-wise-sorted-matrix/



LRU Cache (Java)

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set.

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
set(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

Analysis

The key to solve this problem is using a double linked list which enables us to quickly move nodes.



The LRU cache is a hash table of keys and double linked nodes. The hash table makes the time of get() to be O(1). The list of double linked nodes make the nodes adding/removal operations O(1).

Java Solution

Define a double linked list node.

class Node{
    int key;
    int value;
    Node pre;
    Node next;

    public Node(int key, int value){
        this.key = key;
        this.value = value;
    }
}

public class LRUCache {
    int capacity;
    HashMap map = new HashMap();
    Node head=null;
    Node end=null;

    public LRUCache(int capacity) {
        this.capacity = capacity;
    }

    public int get(int key) {
        if(map.containsKey(key)){
            Node n = map.get(key);
            remove(n);
            setHead(n);
            return n.value;
        }

        return -1;
    }

    public void remove(Node n){
        if(n.pre!=null){
            n.pre.next = n.next;
        }else{
            head = n.next;
        }

        if(n.next!=null){
            n.next.pre = n.pre;
        }else{
            end = n.pre;
        }

    }

    public void setHead(Node n){
        n.next = head;
        n.pre = null;

        if(head!=null)
            head.pre = n;

        head = n;

        if(end ==null)
            end = head;
    }

    public void set(int key, int value) {
        if(map.containsKey(key)){
            Node old = map.get(key);
            old.value = value;
            remove(old);
            setHead(old);
        }else{
            Node created = new Node(key, value);
            if(map.size()>=capacity){
                map.remove(end.key);
                remove(end);
                setHead(created);

            }else{
                setHead(created);
            }

            map.put(key, created);
        }
    }
}

-- linked hash map implementation

import java.util.LinkedHashMap;
import java.util.Map;

public class LRUCacheImpl extends LinkedHashMap {
   private static final long serialVersionUID = 1L;
   private int capacity;

   public LRUCacheImpl(int capacity, float loadFactor){
      super(capacity, loadFactor, true);
      this.capacity = capacity;
   }

   /**
    * removeEldestEntry() should be overridden by the user, otherwise it will not
    * remove the oldest object from the Map.
    */
   @Override
   protected boolean removeEldestEntry(Map.Entry eldest){
      return size() > this.capacity;
   }

   public static void main(String arg[]){
      LRUCacheImpl lruCache = new LRUCacheImpl(4, 0.75f);

      lruCache.put(1, "Object1");
      lruCache.put(2, "Object2");
      lruCache.put(3, "Object3");
      lruCache.get(1);
      lruCache.put(4, "Object4");
      System.out.println(lruCache);
      lruCache.put(5, "Object5");
      lruCache.get(3);
      lruCache.put(6, "Object6");
      System.out.println(lruCache);
      lruCache.get(4);
      lruCache.put(7, "Object7");
      lruCache.put(8, "Object8");
      System.out.println(lruCache);
   }
}

-- output

{2=Object2, 3=Object3, 1=Object1, 4=Object4}
{4=Object4, 5=Object5, 3=Object3, 6=Object6}
{6=Object6, 4=Object4, 7=Object7, 8=Object8}




Remove Nth Node From End of List (Java)

Given a linked list, remove the nth node from the end of list and return its head.

For example, given linked list 1->2->3->4->5 and n = 2, the result is 1->2->3->5.

Java Solution 1 - Naive Two Passes

Calculate the length first, and then remove the nth from the beginning.

public ListNode removeNthFromEnd(ListNode head, int n) {
    if(head == null)
        return null;

    //get length of list
    ListNode p = head;
    int len = 0;
    while(p != null){
        len++;
        p = p.next;
    }

    //if remove first node
    int fromStart = len-n+1;
    if(fromStart==1)
        return head.next;

    //remove non-first node
    p = head;
    int i=0;
    while(p!=null){
        i++;
        if(i==fromStart-1){
            p.next = p.next.next;
        }
        p=p.next;
    }

    return head;
}


Java Solution 2 - One Pass

Use fast and slow pointers. The fast pointer is n steps ahead of the slow pointer. When the fast reaches the end, the slow pointer points at the previous element of the target element.

public ListNode removeNthFromEnd(ListNode head, int n) {
    if(head == null)
        return null;

    ListNode fast = head;
    ListNode slow = head;

    for(int i=0; i


Linked List Cycle Detect

Given a linked list, determine if it has a cycle in it.

Analysis

If we have 2 pointers - fast and slow. It is guaranteed that the fast one will meet the slow one if there exists a circle.

The problem can be demonstrated in the following diagram:



Java Solution

public class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;

        while(fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;

            if(slow == fast)
                return true;
        }

        return false;
    }
}




Money Transfer Operation Program

Write java program to perform a money transfer operation  for a bank, which is multi-threaded and can run parallel with multi-processor machines

Solution can be developed with cachedthreadpool and executorservices.

FixedThreadPool vs CachedThreadPool: the lesser of two evils



A CachedThreadPool is exactly what you should use for your situation as there are no negative consequence to using one for long running threads. The comment in the java doc about CachedThreadPools being suitable for short tasks merely suggest that they are particularly appropriate for such cases, not that they cannot or should not be used for tasks involving long running tasks.

To elaborate further, Executors.newCachedThreadPool and Executors.newFixedThreadPool are both backed by the same thread pool implementation (at least in the open JDK) just with different parameters. The differences just being their thread minimum, maximum, thread kill time, and queue type.

public static ExecutorService newFixedThreadPool(int nThreads) {
     return new ThreadPoolExecutor(nThreads, nThreads,
                                   0L, TimeUnit.MILLISECONDS,
                                   new LinkedBlockingQueue());
 }

public static ExecutorService newCachedThreadPool() {
    return new ThreadPoolExecutor(0, Integer.MAX_VALUE,
                                 60L, TimeUnit.SECONDS,
                                 new SynchronousQueue());
}

A FixedThreadPool does have its advantages when you do in fact want to work with a fixed number of threads, since then you can submit any number of tasks to the executor service while knowing that the number of threads will be maintained at the level you specified. If you explicitly want to grow the number of threads, then this is not the appropriate choice.

This does however mean that the one issue that you may have with the CachedThreadPool is in regards to limiting the number of threads that are running concurrently. The CachedThreadPool will not limit them for you, so you may need to write your own code to ensure that you do not run too many threads. This really depends on the design of your application and how tasks are submitted to the executor service.





Subset Sum Problem

Given a set of non-negative integers, and a value sum, determine if there is a subset of the given set with sum equal to given sum.

Examples: set[] = {3, 34, 4, 12, 5, 2}, sum = 9
Output:  True  //There is a subset (4, 5) with sum 9.


# A recursive solution for subset sum
# problem

# Returns true if there is a subset
# of set[] with sun equal to given sum
def isSubsetSum(set,n, sum) :

    # Base Cases
    if (sum == 0) :
        return True
    if (n == 0 and sum != 0) :
        return False

    # If last element is greater than
    # sum, then ignore it
    if (set[n - 1] > sum) :
        return isSubsetSum(set, n - 1, sum);

    # else, check if sum can be obtained
    # by any of the following
    # (a) including the last element
    # (b) excluding the last element
    return isSubsetSum(set, n-1, sum) or isSubsetSum(set, n-1, sum-set[n-1])


# Driver program to test above function
set = [3, 34, 4, 12, 5, 2]
sum = 9
n = len(set)
if (isSubsetSum(set, n, sum) == True) :
    print("Found a subset with given sum")
else :
    print("No subset with given sum")


-----

similar another problem

Given an array, find there are 3 numbers have when we add them the value will equals a specified sum Example: {1,4,6,10,20,21} Sum=32, Result:true (1+10+21) Sum=65, Result:false

'''
solution pending
'''

arr = [1,4,6,10,20,21]
sum = 32

isSumMatching(arr, sum, 0,0,0)

more at https://www.geeksforgeeks.org/dynamic-programming-subset-sum-problem/

added on 11-Feb-2018




API to handel navigation of web browser

Design an API to handle the navigation history of a web browser (previous page, next page, list the 10 previous pages), and that can be reusable in many parts of the application (here I give concrete examples in our app). Then, sketch up an implementation.

I like this one, because it's simple enough, it's easy to illustrate, it can be solved step by step (add additional behaviors without breaking everything), it allows to talk about edge cases and error handling, and it also allows to talk about data structures.

provide Concrete example

(For a java desktop developper)

-- solution pending

added on 18-Feb-2018




Sort a file with huge volume of data given memory constraint

Points:

    We process thousands of flat files in a day, concurrently.
    Memory constraint is a major issue.
    We use thread for each file process.
    We don't sort by columns. Each line (record) in the file is treated as one column.

Can't Do:

    We cannot use unix/linux's sort commands.
    We cannot use any database system no matter how light they can be.

Now, we cannot just load everything in a collection and use the sort mechanism. It will eat up all the memory and the program is gonna get a heap error.

In that situation, how would you sort the records/lines in a file?


One example of external sorting is the external merge sort algorithm, which is a K-way merge algorithm. It sorts chunks that each fit in RAM, then merges the sorted chunks together.[1][2]

The algorithm first sorts M items at a time and puts the sorted lists back into external memory. It then recursively does a M B {\displaystyle {\tfrac {M}{B}}} {\displaystyle {\tfrac {M}{B}}}-way merge on those sorted lists. To do this merge, B elements from each sorted list are loaded into internal memory, and the minimum is repeatedly outputted.

For example, for sorting 900 megabytes of data using only 100 megabytes of RAM:

1. Read 100 MB of the data in main memory and sort by some conventional method, like quicksort.

2. Write the sorted data to disk.

3. Repeat steps 1 and 2 until all of the data is in sorted 100 MB chunks (there are 900MB / 100MB = 9 chunks), which now need to be merged into one single output file.

4. Read the first 10 MB (= 100MB / (9 chunks + 1)) of each sorted chunk into input buffers in main memory and allocate the remaining 10 MB for an output buffer. (In practice, it might provide better performance to make the output buffer larger and the input buffers slightly smaller.)

5. Perform a 9-way merge and store the result in the output buffer. Whenever the output buffer fills, write it to the final sorted file and empty it. Whenever any of the 9 input buffers empties, fill it with the next 10 MB of its associated 100 MB sorted chunk until no more data from the chunk is available. This is the key step that makes external merge sort work externally -- because the merge algorithm only makes one pass sequentially through each of the chunks, each chunk does not have to be loaded completely; rather, sequential parts of the chunk can be loaded as needed.

Historically, instead of a sort, sometimes a replacement-selection algorithm was used to perform the initial distribution, to produce on average half as many output chunks of double the length.


2-way merge

A 2-way merge, or a binary merge, has been studied extensively due to its key role in merge sort. An example of such is the classic merge that appears frequently in merge sort examples. The classic merge outputs the data item with the lowest key at each step; given some sorted lists, it produces a sorted list containing all the elements in any of the input lists, and it does so in time proportional to the sum of the lengths of the input lists.


k-way merge

The k-way merge problem consists of merging k sorted arrays to produce a single sorted array with the same elements. Denote by n the total number of elements. n is equal to the size of the output array and the sum of the sizes of the k input arrays. For simplicity, we assume that none of the input arrays is empty. As a consequence k < n, which simplifies the reported running times. The problem can be solved in O(n log k) running time with O(n) space. Several algorithms that achieve this running time exist.

added on 20-Feb-2018