BigBasket SDE-2 Interview Questions and Answers

Round duration - 60 minutes
Round difficulty - Easy

Timing: evening
Environment: Online round took at home

Q1. 
Smallest Subarray with K Distinct Elements Problem
Given an array A consisting of N integers, find the smallest subarray of A that contains exactly K distinct integers.
Input:
The first line contains tw...read more
Ans. 
Find the smallest subarray with exactly K distinct integers in an array.
• Use a sliding window approach to keep track of the subarray with K distinct integers.

• Use a hashmap to store the frequency of each integer in the current window.

• Update the window size based on the number of distinct integers found.

• Keep track of the smallest subarray meeting the criteria.

• Return the starting and ending indices of the smallest subarray...read more
Answered by AI
View 1 more answer

Round duration - 90 minutes
Round difficulty - Medium

Machine coding round

Round duration - 60 minutes
Round difficulty - Medium

Q1. 
Rat In a Maze Problem Statement
Given a N * N maze with a rat placed at position MAZE[0][0], find and print all possible paths for the rat to reach its destination at MAZE[N-1][N-1]. The rat is allowed to...read more
Ans. 
The problem involves finding all possible paths for a rat to reach its destination in a maze.
• Use backtracking to explore all possible paths in the maze.

• Mark visited cells to avoid revisiting them.

• Return the path once the destination is reached.

• Handle edge cases like blocked cells and out-of-bounds movements.
Answered by AI
View 1 more answer

Round duration - 60-90 minutes
Round difficulty - Medium

Round duration - 60 minutes
Round difficulty - Medium

Hiring Manager round

Round duration - 60 minutes
Round difficulty - Medium

It was a telephonic interview at 10 in the morning. Interviewer seemed cool.

Q1. 
Best Insert Position for a Target in a Sorted Array
You are provided with a sorted array A of length N consisting of distinct integers and a target integer M. Your task is to determine the position where ...read more
Ans. 
Find the best insert position for a target in a sorted array to maintain order.
• Use binary search to find the correct position for the target integer in the sorted array.

• If the target is already present in the array, return its index.

• Maintain the sorted order of the array after inserting the target integer.

• Handle edge cases like empty array or target being smaller than the first element or larger than the last element.
Answered by AI
Add your answer

Round duration - 60 minutes
Round difficulty - Medium

The interview was in the morning at 10 AM in the office meeting room.

Q1. 
House Robber Problem Statement
Mr. X is a professional robber with a plan to rob houses arranged in a circular street. Each house has a certain amount of money hidden, separated by a security system that ...read more
Ans. 
House Robber problem - find maximum amount of money Mr. X can rob without triggering alarm in circular street.
• Use dynamic programming to keep track of maximum money robbed at each house.

• Consider two cases - robbing the first house and not robbing the first house.

• Handle circular arrangement by considering the first and last houses separately.

• Return the maximum amount of money that can be robbed without triggering the al...read more
Answered by AI
Add your answer

Round duration - 60 minutes
Round difficulty - Medium

The interview was at 11 AM in the meeting office.

Q1. 
Running Median Problem
Given a stream of integers, calculate and print the median after each new integer is added to the stream.
Output only the integer part of the median.
Example:
Input:
N = 5  
Stre...read more
Ans. 
Calculate and print the median after each new integer is added to the stream.
• Use a min heap to store the larger half of the numbers and a max heap to store the smaller half of the numbers.

• Keep the two heaps balanced by ensuring the size difference is at most 1.

• If the total number of elements is odd, the median is the top element of the larger heap. If even, it's the average of the tops of both heaps.
Answered by AI
Add your answer

Round duration - 60 minutes
Round difficulty - Medium

The interview was at 1 AM.

Round duration - 60 minutes
Round difficulty - Easy

The meeting was at 2 PM in the office meeting room.

Round duration - 60 minutes
Round difficulty - Easy

10 AM

Q1. Can you provide a deeper discussion about all the projects you completed in your previous company?
Add your answer

Round duration - 60 mins
Round difficulty - Medium

3 Questions were asked : 2- Trees and 1- Stack.
Interviewer was not receptive at all, I think this was a stress interview.

Q1. 
Validate Binary Search Tree Problem Statement
Given a binary tree with 'N' nodes, determine if it is a Binary Search Tree (BST). Return true if the tree is a BST, otherwise return false.
Example:
Input:
...read more
Ans. 
Validate if a given binary tree is a Binary Search Tree (BST) or not.
• Check if the left subtree of a node contains only nodes with values less than the node's value.

• Check if the right subtree of a node contains only nodes with values greater than the node's value.

• Ensure that both the left and right subtrees are also binary search trees.

• Traverse the tree in-order and check if the elements are in sorted order.

