saurabh
BAN USERapologies @ EPavlova its just a typo the code actually prints the min path and min value,
#include<stdio.h>
#include<limits.h>
#define FALSE 0
#define TRUE 1
/* A tree node structure */
struct node
{
int data;
struct node *left;
struct node *right;
};
// A utility function that prints all nodes on the path from root to target_leaf
int printPath (struct node *root, struct node *target_leaf)
{
if(root==NULL)
return FALSE;
if (root == target_leaf || printPath(root->left, target_leaf) ||
printPath(root->right, target_leaf) )
{
printf("%d ", root->data);
return TRUE;
}
return FALSE;
}
// This function Sets the target_leaf_ref to refer the leaf node of the minimum
// path sum. Also, returns the minimum sum using min_sum_ref
void getTargetLeaf (struct node *node, int *min_sum_ref, int curr_sum,
struct node **target_leaf_ref)
{
if(node == NULL)
return ;
curr_sum = curr_sum + node->data;
if(node->left==NULL && node->right==NULL)
if(curr_sum < *min_sum_ref){
*min_sum_ref = curr_sum;
*target_leaf_ref = node;
}
getTargetLeaf(node->left,min_sum_ref,curr_sum,target_leaf_ref);
getTargetLeaf(node->right,min_sum_ref,curr_sum,target_leaf_ref);
}
// Returns the mininmun sum and prints the nodes on max sum path
int minSumPath (struct node *node)
{
if (node == NULL)
return 0;
struct node *smallest_path;
int min_path = INT_MAX;
getTargetLeaf(node,&min_path,0,&smallest_path);
printPath(node,smallest_path);
return min_path;
// base case
}
/* Utility function to create a new Binary Tree node */
struct node* newNode (int data)
{
struct node *temp = (struct node*)malloc(sizeof(struct node));
temp->data = data;
temp->left = NULL;
temp->right = NULL;
return temp;
}
/* Driver function to test above functions */
int main()
{
struct node *root = NULL;
/* Constructing tree given in the above figure */
root = newNode(10);
root->left = newNode(-2);
root->right = newNode(7);
root->left->left = newNode(8);
root->left->right = newNode(-4);
printf ("Following are the nodes on the minimum sum path \n");
int sum = minSumPath(root);
printf ("\nSum of the nodes is %d ", sum);
getchar();
return 0;
}
explanation :-
the function minSumPath starts from root and explore each branch of the tree leading to a leaf node
i.e
10
/ \
-2 7
/ \
8 -4
for above three it will go like this
step 1 )
10+(-2)+(8) = 16 and the root now points to 8
now root reaches leaf as 8 is a leaf node there will be a check whether curr_sum (here
16 ) is less than min_sum (INT_MAX) which stands true
*min_sum_ref = curr_sum;(i.e min_sum = 16)
*target_leaf_ref = node; (i.e target_leaf_ref points to 8 )
step 2)
step 1 is repeated for all the branches (i.e 10->(-2)->(-4),10->7)
at last the min_sum= 4 (i.e 10+(-2)+(-4))
and target_leaf_ref points to 4
step 3) printPath function checks whether root == target_leaf_ref no in this case so it recursively moves left and right once it becomes equal to 4 it starts printing backwards data
that is -4 -2 10
hence you print the path and the min_sum is returned as 4
--------------------------------------------------------------------------------------------------------------------
--------------------------------------------------------------------------------------------------------------------
in case the explanation doesn't clicks you please let me know i won't mind giving one more try
kudo:)
#include<stdio.h>
#include<limits.h>
#define FALSE 0
#define TRUE 1
/* A tree node structure */
struct node
{
int data;
struct node *left;
struct node *right;
};
// A utility function that prints all nodes on the path from root to target_leaf
int printPath (struct node *root, struct node *target_leaf)
{
if(root==NULL)
return FALSE;
if (root == target_leaf || printPath(root->left, target_leaf) ||
printPath(root->right, target_leaf) )
{
printf("%d ", root->data);
return TRUE;
}
return FALSE;
}
// This function Sets the target_leaf_ref to refer the leaf node of the maximum
// path sum. Also, returns the max_sum using max_sum_ref
void getTargetLeaf (struct node *node, int *max_sum_ref, int curr_sum,
struct node **target_leaf_ref)
{
if(node == NULL)
return ;
curr_sum = curr_sum + node->data;
if(node->left==NULL && node->right==NULL)
if(curr_sum < *max_sum_ref){
*max_sum_ref = curr_sum;
*target_leaf_ref = node;
}
getTargetLeaf(node->left,max_sum_ref,curr_sum,target_leaf_ref);
getTargetLeaf(node->right,max_sum_ref,curr_sum,target_leaf_ref);
}
// Returns the maximum sum and prints the nodes on max sum path
int maxSumPath (struct node *node)
{
if (node == NULL)
return 0;
struct node *smallest_path;
int min_path = INT_MAX;
getTargetLeaf(node,&min_path,0,&smallest_path);
printPath(node,smallest_path);
return min_path;
// base case
}
/* Utility function to create a new Binary Tree node */
struct node* newNode (int data)
{
struct node *temp = (struct node*)malloc(sizeof(struct node));
temp->data = data;
temp->left = NULL;
temp->right = NULL;
return temp;
}
/* Driver function to test above functions */
int main()
{
struct node *root = NULL;
/* Constructing tree given in the above figure */
root = newNode(10);
root->left = newNode(-2);
root->right = newNode(7);
root->left->left = newNode(8);
root->left->right = newNode(-4);
printf ("Following are the nodes on the maximum sum path \n");
int sum = maxSumPath(root);
printf ("\nSum of the nodes is %d ", sum);
getchar();
return 0;
}
caution long answer below:
- saurabh March 16, 2016okay at last i got some time to answer your question .
LRU page replacment,mostly used in operating system but you see it doesn't make sense to me for a website with millions of products ,i mean indexing each product for a single customer and manipulating those indexes relevant to each customer not efficent neither cool.
from my point of view there are three ways to look for at problem
1. Either they use a collection of separate column values to store
products you search or view
problem:-
but com'on how novice is it ,and its not a college project which you are doing just because you are suppose to ,its pure bussiness so this is neither cool not flexible ,and yes cool here means its doesn't seems geeky.
2. Use Browser caches to store and retriev your past history to show suggestions
problem :-
its a good way to do such thing and cool as well but you see broswer caches are small data stores and storing some user related data on user machine is not at all proffesional in terms of bussiness.
so its cool but not flexible for a complex structure like amazon
3.combination of first and second points (i.e columns + browser caches)
there's a catch here that instead of columns amazon may use a graph based database (i.e google for neo4j) using the caches data it can further make nodes and a simple dfs travesal can provide a collection of connected products and using counting inversiopn techinques can give you the data for people who viewed this also viewed this product and whalaaaaaaa you have it..
so these are my point of view on how they would be implementing it ,i would love to have a healthy discussion or re-explanation in case you need it
(note : these are my own point of views it doesn't resembels any of amazons perspective )