300+ SDE Interview Questions and Answers

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

Determine the maximum number of balls (N) to find the lighter one in 2 or 3 weighings using a balance scale.

• In 2 weighings, you can identify the lighter ball among 3 balls (N=3).

• In 3 weighings, you can identify the lighter ball among 9 balls (N=9).

• The strategy involves dividing the balls into groups and using the balance to eliminate possibilities.

• For example, with 9 balls, divide into 3 groups of 3, weigh 2 groups, and use the result to find the lighter group.

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

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

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

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.

Find pairs from sorted arrays a and b that sum to elements in sorted array c.

• Use a two-pointer technique to traverse arrays a and b.

• For each element in c, check if a[i] + b[j] equals c[k].

• Example: a = [1, 2], b = [3, 4], c = [4, 5] results in pairs (1, 3).

• Start with pointers at the beginning of a and b, and adjust based on the sum.

Implementing a Least Recently Used (LRU) Cache using a combination of a doubly linked list and a hash map for O(1) access.

• Use a hash map to store key-value pairs for O(1) access.

• Maintain a doubly linked list to track the order of usage.

• When accessing an item, move it to the front of the list.

• When adding a new item, check if the cache is full; if so, remove the least recently used item from the back of the list.

• Example: For a cache of size 2, accessing keys 1, 2, then 1 again ...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.

Modify a binary tree's random pointers to point to NULL if they don't point to a successor node.

• Traverse the binary tree using DFS or BFS.

• For each node, check if the random pointer points to a valid successor.

• If it points to a node that is not a successor, set it to NULL.

• A successor of a node is defined as its children or their descendants.

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

Find all unique pairs in an array that sum up to a given value s.

• Use a hash set to track numbers we've seen. Example: For array [1, 2, 3, 4] and s=5, pairs are (1,4) and (2,3).

• Iterate through the array, for each number x, check if (s-x) exists in the set. If yes, store the pair.

• Ensure pairs are unique by using a set to store results. Example: For array [1, 2, 3, 2] and s=4, only (1,3) and (2,2) are valid.

• Consider edge cases like empty arrays or no valid pairs. Example: For ar...read more

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

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

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

To find kth-smallest element in BST, perform inorder traversal and return the kth element.

• Perform inorder traversal of the BST

• Maintain a counter variable to keep track of the number of nodes visited

• When the counter reaches k, return the current node's value

• If k is greater than the number of nodes in the BST, return null or throw an exception

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

LRU cache is a data structure that stores most recently used items and discards least recently used items.

• LRU stands for Least Recently Used

• It is implemented using a doubly linked list and a hash map

• When an item is accessed, it is moved to the front of the list

• When the cache is full, the least recently used item is removed from the end of the list

• Example: A web browser cache that stores recently visited web pages

Out of 9 identical marbles, find the one that is heavy.

• Divide the marbles into groups of three

• Weigh two groups against each other

• If one group is heavier, weigh two marbles from that group

• If they are equal, the heavy marble is in the third group

• If the weighed marbles are unequal, the heavy marble is in that group