Saturday, 24 April 2021

Myntra Interview Experience

Myntra Software Engineer Interview Experience

Myntra Software Engineer Interview Experience
Round 1 - Problem Solving

Q1: Class room; number of student 1 to N.
We need to elect class leader such that
* Every student should trust L
* L shouldn’t trust anyone.
(x, y) => x trusts y

Input: N integer
Array pair of ints
Output: Integer  = L
(1, 4) (1,2) (2, 4) (3, 4) (1,2), (3, 2)

Edge cases

(1,2), (2, 3), (1,3), (3, 2)

(4, 1), (1, 4), (2, 4) (3, 4)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 
TrustPairNode {
Integer key; //student
Integer value;//trust on student
}

Int getLeader(List<TrustPairNode> trustPair, int n) {
    Map<Integer, Integer> leaderMap = new HashMap<>();
    for (TrustPairNode node : trustPair) {
        // 4 -> 3
        leaderMap.put(node.value, leaderMap.getOrDefault(node.value, 0)++);
        // (1, 4) (1, 2) (2, 4) (3, 4) (1,2), (3, 2) (5, 4)

If (leaderMap.containsKey(node.key)) {
            leaderMap.remove(node.key);
        }
    }

    for (Map.Entry<Integer, Integer> entrySet : leaderMap.entrySet()) {
    If (entry.getValue() == n-1) {
        return entry.getKey();
    }
    return -1;
}

 

Q2: Field which is walled - of different heights
[2, 0, 2] => 2
Input: array
output : integer -> water stored in field. 

Solution

Round 2: Data Structures & Algorithms

Q1. Get minimum element from stack in 0(1)

 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class MinStack {
    Stack stack;
    Stack minStack;

    Void push(int element) {
        If (minStack.isEmpty() || element < minStack.peek()) {
            minStack.push(element);
        } else {
            minStack.push(minStack.peek());
        }
        stack.push(element);
    }

    Int pop() {
        // if stack is empty check
        minStack.pop();
        Return stack.pop();
    }
       
    Int getMinimum() {
        // if stack is empty
        Return minStack.peek();
    }
}

 

Q2 A number can be broken into different sub-sequence parts. Suppose, a number 3245 can be broken into parts like 3 2 4 5 32 24 45 324 245 3245. And this number is a colorful number, since product of every digit of a sub-sequence are different. That is, 3 2 4 5 (3*2)=6 (2*4)=8 (4*5)=20 (3*2*4)= 24 (2*4*5)= 40

 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
private static void printColorful(String number) {
    Set<String> numSet = new HashSet<>();
   
    for (int i=0; i<number.length(); i++) {
      for (int j=i+1; j<number.length(); j++) {
        String temp = number.substring(i, j);
        System.out.println(temp);
        if (temp.length > 1) {
          String simplify;
          int product = getProduct(temp);
          simplify = String.valueOf(product);
          if (numSet.contains(simplify)) {
            System.out.println("Not colorfull");
          }
        }
        numSet.add(temp);
      }
    }
    System.out.println("colorfull");
  }
 
  private static int getProduct(String temp) {
    int product = 1;
    for (char ch : temp.toCharArray()) {
      product *= (int)ch;
    }
    return product;
  }


Round 3 Low Level Design

Q1 Design a platform where
Write users : Uploading text based posts to the platform
Read users : Giving a search query and retrieving the results of posts. Limiting the result of posts to 100.
Not doing a feed ranking. 

Solution

Read users >> Write users (x50)

Functional Requirements

  • Limit to size of chars published - 200 chars
  • Publishing the text
  • Retrieving the text


Non Functional

  • Low latency for retrieval


Example
<PostId, PostContent>
D1, Furniture bed
D2, bed mattress
D3, mattress furniture

Parameters Attributing to relevancy of the post
Interface RankProvider {
}

TimeBasedRankProvider

CountBasedRankProvider


APIs

PublishResponse PostContent(PublishRequest);
PostResult FetchPost(String query)

Request/Response Model
PostResult {
    List<String> posts;
}


Service Layer


The/a -> clear

Inverted Index
Furniture -> (D1,4,<time>), (D3, 6, <time>)

Get top 100 out of it


Translation Post API
Post will be associated with a document id

Delegated
Break all words from the post
Filter works like a/the/quotes etc
Prepare a hashmap of Word to document id

Map<String, List<DocumentNode>> invertedPostMap;

DocumentNode {
    Int docId
    Int count;
    int publishedTimeEpoch;
}

// Initialize this invertedMap on startup
// Add to this inverted Map at realtime


Database Choice - Nosql (consistent, replicate)
<Key Value store>

Cache - Distributed cache like redis
Cache redis for a key

Updating redis via delegation flow


Operational Responsibility
Data availability

Front will have the load balancer
Cache might fail - that will lead to increase in latency
DB Might be overloaded with connections

Logging - logfile route hourly/daily to a ES cluster (visualization)
Metrics - publish metrics per min cloudwatch

NumberOfPosts Per Sec -> DDOS
DB Connection Metric - DB level

TimeMetric for Read Api -> total time for 1 read operation. Alarm on avg time per min
10 ms read latency, alarm > 100 ms

Alarms on Exceptions - by cache/db over ES cluster

Metrics around service usage ->
How many reqs is you service handling daily?


Round 4 High Level Design

Q1 Design a Video Streaming Service like Youtube

Solution1

Functional Requirements

  1. Upload the video
  2. Search/play the video (timeline)
  3. Manage the user
  4. comments/ratings
  5. Sharing the video over other platforms
  6. Video streaming in different qualities
  7. likes/dislikes
  8. Views for a video


Non Functional Requirement

  1. High availability - service should be available all the time
  2. Reliability - the videos should not be lost
  3. Read heavy so low latency
  4. We are ok with eventual consistency



Scaling Requirements
Uploads
1M uploads per month

Search
5M views per month
5M / 30*24*3600 views / sec

User Registration
1M users / month

Growth - 5%

Storage Requirement
1 video storage (compressed/uncompressed)
Avg size per video → 100 Mb
1M * 100 Mb = 100 Tb
Compression rate of 50% 50 Tb / month

600 Tb/ year

Metadata storage -> 500 Kb / video
500 kb * 1 M * 12 = 6 Tb / year


Metadata {
fileName
fileLocation
ThumbnailReference
}

Thumbnails
Per video we can have say 5 thumbnails.


Database/Storage Requirement
User registration - we can go with a sql database

Metadata and thumbnails
Eventually consistent key value store such as dynamodb
It will offer low latency for reads.

Store for actual thumbnails - s3

Video store will be a big data storage


Database Schema
How will the sharding be?

Shard them based on hash of a video id (these ids should be balanced/unique)
Writes will be balanced across all the shards
Read might overload 1 shard if say a video is viral. (use a cache layer to prevent this)

User registration - Sql database
Master - slave architecture
Challenge will be writes will not be reflected instantly on slaves.
Updates/write will be very less frequent.

Comments
The aim is ordering should be maintained.
If my database is eventually consistent,

A user entered a comment
my system takes the comment and sends success but internally i will retry to make sure that it is stored with the right timestamp.


2 replies happen at the same time
Both reply are present in the queue
Once update succeeds the id is incremented
The second reply will read the latest state, this latest state will have the new id and thus my second reply will be stored.


Schema for comments/replies

Video-id →  List<CommentId>

V1 → [c1, c2, c3, c4]

Hashkey - commentId
{
    commentId: string,
    Title: string,
    Description: string,
    lastUpdated: Timestamp,
    createdTime: Timestamp,
    replyIds: <CommentIds>,
    updateId: integer (0)
}
   
Write: <VideoId, Comment>

2 concurrent writes for the comment
C1 -> R1, R2

Extract the comment json
R1 -> replyIds(R1), updateId -> 1 - Accepted
R2 -> replyIds(R2), updateId -> 0 - Rejected (part of a queue)


How do you serve the video to users?
Service will be partitioned by region
A CDN associated with every region - help me service the thumbnails of the video
Hot store associated with internet gateways


Client -> InternetGateway -> CDN -> LB -> Webserver -> LB -> AppServer -> Cache -> Database


Video Deduplication
When-ever a video uploads, the upload will happen in chunks
Every chunk can pass through a de-dup process.

After compression, 2 chunks can have same properties. Return the reference of existing chunk

Separate service.

Viewing it in different resolutions
Store in different resolutions


Upload happens -> video is broken into chunks -> pass chunk to a encoder to change the format

Async Backend flow to cast the video to different formats
Client -> [Queue - chunk of the video] -> Q1, Q2, Q3, Q4 -> Appserver 


Round 5 Hiring Manager Round

Q1 Give detailed description of your current project?

Q2 Design a Coffee Vending Machine using OOPS. 

Solution

Q3 Given unsorted 100 million integers = 10 crore, Java process JVM  500 MB RAM, 32 core CPU
// input : file having these all numbers
// output : file sorted number

1 million integers = 4MB

Solution

Labels: , ,

No comments :

Post a Comment

Subscribe to: Post Comments ( Atom )