Tata 1mg Software Development Engineer Interview Questions and Answers for Experienced

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

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 to medium questions, Questions on DSA and Node.js.

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

Q1. Implementation of LRU cache
Ans. 
LRU cache is a data structure that stores the most recently used items, discarding the least recently used items when full.
• Use a doubly linked list to keep track of the order of items based on their usage.

• Use a hash map to quickly access items in the cache.

• When a new item is accessed, move it to the front of the linked list. If the cache is full, remove the item at the end of the list.
Answered by AI
Add your answer
Q2. Implementation of HashMap
Ans. 
HashMap is a data structure that stores key-value pairs and allows for fast retrieval of values based on keys.
• HashMap is implemented using an array of linked lists or a balanced tree to handle collisions.

• It uses a hash function to map keys to indices in the array.

• Example: HashMap<String, Integer> map = new HashMap<>(); map.put("key", 123); int value = map.get("key");
Answered by AI
Add your answer

3 Medium level dsa questions

Q1. Lld of cab booking system
Ans. 
The Low Level Design (LLD) of a cab booking system involves detailing the system architecture and components at a lower level of abstraction.
• Identify the main components of the system such as user interface, booking engine, payment gateway, and driver allocation algorithm.

• Define the interactions between these components and how data flows between them.

• Specify the data structures and algorithms used for efficient bookin...read more
Answered by AI
Add your answer
Q2. Discussion about online assesment
Add your answer

3 coding question
2 medium 1 hard

Q1. Online polling system based on OOPs
Add your answer
Q2. Explaining the above code
Add your answer

2 medium - question 1 array and 1 dp
1 med to hard - dynamic programming

Q1. System design LLD - Polling System
Add your answer
Q2. How to implement Concurrency in it.
Ans. 
Concurrency in software development allows multiple tasks to run simultaneously, improving performance and responsiveness.
• Use multithreading to execute multiple tasks concurrently

• Implement asynchronous programming to handle tasks that may take longer to complete

• Use synchronization techniques like locks and semaphores to manage access to shared resources

• Consider using thread pools to manage and reuse threads efficiently
Answered by AI
Add your answer

Dsa question based on dp