Snehal Masne
BAN USEROne might have never met a guy like me! :-)
- 0of 0 votes
AnswersHow to implement a Least Frequently Used (LFU) cache?
- Snehal Masne in India
Least Frequently Used (LFU) is a type of cache algorithm used to manage memory within a computer. The standard characteristics of this method involve the system keeping track of the number of times a block is referenced in memory. When the cache is full and requires more room the system will purge the item with the lowest reference frequency.
What would be the best way to implement a most-recently-used cache of objects, say in Java?
I've already implemented one using LinkedHashMap(by maintaining the no. of times objects are accessed) But I'm curious if any of the new concurrent collections would be better candidates.
Consider this case : Suppose cache is full and we need to make space for another one. Say two objects are noted in cache which are accessed for one time only. Which one to remove if we come to know that other(which is not in cache)object is being accessed for more than once ?
Thanks!| Report Duplicate | Flag | PURGE
Algorithm
How about this one ?
public class DiameterOfTree {
public static int diameter = 0;
public static int getDiameter(BinaryTreeNode root) {
if (root != null) {
int leftCount = getDiameter(root.getLeft());
int rightCount = getDiameter(root.getRight());
if (leftCount + rightCount > diameter) {
diameter = leftCount + rightCount;
System.out.println("---diameter------------->" + diameter);
}
if ( leftCount > rightCount) {
return leftCount + 1;
}
return rightCount + 1;
}
return 0;
}
}
Little different approach but this one works :
package com.snehal.gainsight.test;
import java.io.*;
import java.util.StringTokenizer;
public class Solution {
public static void main(String args[]) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String line = br.readLine();
int N = Integer.parseInt(line);
int arr[];
arr = new int[N];
String line2 = br.readLine();
StringTokenizer st = new StringTokenizer(line2, " ");
int i = 0;
// System.out.println("---- Split by space ------");
while (st.hasMoreElements()) {
arr[i] = Integer.parseInt((String) st.nextElement());
// System.out.println(arr[i]);
i++;
}
int diff1 = arr[1] - arr[0];
// System.out.println("Diff 1 = " + diff1);
int diff2 = 0;
int oddPosition = 0;
int diff2count = 0;
int diff[] = new int[N - 1];
for (int k = 0; k < N - 1; k++) {
diff[k] = arr[k + 1] - arr[k];
}
int count = 0;
for (int p = 1; p < N - 1; p++) {
if (diff[0] != diff[p]) {
oddPosition = p;
count++;
}
}
if (count == 1) {
System.out.println(arr[oddPosition] + diff[0]);
} else if (count > 1) {
System.out.println(arr[0] + diff[1]);
}
}
}
There are three cases to consider when trying to find the longest path between two nodes in a binary tree (diameter):
The longest path passes through the root,
The longest path is entirely contained in the left sub-tree,
The longest path is entirely contained in the right sub-tree.
The longest path through the root is simply the sum of the heights of the left and right sub-trees + 1 (for the root node), and the other two can be found recursively:
- Snehal Masne November 10, 2013