• Use a recurs...read more
Answered by AI
Add your answer
Q2. 
Binary Tree Conversion to Greater Tree
Given a binary tree with 'N' nodes, transform it into a Greater Tree. In this transformation, each node's value should be updated to the sum of its original value and...read more
Ans. 
Convert a binary tree into a Greater Tree by updating each node's value to the sum of its original value and the values of all nodes greater than or equal to it.
• Traverse the tree in reverse inorder (right, root, left) to update the nodes' values.

• Keep track of the sum of nodes visited so far to update each node's value.

• Recursively update the node's value by adding the sum of greater nodes to it.
Answered by AI
Add your answer
Q3. 
Check for Valid Parentheses
You are given a string STR containing only the characters "{", "}", "(", ")", "[", and "]". Your task is to determine if the parentheses in the string are balanced.
Input:
Th...read more
Ans. 
Check if the given string containing only parentheses is balanced or not.
• Use a stack to keep track of opening parentheses.

• Iterate through the string and push opening parentheses onto the stack.

• When a closing parenthesis is encountered, pop from the stack and check if it matches the corresponding opening parenthesis.

• If at the end the stack is empty, return 'YES' else return 'NO'.
Answered by AI
Add your answer

Round duration - 60 mins
Round difficulty - Hard

2 Coding Questions were asked, both were of Medium to Hard Difficulty.

Q1. 
Flatten Multi-Level Linked List
You are given a multi-level linked list containing 'N' nodes. Each node has 'next' and 'child' pointers that may or may not point to other nodes. Your task is to flatten th...read more
Ans. 
Flatten a multi-level linked list into a single linked list by rearranging the pointers.
• Traverse the linked list and whenever a node has a child, flatten the child list and append it after the current node.

• Update the 'next' and 'child' pointers accordingly while flattening the list.

• Continue this process until all nodes are rearranged into a single linked list.
Answered by AI
Add your answer
Q2. 
Rain Water Trapping Problem Statement
Given an array/list ARR of size N, representing an elevation map where each element ARR[i] denotes the elevation of the i-th bar. Your task is to calculate and print ...read more
Ans. 
Calculate the total amount of rainwater that can be trapped between given elevations in an elevation map.
• Use two-pointer approach to keep track of left and right boundaries.

• Calculate the trapped water by finding the minimum of left_max and right_max for each bar.

• Subtract the current bar's height from the minimum of left_max and right_max to get the trapped water.

• Keep updating the left_max and right_max as you iterate t...read more
Answered by AI
Add your answer

Round duration - 90 minutes
Round difficulty - Medium

Timing : It was late night.
How the interviewer was? He was very tired and I had to lead the discussion.
1 System Design Question was asked, had to provide - HLD, LLD, APIs.

Round duration - 60 minutes
Round difficulty - Medium

Timing : Afternoon
How was the environment? Home
Interviewer : Hiring Manager

Q1. Hiring Manager Discussion
Discussed about past Projects, challenges faced, disagreements with manager, why looking for job switch,  leadership principle questions were asked.
Add your answer

Round duration - 60 minutes
Round difficulty - Medium

Timing - Afternoon
How was the environment? Home
How the interviewer was? Very Helpful Interviewer
Bar raiser Round - Coding + System Design + Leadership principle

Diameter of a binary tree and bfs and dfs questions

Data structure and algorithms

Q1. System design questions
Add your answer

Round duration - 90 minutes
Round difficulty - Easy

I got a call from an Amazon recruiter regarding the schedule of the test . She sent me the coding test link which I had to complete within a week. we can attempt the online test anytime, when we have time for a period of 90 minutes at a stretch.Once I completed the test, I got a call to schedule the interviews in two weeks.

Q1. 
Shopping Options Problem Statement
Given arrays representing the costs of pants, shirts, shoes, and skirts, and a budget amount 'X', determine the total number of valid combinations that can be purchased ...read more
Ans. 
Determine total number of valid shopping combinations within budget
• Iterate through all possible combinations of items from each array

• Check if the total cost of the combination is within the budget

• Return the count of valid combinations
Answered by AI
Add your answer
Q2. 
Max Submatrix Problem Statement
You are provided with a matrix MAT consisting of integers, with dimensions N x M (i.e., N rows and M columns). Your objective is to determine the maximum sum submatrix with...read more
Ans. 
Find the maximum sum submatrix in a given matrix.
• Iterate over all possible submatrices and calculate their sums

• Use Kadane's algorithm to find the maximum sum subarray in each row

• Combine the sums of rows to find the maximum sum submatrix
Answered by AI
Add your answer

Round duration - 60 minutes
Round difficulty - Medium

Virtual interview occured in amazon chime.The interviewer gave his introduction, asked me a bit on the kind of projects I’ve worked on. Then he started with a data structure problem.

