They ask the same questions to every interviewee.
First Round - HackerEarth Test - 2 Coding Questions [Easy, Implementation Based] . Had to Score 100/100 to qualify for the next round. There were some edgy corner case tests in one problem.
Tech Round -1
Given a “snapshot” interface, which stores the state of data for ‘n’ keys against snapshot ids.
Implement this interface in a class.
Interface Snapshot {
int get(int key) -> value
void set(int key, int value)
int takeSnapshot()
Int getValueAtSnapshot(int key, int snapshotId)
}
I solved using HasMap<snapshotId> of HashMap<key, value>.
Follow up question on this question based on the following scenario
Access Pattern
Only 3-4% keys values are changing between consecutive snapshots
The client takes a lot of snapshots ( S is very high)
On an average a key changes in S` (<<<<< S) number of snapshots
The goal was to reduce space complexity because only a few keys were being changed in every snapshot. Reduce Redundancy
I solved by having an ArrayList <value, snapshot_id> for every key, update only when the current value of this key is updated.
Binary search can be done on snapshot_id for getValueAtSnapshot(key, snapshot_id)
Tech Round - 2
I was given a Machine Coding Assignment , which I had to complete in 2 hours.
Client-side API Rate Limiting -
The Problem Statement is below-
Machine Coding Round
Time Limit: 2 hours
You have to implement a custom JSON configuration-based API Rate Limiting module which can be used to
limit the number of HTTP API calls made to an external service. This is a client-side rate-limiting. That is,
before you make an API call from your application to another service, you should be able to use this module to
check if you can actually make that call.
In the configuration, there are service s that contains globalLimits and apiLimits . Each service
contains zero/more APIs. globalLimits define the overall limits for a service. apiLimits define individual
API specific limits for different HTTP Methods. For each HTTP Method (GET, POST etc.), there is a limit and
granularity. Eg. A limit of 10 and granularity of minute means that the module should rate-limit
after 10 requests in any 1 min or 60 sec interval. Note: the interval is not fixed. You can assume second as the
lowest possible granularity.
The globalLimits apply to all the APIs inside that service . Eg. Service - S1 (Global Limit of 10/min) has 3
APIs - A1, A2, A3 each having an API Limit of 100/min. This means that even though 100/min is defined for
each API, since the Global Limit is 10/min - we cannot make more than 10 calls combined in any given minute
to APIs of that service. Similarly vice versa, logic applies. If A1 had 3/min defined, you cannot make more than
3 calls in a minute to A1.
Evaluation Criteria:
1. You can trigger requests to the module from a Main() method. The interviewer would ask you to run
through various scenarios by changing the JSON configuration values. Eg. Put Global Limit as 10/min &
API Limit as 5/min, Vice versa, and so on and check that rate limiting is applied. You can put print
statements to indicate “Rate limited” / “Allowed” for requests.
2. The interviewer would evaluate Modularity, Readability, Extensibility of the code - This would be treated
as important as the working code and logic itself. Try to get to working code as the first priority, and
improve on these aspects after that.
Eg. Json Configuration -
{
"serviceLimits": [
{
"service": "OrderService",
"globalLimits": {
"GET": {
"limit": 10,
"granularity": "second"
},
"POST": {
"limit": 20,
"granularity": "minute"
}
},
"apiLimits": [
{
"methods": {
"GET": {
"limit": 15,
"granularity": "second"
},
"POST": {
"limit": 20,
"granularity": "minute"
}
},
"api": "CreateOrder"
},
{
"methods": {
"GET": {
"limit": 10,
"granularity": "second"
},
"POST": {
"limit": 10,
"granularity": "second"
}
},
"api": "GetOrderById"
}
]
},
{
"service": "DeliveryService",
"globalLimits": {
"GET": {
"limit": 10,
"granularity": "second"
},
"POST": {
"limit": 20,
"granularity": "minute"
}
},
"apiLimits": []
}
]
}