Arya
BAN USER1.Generate a random number between 1-5 say 1 using rand()%(5-1+1)+1
2.multiply it with 3 ,now my range will lie between 3-15 ,my number becomes 3
3.subtract by 1 range will become 2-14 ,my number becomes 2
4.Divide it by 2 will gibe the number between range 1-7 ,in my case it is 1;
Implementing the LRU cache algorithm. Given following interface.
interface CacheStrategy<K, T> {
// get the data by key from the cache.
T get(K key);
// put <key, data> pair to the cache
void put(K key, T data);
}
Answer :
The get and put can be done in O(1) time.
1. the data structure
The core of the algorithm is a doubly linked list that indexed by a hash map. The double link is implicitly sorted by the age of the data. Once the data is accessed, it is refreshed. So, the data is moved to the head of the list(age==0).
class Node {
Node prev; //doubly linked list
Node next;
T data; //data and the key
K key;
}
Map<K, Node> map; //node is indexed by the key to support node access in O(1).
2 doubly linked list
For a doubly linked list, the insert and deletion only takes O(1). So, it is quite efficient to implement the LRU algorithm. The reason to use doubly linked list rather than the singly linked list is to delete the nodes in the middle.
By define the head and tail node, the insertion and deletion of a node can be simplified.
a.Initialize the head nodes.
//hook up the head and tail nodes
head = new Node(null, null);
tail = new Node(null, null);
head.next = tail;
tail.prev = head;
b.Remove the node from the list.
private void detach(Node node) {
// detach it from the queue
node.prev.next = node.next;
node.next.prev = node.prev;
}
c. Attach the node to the list.
private void attach(Node head, Node node) {
// add a node after the head.
node.prev = head;
node.next = head.next;
node.next.prev = node;
node.prev.next = node;
}
3 maintain the cache
Get the data from the cache needs to refresh the data in the cache. That is, move the node from the middle to the head.
@Override
public T get(K key) {
Node node = map.get(key);
if (node == null)
return null;
if (map.size() == 1)
return node.data;
// refresh
// - detach it from the queue
detach(node);
// - attach it to head
attach(head, node);
return node.data;
}
Besides a refresh action, putting data into the cache also needs to maintain the cache size and update the content.
/**
* put <key,data> into cache.
*/
@Override
public void put(K key, T data) {
if (maxsize <= 0)
return;
Node node = map.get(key);
if (node != null) {
// hit. Refresh the data
detach(node);
attach(head, node);
node.data = data;
} else {
// miss. Create new node and adjust the size.
node = new Node(key, data);
map.put(key, node);
attach(head, node);
if (map.size() > maxsize) {
// overflow, remove the tail
detach(tail.prev);
map.remove(tail.prev.key);
}
}
// shondik's running code
#include<stdio.h>
#include<stdlib.h>
struct node {
struct node *left;
struct node *right;
int data;
};
struct node *newnode(int data)
{
struct node *node=(struct node *)malloc(sizeof(struct node));
node->data=data;
node->left=NULL;
node->right=NULL;
return node;
}
void printBoundaryLeft(struct node *root)
{
if(root==NULL)
return;
if(root->left)
{
printf("%d ",root->data);
printBoundaryLeft(root->left);
}
else if(root->right)
{
printf("%d ",root->data);
printBoundaryLeft(root->right);
}
}
void printBoundaryLeaf(struct node *root)
{
if(root==NULL)
return ;
else
{
printBoundaryLeaf(root->left);
if(root->left==NULL&&root->right==NULL)
printf("%d ",root->data);
printBoundaryLeaf(root->right);
}
}
void printBoundaryRight(struct node *root)
{
if(root==NULL)
return;
if(root->right)
{
printBoundaryLeft(root->right);
printf("%d ",root->data);
}
else if(root->left)
{
printBoundaryLeft(root->left);
printf("%d ",root->data);
}
}
void printBoundary(struct node *root)
{
if(root)
{
printf("%d ",root->data);
printBoundaryLeft(root->left);
printBoundaryLeaf(root);
printBoundaryRight(root->right);
}
}
int main()
{
struct node *root=newnode(1);
root->left=newnode(2);
root->right=newnode(3);
root->left->right=newnode(4);
root->left->right->left=newnode(13);
root->left->left=newnode(5);
root->right->right=newnode(7);
root->right->left=newnode(12);
printBoundary(root);
return 0;
}
It's undefined behaviour...
In practice, what you're seeing is probably due to the fact that %f makes printf pull a double from its argument list, which is 8 bytes*. But d is only 4 bytes in size, so now everything is misaligned.
Remember that printf is a variadic function, which means it's completely non-type-safe; printf has to extract raw bytes from the stack without any help from the compiler. It's entirely up to you to ensure that the arguments correspond precisely to the format string.
- Arya July 03, 2012