SDE - Intern Zomato interview experience | Anonymous

Interview rounds

Round

Medium

Online Coding Test

Duration60 minutes

Interview date2 Nov 2021

Coding problem2

2 coding questions

1. Unique Paths II

Moderate

25m average time

70% success

0/80

Asked in companies

Given a ‘N’ * ’M’ maze with obstacles, count and return the number of unique paths to reach the right-bottom cell from the top-left cell. A cell in the given maze has a value '-1' if it is a blockage or dead-end, else 0. From a given cell, we are allowed to move to cells (i+1, j) and (i, j+1) only. Since the answer can be large, print it modulo 10^9 + 7.

For Example :

Consider the maze below :
0 0 0 
0 -1 0 
0 0 0

There are two ways to reach the bottom left corner - 

(1, 1) -> (1, 2) -> (1, 3) -> (2, 3) -> (3, 3)
(1, 1) -> (2, 1) -> (3, 1) -> (3, 2) -> (3, 3)

Hence the answer for the above test case is 2.

Problem approach

The most efficient solution to this problem can be achieved using dynamic programming. Like every dynamic problem concept, we will not recompute the subproblems. A temporary 2D matrix will be constructed and value will be stored using the top-down approach.

Try solving now

2. Allocate Books

Hard

0/120

Asked in companies

You are the Librarian of the Ninja library. There are ‘N’ books available in the library and ‘B’ ninjas want to read the books. You know the number of pages in each book and you have to allocate the books to the ‘B’ ninjas in such a way that the maximum number of pages allocated to a ninja is minimum.

Note

A book will be allocated to exactly one ninja. 
At least one book has to be allocated to a ninja.
Allotment of the books should be done in a contiguous manner. For example, a ninja can not be allocated book 2 and book 4, skipping book 3.

The task is to return the minimum of the maximum number of pages allocated to a ninja.

Problem approach

The idea is to use Binary Search. We fix a value for the number of pages as mid of current minimum and maximum. We initialize minimum and maximum as 0 and sum-of-all-pages respectively. If a current mid can be a solution, then we search on the lower half, else we search in higher half.

Try solving now

Round

Easy

Face to Face

Duration60 minutes

Interview date4 Nov 2021

Coding problem2

The interviewer started with asking my intro and then asked 2 DSA question.

1. Partition String

Moderate

25m average time

75% success

0/80

Asked in companies

Given a string S of lowercase English letters, your task is to partition the list in as many parts as possible such that each letter appears in at most one part, and return a list of integers representing the size of these parts.

Note

You don’t have to print anything, it has already been taken care of. Just implement the function. 
The string will contain lowercase alphabets only.

Try solving now

2. Largest rectangle in a histogram

Hard

25m average time

75% success

0/120

Asked in companies

You have been given an array/list 'HEIGHTS' of length ‘N. 'HEIGHTS' represents the histogram and each element of 'HEIGHTS' represents the height of the histogram bar. Consider that the width of each histogram is 1.

You are supposed to return the area of the largest rectangle possible in the given histogram.

For example :

In the below histogram where array/list elements are {2, 1, 5, 6, 2, 3}.

The area of largest rectangle possible in the given histogram is 10.

Problem approach

By finding next smaller element and previous smaller element for every element in O(n) time complexity and O(n) auxiliary space .

Try solving now

Round

Medium

Face to Face

Duration60 minutes

Interview date19 Nov 2021

Coding problem1

As the round is only for 40-45 minutes, he told me not to write the code. Then he told me about his work at zomato and his recent achievements. I asked a few doubts regarding his work and how did they tackle a few problems (about the search option in the Zomato app as the interviewer worked on this particularly). This discussion went on for another 5 minutes and he ended the interview by adding a few points on work culture at zomato.

1. LRU Cache Implementation

Moderate

25m average time

65% success

0/80

Asked in companies

Design and implement a data structure for Least Recently Used (LRU) cache to support the following operations:

1. get(key) - Return the value of the key if the key exists in the cache, otherwise return -1.

2. put(key, value), Insert the value in the cache if the key is not already present or update the value of the given key if the key is already present. When the cache reaches its capacity, it should invalidate the least recently used item before inserting the new item.

You will be given ‘Q’ queries. Each query will belong to one of these two types:

Type 0: for get(key) operation.
Type 1: for put(key, value) operation.

Note :

1. The cache is initialized with a capacity (the maximum number of unique keys it can hold at a time).

2. Access to an item or key is defined as a get or a put operation on the key. The least recently used key is the one with the oldest access time.

Problem approach

When a page is referenced, the required page may be in the memory. If it is in the memory, we need to detach the node of the list and bring it to the front of the queue.
If the required page is not in memory, we bring that in memory. In simple words, we add a new node to the front of the queue and update the corresponding node address in the hash. If the queue is full, i.e. all the frames are full, we remove a node from the rear of the queue, and add the new node to the front of the queue.

Try solving now