200+ SDE-2 Interview Questions and Answers

Count subarrays with sum divisible by K in an array.

• Iterate through the array and keep track of prefix sum modulo K.

• Use a hashmap to store the frequency of each prefix sum modulo K.

• For each prefix sum, increment the count by the frequency of (prefix sum - K) modulo K in the hashmap.

• Handle the case where prefix sum itself is divisible by K separately.

• Return the total count of subarrays with sum divisible by K.

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

The N Queens Problem involves finding all possible placements of N queens on an N x N chessboard without threatening each other.

• Use backtracking algorithm to explore all possible configurations.

• Keep track of rows, columns, and diagonals to ensure queens do not threaten each other.

• Generate all valid configurations and print them out.

The task is to find the Kth row of Pascal's Triangle given a non-negative integer K.

• Create an array to store the elements of the Kth row of Pascal's Triangle.

• Use the formula C(n, k) = C(n-1, k-1) + C(n-1, k) to calculate the elements.

• Return the array as the output.

The task is to determine the minimum number of platforms required at a railway station so that no train has to wait.

• Sort the arrival and departure times arrays in ascending order.

• Initialize two pointers, one for arrival and one for departure.

• Increment the platform count when a train arrives and decrement when it departs.

• Keep track of the maximum platform count needed.

• Return the maximum platform count as the minimum number of platforms needed.

Minimum number of operations to make all elements in the array equal by performing addition, subtraction, multiplication, or division.

• Iterate through the array to find the maximum and minimum values.

• Calculate the difference between the maximum and minimum values.

• The minimum number of operations needed is the difference between the maximum and minimum values.

The problem involves determining the number of similar string groups in a given list of strings based on a specific criteria.

• Iterate through each pair of strings in the list and check if they are similar based on the given criteria.

• Use a hash set to keep track of visited strings to avoid counting duplicates in the same group.

• Consider implementing a function to check if two strings are similar by allowing at most one swap of characters.

• Count the number of distinct groups of si...read more

The task is to determine and return the top view of a given Binary Tree of integers.

• The top view of a binary tree consists of all the nodes visible when the tree is viewed from the top.

• Identify the nodes that appear on the top when looking from above the tree.

• Output the top view as a space-separated list of node values from left to right.

The problem involves determining if a given pattern aligns with a list of words in the same sequence.

• Iterate through the pattern and words list simultaneously to check for matching sequences.

• Use a hashmap to store the mapping between characters in the pattern and words in the list.

• Compare the mappings to determine if the pattern and words align in the same sequence.

Recursively remove consecutive duplicate characters from a string.

• Use recursion to check if the current character is the same as the next character, if so, skip the next character

• Base case: if the string is empty or has only one character, return the string

• Recursive case: if the current character is the same as the next character, call the function recursively with the string excluding the next character

Given a phone number string, generate all possible words by mapping digits to letters on a T9 keypad.

• Create a mapping of digits to corresponding letters on a T9 keypad

• Use recursion to generate all possible combinations of letters for the input phone number

• Sort the generated strings in lexicographical order

Create a deep copy of a linked list with random pointers.

• Iterate through the original linked list and create a new node for each node in the list.

• Store the mapping of original nodes to their corresponding new nodes.

• Update the next and random pointers of the new nodes based on the mapping.

• Return the head of the newly created deep copied linked list.

Connect adjacent nodes at the same level in a binary tree by populating each node's 'next' pointer.

• Traverse the tree level by level using a queue.

• For each node, connect it to the next node in the queue.

• Set the 'next' pointer of the last node in each level to NULL.

• Use constant extra space and do not alter the node structure.

Find the duplicate number in an array of integers from 0 to (N-2).

• Iterate through the array and keep track of the frequency of each number using a hashmap.

• Return the number with a frequency greater than 1 as the duplicate number.

Reverse a given singly linked list by changing the links between nodes.

• Iterate through the linked list and reverse the links between nodes

• Use three pointers to keep track of the current, previous, and next nodes

• Update the links between nodes to reverse the list

• Return the head of the reversed linked list

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

Implement a function to determine the 'Count and Say' sequence after N iterations.

• Create a function that takes a positive integer N as input

• Generate the 'Count and Say' sequence for N iterations

• Return an array of strings representing the sequence after each iteration

Implement a circular queue based on given queries to insert and remove elements.

• Create a circular queue of size N to store elements.

• For query type 1, insert element X at the end of the nth queue.

• For query type 2, remove and return the element at the front of the nth queue.

• Return true if insertion is successful, false otherwise.

• Return -1 if the queue is empty during dequeue operation.

Design a bookmyshow system

• Design a system to book and manage movie tickets

• Consider features like seat selection, payment, and ticket cancellation

• Include user authentication and authorization

• Implement a database to store movie and theater information

• Consider scalability and performance of the system

Design a system like Pastebin for sharing text snippets

• Use a web application framework like Django or Flask for the backend

• Store text snippets in a database with unique URLs for each snippet

• Implement user authentication and permissions for private and public sharing

• Include features like syntax highlighting, expiration dates, and password protection

• Optimize for fast and efficient text retrieval and storage

Determine the minimum number of operations needed to transform one string into another by moving characters to the end.

• Iterate through each character in str1 and check if it matches the first character in str2. If it does, calculate the number of operations needed to move it to the end.

• If no match is found for the first character in str2, return -1 as transformation is not possible.

• Repeat the process for each test case and output the minimum number of operations needed for ea...read more

Check if a given integer is a power of two or not.

• Check if the given integer is greater than 0.

• Check if the given integer has only one set bit (i.e., it is a power of 2).

• Return true if the above conditions are met, else return false.

Approach to low-level system design involves understanding requirements, breaking down components, defining interfaces, and optimizing performance.

• Understand the requirements and constraints of the system

• Break down the system into smaller components/modules

• Define clear interfaces between components for communication

• Optimize performance by considering data structures, algorithms, and resource utilization

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.

Tilt the container until the liquid reaches the edge, then pour out half of it.

• Tilt the container slowly until the liquid reaches the edge

• Once the liquid is at the edge, pour out half of it

• This method works because the liquid will naturally settle at the lowest point, allowing you to estimate the halfway mark

Find the closest palindromic number to a given integer represented by a string.

• Convert the string to an integer and iterate to find the closest palindromic number.

• Check for palindromic numbers by reversing the digits and comparing with the original number.

• Handle cases where multiple closest palindromic numbers exist by choosing the smaller one.

Diamond Problem is a common issue in multiple inheritance in C++ where a class inherits from two classes that have a common base class.

• Diamond Problem occurs when a class inherits from two classes that have a common base class, leading to ambiguity in accessing members.

• It can be resolved in C++ using virtual inheritance, where the common base class is inherited virtually to avoid duplicate copies of base class members.

• Example: class A is inherited by classes B and C, and then...read more