Miral Patel
BAN USER- 1of 1 vote
AnswersImplement LRU cache of size 10 which can store Key, Value pair. (get(key) & put(key,value) methods)
- Miral Patel in United States
- If we try to add 11th element, the least recently used element should get removed.
- If key already present, overwrite it and mark it as most recently used.| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Data Structures
Apparently, the simplest possible implementation is,
public class LRUCache extends LinkedHashMap<Integer, String>{
private int cacheSize;
public LRUCache(int size) {
super(size, 0.75f, true);
this.cacheSize = size;
}
@Override
protected boolean removeEldestEntry(
java.util.Map.Entry<Integer, String> eldest) {
// remove the oldest element when size limit is reached
return size() > cacheSize;
}
}
Linked Hashmap will, apart from doing its basic work i.e, storing key value pairs, also keep track of insertion order of they keys.
LinkedHashmap knows the order in which keys were added.
So if you know firstLink and lastLink of the map then,
both your get and put operations will have O(1) complexity.
get(key, value)
- Return the map.get(key) - O(1),
- Remove it from map (link.previous = link.next) and put it back in the map making it the first element of the map.
put(key, value)
- if the list is full, then lastElement.previous.next = null; (making the second last element as the last element of the map)
- add the new element and make it the firstElement of the map.
The best bet would be to implement doubly - LinkedHashMap.
- Miral Patel May 07, 2014Tried that already, it wont work for this:
(((a+b)+c))
Looks interesting solution but there is some catch.
For String "(( a + b ) + (( c + d )) + e)" o/p should be ((a + b) + ( c + d ) + e )
but, your code gives o/p = (a + b) + ( c + d ) + e )
public class Parenthesis{
public static void main(String []args){
System.out.println("Parenthesis valid : "
+ hasValidParenthesis("abcd"));
}
public static boolean hasValidParenthesis(String s) {
// negative conditions
if( null == s ) return false;
if( s.isEmpty() ) return false;
if( s.indexOf('(') == -1 && s.indexOf(')') == -1 ) return false;
// to track matching Parenthesis
int count = 0;
// to track each char
int index = 0;
// array to know if there is content between two parenthesis
boolean[] contentArray = new boolean[50];
for(char c : s.toCharArray()) {
if( c == '(') {
count++;
} else if ( c == ')') {
if( count == 0 ) {
// ')' encountered without any prior '('
return false;
}
// if content is not present between ( and ), then
// treat them as a duplicate entry
if( false == contentArray[count-1] ) {
return false;
}
contentArray[count-1] = false;
// decrement Parenthesis count
count --;
} else if( count > 0 ) {
// store the content between parenthesis
if(!contentArray[count-1])
contentArray[count-1] = true;
}
// increment index
index++;
}
return (count == 0);
}
}
-1, because correct answer but not for this question.
- Miral Patel May 02, 2014Tried to implement the solution provided by Kishore.
public static void findShortestSubString() {
String s1 = "spqrstrupvqw";
String s2 = "sprt";
String s3 = "q";
Set<String> results = new HashSet<String>();
// 1. split the s1 with s3
// 2. sp rstrupv wrpts
// 3. find the shortest word that has s2 in it.
// -- if word's length >= s2.length --> find the shortest word sequence containing s2
String[] stringsToFind = s1.split(s3);
for(String stringToFind : stringsToFind)
{
// ignore shorter strings
if( stringToFind.length() < s2.length() )
{
continue;
}
// ignore the words that dont have every characters present in s2
if( !stringHasAllLetters(stringToFind, s2))
{
continue;
}
boolean subStringFound = false;
int offset = 0;
int i = 0;
// start with the exact length
while( !subStringFound )
{
// start to find all characters of s2 within equal length of words in stringToFind,
// if not found, increase length each time
for(i=0; i <= (stringToFind.length() - s2.length() - offset); i++ )
{
String currentSegment = stringToFind.substring(i, i + s2.length() + offset);
if( stringHasAllLetters(currentSegment, s2) )
{
results.add(currentSegment);
subStringFound = true;
break;
}
}
if( !subStringFound )
{
i = 0;
offset++;
}
}
}
System.out.println(results);
}
private static boolean stringHasAllLetters(String stringToFind, String letters)
{
boolean allLettersPresent = true;
for(char c : letters.toCharArray())
{
if(stringToFind.indexOf(c) == -1){
allLettersPresent = false;
break;
}
}
return allLettersPresent;
}
correction -
- Miral Patel February 10, 2016