Zomato | SDE 2 | R1
Summary
I encountered two technical problems during my Zomato SDE 2 interview: one on maximum bipartite matching and another on designing a search algorithm with highest matching frequency.
Full Experience
- You have a class with m boys and n girls who are attending an upcoming party. You need to determine the maximum number of boy-girl pairs that can be formed for the party.
You're given an m x n matrix called a grid where each element is either 0 or 1. If grid[i][j] == 1, this means the i-th boy can invite the j-th girl to the party. If grid[i][j] == 0, the i-th boy cannot invite the j-th girl.
The matching rules are: Each boy can invite at most one girl Each girl can accept at most one invitation from a boy Your task is to find the maximum number of successful invitations (matched pairs) possible.
For example, if you have 3 boys and 3 girls with a grid like:
[[1, 1, 0], [1, 0, 1], [0, 0, 1]]
Boy 0 can invite girls 0 or 1, boy 1 can invite girls 0 or 2, and boy 2 can only invite girl 2. The maximum number of matches would be 3 (boy 0 → girl 1, boy 1 → girl 0, boy 2 → girl 2).
- Design a Search algo which returns the result with highest matching frequency
Products - name, tags, description
Amul P1 - Amul Chocolate 1kg, Amul’s chocolates are good P2 - Amul, Paras P3 - X
Sol - Using inverted index and elastic search
Interview Questions (2)
You have a class with m boys and n girls who are attending an upcoming party. You need to determine the maximum number of boy-girl pairs that can be formed for the party.
You're given an m x n matrix called a grid where each element is either 0 or 1. If grid[i][j] == 1, this means the i-th boy can invite the j-th girl to the party. If grid[i][j] == 0, the i-th boy cannot invite the j-th girl.
The matching rules are: Each boy can invite at most one girl Each girl can accept at most one invitation from a boy Your task is to find the maximum number of successful invitations (matched pairs) possible.
For example, if you have 3 boys and 3 girls with a grid like:
[[1, 1, 0], [1, 0, 1], [0, 0, 1]]
Boy 0 can invite girls 0 or 1, boy 1 can invite girls 0 or 2, and boy 2 can only invite girl 2. The maximum number of matches would be 3 (boy 0 → girl 1, boy 1 → girl 0, boy 2 → girl 2).
Design a Search algo which returns the result with highest matching frequency
Products - name, tags, description
Amul P1 - Amul Chocolate 1kg, Amul’s chocolates are good P2 - Amul, Paras P3 - X