10+ Zomato Software Developer Intern Interview Questions and Answers

Design and implement a Least Frequently Used (LFU) Cache with put and get functionalities, handling capacity and frequency of use.

• Implement a LFU cache with put and get functions

• Handle capacity and frequency of use for eviction

• Return the value of key if present, -1 otherwise

• Consider multiple elements with least frequency, remove least recently used

• Example: Insert, update, and retrieve values based on operations

Given two sorted arrays, find the path through common elements for maximum sum.

• Start with the array containing the smaller first common element

• Switch arrays at common elements to maximize the sum

• Continue adding elements until the end of the arrays

Given an array of integers and a target, find all pairs of elements that add up to the target.

• Iterate through the array and for each element, check if the complement (target - current element) exists in a hash set.

• If the complement exists, add the pair to the result. If not, add the current element to the hash set.

• Handle cases where the same element is used twice in a pair by keeping track of the frequency of elements.

• Return (-1, -1) if no pair is found.

• Time complexity: O(N),...read more

Convert a binary tree into a sum tree where each node's value is replaced by the sum of its left and right subtrees.

• Traverse the tree in postorder fashion to calculate the sum of left and right subtrees for each node.

• Set leaf nodes to zero.

• Update the node values with the sum of left and right subtrees.

Reverse groups of K nodes in a doubly linked list

• Iterate through the linked list in groups of size K

• Reverse each group of nodes

• Handle cases where the number of remaining nodes is less than K

Calculate the area of the largest rectangle that can be formed within the bounds of a given histogram.

• Iterate through the histogram bars and maintain a stack to keep track of increasing heights.

• Calculate the area of the rectangle formed by each bar as the smallest height in the stack multiplied by the width.

• Update the maximum area found so far and return it as the result.

Count the number of islands in a 2D matrix of 1s and 0s.

• Use Depth First Search (DFS) or Breadth First Search (BFS) to traverse the matrix and identify connected groups of 1s.

• Maintain a visited array to keep track of visited cells to avoid redundant traversal.

• Increment the island count each time a new island is encountered.

• Consider all eight possible directions for connectivity between cells.

• Handle edge cases such as boundary conditions and invalid inputs.

• Example: For the give...read more

Find the minimum number of dice throws required to reach the last cell on a Snake and Ladder board.

• Use Breadth First Search (BFS) algorithm to find the shortest path on the board.

• Create a mapping of each cell to its next possible moves based on dice outcomes.

• Consider the snakes and ladders on the board while calculating the next possible moves.

• Track the number of dice throws needed to reach each cell and update it as you explore the board.

• Return the minimum number of throws n...read more

Implement a function to delete a node at a given position in a Doubly Linked List.

• Traverse to the node at the specified position in the Doubly Linked List.

• Adjust the pointers of the previous and next nodes to remove the node at the specified position.

• Update the pointers accordingly to maintain the integrity of the Doubly Linked List.

• Handle edge cases such as deleting the head or tail node.

• Ensure to free the memory of the deleted node to avoid memory leaks.

Polymorphism is the ability of a function or method to behave differently based on the object it is called on.

• Polymorphism allows objects of different classes to be treated as objects of a common superclass.

• Real-time polymorphism is achieved through method overloading, where multiple methods have the same name but different parameters.

• Run-time polymorphism is achieved through method overriding, where a subclass provides a specific implementation of a method defined in its sup...read more

SQL query to find the X percentile of students

• Use the NTILE() function to divide students into X groups

• Calculate the total number of students and the number of students in each group

• Select the students from the group that corresponds to the X percentile