Utility Hub Interview Questions and Answers

Check if a binary tree is a Partial Binary Search Tree (BST) based on specific properties.

• Traverse the tree in level order and check if each node satisfies the properties of a Partial BST.

• Use recursion to check if the left and right subtrees are also Partial BSTs.

• Compare the data of each node with its children to ensure the BST properties are maintained.

• Example: For input 1 2 3 4 -1 5 6 -1 7 -1 -1 -1 -1 -1 -1, the output should be true.

Find the maximum sum of any contiguous subarray within an array of integers.

• Iterate through the array and keep track of the maximum sum of subarrays encountered so far.

• Use Kadane's algorithm to efficiently find the maximum subarray sum.

• Handle cases where all elements are negative by returning the maximum element in the array.

• Example: For array [34, -50, 42, 14, -5, 86], the maximum subarray sum is 137.

Find the element that appears an odd number of times in an array of integers.

• Iterate through the array and use XOR operation to find the element that appears odd number of times.

• Keep a count of occurrences of each element using a hashmap.

• Return the element that has an odd count of occurrences.

Implement a function to find the shortest path in an unweighted graph from a given start house to a destination house.

• Use Breadth First Search (BFS) algorithm to find the shortest path in an unweighted graph.

• Maintain a queue to explore neighboring houses and keep track of visited houses to avoid revisiting them.

• Return the path once the destination house is reached.

• Example: For input N=8, M=9, S=1, T=8 and roads (1, 2), (1, 3), (2, 4), (2, 5), (3, 6), (3, 8), (4, 7), (5, 8), (...read more

Merge two sorted linked lists into a single sorted linked list.

• Create a new linked list to store the merged result.

• Iterate through both input linked lists simultaneously, comparing and adding nodes to the result list.

• Handle cases where one list is empty or both lists are empty.

• Ensure the final merged list is sorted in ascending order.

• Use constant space complexity and linear time complexity for the solution.