Add office photos
Employer?
Claim Account for FREE

Josh Technology Group

3.0
based on 75 Reviews
Filter interviews by

20+ Utility Hub Interview Questions and Answers

Updated 18 Sep 2024
Popular Designations

Q1. Validate Binary Tree Nodes Problem

You are provided with 'N' binary tree nodes labeled from 0 to N-1, where node i has two potential children, recorded in the LEFT_CHILD[i] and RIGHT_CHILD[i] arrays. Determine ...read more

Ans.

The task is to determine if the given binary tree nodes form exactly one valid binary tree.

  • Check if there is only one root node (a node with no parent)

  • Check if each node has at most one parent

  • Check if there are no cycles in the tree

  • Check if all nodes are connected and form a single tree

Add your answer

Q2. Balanced Binary Trees Problem Statement

You are provided with an integer 'H'. Your task is to determine and print the maximum number of balanced binary trees possible with height 'H'.

A balanced binary tree is ...read more

Ans.

The maximum number of balanced binary trees possible with a given height is to be counted and printed.

  • A balanced binary tree is one in which the difference between the left and right subtree heights is less than or equal to 1.

  • The number of balanced binary trees can be calculated using dynamic programming.

  • The number of balanced binary trees with height 'H' can be obtained by summing the product of the number of balanced binary trees for each possible left and right subtree hei...read more

Add your answer

Q3. Wave Array Sorting Problem

Your goal is to sort a given unsorted array ARR such that it forms a wave array.

Explanation:

After sorting, the array should satisfy the wave pattern conditions:

  • ARR[0] >= ARR[1]
  • AR...read more
Ans.

The task is to sort an array in a wave form, where each element is greater than or equal to its adjacent elements.

  • Iterate through the array and swap adjacent elements if they do not follow the wave pattern

  • Start from the second element and compare it with the previous element, swap if necessary

  • Continue this process until the end of the array

  • Repeat the process for the remaining elements

  • Return the sorted wave array

Add your answer

Q4. Pair Sum in BST Problem Statement

Given a Binary Search Tree (BST) and a target value K, determine if there exist two unique elements in the BST such that their sum equals K.

Input:

An integer T, the number of ...read more
Ans.

The task is to check if there exist two unique elements in the given BST such that their sum is equal to the given target 'K'.

  • Traverse the BST in-order and store the elements in a sorted array

  • Use two pointers, one at the beginning and one at the end of the array

  • Check if the sum of the elements at the two pointers is equal to the target 'K'

  • If the sum is less than 'K', move the left pointer to the right

  • If the sum is greater than 'K', move the right pointer to the left

  • Repeat the...read more

Add your answer
Discover Utility Hub interview dos and don'ts from real experiences

Q5. Maximum Sum BST Problem Statement

You are presented with a Binary Tree 'root', which may not necessarily be a Binary Search Tree (BST). Your objective is to identify the maximum sum of node values in any subtre...read more

Ans.

The task is to find the maximum sum of node values of any subtree that is a Binary Search Tree(BST).

  • Traverse the binary tree in a bottom-up manner

  • For each node, check if it forms a BST and calculate the sum of its subtree

  • Keep track of the maximum sum encountered so far

  • Return the maximum sum

Add your answer

Q6. Find Nodes at Distance K in a Binary Tree

Your task is to find all nodes that are exactly a distance K from a given node in an arbitrary binary tree. The distance is defined as the number of edges between nodes...read more

Ans.

The task is to find all nodes in a binary tree that are at a distance K from a given node.

  • Implement a function that takes the binary tree, target node, and distance K as input.

  • Use a depth-first search (DFS) algorithm to traverse the tree and find the nodes at distance K.

  • Keep track of the distance from the current node to the target node while traversing.

  • When the distance equals K, add the current node to the result list.

  • Continue the DFS traversal to explore other nodes in the...read more

Add your answer
Are these interview questions helpful?

Q7. 0/1 Knapsack Problem Statement

A thief is planning to rob a store and can carry a maximum weight of 'W' in his knapsack. The store contains 'N' items where the ith item has a weight of 'wi' and a value of 'vi'....read more

Ans.

Yes, the 0/1 Knapsack problem can be solved using dynamic programming with a space complexity of not more than O(W).

  • Use a 1D array to store the maximum value that can be stolen for each weight capacity from 0 to W.

  • Iterate through each item and update the array based on whether including the item would increase the total value.

  • The final value in the array at index W will be the maximum value that can be stolen.

Add your answer

Q8. K Largest Elements Problem Statement

You are given an unsorted array containing 'N' integers. Your task is to find the 'K' largest elements from this array and return them in non-decreasing order.

Input:

The fi...read more
Ans.

