300+ SDE Interview Questions and Answers

Given an array and an integer, return all subsets that sum to the given integer.

• Use backtracking to generate all possible subsets of the array.

• For each subset, check if the sum equals the given integer 'K'.

• Print the subsets that satisfy the condition.

• Example: For input [1, 2, 3] and K=3, subsets [1, 2] and [3] have sum 3.

The problem involves dividing an array into K subsets with equal sum.

• Use backtracking to try all possible combinations of subsets.

• Keep track of the sum of elements in each subset and check if they are equal to the target sum.

• Optimize by sorting the array in descending order and assigning elements to subsets greedily.

• Handle edge cases like when the sum of elements is not divisible by K.

Sort a doubly linked list where each node's position deviates at most K positions from its position in the sorted list.

• Iterate through the doubly linked list and maintain a min-heap of size K+1 to keep track of the next smallest element.

• Remove the smallest element from the heap and add it to the sorted list. Update the heap with the next element from the removed node's next position.

• Continue this process until all nodes are added to the sorted list.

The longest continuous patch of a road being repaired by a contractor is determined.

• Iterate through the updates and keep track of the start and end points of each patch

• Calculate the length of each patch and update the longest patch if necessary

• Return the start and end points of the longest patch

Find the length of the longest strictly increasing subsequence in an array of integers.

• Use dynamic programming to keep track of the longest increasing subsequence ending at each element.

• Initialize an array to store the length of the longest increasing subsequence ending at each index.

• Iterate through the array and update the length of the longest increasing subsequence for each element.

• Return the maximum value in the array as the length of the longest increasing subsequence.

Find root values of duplicate subtrees in a binary tree.

• Traverse the tree in a bottom-up manner to identify duplicate subtrees.

• Use a hashmap to store the subtree structures and their frequencies.

• Return the root values of duplicate subtrees based on hashmap entries.

Merge k sorted linked lists into one single sorted linked list.

• Create a min-heap to store the heads of all linked lists.

• Pop the smallest element from the heap and add it to the result list.

• If the popped element has a next element, push it back to the heap.

• Repeat until all elements are merged into a single sorted list.

Reverse a singly linked list of integers and return the head of the reversed linked list.

• Iterate through the linked list and reverse the pointers to point to the previous node instead of the next node.

• Use three pointers - prev, current, and next - to keep track of the nodes while reversing the linked list.

• Update the head of the reversed linked list as the last node encountered during reversal.

Count the total number of inversions in an integer array.

• Iterate through the array and for each pair of elements, check if the conditions for inversion are met.

• Use a nested loop to compare each element with all elements to its right.

• Keep a count of the inversions found and return the total count at the end.

Given a hashmap M and an input string S, return an array of all possible mutations of S using M's substitutes.

• Iterate through each character in S and get its substitutes from M

• Use recursion to generate all possible combinations of substitutes for each character

• Time complexity: O(n^m) where n is the average number of substitutes per character and m is the length of S

• Space complexity: O(n^m) due to the number of possible combinations

• Optimization: Use memoization to store previo...read more

Boundary traversal of a binary tree in anti-clockwise direction starting from the root node.

• Implement a function to calculate the boundary traversal of a binary tree

• Include nodes from left boundary, leaf nodes, and right boundary in sequence

• Ensure only unique nodes are included in the output

• Print the boundary nodes separated by single spaces for each test case

Calculate the number of ways to reach the end of a snakes and ladders board using dice rolls and ladders.

• The board is represented as an n x n matrix, where each cell corresponds to a position.

• You start at position 1 and aim to reach position n^2.

• Each dice roll can result in moving 1 to 6 steps forward.

• Ladders allow you to jump from one position to another, effectively skipping some cells.

• Use dynamic programming to count the number of ways to reach each cell based on previous ...read more

A thread is a unit of execution within a process that can run independently and concurrently with other threads.

• Threads allow for concurrent execution of tasks within a program.

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

• Threads can communicate and synchronize with each other through shared data structures like locks and semaphores.

• Threads can improve performance by utilizing multiple CPU cores or by handling I/O operations asynchronously.

• E...read more

Given a list of numbers and symbols, provide an expression that evaluates to a target number.

