200+ 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.

Given start and end times of meetings, find the maximum number of meetings that can be scheduled in a single room.

• Sort the meetings based on their end times in ascending order.

• Iterate through the sorted meetings and select the ones that do not overlap with the previously selected meetings.

• Keep track of the selected meetings and return their indices.

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.

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.

Arrange nuts and bolts so that every nut fits perfectly with the bolt in the same position.

• Sort both arrays in the same order using a comparison function

• Use a binary search to find the matching bolt for each nut

• Repeat until all nuts are matched with bolts

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

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

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 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

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.

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

Minimum comparisons needed to find median in unsorted array of size n

• For odd n, median is the middle element. For even n, median is the average of middle two elements

• Minimum comparisons needed for odd n is (n-1)/2. For even n, it is n/2

• Various sorting algorithms can be used to find median in an unsorted array

Program to determine if a graph is a tree using adjacency matrix

• A graph is a tree if it is connected and has no cycles

• Check if the graph is connected by performing a depth-first search or breadth-first search

• Check if the graph has cycles by performing a depth-first search and tracking visited nodes

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

Copying fixed number of bytes from source to destination and its test cases.

• Ensure source and destination are not overlapping

• Check if the number of bytes to be copied is greater than the available space in the destination

• Handle cases where source or destination is NULL

• Test cases should cover all possible scenarios including edge cases

Given a sorted array with repeated elements, find the occurrence of a given element using binary search.

• Use binary search to find the first occurrence of the element

• Use binary search to find the last occurrence of the element

• Calculate the occurrence by subtracting the indices of the last and first occurrences and adding 1

Hashing is a technique to map data to a fixed-size table. Time complexity of searching a hash table is O(n) in worst case.

• Hashing is used to store and retrieve data quickly

• It uses a hash function to map data to a fixed-size table

• In the best case, searching a hash table takes O(1) time

• In the worst case, all the data maps to the same index and searching takes O(n) time

• Collision resolution techniques like chaining and open addressing are used to handle collisions

Functional relations in DBMS define a relationship between input and output values where each input has a unique output.

• Functional relations ensure that each input value maps to only one output value.

• They are commonly used in database design to enforce data integrity and consistency.

• For example, in a table storing employee information, the employee ID can be a functional key that uniquely identifies each employee.

The number of swaps required to sort an array using bubblesort

• Bubble sort compares adjacent elements and swaps them if they are in the wrong order

• Count the number of swaps required to sort the given array

• The given array requires 19 swaps to be sorted using bubblesort

An array of key-value pairs is the best data structure for a dictionary.

• Use a hash table or a balanced tree to implement the dictionary.

• Keys should be unique and immutable.

• Values can be any data type.

• Access time should be O(1) or O(log n) depending on the implementation.

• Examples: Python's dict, Java's HashMap, C++'s unordered_map.

Time complexity to find an element in an alternatively sorted array.

• The time complexity will be O(log n) using binary search.

• Check the middle element and compare with the target element.

• If the middle element is greater than the target, search in the left half of the array.

• If the middle element is smaller than the target, search in the right half of the array.

• Repeat until the target element is found or the array is exhausted.

iOS manual memory management requires developers to manually allocate and deallocate memory for objects.

• Developers must manually allocate memory for objects using methods like alloc and init.

• Developers must also manually deallocate memory for objects using methods like release.

• Failure to properly manage memory can lead to memory leaks and crashes.

• ARC (Automatic Reference Counting) was introduced in iOS 5 to automate memory management.

• However, manual memory management is still...read more

Program to print powerset of a given set

• Create an empty list to store subsets

• Loop through all possible binary numbers from 0 to 2^n-1 where n is the length of the set

• For each binary number, convert it to binary and use the 1's as indices to select elements from the set

• Add the selected elements to the list of subsets

• Return the list of subsets

The transaction process involves transferring funds from one account to another. A scheme is designed to ensure secure and accurate transfers.

• Verify the availability of sufficient funds in the sender's account

• Authenticate the sender's identity and authorization for the transaction

• Deduct the transfer amount from the sender's account balance

• Initiate a request to transfer the funds to the recipient's account

• Validate the recipient's account details

• Add the transferred amount to th...read more

Sort a linked list by nodes whose alternate nodes are already sorted.

• Traverse the linked list and identify the alternate nodes.

• Sort the alternate nodes using any sorting algorithm.

• Merge the sorted alternate nodes back into the original linked list.

Graphs are non-linear data structures with cycles while trees are hierarchical data structures without cycles.

• Graphs can have cycles while trees cannot

• Graphs can have multiple root nodes while trees have only one

• Graphs can have disconnected components while trees are always connected

• Graphs can have directed or undirected edges while trees have only directed edges

• Examples of graphs include social networks, road networks, and computer networks while examples of trees include fi...read more

The first declaration casts i to int pointer and dereferences it, while the second declaration casts the address of i to int pointer and dereferences it.

• The first declaration assumes i is already an int pointer.

• The second declaration takes the address of i and casts it to an int pointer.

• The first declaration may cause a segmentation fault if i is not an int pointer.

• The second declaration may cause unexpected behavior if i is not aligned to an int.

• Example: int i = 42; int p = ...read more

Efficiently check if a number is present in an array where each element differs by 1.

• Use binary search to find the element in the array

• Calculate the difference between the middle element and the first element

• If the difference is equal to the index of the middle element minus the index of the first element, then the left half of the array is consecutive

• If the difference is not equal, then the right half of the array is consecutive

• Repeat the process on the appropriate half of t...read more

Solve for x in a given expression with single variable.

• Simplify the expression by applying the distributive property and combining like terms.

• Isolate the variable term on one side of the equation and the constant terms on the other side.

• Solve for x by dividing both sides of the equation by the coefficient of the variable term.

• Check the solution by substituting the value of x back into the original equation.

• In this case, simplify the expression to -5x/3 = -4 and solve for x to...read more

To merge two double linked lists, traverse to the end of the first list and connect it to the head of the second list.

• Traverse to the end of the first list

• Connect the last node of the first list to the head of the second list

• If the lists are singly linked, we need to traverse to the end of the first list and connect it to the head of the second list. But we also need to keep track of the last node of the first list to connect it to the head of the second list.

• Example: list1: ...read more

Endianess refers to the order in which bytes are stored in memory. Little endian stores the least significant byte first.

• Check the byte order of a multi-byte integer value

• Use a test value with known byte order to determine the system's endianess

• Check the system's documentation or specifications

• Use a code snippet to determine the endianess

Inter-process communication mechanisms like pipes, sockets, message queues, shared memory can be used to call a function from one user process to another.

• Use pipes to establish a unidirectional communication channel between two processes.

• Use sockets to establish a bidirectional communication channel between two processes.

• Use message queues to send messages between processes.

• Use shared memory to share data between processes.

• Remote Procedure Call (RPC) can also be used to call ...read more

Program to rearrange shuffled 16 squares to get original big square

• Create a 4x4 matrix to represent the big square and fill it with shuffled squares

• Loop through the matrix and check if each square is in the correct position

• If a square is not in the correct position, swap it with the square in the correct position

• Repeat until all squares are in the correct position

Function pointers can be shared across processes using inter-process communication mechanisms like shared memory, pipes, sockets, etc.

• Function pointers can be stored in shared memory regions that are accessible by multiple processes.

• Processes can communicate with each other using pipes or sockets and pass function pointers as arguments.

• Remote Procedure Call (RPC) mechanisms can also be used to share function pointers across processes.

• Message Passing Interface (MPI) is another...read more