Q1. 
Clone a Binary Tree with Random Pointers
Given a binary tree where each node has pointers to its left, right, and a random node, create a deep copy of the binary tree.
Input:
The first line contains an ...read more
Ans. 
Clone a binary tree with random pointers and verify if cloning was successful by printing inorder traversal.
• Create a deep copy of the binary tree with random pointers.

• Print the inorder traversal of the cloned binary tree.

• Verify cloning success by printing '1' if successful, '0' otherwise.
Answered by AI
Add your answer
Q2. 
The Ninja Port Problem
Ninja is in a city with 'N' colonies, where each colony contains 'K' houses. He starts at house number "sourceHouse" in colony number "sourceColony" and wants to reach house number ...read more
Ans. 
The Ninja Port Problem involves finding the minimum time for a ninja to travel between colonies and houses using secret paths and teleportation.
• Calculate the minimum time considering teleportation within colonies, traveling between colonies, and secret paths.

• Keep track of the number of secret paths used and ensure they are one-way.

• Consider the constraints provided to optimize the solution.

• Example: N=2, K=3, S=1, P=1, s...read more
Answered by AI
Add your answer

Round duration - 75 Minutes
Round difficulty - Easy

This was taken by an engineering manager who asked me regarding my projects for around 10-15 mins and then we moved to a system design problem. He asked me to design Slack messenger.
I started by listing the functional and non-functional requirements(on which he questioned me a bit), then I moved to draw the high-level architecture. The components which I drew were the clients, gateway service(LB + authentication, etc), Messaging Service, User Service, Web Socket Manager service, Fan Out service(I added this for the group messages thing, but he didn’t interrogate much on that).

He asked me what would be the schema of my messages table and the scenarios in which the recipient user is online/offline.Also asked about the partitioning key and primary key of the 2-3 tables which I had made

Round duration - 60 minutes
Round difficulty - Hard

BarRaiser Round

This was again taken by an engineering manager who discussed my projects in depth for around 20-25 mins. In the remaining time he asked me 2 dsa questions. (Yes I too was surprised that he didn’t ask anything regarding design).

