0

LRU Cache

In computers, cache memory provides fast access to processor by storing frequently used computer programs, data and applications; However size of cache memory is relatively small. Because of the size constraint, it is required to invalidate data from cache and store new data frequently when it is full.So, algorithms are required to decide which data should be removed from cache.

One of the algorithm to decide what to remove from cache is  Least Recently Used (LRU). In this algorithm, least recently used data is removed from cache.
Example:
Imagine cache size is 4. Initially data D1,D2 and D3 requested by some program.
– As initially cache is empty, all three data elements inserted in cache sequentially.
-Then D1 and D2 data access requested. As, it is already in cache, D1 and D2 will be accessed directly from cache.
-Now new data D4 requested by program ,as it is not in cache, D4 added in cache.
-Now new data D4 requested by program. As cache does not have D5 stored ,D5 needs to be added in cache.
However, cache is already full, so we need to replace data in cache. As per LRU algorithm, we will find least recently used data in cache. For current scenario it is D3. Though, D3 inserted in cache after D1 and D2, data D1 and D2 accessed after insertion however D3 not, so we will remove D3 from cache and insert D5 in cache.
Input : Cache capacity and <key,value> pair as data.
Problem statement:(Leetcode problem no. 146)

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.

To keep track of recently used data, we will use LinkedHashSet data structure and input data will be stored in HashMap as input is in the form of key, value.
Logic:
– Whenever new data is put in cache(HashMap)  using set function check if cache is completely filled, if not add that value to cache. Insert key value in LinkedHashSet. Else, extract oldest element from LinkedHashSet (which will be first element in hashSet) and remove that from HashMap and then insert new <key,value>.
– If get function called which is accessing data already present in cache, value for the key is returned from HashMap if present, else -1. Requested key removed from LinkedHashSet and inserted again. Removal of required as LinkedHashSet keep keys in order of access.
– If set function called however that key is already present in the cache (HashMap), we need to update value of that key and make it most recently used by removing key from HashSet and inserting it again.
Code:

 

0

Bitwise Operators

Bitwise operators are used to perform operations on bits. Most of the times programmers works on byte, int, char etc. data types and does not pay attention to bit level operations. However bit operators are used to manipulate values for comparisons and calculation.

Bits always have value either ‘1’ or ‘0’.  Binary operators are used to manipulate these values. In simple words ‘1’ means bit is ‘set’ and ‘0’ means bit is ‘clear’.

Following are few operators used to perform bitwise operations:

  • NOT/Complement :

This is a unary operator which means it works on only one operand. Not operator flips each bit means 1 become 0 and 0 become 1.

Not 5: ~5 :: Not 0101 :: result will be 1010 (10).

  • AND ( & ) :

Binary And operator compares each bit of first operand to the  corresponding bit of second operand in two equal length operands.

Result bit will be ‘1’ if and only if both bits in the compared positions are ‘1’.

When we multiply any number by 0, output is always 0. same rule applies to And operator, whenever we multiply 1*1 result bit will be 1.

BitwiseAnd

Clear bit:  & operator is used to clear a particular bit in a number.

Eg. clear 2nd  bit in 46 (0 0 1 0 1 1 1 0 ) :

 

ClearBit

Not of 1 changes only expected bit in number and keeps remaining bits as it is.

 

  • OR ( | ) :

Binary Or operator compares each bit of first operand to the  corresponding bit of second operand in two equal length operands.

Result bit will be ‘o’ if and only if both bits in the compared positions are ‘0’.

BitwiseOr

Set bit :   As we saw & operator is used to clear a particular bit in a number, Or operator is used to set a particular bit in number.

Eg. Set 4th  bit in 46 (0 0 1 0 1 1 1 0 ) :

.   SetBit

This set bit method is used to efficiently store a number of Boolean values using little memory.

  • XOR ( ^ ) :

Binary Xor operator compares each bit of first operand to the  corresponding bit of second operand in two equal length operands.

Result bit will be ‘1’ if and only if either of the bits in the compared positions are ‘1’. That means if both bits are 1 then result will be 0.

XOR

Any bit can be toggled when XORed with 1.

Xor is  used in a tricky way to swap to integer variables without any extra space.

eg.  int a = 3 , b=9.      a:  0   0   1  1

b : 1   0   0  1

a= a ^ b         (a will be    1   0  1  0)

b= a ^ b        ( b will be   0  0  1   1)  which is value of a,  So now b=3

a=  a ^ b        (a will be     1  0  0   1)  which is value of b, So now a =9

  • Left Shift ( << ) :

Left shift operator shifts bits in first operand to left by number of bits given in second operand and inserts 0 bits are filled in vacant bits.

Eg. 23 << 1   :    0  0   0  1  0  1  1  1 << 1   result is :  0  0  1  0  1   1  1  0

  • Right Shift ( >> ) :

Right shift operator shifts bits in first operand to right by number of bits given in second operand and inserts 0 in vacant bits for unsigned numbers and for unsigned numbers  logically signed bit is copied as it is in most significant left bit and then 0 inserted in vacant bits. In C++, singed bit is copied in all the vacant bits.

Eg.  14 >> 2  : 0  0  0  0  1  1  1  0  >> 2  result is:  0  0   0   0   0  0  1  1

Tricks :

1. 0 1 1 1 + 0 1 1 1 (7+7) is equivalent to 0 1 1 1 * 2 (1 1 1 0 : 14), which is equivalent to shifting input number left by 1.  0 1 1 1 << 1 = 1 1 1 0 (14)

2. If a number is XOR with its own negated value, result will be sequence of 1s.  Eg. 0 1 1 1 ^ (1 0 0 0 ) = 1 1 1 1 . i.e. 7 ^(~7)

3. If we multiply any number by  2, simple way is to left shift that number by n. Eg. (3 * 4)  0 0 1 1 * 0 1 0 0  :: 4 =22

so 0 0 1 1 << 2 : : 1 1 0 0

0

Divisibility Puzzle

Yesterday a friend of mine gave me this puzzle to solve :

Find a number consisting of 9 digits in which each of the digits from 1 to 9 appears only once. This number should satisfy the following requirements:

  • The number should be divisible by 9.
  • If the right-most digit is removed, the remaining number should be divisible by 8.
  • If the two right-most digits are removed, the remaining number should be divisible by 7.
  • If the three right-most digits are removed, the remaining number should be divisible by 6.
  • If the eight right-most digits are removed, the remaining number should be divisible by 1.

 

We sure can solve this using crazy mathematics, but I have a clever idea, let the computer solve it for us.

How about writing code to solve this .. FUN \m/

When you break down this problem , its basically which permutation of 123456789  satisfy the above conditions.

So All we have to do is loop through all the permutations and for every permutation check if it satisfies the above conditions.

I know its not ideal to go through all the n! permutations and find the number. But it WORKS and it gave me solution in seconds.

You can read about this puzzle here (Mathematical Approach):

http://math.ucsd.edu/~wgarner/personal/puzzles/div_puzzle_sol.htm
Here is my code :