• Use recursion to try all possible combinations of numbers and symbols

• Check for division by zero and negative numbers

• Return False if no expression evaluates to the target number

Measure the time from typing a URL to page load using network requests and timestamps.

• Use browser developer tools to monitor network requests and timestamps.

• Implement a JavaScript function to capture the time when the URL is entered.

• Send a dummy request after the page load to measure response time.

• Utilize performance APIs like 'performance.now()' for precise timing.

• Log the time taken for DNS resolution, TCP connection, and page rendering.

Merge two sorted arrays into one sorted array with one traversal.

• Use two pointers to track the current elements in arrays A and B.

• Compare the elements at the current pointers and insert the smaller one into array A.

• Move the pointer of the array from which the smaller element was inserted.

• Repeat the above steps until all elements are merged into array A.

A binary tree with 4 internal nodes has 5 leaf nodes.

• A binary tree with n internal nodes has n+1 leaf nodes.

• A leaf node is a node with no children.

• Count the number of leaf nodes to find the answer.

Given preorder and postorder traversal, find inorder traversal of a binary tree.

• The last element of postorder traversal is the root of the tree

• Find the root in preorder traversal and divide the tree into left and right subtrees

• Recursively find the inorder traversal of left and right subtrees

• Combine the inorder traversal of left subtree, root, and inorder traversal of right subtree

The program counts the number of tree structures that can be made using n nodes.

• Use dynamic programming to solve the problem efficiently

• Break down the problem into subproblems and store their solutions in an array

• Iterate through the array to calculate the number of tree structures

• The time complexity of the program is O(n^2)

Design a system using Max Heap to find the costliest element from a box when an element is picked.

• Implement a Max Heap data structure to store the elements in the box.

• Whenever an element is picked, the costliest element can be found at the root of the Max Heap.

• After picking an element, update the Max Heap by removing the root and reorganizing the heap.

• Ensure the Max Heap property is maintained during insertion and deletion operations.

• Example: If the box contains elements [5, ...read more

When a server receives an HTTP request, it interacts with the operating system, handles threading, thread pooling, synchronization, and hashing.

• Upon receiving an HTTP request, the server creates a new thread to handle the request.

• The operating system manages the allocation of system resources to the server process.

• Thread pooling is used to efficiently manage and reuse threads for handling multiple requests.

• Synchronization mechanisms like locks or semaphores are used to ensure...read more

Implement a data structure and algorithm to print all files in a directory, including sub-directories.

• Use an n-ary tree or stack to represent the directory structure

• Implement a BFS or DFS algorithm to traverse the directory and print files

• Handle sub-directories recursively

• Consider using a queue or stack to keep track of directories to visit

Keys in database management systems are unique identifiers for rows in a table.

• Keys ensure data integrity by enforcing uniqueness and relationships between tables.

• Primary key uniquely identifies each record in a table (e.g. employee ID).

• Foreign key establishes a link between two tables by referencing the primary key of another table.

Find row with maximum 1s in a sorted 2D array of 0s and 1s.

• Use binary search to find the first occurrence of 1 in each row.

• Calculate the number of 1s in each row using the index found in step 1.

• Keep track of the row with maximum number of 1s.

• Time complexity: O(m log n), where m is the number of rows and n is the number of columns.

Find minimum number of jumps required to reach end of array with max moves in right direction at each index.

• Use dynamic programming approach to solve the problem

• Maintain an array to store minimum number of jumps required to reach each index

• Traverse the array and update the minimum number of jumps for each index

• Return the minimum number of jumps required to reach the end of array

To get the mth element of a stack with n elements, without using another stack.

• Create a temporary variable to store the mth element

• Pop the top (n-m) elements from the stack and discard them

• Pop and store the mth element in the temporary variable

• Push back the discarded elements to the stack

• Return the temporary variable as the result

Program with 2 threads printing even and odd numbers in sequence. How to make it SMP safe?

• Use mutex locks to ensure only one thread accesses the shared resource (the number to be printed) at a time

• Use condition variables to signal when it's safe for the other thread to access the shared resource

• Use atomic variables to ensure that the shared resource is accessed atomically

• Use thread-safe data structures to store the shared resource

• Use thread-local storage to avoid contention b...read more