BCForward Executive Trainer Interview Questions and Answers

Merge Sort is a divide and conquer algorithm that sorts an array by dividing it into two halves, sorting them separately, and then merging the sorted halves.

• Divide the array into two halves

• Recursively sort the two halves

• Merge the sorted halves

Find pairs of integers in a BST whose sum is equal to a given number.

• Traverse the BST and store the values in a hash set.

• For each node, check if (X - node.value) exists in the hash set.

• If yes, add the pair (node.value, X - node.value) to the result.

• Continue traversal until all nodes are processed.

Merge overlapping time intervals into mutually exclusive intervals.

• Sort the intervals based on their start time.

• Iterate through the intervals and merge overlapping intervals.

• Output the mutually exclusive intervals.

• Example: [(1,3), (2,6), (8,10), (15,18)] -> [(1,6), (8,10), (15,18)]

Different types of hashing and alternative for Linear Chaining

• Different types of hashing include division, multiplication, and universal hashing

• Alternative for Linear Chaining is Open Addressing

• Open Addressing includes Linear Probing, Quadratic Probing, and Double Hashing

An AVL tree is a self-balancing binary search tree where the heights of the left and right subtrees differ by at most one.

• AVL tree is a binary search tree with additional balance factor for each node.

• The balance factor is the difference between the heights of the left and right subtrees.

• Insertion and deletion operations in AVL tree maintain the balance factor to ensure the tree remains balanced.

• Rotations are performed ...read more

Find the minimum number of squares whose sum equals to a given number n.

• Use dynamic programming to solve the problem efficiently.

• Start with finding the square root of n and check if it is a perfect square.

• If not, then try to find the minimum number of squares required for the remaining number.

• Repeat the process until the remaining number becomes 0.

• Return the minimum number of squares required for the given number n.

Insertion sort for a singly linked list.

• Traverse the list and compare each node with the previous nodes

• If the current node is smaller, swap it with the previous node

• Repeat until the end of the list is reached

• Time complexity is O(n^2)

Implemented a new customer feedback system that increased customer satisfaction by 20%

• Implemented a new customer feedback system to gather insights and improve customer experience

• Analyzed feedback data to identify common issues and areas for improvement

• Implemented changes based on feedback to address customer concerns and enhance overall satisfaction

• Trained team members on how to effectively use the new system and inte...read more

Function to return mutual friends given two ids and getFriends(id) function

• Call getFriends(id) for both ids to get their respective friend lists

• Iterate through both lists and compare to find mutual friends

• Return the list of mutual friends

Function to return list of friends of friends in decreasing order of mutual friends

• Use a set to store all friends of friends

• Iterate through the list of friends of the given id

• For each friend, iterate through their list of friends and count mutual friends

• Sort the set of friends of friends by decreasing number of mutual friends

Given time slots, find a specific time with maximum overlap. Prove solution.

• Create a list of all start and end times

• Sort the list in ascending order

• Iterate through the list and keep track of the number of overlaps at each time

• Return the time with the maximum number of overlaps

• Prove solution by testing with different input sizes and edge cases

Find the longest sub-array with increasing order of integers.

• Iterate through the array and keep track of the current sub-array's start and end indices.

• Update the start index whenever the current element is smaller than the previous element.

• Update the end index whenever the current element is greater than or equal to the next element.

• Calculate the length of the sub-array and compare it with the longest sub-array found s

Find the length of longest increasing subsequence and print the sequence from an array of integers.

• Use dynamic programming to solve the problem

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

• Traverse the array and update the length of longest increasing subsequence for each index

• Print the sequence by backtracking from the index with the maximum length

• Time complexity: O(n^2)

• Exam...read more

Code to find a given integer in a rotated sorted array.

• Use binary search to find the pivot point where the array is rotated.

• Divide the array into two subarrays and perform binary search on the appropriate subarray.

• Handle edge cases such as the target integer not being present in the array.

Use a min-heap to keep track of the largest K numbers seen so far.

• Create a min-heap of size K.

• For each incoming integer, add it to the heap if it's larger than the smallest element in the heap.

• If the heap size exceeds K, remove the smallest element.

• At the end, the heap will contain the largest K numbers in the input.

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

• Use a doubly linked list to keep track of the order of items in the cache

• Use a hash map to store the key-value pairs for fast 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 the hash map