java - How can you implement LFU cache using simplest and minimum data structures.? -

-

this question has answer here:

i asked question in interview asked first difference between lru , lfu , asked implement both. knew lru can implemented through linkedhashmap got confused lfu. can tell me how implement simplest data structures explaination? can implemented linkedhashmap too.?

assuming cache entries keyed, queue (linkedlist) , map (hashmap).

(assume queue , map full)
pick bound b queue. on every cache request, push key requested page queue poll queue.
if page want in map, return page. if page isn't in map find least occurring key in queue in map or key page want. if key key page want, nothing; else remove entry map key , insert page map.
return page.

complexity cache hit o(1), o(b) miss.
assumes want bound frequency. ie. "least used in last b requests" instead of "least used ever".


Comments

Post a Comment

Popular posts from this blog

wordpress - (T_ENDFOREACH) php error -

-
creating wordpress website , i'm getting following php error: parse error: syntax error, unexpected 'endforeach' (t_endforeach) in /home/soralmedia/public_html/wp-content/themes/soral media/woocommerce/myaccount/my-orders.php on line 98 here's code file: <?php /** * orders * * shows recent orders on account page. * * template can overridden copying yourtheme/woocommerce/myaccount/my-orders.php. * * however, on occasion woocommerce need update template files , (the theme developer). * need copy new files theme maintain compatibility. try this. * little possible, happen. when occurs version of template file will. * bumped , readme list important changes. * * @see http://docs.woothemes.com/document/template-structure/ * @author woothemes * @package woocommerce/templates * @version 2.5.0 */ if ( ! defined( 'abspath' ) ) { exit; } $my_orders_columns = apply_filters( 'woocommerce_my_account_my_orders_columns', array(
Read more

Export Excel workseet into txt file using vba - (text and numbers with formulas) -

-
i new vba have developed code use in excel move text/numbers txt file. issue have 3 functions need go same txt file. when run first function has set fs = createobject("scripting.filesystemobject") set = fs.createtextfile(module1.nys45uploadfilename, true) a.writeline (str) a.close. the other 2 functions had save. set fs = createobject("scripting.filesystemobject") set = fs.savetextfile(module1.nys45uploadfilename, true) a.writeline (str) a.close. the first function go txt file, other 2 error object doesn't support property or method. when changed 3 create last function goes txt file. can not figure out word use in order make other 2 functions follow txt file in order keyed. the entire code follows private sub addrecord_click() on error goto errhandler module1.nys45uploadfilename = application.getsaveasfilename(filefilter:="textfiles (*.txt), *.txt") if module1.nys45uploadfilename = "false" exit sub
Read more

Using django-mptt to get only the categories that have items -

-
sample structure: all uppercase: category mixed case: item root ├── books │   ├── fiction │   │   └── classics │   └── non-fiction ├── clothing └── electronics ├── laptops ├── phones │   ├── apple │   │   ├── iphone 6 │   │   ├── iphone 6 plus │   │   ├── iphone 6s │   │   └── iphone 6s plus │   ├── motorola │   │   ├── moto g4 │   │   ├── moto g4 play │   │   ├── moto g4 plus │   │   └── moto x │   └── samsung └── tablets └── apple i'm trying have index page show "electronics" category. "clothing" category shouldn't show since it's empty , "books" category shouldn't show either since, although has child categories, child categories don't have items. similarly, "electronics" page should show "phones" category. "laptops" category shouldn't show since it's empty , "tablets" category shouldn't show either since
Read more