Wednesday, January 6, 2016

Calculate price of parking from parking start end time prices - GoHired



Calculate price of parking from parking start end time prices - GoHired
http://www.gohired.in/2016/01/05/calculate-price-of-parking-from-parking-start-end-time-prices/
1 Given a price rules of parking and start time and end time of parking. Calculate the price (Below is the table of price rule) Come up with data structure you can store these price rules PriceRule
Price Rules:
On Weekday      On Weekend
Hours   Price       Hours       Price
0 – 2      $5           0 – 2          $8
2 – 6      $10         2 – 6          $13
6 – 12    $15         6 – 12        $18
12 – 24  $20        12 – 24       $25
2 The interviewer asked  to come up with an architecture for a system which shows the parking spaces available near customers' location in a mobile app.
Lets start with 1). What is correct way to store Prices.

In order to think the solution we need to find the way input will be given, Input will be number of hrs like 3 hrs of parking or 6 hrs of parking. So we can find the charges for such parking directly.

Solution 1 : we can store this input in 2 hashmaps one for weekday and one for weekend.

Hashmap will be <int, int> we can store {{2,5},{6,10},{12,15},{24,20}}.
Once we get input 3 hrs.

Search for first key greater than input(3) which is 6, so it will be in range of 2-6 and charge accordingly.

( Obviously as per day, search for which Hashmap to take, week or weekend)
Space Complexity :  O(n)

Time Complexity : O(n) -> as searching key in sequence.
logN - >using treemap

Solution 2 : Can we think for similar solution so that search complexity we can improve, as in solution 1 we are not utilizing Hashmap's search complexity which is O(1).

Then there are two solution : Use Interval Tree or BST.
Interval Tree : In node keep 5 parameters
                       Least Value, Most Value, Price, LPtr, RPtr
Interval tree will be balanced same as BST.

We can use BST as ranges are not overlapping.

BST : Store 4 parameters : Most Value, Price, LPtr, RPtr.
We can search for parking hrs will fall in which range with same way we used in Hashmap.
But here in Interval Tree or BST
Space Complexity : O(n)
Time Complexity : O(log n)

Read full article from Calculate price of parking from parking start end time prices - GoHired

Labels

Review (572) System Design (334) System Design - Review (198) Java (189) Coding (75) Interview-System Design (65) Interview (63) Book Notes (59) Coding - Review (59) to-do (45) Linux (43) Knowledge (39) Interview-Java (35) Knowledge - Review (32) Database (31) Design Patterns (31) Big Data (29) Product Architecture (28) MultiThread (27) Soft Skills (27) Concurrency (26) Cracking Code Interview (26) Miscs (25) Distributed (24) OOD Design (24) Google (23) Career (22) Interview - Review (21) Java - Code (21) Operating System (21) Interview Q&A (20) System Design - Practice (20) Tips (19) Algorithm (17) Company - Facebook (17) Security (17) How to Ace Interview (16) Brain Teaser (14) Linux - Shell (14) Redis (14) Testing (14) Tools (14) Code Quality (13) Search (13) Spark (13) Spring (13) Company - LinkedIn (12) How to (12) Interview-Database (12) Interview-Operating System (12) Solr (12) Architecture Principles (11) Resource (10) Amazon (9) Cache (9) Git (9) Interview - MultiThread (9) Scalability (9) Trouble Shooting (9) Web Dev (9) Architecture Model (8) Better Programmer (8) Cassandra (8) Company - Uber (8) Java67 (8) Math (8) OO Design principles (8) SOLID (8) Design (7) Interview Corner (7) JVM (7) Java Basics (7) Kafka (7) Mac (7) Machine Learning (7) NoSQL (7) C++ (6) Chrome (6) File System (6) Highscalability (6) How to Better (6) Network (6) Restful (6) CareerCup (5) Code Review (5) Hash (5) How to Interview (5) JDK Source Code (5) JavaScript (5) Leetcode (5) Must Known (5) Python (5)

Popular Posts