Infibeam Software Engineer Interview Questions and Answers

Program to find lowest common ancestor of two nodes in binary search tree and binary tree with brute force approach.

• For binary search tree, traverse from root to both nodes and store the path. Then compare paths to find LCA.

• For binary tree, traverse from root to both nodes and store the path. Then compare paths to find LCA.

• Brute force approach involves checking each node's descendants to see if they contain both nodes.

• Time complexity for brute force approach is O(n^2) for wor...read more

Find two numbers in an unsorted array that add up to a given sum in O(n)

• Use a hash table to store the difference between the sum and each element in the array

• Iterate through the array and check if the current element is in the hash table

• If it is, return the current element and the corresponding difference

• If not, add the current element to the hash table

Program to print matrix elements in spiral order recursively

• Create a recursive function to print the elements in spiral order

• Define the boundaries of the matrix and traverse the matrix in spiral order

• Call the recursive function to print the elements in spiral order

• Handle edge cases such as empty matrix or matrix with only one row/column

Program to print all ancestors of a node in a binary tree

• Create a recursive function to traverse the binary tree

• Check if the current node is the target node

• If yes, print all the nodes in the call stack

• If not, recursively call the function for left and right subtrees

Dijkstra's algorithm finds shortest path between nodes in a graph

• Create a graph with nodes and edges

• Initialize distances from source node to all other nodes as infinity

• Set distance from source node to itself as 0

• Create a set of unvisited nodes

• While unvisited set is not empty, select node with minimum distance

• For each neighbor of selected node, calculate distance from source node

• If calculated distance is less than current distance, update distance

• Mark selected node as visited

• R...read more

Floyd-Warshall's algorithm is used to find the shortest path between all pairs of vertices in a weighted graph.

• Create a 2D array to store the distances between all pairs of vertices.

• Initialize the array with the weights of the edges in the graph.

• Use nested loops to iterate over all pairs of vertices and update the distances if a shorter path is found through a third vertex.

• The final array will contain the shortest distances between all pairs of vertices.

A program to swap two pointers.

• Declare two pointers of the same data type

• Assign the first pointer to a temporary variable

• Assign the second pointer to the first pointer

• Assign the temporary variable to the second pointer

Indexing is a technique used in DBMS to improve the performance of queries.

• Indexing creates a separate data structure that allows faster retrieval of data.

• It works by creating a pointer to the location of data in the table.

• Indexes can be created on one or more columns of a table.

• Types of indexing include B-tree, hash, and bitmap indexing.

• Indexes can also be clustered or non-clustered.

• Clustered indexes determine the physical order of data in a table.

• Non-clustered indexes creat...read more