200+ SDE-2 Interview Questions and Answers

Determine the number of good quality bulbs remaining after 'N' rounds of a unique technique.

• Start with all bulbs on in the first round

• Toggle every 'i' bulb in 'i' round

• Count the bulbs that remain on after 'N' rounds

The task is to identify the total instances of equivalent prime groups given the number of hours in a day and the day divided into equal parts.

• Identify prime hours in each part of the day

• Find equivalent prime groups across different parts

• Output the total number of equivalent prime groups

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 data less than the node's data

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

• Recursively check if both left and right subtrees are also binary search trees

Construct a balanced binary search tree from a sorted array.

• Create a recursive function to construct the BST by selecting the middle element as the root.

• Recursively construct the left subtree with elements to the left of the middle element and the right subtree with elements to the right.

• Ensure that the constructed tree is balanced by maintaining the height difference of left and right subtrees at most 1.

Find the minimum number of jumps Bob needs to make from shop 0 to reach the final shop, or return -1 if impossible.

• Use a greedy approach to keep track of the farthest reachable shop from the current shop.

• If at any point the current shop is not reachable, return -1.

• Update the current farthest reachable shop as you iterate through the array.

Design a Least Recently Used (LRU) cache data structure that supports get and put operations with capacity constraint.

• Use a combination of hashmap and doubly linked list to implement the LRU cache.

• Keep track of the least recently used item and evict it when the cache reaches its capacity.

• Update the position of an item in the cache when it is accessed or updated.

• Handle both get and put operations efficiently to maintain the LRU property.

• Ensure the time complexity of get and pu...read more

Given pairs of integers, find the length of the longest pair chain where each pair follows the given condition.

• Sort the pairs based on the second element in ascending order.

• Iterate through the sorted pairs and keep track of the maximum chain length.

• Update the chain length if the current pair can be added to the chain.

• Return the maximum chain length as the result.

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 through the array.

Return the level order traversal of a binary tree in a single line for each test case.

• Use a queue to perform level order traversal of the binary tree

• Print the nodes in level order traversal separated by a single space

• Handle null nodes represented by '-1' in the input

Check if a given graph is bipartite by dividing its vertices into two independent sets.

• Create two sets 'U' and 'V' to store vertices based on their connections

• Use BFS or DFS to traverse the graph and assign vertices to sets

• Check if any edge connects vertices within the same set, if yes, the graph is not bipartite

The N Queens problem involves placing N queens on an N x N chessboard so that no two queens can attack each other.

• Use backtracking to explore all possible configurations of queen placements.

• Keep track of rows, columns, and diagonals to ensure no two queens are attacking each other.

• Print all valid configurations of queen placements.

Find total instances of equivalent prime groups in a day divided into equal parts.

• Iterate through each part of the day and check for prime pairs in different parts

• Use a helper function to check if a number is prime

• Ensure the day is evenly divided by parts and each prime group has hours from different parts

Find the minimum time required to rot all fresh oranges in a grid.

• Use Breadth First Search (BFS) to simulate the rotting process

• Track the time taken to rot all oranges and return it

• If any fresh oranges remain after simulation, return -1

• Handle edge cases like empty grid or no fresh oranges

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 from start to end cell.

• Keep track of visited cells and the number of dice throws required to reach each cell.

• Consider the presence of snakes and ladders while calculating the next possible moves.

• Return the minimum number of dice throws to reach the last cell, or -1 if unreachable.

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.

The task is to print the bottom view of a binary tree from left to right.

• Traverse the binary tree in level order and keep track of the horizontal distance of each node from the root.

• For each horizontal distance, update the node value in a map to get the bottom view nodes.

• Print the values of the map in sorted order of horizontal distance to get the bottom view sequence.

The task is to find the minimum number of operations required to convert one string into another using delete, replace, and insert operations.

• Use dynamic programming to solve the problem efficiently.

• Create a 2D array to store the minimum edit distance for substrings of the two input strings.

• Iterate through the strings and update the array based on the operations needed for each character.

• Return the value in the bottom right corner of the array as the minimum edit distance.

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 find the smallest substring in string S which contains all the characters present in string X.

• Iterate through string S and keep track of characters in X using a hashmap

• Use two pointers to maintain a sliding window with all characters from X

• Update the window size and start index when a valid window is found

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

Given an array of integers, find a subarray with a given sum S.

• Use a sliding window approach to find the subarray with the given sum.

• Keep track of the current sum and adjust the window based on the sum.

• Return the start and end indices of the subarray if found, otherwise return [-1, -1].

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

Find the smallest missing positive integer in an array efficiently.

• Iterate through the array and mark positive integers as visited using index as value

• Iterate through the marked array to find the first missing positive integer

• Handle negative numbers by ignoring them during marking process

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

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

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.