Cloudtailor Interview Questions and Answers

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

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 curre...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 dist

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

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

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 phy...read more

B and B+ trees are data structures used for efficient searching and sorting of large datasets.

• B trees are balanced trees used for disk-based storage systems.

• B+ trees are similar to B trees but have all data stored in the leaf nodes for faster searching.

• B trees have a variable number of keys per node, while B+ trees have a fixed number.

• B trees have a higher fanout than B+ trees, making them more efficient for smaller da...read more

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.

• ...read more

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

Print the level order traversal of binary tree in spiral form

• Perform level order traversal of the binary tree

• Alternate the direction of traversal for each level

• Use a stack to reverse the order of nodes in each level

• Print the nodes in the order of traversal

Find the maximum element in each subarray of size k in a given array.

• Iterate through the array from index 0 to n-k.

• For each subarray of size k, find the maximum element.

• Store the maximum elements in a separate array.

• Return the array of maximum elements.

To find the Kth largest element in two sorted arrays, we can use the merge step of merge sort algorithm.

• Merge the two arrays into a single sorted array using a modified merge sort algorithm.

• Return the Kth element from the merged array.

Merge two sorted arrays into one sorted array with expected time complexity of (m+n).

• Use a two-pointer approach to compare elements from both arrays and merge them into the first array.

• Start comparing elements from the end of both arrays and place the larger element at the end of the first array.

• Continue this process until all elements from the second array are merged into the first array.

The algorithm finds the position of the 3rd occurrence of 'B' in an n-ary tree from a given index in constant time complexity.

• Traverse the n-ary tree using a depth-first search (DFS) algorithm

• Keep track of the count of 'B' occurrences

• When the count reaches 3, return the current position

• If the end of the tree is reached before the 3rd 'B', return -1

Check if a given string is a composite of two words from a limited dictionary.

• Create a hash set of all the words in the dictionary.

• Iterate through all possible pairs of substrings in the given string.

• Check if both substrings are present in the hash set.

• If yes, return true. Else, return false.

Switch adjacent nodes in a single linked list.

• Traverse the linked list and swap adjacent nodes.

• Keep track of previous node to update its next pointer.

• Handle edge cases for first two nodes and last node.

• Example: 1->2->3->4 becomes 2->1->4->3.

Traverse only the left sub-tree of a binary search tree.

• Start at the root node

• If the left child exists, visit it and repeat the process

• If the left child does not exist, return to the parent node

• Continue until all nodes in the left sub-tree have been visited

Design an efficient data structure for two lifts in a building of n floors.

• Use a priority queue to keep track of the floors each lift is heading to

• Implement a scheduling algorithm to determine which lift to assign to a new request

• Consider adding a weight limit to each lift to prevent overloading

• Use a hash table to keep track of the current location of each lift

To find the maximum number that can be formed from the digits of an integer.

• Convert the integer to a string

• Sort the characters in descending order

• Join the sorted characters to form the maximum number

Reverse all the words in a given string

• Split the string into an array of words

• Loop through the array and reverse each word

• Join the reversed words back into a string

Explaining how to handle 'n' in a string during swapping process

• Identify the positions of 'n' in the string

• Exclude those positions from the swapping process

• Use a temporary variable to swap the characters

• Ensure the swapped characters are not 'n'

• Return the modified string

We can use any sorting algorithm like quicksort, mergesort, heapsort, etc.

• Choose the appropriate sorting algorithm based on the size of the file and the range of numbers

• Implement the chosen algorithm in the programming language of choice

• Read the numbers from the file into an array or list

• Apply the sorting algorithm to the array or list

• Write the sorted numbers back to the file

Word suggestions in Eclipse can be implemented using algorithms like Trie or N-gram models.

• Use Trie data structure to store the dictionary of words

• Implement auto-complete feature using Trie

• Use N-gram models to suggest words based on context

• Train the N-gram model on a large corpus of text data

• Combine both approaches for better accuracy

• Consider user's typing speed and frequency of words for better suggestions

To check if a number k lies in a sequence formed by adding previous 2 elements, start with a=0 and b=1 and iterate until k is found or exceeded.

• Start with a=0 and b=1

• Iterate through the sequence until k is found or exceeded

• If k is found, return true. If exceeded, return false

Check if a Binary Tree is a Binary Search Tree (BST)

• A BST has the property that all nodes in the left subtree of a node have values less than the node's value, and all nodes in the right subtree have values greater than the node's value

• We can traverse the tree in-order and check if the resulting sequence is sorted

• Alternatively, we can recursively check if each node satisfies the BST property

Keep track of kth largest number in a stream of numbers.

• Use a min-heap of size k to keep track of kth largest number.

• For each incoming number, compare it with the root of the heap.

• If it is larger than the root, replace the root with the new number and heapify.

• The root of the heap will always be the kth largest number.

Infix expression can be evaluated using the concept of operator precedence and associativity.

• Convert the infix expression to postfix expression using stack data structure

• Evaluate the postfix expression using stack data structure

• Use operator precedence and associativity rules to determine the order of evaluation

• Parentheses can be used to override the default order of evaluation

Design optimal data structures for LRU cache

• Use a doubly linked list to keep track of recently used items

• Use a hash table to store key-value pairs for quick access

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

• When the cache is full, remove the least recently used item from the back of the linked list and hash table

Convert a sorted array to balanced binary search tree

• Find the middle element of the array and make it the root of the tree

• Recursively construct the left subtree using the left half of the array

• Recursively construct the right subtree using the right half of the array

• Repeat until all elements are added to the tree

Reverse a singly linked list in groups of k in­place

• Divide the linked list into groups of k nodes

• Reverse each group of k nodes

• Connect the reversed groups to form the final linked list

Optimal data structure for storing words and their meanings

• Use a hash table with the word as the key and a list of meanings as the value

• Each meaning can be stored as a string or an object with additional information

• Consider using a trie data structure for efficient prefix search

• Implement a search function that can handle partial matches and synonyms

A recursive routine to calculate a ^ n

• The base case is when n is 0, in which case the result is 1

• For any other value of n, the result is a multiplied by the result of a^(n-1)

• The recursive function should call itself with a^(n-1) as the new input

Design optimal data structure for never-ending stream of numbers for insertion, deletion, searching, kth largest and kth smallest.

• Use a balanced binary search tree like AVL or Red-Black tree for efficient insertion, deletion, and searching.

• Maintain two heaps, one for kth largest and one for kth smallest.

• For finding kth largest, use a min heap of size k and for kth smallest, use a max heap of size k.

• Alternatively, use a...read more