Dinkar
BAN USERMy Solution-
class Level {
int level = 0;
boolean atNotSameLevel = false;
}
class GfG
{
Level level = new Level();
boolean check(Node root)
{
// Your code here
getFirstLeafLevel(root, 1);
// level.level = deepestLeafLevel;
// System.out.println("getFirstLeafLevel "+level.level);
leafAtSameLevel(root, level, 1);
return !level.atNotSameLevel;
}
private void leafAtSameLevel(Node root, Level level, int lvl) {
// base case
if(root == null) {
return;
}
// System.out.println(" data "+root.data +" lvl "+lvl);
if(root.left == null && root.right == null && level.level != lvl) {
level.atNotSameLevel = true;
return;
}
leafAtSameLevel(root.right, level, lvl+1);
leafAtSameLevel(root.left, level, lvl+1);
}
private void getFirstLeafLevel(Node root, int l) {
if(root == null) {
return;
}
if(root.left == null && root.right == null) {
level.level = l;
return;
}
// System.out.println("data "+root.data);
getFirstLeafLevel(root.left, l+1);
getFirstLeafLevel(root.right, l+1);
}
}
See my solution i have posted on geeks for geeks
i have simplified solution in two parts
1. get any leaf node level
2. compare this level with any of leaf node, if any of leaf node in tree is not having same level then all leaf are not present at same level.
class Level {
int level = 0;
boolean atNotSameLevel = false;
}
class GfG
{
Level level = new Level();
boolean check(Node root)
{
// Your code here
getFirstLeafLevel(root, 1);
// level.level = deepestLeafLevel;
// System.out.println("getFirstLeafLevel "+level.level);
leafAtSameLevel(root, level, 1);
return !level.atNotSameLevel;
}
private void leafAtSameLevel(Node root, Level level, int lvl) {
// base case
if(root == null) {
return;
}
// System.out.println(" data "+root.data +" lvl "+lvl);
if(root.left == null && root.right == null && level.level != lvl) {
level.atNotSameLevel = true;
return;
}
leafAtSameLevel(root.right, level, lvl+1);
leafAtSameLevel(root.left, level, lvl+1);
}
private void getFirstLeafLevel(Node root, int l) {
if(root == null) {
return;
}
if(root.left == null && root.right == null) {
level.level = l;
return;
}
// System.out.println("data "+root.data);
getFirstLeafLevel(root.left, l+1);
getFirstLeafLevel(root.right, l+1);
}
}
- Dinkar August 20, 2017O(n) solution-
The idea is is keeping the values in array multiplied from the last element index and using the multiplied value for calculating the previous value.
-Traverse array from last
-pickup element from last-1(not required for last element to multiply)
- multiply it multiply it by last element(it is multiplied value for next iteration)
-store it value at current index
-repeat above step until first element
The idea is, start from zero index and sum with previous element and compare with next values some of array from that index to last index,
See algo
Leftsum=0
rightsum=0
I =0 to n
Leftsum+=a(I)
And j =I+1
Rightsum+=a(j)
End inner loop
If leftsum==rightsum
Return index I and break from outer loop
Else rightsum=0
(n2) complexity worst
Best (n)
Thanks
The idea is first put the houses location in a array,
and now traverse the inputArray and find the distance between each point with the houses location array, if any single point distance is equal to all house location array then that point is the answer.
houseLocations[][]<- put locations
int inputArray[][]<- put 1 where location are valid like for A, B, C and rest all is 0
traverse inputArray- now for each inputArray points, cosider index i, j position to calculate the distance,
now for houseLocations array calculate the distance from each points of i,j
if all distance is equal then break with this point and this point is the desired position from where all houses are at equal distance.
If any one need clarification please leave a comment
More clarification on answer.
distance is calculated for (x1, x2), (y1, y2) points using distance formula between two points- sqrroot{(x2-x1)^2 + (y2-y1)^2}
- x1 and x2 are i and j where house location array is having value 1
- For each i, j, goo to loop for houselocation array ie.
start loop k,j - to houselocation array size, now k, j is y1 and y2
- this way you calculate the distance for single point in input array with all house locations values- and this all distance are equal if any point then this is the right location of i,j- which is house location,
still any query please ask.
shopping cart design
- Dinkar January 16, 2018Features
Add item in cart
save cart item in data base
Update cart amount on item added in art
Calculate total price
Apply coupon
Get quantity
restrict user can not add more than 10 same items in cart
Remove cart item remove on request
send notification to user that item going to be out of stock
remove item if item is removed from inventory and message and mail to user
Server side Handle thousands of request per second - use load balancer
Data base selection data base sql or no sql - nosql store data in form of tree - design
sql db design
Table Structure
Offer
PromotionCoupan amount
promotionId
GiftCoupan
gift ID amount
Cart
item id user id price discount color size
Item
item id category id itemvariationid item description - very good product
Item Variations
item variation id price
Color
color id color
Item Color
item variation id color id
User
user id
Order Item
item id
user id
Order
user id
More on design
Java classes design - will update later
Java design pattern - will update later
Above is very rough high level design, this can be drilled down and feature and sub feature of system can be identified and data base table can be refined.
Thanks