Yes, the problem can be solved in less than O(N*log(N)) time complexity using the Quick Select algorithm.

  • Implement Quick Select algorithm to find the Kth largest element in O(N) time complexity.

  • Partition the array around a pivot element and recursively search in the left or right partition based on the position of the pivot.

  • Once you find the Kth largest element, return all elements greater than or equal to it in non-decreasing order.

Add your answer
Share interview questions and help millions of jobseekers 🌟

Q9. Majority Element Problem Statement

Given an array/list 'ARR' consisting of 'N' integers, your task is to find the majority element in the array. If there is no majority element present, return -1.

Example:

Inpu...read more
Ans.

Find the majority element in an array, return -1 if no majority element exists.

  • Iterate through the array and keep track of the count of each element using a hashmap.

  • Check if any element's count is greater than floor(N/2) to determine the majority element.

  • Return the majority element or -1 if no majority element exists.

Add your answer

Q10. Maximize Stock Trading Profit

You are given an array prices, representing stock prices over N consecutive days. Your goal is to compute the maximum profit achievable by performing multiple transactions (i.e., b...read more

Ans.

Find maximum profit by buying and selling stocks multiple times.

  • Iterate through the array and find all increasing sequences of stock prices.

  • Calculate profit by buying at the start and selling at the end of each increasing sequence.

  • Sum up all profits to get the maximum profit achievable.

Add your answer

Q11. Size of Largest BST in a Binary Tree

Given a binary tree with 'N' nodes, determine the size of the largest subtree that is also a Binary Search Tree (BST).

Explanation:

A Binary Search Tree (BST) is defined as ...read more

Ans.

Find the size of the largest BST subtree in a binary tree.

  • Traverse the tree in a bottom-up manner to check if each subtree is a BST.

  • Keep track of the size of the largest BST found so far.

  • Recursively check if the current subtree is a BST and update the size accordingly.

Add your answer

Q12. Longest Common Subsequence Problem Statement

Given two strings STR1 and STR2, determine the length of their longest common subsequence.

A subsequence is a sequence that can be derived from another sequence by d...read more

Ans.

The problem involves finding the length of the longest common subsequence between two given strings.

  • Use dynamic programming to solve the problem efficiently.

  • Create a 2D array to store the lengths of common subsequences of substrings.

  • Iterate through the strings to fill the array and find the length of the longest common subsequence.

  • Example: For input STR1 = 'abcde' and STR2 = 'ace', the longest common subsequence is 'ace' with a length of 3.

Add your answer

Q13. Height of a Binary Tree

You are provided with an arbitrary binary tree consisting of 'N' nodes where each node is associated with a certain value. The task is to determine the height of the tree.

Explanation:

T...read more

Ans.

Calculate the height of a binary tree given its level order traversal.

  • Traverse the binary tree level by level and keep track of the height as you go down the tree.

  • Use a queue data structure to perform level order traversal efficiently.

  • The height of a binary tree is the maximum number of edges from the root to any leaf node.

  • Handle NULL nodes represented by -1 in the input.

  • Return the height of the binary tree as a single integer.

Add your answer

Q14. Number of Islands Problem Statement

You are provided with a 2-dimensional matrix having N rows and M columns, containing only 1s (land) and 0s (water). Your goal is to determine the number of islands in this ma...read more

Ans.

Count the number of islands in a 2D matrix of 1s and 0s.

  • Use Depth First Search (DFS) or Breadth First Search (BFS) to traverse the matrix and count the number of connected components.

  • Maintain a visited array to keep track of visited cells to avoid counting the same island multiple times.

  • Iterate through each cell in the matrix and if it is a land (1) and not visited, perform DFS/BFS to explore the connected land cells.

  • Increment the island count each time a new island is encoun...read more

Add your answer

Q15. Matrix Chain Multiplication Problem

Given 'N' 2-dimensional matrices and an array ARR of length N + 1, where the first N integers denote the number of rows in each matrix and the last integer represents the num...read more

Ans.

Find the minimum number of multiplication operations required to multiply a series of matrices together.

  • Use dynamic programming to solve this problem efficiently.

  • Create a 2D array to store the minimum number of operations needed to multiply matrices.

  • Iterate through different combinations of matrices to find the optimal solution.

  • Consider the dimensions of the matrices to determine the number of operations required.

  • Calculate the minimum number of operations by considering all p...read more

Add your answer

Q16. Longest Palindromic Substring Problem Statement

You are provided with a string STR of length N. The task is to find the longest palindromic substring within STR. If there are several palindromic substrings of t...read more

Ans.

Given a string, find the longest palindromic substring within it.

  • Iterate through the string and expand around each character to find palindromes

  • Keep track of the longest palindrome found so far

  • Return the longest palindromic substring

Add your answer

Q17. Maximum Length Pair Chain Problem Statement

You are given 'N' pairs of integers where the first number is always smaller than the second number, i.e., in pair (a, b) -> a < b always. A pair chain is defined as ...read more

Ans.

Find the length of the longest pair chain that can be formed using the given pairs.

  • Sort the pairs based on the second element in ascending order.

  • Iterate through the sorted pairs and keep track of the maximum chain length.

  • Update the chain length if the current pair can be added to the chain.

  • Return the maximum chain length at the end.

Add your answer

Q18. Rotate Linked List Problem Statement

Given a linked list consisting of 'N' nodes and an integer 'K', your task is to rotate the linked list by 'K' positions in a clockwise direction.

Example:

Input:
Linked List...read more
Ans.

Rotate a linked list by K positions in a clockwise direction.

  • Traverse the linked list to find the length and the last node.

  • Connect the last node to the head to form a circular linked list.

  • Find the new head by moving (length - K) steps from the last node.

  • Break the circular list at the new head to get the rotated linked list.

Add your answer
Q19. Can you describe how to design a web crawler?
Ans.

Designing a web crawler involves defining the scope, selecting a crawling strategy, implementing the crawler, handling data storage, and ensuring politeness.

  • Define the scope of the web crawler by determining the websites to crawl and the depth of the crawl.

  • Select a crawling strategy such as breadth-first or depth-first search based on the requirements.

  • Implement the web crawler using a programming language like Python or Java, utilizing libraries like Scrapy or BeautifulSoup.

  • H...read more

Add your answer

Q20. What is software development life cycle and which steps are following?

Ans.

Software development life cycle (SDLC) is a process used by software developers to design, develop, and test software.

  • 1. Planning: Define the project scope, requirements, and objectives.

  • 2. Analysis: Gather and analyze user requirements.

  • 3. Design: Create a detailed design of the software.

  • 4. Implementation: Develop the software based on the design.

  • 5. Testing: Test the software for bugs and issues.

  • 6. Deployment: Release the software to users.

  • 7. Maintenance: Update and maintain t...read more

Add your answer

Q21. Given a value find next sibling on right side of it without using global/heap variables

Ans.

Use a binary tree traversal algorithm to find the next sibling on the right side of a given value.

  • Implement an in-order traversal algorithm to traverse the binary tree

  • Keep track of the parent node and the direction of traversal to find the next sibling on the right side

  • If the given value is the right child of its parent, move up the tree until finding a node that is the left child of its parent

Add your answer

Q22. What is api and how it is work ?

Ans.

API stands for Application Programming Interface. It is a set of rules and protocols that allows different software applications to communicate with each other.

  • APIs define the methods and data formats that applications can use to request and exchange information.

  • APIs can be used to access services provided by other software applications, such as retrieving data from a database or sending notifications.

  • Examples of APIs include the Google Maps API, which allows developers to in...read more

Add your answer

Q23. Delete a node from a binary tree.

Ans.

Delete a node from a binary tree.

  • Find the node to be deleted

  • If the node has no children, simply delete it

  • If the node has one child, replace it with its child

  • If the node has two children, find the minimum value in its right subtree, replace the node with that value, and delete the minimum value node

Add your answer

Q24. Detect a loop in linked list

Ans.

Use Floyd's Tortoise and Hare algorithm to detect a loop in a linked list.

  • Initialize two pointers, slow and fast, at the head of the linked list.

  • Move slow pointer by one step and fast pointer by two steps.

  • If they meet at any point, there is a loop in the linked list.

Add your answer

Q25. Left view of tree

Ans.

Left view of a tree is the set of nodes visible when the tree is viewed from the left side.

  • Traverse the tree in a level order manner

  • Keep track of the first node encountered at each level

  • Add the first node encountered at each level to the result array

Add your answer
Contribute & help others!
Write a review
Share interview
Contribute salary
Add office photos

Interview Process at Utility Hub

based on 15 interviews
3 Interview rounds
Aptitude Test Round
Coding Test Round - 1
Coding Test Round - 2
View more
Interview Tips & Stories
Ace your next interview with expert advice and inspiring stories

Top Software Developer Interview Questions from Similar Companies

3.8
 • 47 Interview Questions
3.7
 • 45 Interview Questions
4.3
 • 31 Interview Questions
3.3
 • 24 Interview Questions
4.7
 • 15 Interview Questions
3.5
 • 10 Interview Questions
View all
Share an Interview
Stay ahead in your career. Get AmbitionBox app
qr-code
Helping over 1 Crore job seekers every month in choosing their right fit company
70 Lakh+

Reviews

5 Lakh+

Interviews

4 Crore+

Salaries

1 Cr+

Users/Month

Contribute to help millions

Made with ❤️ in India. Trademarks belong to their respective owners. All rights reserved © 2024 Info Edge (India) Ltd.

Follow us
  • Youtube
  • Instagram
  • LinkedIn
  • Facebook
  • Twitter