In almost all the rounds, I was asked questions related to Amazon Leadership principles, so do make sure you go through those before sitting for the interview process. You can refer to this link(https://www.codingninjas.com/codestudio/problem-lists/top-amazon-coding-interview-questions) for practicing the same, I found it useful. 
In the design rounds, interviewer doesn’t expect the most ideal answer from you and unless your choice of technology is outrageously wrong, he won’t pinpoint that.

Q1. 
Group Anagrams Together
Given an array/list of strings STR_LIST, group the anagrams together and return each group as a list of strings. Each group must contain strings that are anagrams of each other.
E...read more
Ans. 
Group anagrams together in a list of strings.
• Iterate through the list of strings and sort each string to group anagrams together.

• Use a hashmap to store the sorted string as key and the original string as value.

• Return the values of the hashmap as the grouped anagrams.
Answered by AI
Add your answer
Q2. 
Add Two Numbers Represented by Linked Lists
Your task is to find the sum list of two numbers represented by linked lists and return the head of the sum list.
Explanation:
The sum list should be a linked...read more
Ans. 
Add two numbers represented by linked lists and return the head of the sum list.
• Traverse both linked lists simultaneously while keeping track of carry from previous sum

• Create a new linked list to store the sum of the two numbers

• Handle cases where one linked list is longer than the other by padding with zeros

• Update the sum and carry values accordingly while iterating through the linked lists
Answered by AI
Add your answer

Round duration - 90 minutes
Round difficulty - Medium

Q1. 
Number of Islands Problem Statement
You are provided with a 2D array or list containing 'N' rows and 'M' columns, filled with 1s and 0s. Here, 1 indicates land, and 0 indicates water.
Your task is to ide...read more
Ans. 
Count the number of islands in a 2D matrix filled with 1s and 0s.
• Iterate through the matrix and perform depth-first search (DFS) to find connected islands.

• Use a visited array to keep track of visited cells to avoid redundant calculations.

• Increment the island count whenever a new island is encountered.

• Consider all eight directions (horizontal, vertical, and diagonal) while exploring the island.

• Handle edge cases like out...read more
Answered by AI
Add your answer
Q2. 
Add First and Second Half Problem Statement
You are provided with a Singly Linked List having 'N' nodes, where each node contains a single digit.
Your task is to return a node 'X', which serves as the he...read more
Ans. 
Return a node representing the head of a new Linked List with the sum of the 1st and 2nd half of the given Linked List.
• Split the Linked List into two halves

• Reverse the 2nd half of the Linked List

• Add the corresponding digits from both halves while considering carry

• Create a new Linked List with the sum digits
Answered by AI
Add your answer

Round duration - 60 minutes
Round difficulty - Medium

Q1. 
Next Greater Element Problem Statement
You are given an array arr of length N. For each element in the array, find the next greater element (NGE) that appears to the right. If there is no such greater ele...read more
Ans. 
The task is to find the next greater element for each element in an array to its right, if no greater element exists, return -1.
• Use a stack to keep track of elements for which the next greater element is not found yet.

• Iterate through the array from right to left, popping elements from the stack until a greater element is found.

• Store the next greater element for each element in a separate array.

• If the stack is empty aft...read more
Answered by AI
Add your answer

Round duration - 60 Minutes
Round difficulty - Hard

Q1. 
Word Break Problem Statement
You are given a non-empty string without spaces, referred to as 'sentence', and a list of non-empty strings representing a dictionary. Your task is to construct and return all...read more
Ans. 
Given a sentence and a dictionary, construct and return all possible sentences by inserting spaces to form words from the dictionary.
• Use backtracking to generate all possible combinations of words from the dictionary to form sentences.

• Check if a substring of the sentence matches any word in the dictionary, if so, recursively call the function with the remaining substring.

• Continue this process until the entire sentence ...read more
Answered by AI
Add your answer
Q2. 
Valid Parenthesis Problem Statement
Given a string str composed solely of the characters "{", "}", "(", ")", "[", and "]", determine whether the parentheses are balanced.
Input:
The first line contains ...read more
Ans. 
Check if given string of parentheses is balanced or not.
• Use a stack to keep track of opening parentheses and pop when a closing parenthesis is encountered.

• If stack is empty at the end and all parentheses are matched, the string is balanced.

• If stack is not empty at the end or mismatched parentheses are encountered, the string is not balanced.
Answered by AI
Add your answer

Round duration - 60 minutes
Round difficulty - Easy

Q1. Design a local transport system similar to BMTC.
Ans. 
Design a local transport system similar to BMTC
• Introduce a fleet of buses covering various routes within the city

• Implement a smart card system for easy payment and tracking

• Include different types of buses like regular, AC, and Volvo for passenger comfort

• Have designated bus stops with real-time information on bus arrivals

• Offer discounted fares for students and senior citizens
Answered by AI
Add your answer

Round duration - 60 minutes
Round difficulty - Easy

Round duration - 60 minutes
Round difficulty - Easy

Started with brief intro(5 mins) about interviewer.
Problem solving question, question was already there in the codelink shared by the interviewer. He explained the problem again with sample testcase. 
The Interviewer was friendly.

Q1. 
Course Schedule II Problem Statement
You are provided with a number of courses 'N', some of which have prerequisites. There is a matrix named 'PREREQUISITES' of size 'M' x 2. This matrix indicates that fo...read more
Ans. 
Given courses with prerequisites, determine a valid order to complete all courses.
• Create a graph with courses as nodes and prerequisites as edges.

• Use topological sorting to find a valid order to complete all courses.

• Return an empty list if it's impossible to complete all courses.
Answered by AI
Add your answer
Q2. Design a live video broadcast platform.
Ans. 
Design a live video broadcast platform.
• Implement video streaming functionality using protocols like RTMP or WebRTC

• Include features for live chat, reactions, and audience engagement

• Ensure scalability and reliability by using cloud services like AWS or Azure

• Provide analytics for viewership data and user engagement

• Integrate monetization options such as ads or subscriptions
Answered by AI
Add your answer

Round duration - 90 minutes
Round difficulty - Medium

There were 2 interviewers(India HM and Seattle HM), India HM was just shadowing and didn't ask any questions. Started with intro, he asked in detail about what I do at current company(10 mins). Again, jumped into LP's(25 mins).

Q1. 
Distance Between Two Nodes in a Binary Tree
Given a binary tree and the values of two distinct nodes, determine the distance between these two nodes in the tree. The distance is defined as the minimum num...read more
Ans. 
Calculate the distance between two nodes in a binary tree.
• Traverse the tree to find the paths from the root to each node

• Find the lowest common ancestor of the two nodes

• Calculate the distance by summing the distances from each node to the common ancestor
Answered by AI
Add your answer
Q2. 
Median in a Stream Problem Statement
Your task is to determine the median of integers as they are read from a data stream. The median is the middle value in the ordered list of numbers. If the list length...read more
Ans. 
Find median of integers in a data stream as they are read.
• Use two heaps - max heap for lower half of numbers and min heap for upper half.

• Keep the size of two heaps balanced to find the median efficiently.

• Handle even and odd number of elements separately to calculate median.

• Return vector of medians after each element is read from the stream.
Answered by AI
Add your answer

Round duration - 60 minutes
Round difficulty - Medium

There was only 1 interviewer in this round and We had no video sharing in this round so it was becoming difficult to understand each other.