Tata 1mg Software Development Engineer Interview Questions and Answers

Round duration - 60 Minutes
Round difficulty - Easy

Q1. 
0/1 Knapsack Problem Statement
A thief is planning to rob a store and can carry a maximum weight of 'W' in his knapsack. The store contains 'N' items where the ith item has a weight of 'wi' and a value of...read more
Ans. 
Yes, the 0/1 Knapsack problem can be solved using dynamic programming with a space complexity of not more than O(W).
• Use a 1D array to store the maximum value that can be stolen for each weight capacity from 0 to W.

• Iterate through each item and update the array based on whether including the item would increase the total value.

• The final value in the array at index W will be the maximum value that can be stolen.
Answered by AI
Add your answer
Q2. 
Find the Second Largest Element
Given an array or list of integers 'ARR', identify the second largest element in 'ARR'.
If a second largest element does not exist, return -1.
Example:
Input:
ARR = [2,...read more
Ans. 
Find the second largest element in an array of integers.
• Iterate through the array to find the largest and second largest elements.

• Handle cases where all elements are identical.

• Return -1 if a second largest element does not exist.
Answered by AI
Add your answer

Round duration - 60 Minutes
Round difficulty - Easy

System Design Round

Q1. Design a system for Twitter, discussing its architecture, key components, and scalability considerations.
Ans. 
Design a scalable system for Twitter with key components and architecture.
• Use microservices architecture for scalability and fault isolation.

• Key components include user service, tweet service, timeline service, and notification service.

• Use a distributed database like Cassandra for storing tweets and user data.

• Implement a message queue like Kafka for handling real-time updates and notifications.

• Use a caching layer like ...read more
Answered by AI
Add your answer

Round duration - 30 Minutes
Round difficulty - Easy

It is just a formality

Easy to medium questions, Questions on DSA and Node.js.

Q1. Valid parenthesis
Add your answer
Q2. Three sum problem
Add your answer

Data Structures, Coding MCQs

Q1. What is Data Structure
Ans. 
Data structures are organized formats for storing, managing, and accessing data efficiently.
• 1. Types: Common data structures include arrays, linked lists, stacks, queues, trees, and graphs.

• 2. Arrays: Fixed-size collections of elements, e.g., [1, 2, 3, 4].

• 3. Linked Lists: Collections of nodes where each node points to the next, e.g., 1 -> 2 -> 3.

• 4. Stacks: Last-in, first-out (LIFO) structures, e.g., function call ...read more
Answered by AI
Add your answer
Q2. Write DFS Algorithm
Ans. 
Depth-First Search (DFS) is a graph traversal algorithm that explores as far as possible along each branch before backtracking.
• DFS uses a stack data structure, either explicitly or via recursion.

• It starts from a selected node and explores each branch before backtracking.

• Example: In a binary tree, DFS can be implemented using pre-order, in-order, or post-order traversal.

• DFS can be used to find connected components in a ...read more
Answered by AI
Add your answer

Easy level to Medium level

2 Easy questions of DSA

Q1. One DSA question
Add your answer
Q2. Normal discussion about tech stack
Add your answer

Q1. Tell about yourself
Add your answer
Q2. Why do you want to join digit?
Add your answer

Q1. Stock buy and sell with at most 2 transaction
Ans. 
Implement a solution to find the maximum profit from buying and selling stocks with at most 2 transactions.
• Use dynamic programming to keep track of maximum profit at each day with 0, 1, or 2 transactions.

• Consider the possibility of splitting the transactions into two separate parts.

• Calculate the maximum profit by iterating through the prices array and updating the maximum profit accordingly.
Answered by AI
Add your answer
Q2. Binary search to find target
Ans. 
Binary search is a divide and conquer algorithm that efficiently finds a target value in a sorted array.
• Divide the array in half and compare the target value with the middle element

• If the target is less than the middle element, search the left half. If greater, search the right half

• Repeat the process until the target is found or the subarray is empty
Answered by AI
Add your answer

Q1. General about project
Add your answer
Q2. Design paytm wallet
Ans. 
Design a digital wallet system similar to Paytm.
• Allow users to add money to their wallet using various payment methods like credit/debit cards, net banking, UPI, etc.

• Enable users to make payments for various services like mobile recharge, bill payments, online shopping, etc.

• Implement security measures like two-factor authentication, encryption of sensitive data, and regular security audits.

• Provide features like transac...read more
Answered by AI
Add your answer

Q1. What is thread ?
Ans. 
A thread is a lightweight process that can run concurrently with other threads within the same process.
• Threads allow for parallel execution of tasks within a single process.

• Threads share the same memory space and resources of the process they belong to.

• Threads can communicate with each other through shared memory or message passing.

• Examples: Java threads, POSIX threads (pthreads) in C/C++.
Answered by AI
Add your answer
Q2. Inter process communication and project?
Add your answer

Seat reservation system
bit manipulation
binary tree related

Q1. Bfs / dfs traversal question
Add your answer

Round duration - 60 minutes
Round difficulty - Easy

The round consisted of 2 coding Problems and it lasted for 60 minutes from 12:00 PM to 1:00 PM on Hackerearth.
Use of other IDEs was prohibited and video was on.

Q1. 
Implement indexOf Function
You are provided with two strings A and B. Your task is to find the index of the first occurrence of A within B. If A is not found in B, return -1.
Example:
Input:
A = "bc", ...read more
Ans. 
Implement a function to find the index of the first occurrence of one string within another string.
• Iterate through the second string and check if a substring of the same length as the first string matches the first string.

• Return the index of the first occurrence of the first string within the second string, or -1 if not found.

• Handle edge cases like empty strings or when the first string is longer than the second string
Answered by AI
Add your answer
Q2. 
Problem: Search In Rotated Sorted Array
Given a sorted array that has been rotated clockwise by an unknown amount, you need to answer Q queries. Each query is represented by an integer Q[i], and you must ...read more
Ans. 
Search for integers in a rotated sorted array efficiently.
• Implement binary search to find the target integer in the rotated array.

• Handle the rotation by checking which side of the array is sorted before performing binary search.

• Return the index of the target integer if found, else return -1.

• Time complexity of O(logN) is required for each query.
Answered by AI
Add your answer

Round duration - 60 minutes
Round difficulty - Medium

The round was conducted on Google Meet with 2 interviewers . They were friendly and helpful.
The timing was 12:00 to 1:00 PM.
Our Video was on .

Q1. 
Distinct Subsequences Problem Statement
You are given a string 'S' of length 'N' which may include duplicate alphabets. Your goal is to calculate the number of distinct subsequences in the string.
Exampl...read more
Ans. 
Calculate the number of distinct subsequences in a string with possible duplicates.
• Use dynamic programming to keep track of the count of distinct subsequences for each character in the string.

• Consider the cases where the current character is included or excluded in the subsequence.

• Handle duplicates by considering the previous occurrence of the character.

• Return the count of distinct subsequences modulo 10^9 + 7.
Answered by AI
Add your answer

Round duration - 60 minutes
Round difficulty - Easy

This was a Behavioral Round. It lasted for 45-50 minutes. It consisted of a discussion on my projects. The interviewer was very impressed by the way I explained my projects. She even appreciated me for that. This was followed by normal HR questions .Timing of This round was 4:00 PM to 5:00 PM