[LeetCode #5] LRU Cache

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.

public class LRUCache {
	class Node {
		int key;
		int value;
		Node prev;
		Node next;
	}
	
	private int lruCapacity;
	private Map<Integer, Node> lruCache;
	private Node head;
	private Node tail;

	public LRUCache(int capacity) {
		this.lruCapacity = capacity;
		this.lruCache = new HashMap<Integer, Node>();
	}

	public int get(int key) {
		// Existing key
		if (this.lruCache.containsKey(key)) {
			// Move to first place
			Node node = this.lruCache.get(key);
			this.moveFirst(node);
			// Return the value
			return node.value;
		}
		// Not found
		return -1;
	}

	private void add(Node node) {
		// Reset position
		node.next = null;
		node.prev = null;
		// First element
		if (null == this.head) {
			this.head = node;
			this.tail = node;
			return;
		}
		// Existing element
		this.head.prev = node;
		node.next = this.head;
		this.head = node;
	}

	private void remove(Node node) {
		// Nothing to do
		if (this.head == null || null == node) {
			return;
		}
		// The only one item
		if (this.head == this.tail && this.head == node) {
			this.head = null;
			this.tail = null;
			return;
		}
		// Remove from head
		if (node == this.head) {
			this.head.next.prev = null;
			this.head = this.head.next;
			return;
		}
		// Remove from end
		if (node == this.tail) {
			this.tail.prev.next = null;
			this.tail = this.tail.prev;
			return;
		}
		// Remove in the middle
		node.prev.next = node.next;
		node.next.prev = node.prev;

	}

	private void removeLast() {
		this.remove(this.tail);
	}

	private void moveFirst(Node node) {
		this.remove(node);
		this.add(node);
	}

	public void set(int key, int value) {
		if (this.lruCache.containsKey(key)) {
			Node node = this.lruCache.get(key);
			this.moveFirst(node);
			node.value = value;
			return;
		}
		// Out of capacity, cleaning the oldest slot
		if (this.lruCache.size() >= this.lruCapacity) {
			int id = this.tail.key;
			this.removeLast();
			this.lruCache.remove(id);
		}

		// New slot
		Node node = new Node();
		node.key = key;
		node.value = value;
		this.add(node);
		this.lruCache.put(key, node);
	}
}

Google Code Jam Practice Problem – File Fix-it

Problem

On Unix computers, data is stored in directories. There is one root directory, and this might have several directories contained inside of it, each with different names. These directories might have even more directories contained inside of them, and so on.

package avdongre.google.code.jam;

import java.util.HashSet;
import java.util.Scanner;

public class Solution {
	private static void solve(String[] existingDirectories,
			String[] directoriesTobeCreated) {
		HashSet<String> availableDirectories = new HashSet<String>();
		for ( int i = 0; i < existingDirectories.length; i++) {
			String[] splits = existingDirectories[i].split("/");
			StringBuilder sb = new StringBuilder();
			for ( int j = 0; j < splits.length; j++ ) {
				if ( splits[j].length() != 0) {					
					availableDirectories.add(sb.append("/").append(splits[j]).toString());
				} 
			}
			sb.setLength(0);
		}
		int mkdirCount = 0;
		for ( int i = 0; i < directoriesTobeCreated.length; i++) {
			String[] splits = directoriesTobeCreated[i].split("/");
			StringBuilder sb = new StringBuilder();
			for ( int j = 0; j < splits.length; j++ ) {
				if ( splits[j].length() != 0) {
					String possibleNewDirectory = sb.append("/").append(splits[j]).toString();
					if ( availableDirectories.contains(possibleNewDirectory) == false) {						
						availableDirectories.add(possibleNewDirectory);						
						mkdirCount++;
					} else {
					}
				}
			}
			sb.setLength(0);
		}
		System.out.println(mkdirCount);
	}

	public static void main(String[] args) {
		Scanner stdin = new Scanner(System.in);
		// number of test cases
		int T = Integer.parseInt(stdin.nextLine());
		for (int i = 0; i < T; i++) {
			String next = stdin.nextLine();
			String[] next_split = next.split(" ");
			int N = Integer.parseInt(next_split[0]);
			int M = Integer.parseInt(next_split[1]);

			String[] existingDirectories = new String[N];
			for (int j = 0; j < N; j++) {
				existingDirectories[j] = stdin.nextLine();
			}
			String[] directoriesTobeCreated = new String[M];
			for (int k = 0; k < M; k++) {
				directoriesTobeCreated[k] = stdin.nextLine();
			}
			System.out.print("Case #" + ( i + 1) + ": ");
			solve(existingDirectories, directoriesTobeCreated);
		}

	}

}

Google Code Jam Practice Problem – T9 Spelling

Problem

The Latin alphabet contains 26 characters and telephones only have ten digits on the keypad. We would like to make it easier to write a message to your friend using a sequence of keypresses to indicate the desired characters. The letters are mapped onto the digits as shown below. To insert the character B for instance, the program would press 22. In order to insert two characters in sequence from the same key, the user must pause before pressing the key a second time. The space character ‘ ‘ should be printed to indicate a pause. For example, 2 2 indicates AA whereas 22 indicates B.

Old_Phone

package avdongre.google.code.jam;

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Solution {
	static Map<Character, String> keyToNumberMap = new HashMap<Character, String>();
	static Map<Character, Integer> keyOnSameButtton = new HashMap<Character, Integer>();

	static {
		keyToNumberMap.put('a', "2");
		keyToNumberMap.put('b', "22");
		keyToNumberMap.put('c', "222");

		keyToNumberMap.put('d', "3");
		keyToNumberMap.put('e', "33");
		keyToNumberMap.put('f', "333");

		keyToNumberMap.put('g', "4");
		keyToNumberMap.put('h', "44");
		keyToNumberMap.put('i', "444");

		keyToNumberMap.put('j', "5");
		keyToNumberMap.put('k', "55");
		keyToNumberMap.put('l', "555");

		keyToNumberMap.put('m', "6");
		keyToNumberMap.put('n', "66");
		keyToNumberMap.put('o', "666");

		keyToNumberMap.put('p', "7");
		keyToNumberMap.put('q', "77");
		keyToNumberMap.put('r', "777");
		keyToNumberMap.put('s', "7777");

		keyToNumberMap.put('t', "8");
		keyToNumberMap.put('u', "88");
		keyToNumberMap.put('v', "888");

		keyToNumberMap.put('w', "9");
		keyToNumberMap.put('x', "99");
		keyToNumberMap.put('y', "999");
		keyToNumberMap.put('z', "9999");

		keyToNumberMap.put(' ', "0");

		keyOnSameButtton.put('a', 1);
		keyOnSameButtton.put('b', 1);
		keyOnSameButtton.put('c', 1);

		keyOnSameButtton.put('d', 2);
		keyOnSameButtton.put('e', 2);
		keyOnSameButtton.put('f', 2);

		keyOnSameButtton.put('g', 3);
		keyOnSameButtton.put('h', 3);
		keyOnSameButtton.put('i', 3);

		keyOnSameButtton.put('j', 4);
		keyOnSameButtton.put('k', 4);
		keyOnSameButtton.put('l', 4);

		keyOnSameButtton.put('m', 5);
		keyOnSameButtton.put('n', 5);
		keyOnSameButtton.put('o', 5);

		keyOnSameButtton.put('p', 6);
		keyOnSameButtton.put('q', 6);
		keyOnSameButtton.put('r', 6);
		keyOnSameButtton.put('s', 6);

		keyOnSameButtton.put('t', 7);
		keyOnSameButtton.put('u', 7);
		keyOnSameButtton.put('v', 7);

		keyOnSameButtton.put('w', 8);
		keyOnSameButtton.put('x', 8);
		keyOnSameButtton.put('y', 8);
		keyOnSameButtton.put('z', 8);

		keyOnSameButtton.put(' ', 9);

	}

	private static String solve(String nextLine) {
		char[] nextLineCharArray = nextLine.toCharArray();
		char previous = nextLineCharArray[0];
		StringBuilder sb = new StringBuilder();
		sb.append(keyToNumberMap.get(previous));
		for (int i = 1; i < nextLineCharArray.length; i++) {
			char current = nextLineCharArray[i];
			if (keyOnSameButtton.get(previous) == keyOnSameButtton.get(current)) {
				sb.append(" ");
			}
			previous = current;
			sb.append(keyToNumberMap.get(previous));
		}
		return sb.toString();
	}

	public static void main(String[] args) {

		Scanner stdin = new Scanner(System.in);
		// number of test cases
		int N = Integer.parseInt(stdin.nextLine());
		for (int i = 0; i < N; i++) {
			System.out.println("Case #" + (i + 1) + ": "
					+ solve(stdin.nextLine()));
		}
	}

}

Google Code Jam Practice Problem – Store Credit

Problem is described at Store Credit

Analysis
This is variation of the problem where you have you have unsorted array of integers and sum K. You need to find two numbers from the array whose sum is K

package avdongre.google.code.jam;

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Solution {
	private static void solve(int credit, int numOfItems, int[] items) {
		// Map has key[i] = item[i]
		// and value[i] = Index of Item in items array + 1
		Map<Integer, Integer> itemToCreditSum = new HashMap<Integer, Integer>();
		for (int i = 0; i < numOfItems; i++) {
			if (itemToCreditSum.get(credit - items[i]) != null) {
				System.out.println(itemToCreditSum.get(credit - items[i]) + " "
						+ (i + 1));
				break;
			} else {
				itemToCreditSum.put(items[i], i + 1);
			}
		}
	}

	public static void main(String[] args) {

		Scanner stdin = new Scanner(System.in);
		// number of test cases
		int N = Integer.parseInt(stdin.nextLine());
		for (int i = 0; i < N; i++) {
			// Read credit
			int C = Integer.parseInt(stdin.nextLine());
			// Number of Items in the store
			int I = Integer.parseInt(stdin.nextLine());
			// Create item array
			int[] items = new int[I];
			// Read the items values
			String next = stdin.nextLine();
			String[] next_split = next.split(" ");
			for (int j = 0; j < I; j++) {
				int item = Integer.parseInt(next_split[j]);
				items[j] = item;
			}
			System.out.print("Case #" + (i + 1) + ": ");
			solve(C, I, items);
		}
	}

}

[LeetCode #98] Validate Binary Search Tree

Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a BST is defined as follows:

The left subtree of a node contains only nodes with keys less than the node’s key.
The right subtree of a node contains only nodes with keys greater than the node’s key.
Both the left and right subtrees must also be binary search trees.

package avdongre.leetcode;

public class Solution {
	java.util.ArrayList<Integer> arr = new java.util.ArrayList<Integer>();

	private void performInorder(TreeNode root) {
		if ( root == null) {
			return;
		}
		performInorder(root.left);
		arr.add(root.val);
		performInorder(root.right);
	}

	public boolean isValidBST(TreeNode root) {
		if (root == null) {
			return true;
		}
		performInorder(root);
		int previous = arr.get(0).intValue();
		
		for (int i = 1 ; i < arr.size();i++) {
			int current = arr.get(i).intValue(); 
			if (current <= previous) {
				return false;
			}
			previous = current;
		}
		return true;
	}

	public static void main(String[] args) {
		Solution s = new Solution();
		{
			TreeNode tn1 = new TreeNode(1);
			TreeNode tn2 = new TreeNode(1);
			tn1.left = tn2;
			System.out.println(s.isValidBST(tn1));
		}		
		
		{
			TreeNode tn5  = new TreeNode(5);
			TreeNode tn14 = new TreeNode(14);
			TreeNode tn1  = new TreeNode(1);
			
			tn5.left = tn14;
			tn14.left = tn1;
			
			System.out.println(s.isValidBST(tn5));
		}		
		
		{
			System.out.println(s.isValidBST(null));
		}
		
	}

}

Programming Pearls Chapter 1 Problem 6

What would you recommend to the programmer if, instead of saying that each integer could appear at most once, he told you that each integer could appear at most ten times? How would your solution change as a function of the amount of available storage?

package avdongre.programming.pearls;

/**
 * Programming Pearls Chapter 1 Problem 6 
 * 
 * 6. What would you recommend to the  programmer if, instead of saying that 
 * each integer could appear at most once, he told you that each integer 
 * could appear at most ten times? How would your solution change as a 
 * function of the amount of available storage?
 * 
 * @author adongre
 *
 */

public class SolutionChapterOneProblemSix {

	public void solve(int range, int repetition, int[] array) {
		/*
		 * Since each number can appear at most 'repetition' times Let us have bit-vector
		 * with size equal to range * 10
		 */
		java.util.BitSet storage = new java.util.BitSet(range * repetition);
		for (int i = 0; i < array.length; i++) {
			/*
			 * Find the slot where the new number should be stored in the form
			 * of bit ON or OFF
			 */
			int currentNumber = array[i];
			/* Identify the slot start */
			int slotStart = (currentNumber * range) - range;
			/* iterate over the slot */
			int slotEnds = slotStart + repetition - 1;
			for (int j = slotStart; j < slotEnds; j++) {
				if ( storage.get(j) == false) {
					storage.set(j);
					break;
				}
			}

		}
		for ( int i = 0; i < storage.length(); i++) {
			if ( storage.get(i)) {
				System.out.println((i / range) + 1);
			}
		}
	}

	public static void main(String[] args) {
		SolutionChapterOneProblemSix sol = new SolutionChapterOneProblemSix();
		{
			int [] array = new int [] {1,2,3,4,5,1,2,3,4,5,1,2,3,4,5};		 
			sol.solve(5, 5, array);
		}
	}

}

The Algorithm Design Manual Chapter 4 Problem 34

Suppose that you are given a sorted sequence of distinct integers {a1 , a2 , . . . , an },
drawn from 1 to m where n < m. Give an O(lg n) algorithm to find an integer ≤ m that is not present in a. For full credit, find the smallest such integer.

package avdongre.tadm;

public class SmallestMissingNumber {
	public int findSmallestMissingNumber(int[] arr) {

		int low = 0;
		int high = arr.length - 1;
		while (low <= high) {
			int mid = (low + high) / 2;
			if (arr[mid] > mid + 1) {
				high = mid - 1;
			} else if (arr[mid] <= mid + 1) {
				low = mid + 1;
			}
		}
		return low + 1;
	}

	public static void main(String[] args) {
		SmallestMissingNumber smn = new SmallestMissingNumber();
		{
			int[] arr = new int[] { 1, 2, 4, 5 };
			System.out.println(smn.findSmallestMissingNumber(arr));
		}

	}

}

The Algorithm Design Manual Chapter 4 Problem 33

Suppose that you are given a sorted sequence of distinct integers {a1 , a2 , . . . , an }.Give an O(lg n) algorithm to determine whether there exists an i index such as ai = i. For example, in {−10, −3, 3, 5, 7}, a3 = 3. In {2, 3, 4, 5, 6, 7}, there is no such i.

package avdongre.tadm;

public class ElementAtIndex {
	public int findElementAtIndex(int[] arr) {

		int low = 0;
		int high = arr.length - 1;
		while (low &lt;= high) {
			int mid = (low + high) / 2;
			if (arr[mid] &gt; mid + 1) {
				high = mid - 1;
			} else if (arr[mid] &lt; mid + 1) {
				low = mid + 1;
			} else {
				return mid + 1;
			}
		}
		return -1;
	}

	public static void main(String[] args) {
		ElementAtIndex eai = new ElementAtIndex();
		{
			int[] arr = new int[] { 10, 20, 30, 40, 50 };
			System.out.println(eai.findElementAtIndex(arr));
		}
		{
			int[] arr = new int[] { 1, 2, 3, 4, 5, 6, 7 };
			System.out.println(eai.findElementAtIndex(arr));
		}
		{
			int[] arr = new int[] { 10, 1, 66, 5, 6, 7 };
			System.out.println(eai.findElementAtIndex(arr));
		}
		{
			int[] arr = new int[] { -10, -3, 3, 5, 7, 8, 11, 12 };
			System.out.println(eai.findElementAtIndex(arr));
		}

		{
			int[] arr = new int[] { -10, -3, 3, 5, 7 };
			System.out.println(eai.findElementAtIndex(arr));
		}
	}
}

The Algorithm Design Manual 4-6

Given two sets S1 and S2 (each of size n), and a number x, describe an O(n log n) algorithm for finding whether there exists a pair of elements, one from S1 and one from S2 , that add up to x. (For partial credit, give a Θ(n2) algorithm for this
problem.)

package avdongre.tadm;

import java.util.Arrays;

public class TwoSetFindElementWithSum {
	private class Pair&lt;FIRST, SECOND&gt; {
		public FIRST first;
		public SECOND second;

		public Pair(FIRST x, SECOND y) {
			first = x;
			second = y;
		}

		@Override
		public String toString() {
			return String.format(first + &amp;amp;quot;,&amp;amp;quot; + second);
		}
	}

	private int binarySearch(int[] input, int key) {
		int left = 0;
		int right = input.length - 1;
		while (left &lt;= right) {
			int mid = left + (right - left) / 2;
			if (key &lt; input[mid]) {
				right = mid - 1;
			} else if (key &gt; input[mid]) {
				left = mid + 1;
			} else {
				return input[mid];
			}

		}
		return Integer.MAX_VALUE;

	}

	public Pair&lt;Integer, Integer&gt; solveTwoSetFindElementWithSum(int[] input1,
			int[] input2, int target) {	

		Arrays.sort(input2); // n log n
		// iterate over the input1 and search for target - input[i]
		// using binary search so this will be
		// n times logn
		// nlogn + nlogn will be order of the solution.

		for (int i = 0; i &lt; input1.length; i++) {
			int val = binarySearch(input2, target - input1[i]);
			if (val != Integer.MAX_VALUE) {
				return new Pair&lt;Integer, Integer&gt;(input1[i], val);
			}
		}
		return new Pair&lt;Integer, Integer&gt;(Integer.MAX_VALUE, Integer.MAX_VALUE);

	}

	public static void main(String[] args) {
		TwoSetFindElementWithSum s = new TwoSetFindElementWithSum();
		{
			int[] input1 = new int[] {};
			int[] input2 = new int[] {};
			System.out.println(s.solveTwoSetFindElementWithSum(input1, input2,
					0));
		}
		{
			int[] input1 = new int[] {1,5,7,3,9,4};
			int[] input2 = new int[] {6,2,1,7,4,10};
			System.out.println(s.solveTwoSetFindElementWithSum(input1, input2,
					13));
		}		
		{
			int[] input1 = new int[] {10, 50, 40, 30, 20};
			int[] input2 = new int[] {60, 90, 80, 70};
			System.out.println(s.solveTwoSetFindElementWithSum(input1, input2,
					100));
		}		

	}

}

The Algorithm Design Manual Problem 4-5

The mode of a set of numbers is the number that occurs most frequently in the
set. The set (4, 6, 2, 4, 3, 1) has a mode of 4. Give an efficient and correct algorithm
to compute the mode of a set of n numbers.

package avdongre.tadm;

import java.util.HashMap;
import java.util.Map;
import java.util.Map.Entry;

public class ModeOfSet {

	public int solveModeOfSetUsingHashMap(int[] input) {
		if ( input == null) {
			return -1;
		}
		if ( input.length <= 0 ) {
			return -1;
		}
		Map<Integer, Integer> frequencyMap = new HashMap<Integer, Integer>();
		for (int i = 0; i < input.length; i++) {
			if (frequencyMap.containsKey(input[i])) {
				frequencyMap.put(input[i], frequencyMap.get(input[i]) + 1);
			} else {
				frequencyMap.put(input[i], 1);
			}
		}

		int maxFrequent = frequencyMap.get(input[0]);
		int currentFrequency = Integer.MIN_VALUE;

		for (Entry<Integer, Integer> entry : frequencyMap.entrySet()) {
			Integer Key = entry.getKey();
			Integer Val = entry.getValue();

			if (currentFrequency < Val) {
				currentFrequency = Val;
				maxFrequent = Key;
			}

		}

		return maxFrequent;
	}

	public static void main(String[] args) {
		ModeOfSet mos = new ModeOfSet();
		{
			int[] input = new int[] { 4, 6, 2, 4, 3, 1 };
			System.out.println(mos.solveModeOfSetUsingHashMap(input));
		}
		{
			int[] input = new int[] { 4, 6, 2, 4, 3, 1, 1, 1, 1, 1 };
			System.out.println(mos.solveModeOfSetUsingHashMap(input));
		}
		{
			int[] input = new int[] {};
			System.out.println(mos.solveModeOfSetUsingHashMap(input));
		}		

	}

}


Follow

Get every new post delivered to your Inbox.