40+ ITC Interview Questions and Answers

Remove consecutive duplicate characters from a given string.

• Iterate through the string and compare each character with the previous one.

• If the current character is different from the previous one, add it to the result string.

• Return the result string as the output.

Count the number of leaf nodes in a binary tree where each node has at most two children.

• Traverse the binary tree and count nodes with both children as NULL.

• Use recursion to check each node in the tree.

• Leaf nodes have no child nodes.

• Example: For input 20 10 35 5 15 30 42 -1 13 -1 -1 -1 -1 -1 -1 -1, output should be 4.

Determine the winner of a game where two players take stones alternately, with specific rules.

• Implement a recursive function to simulate the game, considering the rules provided.

• Check if the current player can take any stones, if not, the other player wins.

• Return 'Ale' if 'Ale' will win the game, otherwise return 'Bob'.

Find the path from a leaf node to the root node with the maximum sum in a binary tree.

• Traverse the binary tree from leaf to root while keeping track of the sum of each path.

• Compare the sums of all paths and return the path with the maximum sum.

• Use recursion to traverse the tree efficiently.

• Consider negative values in the tree when calculating the sum of paths.

The 0-1 Knapsack Problem involves maximizing profit by selecting items with known weights and values within a given weight capacity.

• Understand the problem: Given items with weights and values, determine the maximum profit the thief can achieve within the knapsack's weight capacity.

• Dynamic Programming: Use dynamic programming to solve the problem efficiently by considering the weight constraints and maximizing the total value.

• Example: For input (1, 4, 10, [6, 1, 5, 3], [3, 6, ...read more

Merge two sorted linked lists into a single sorted linked list without using additional space.

• Create a dummy node to start the merged list

• Compare the nodes of the two lists and link them accordingly

• Move the pointer to the next node in the merged list

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

• Time complexity: O(n), Space complexity: O(1)

Find the largest number that can be formed by concatenating all node values in a Binary Tree.

• Traverse the Binary Tree in a way that ensures the largest values are concatenated first.

• Use a custom comparator function to sort the node values in descending order before concatenating.

• Handle null nodes by skipping them during concatenation.

• Convert integer node values to strings for concatenation.

• Implement a recursive function to traverse the Binary Tree and concatenate node values.

Find all the bridges in an undirected graph by identifying edges that, when removed, increase the number of connected components.

• Use Tarjan's algorithm to find bridges in the graph.

• A bridge is an edge that, when removed, increases the number of connected components.

• Identify bridges by performing DFS traversal and keeping track of low and discovery times.

• Return the count of bridges and the vertices defining each bridge in non-decreasing order.

Given a string, find the minimum number of characters needed to make it a palindrome.

• Iterate through the string from both ends and count the number of characters that need to be added to make it a palindrome.

• Use dynamic programming to optimize the solution by considering subproblems.

• Handle edge cases such as an already palindrome string or an empty string.

• Example: For input 'abb', the output should be 1 as adding 'a' makes it 'abba', a palindrome.

Given a binary tree and a specific node, return a sorted list of the node's cousins.

• Traverse the binary tree to find the parent of the given node and its depth.

• Traverse the tree again to find nodes at the same depth but with different parents.

• Return the sorted list of cousin node values or -1 if no cousins exist.

Implement a function to delete a node from a linked list at a specified position.

• Traverse the linked list to find the node at the specified position.

• Update the pointers of the previous and next nodes to skip the node to be deleted.

• Handle cases where the position is at the beginning or end of the linked list.

• Ensure to free the memory of the deleted node to avoid memory leaks.

Rotate a square matrix by 90 degrees in an anti-clockwise direction using constant extra space.

• Iterate through each layer of the matrix from outer to inner layers

• Swap elements in groups of 4 to rotate the matrix

• Handle odd-sized matrices separately by adjusting the center element if needed

Find the length of the longest strictly increasing subsequence in an array of integers.

• Use dynamic programming to keep track of the longest increasing subsequence ending at each element.

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

• Iterate through the array and update the length of the longest increasing subsequence for each element.

• Return the maximum value in the array as the length of the longest increasing subsequence.

Calculate the sum of squares of the first N natural numbers for given test cases.

• Iterate through each test case and calculate the sum of squares using the formula: N*(N+1)*(2N+1)/6

• Output the result for each test case on a new line

• Handle constraints efficiently to avoid timeouts

Given a linked list of single digits, construct the largest number possible.

• Traverse the linked list to extract the digits

• Sort the digits in descending order

• Concatenate the sorted digits to form the maximum number

Find the maximum subsequence sum from an array without selecting three consecutive elements.

• Use dynamic programming to keep track of the maximum sum without selecting three consecutive elements.

• At each index, consider the maximum sum with the current element included or excluded.

• Handle edge cases where the array length is less than 3 separately.

• Example: For input [1, 2, 3, 4], the maximum sum is 9 (1 + 3 + 4).

Count the number of occurrences of a given word in a two-dimensional grid of characters.

• Iterate through each cell in the grid and check if the word can be formed starting from that cell in any of the eight directions.

• Use backtracking to explore all possible paths while matching the characters of the word.

• Keep track of visited cells to avoid revisiting the same cell in the same path.

• Return the count of occurrences of the word in the grid.

Rearrange array with negative numbers at the beginning, order not important.

• Iterate through the array and swap negative numbers to the beginning using two pointers approach.

• Maintain one pointer for negative numbers and another for positive numbers.

• Time complexity: O(N), Space complexity: O(1).

Find the length of the shortest path in a binary maze from a given source to destination.

• Use Breadth First Search (BFS) algorithm to find the shortest path in the binary maze.

• Create a queue to store the cells to be visited and keep track of visited cells to avoid revisiting them.

• Check for valid moves in all four directions and update the distance to reach each cell.

• Return the length of the shortest path if it exists, else return -1.

• Example: For the given input, the shortest p...read more

Reverse a singly linked list of integers and return the head of the reversed linked list.

• Iterate through the linked list and reverse the pointers to point to the previous node instead of the next node.

• Use three pointers to keep track of the current, previous, and next nodes while reversing the linked list.

• Update the head of the reversed linked list as the last node encountered during the reversal process.

Reverse a given string containing alphabets, numbers, and special characters.

• Iterate through the string from the end to the beginning and append each character to a new string.

• Use built-in functions like reverse() or slicing to reverse the string.

• Handle special characters and numbers while reversing the string.

• Ensure to consider the constraints on the input size and number of test cases.

The problem involves finding the ceil value of a key in a Binary Search Tree (BST).

• Traverse the BST to find the closest integer greater than or equal to the given key.

• Compare the key with the current node value and update the ceil value accordingly.

• Handle cases where the key is equal to a node value or falls between two nodes.

• Implement a recursive or iterative solution to efficiently find the ceil value.

Given an integer 'N', find the final single-digit value by summing its digits iteratively.

• Iteratively sum the digits of the given integer until the result is a single-digit number

• Output the final single-digit integer for each test case

• Handle multiple test cases efficiently

Convert a Binary Tree into a Doubly Linked List following Inorder Traversal.

• Perform Inorder Traversal of the Binary Tree to get the nodes in order.

• Create a Doubly Linked List by linking the nodes in the order obtained from Inorder Traversal.

• Return the head of the Doubly Linked List as the output.

Convert a binary tree into its mirror tree by interchanging left and right children of non-leaf nodes.

• Traverse the tree in postorder fashion and swap the left and right children of each node.

• Recursively call the function on the left and right subtrees.

• Modify the tree in place without creating a new tree.

Find the shortest path between two nodes in a tree.

• Use Breadth First Search (BFS) algorithm to find the shortest path in a tree.

• Start BFS from one of the nodes and keep track of the parent of each node to reconstruct the path.

• Once both nodes are reached, backtrack from both nodes to the root to find the common ancestor and then reconstruct the path.

• Consider implementing a function to find the LCA (Lowest Common Ancestor) of two nodes in a tree.

• Handle cases where one node is a...read more

Check if a given integer is a power of two or not.

• Check if the given integer is positive.

• Use bitwise operations to determine if it is a power of two.

• Return true if it is a power of two, false otherwise.

The task is to find the minimum number of characters needed to insert into a given string to make it a palindrome.

• Use dynamic programming to find the longest palindromic subsequence of the given string.

• Subtract the length of the longest palindromic subsequence from the length of the original string to get the minimum insertions required.

• Handle edge cases like an empty string or a string that is already a palindrome.

• Example: For input 'abcaa', the longest palindromic subsequen...read more

Implement merge sort algorithm to sort a singly linked list of integers.

• Divide the linked list into two halves using slow and fast pointer technique.

• Recursively sort the two halves.

• Merge the sorted halves using a merge function.

• Handle base cases like empty list or single node list.

• Ensure the termination of the linked list with -1 at the end.

Given a string, find the longest palindromic substring, prioritizing the one with the smallest start index.

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

• Keep track of the longest palindrome found, updating it as needed

• Return the longest palindromic substring with the smallest start index

Identify all distinct triplets within an array that sum up to a specified number.

• Iterate through all possible triplets using three nested loops.

• Check if the sum of the triplet equals the target sum.

• Print the triplet if found, else print -1.

Implement a priority queue using a heap data structure with push, pop, getMaxElement, and isEmpty functions.

• Implement push function to insert element into the queue

• Implement pop function to remove the largest element from the queue

• Implement getMaxElement function to return the largest element

• Implement isEmpty function to check if the queue is empty

Implement a function to create an AVL tree from scratch by inserting given values and return the root of the tree.

• Create a Node class with data, left, and right pointers for the AVL tree nodes.

• Implement rotation functions (left rotation, right rotation) to maintain AVL tree balance.

• Update the height and balance factor of nodes after each insertion to ensure AVL tree properties are maintained.

Check if a given singly linked list is a palindrome or not.

• Use two pointers approach to find the middle of the linked list

• Reverse the second half of the linked list

• Compare the first half with the reversed second half to determine if it's a palindrome

Convert a given BST into a Greater Tree by updating each node's data to the sum of original data and all greater nodes' data.

• Traverse the BST in reverse inorder (right, root, left) to update each node's data with the sum of all greater nodes' data.

• Keep track of the running sum of nodes visited so far to update the current node's data.

• Modify the BST in place without using any extra data structures.

• Example: Input BST: 4 1 6 0 2 5 7 -1 -1 -1 3 -1 -1 -1 -1. Output Greater Tree: 2...read more

Remove BST keys outside given range while maintaining validity of BST.

• Traverse the BST in inorder fashion and remove nodes outside the specified range.

• Recursively call the function on left and right subtrees.

• Adjust the pointers of parent nodes accordingly after removing nodes.

• Ensure the BST remains valid after modifications.

• Return the inorder traversal of the adjusted BST.

Determine the minimum cost to supply water to all houses in a village by building wells or connecting them with pipes.

• Iterate through all possible connections and choose the minimum cost between building a well or connecting two houses with a pipe.

• Use a minimum spanning tree algorithm like Kruskal's or Prim's to find the optimal cost.

• Consider the cost of building wells and connecting pipes to minimize the total cost.

• Example: For the input (3 2, 1 2 2, 1 2 1, 2 3 1), the optim...read more

Find the minimum number of trampoline jumps Bob needs to make to reach the final shop, or return -1 if it's impossible.

• Use Breadth First Search (BFS) to find the minimum number of jumps needed.

• Keep track of the visited shops to avoid revisiting them.

• If a shop has an Arr value of 0, it is impossible to reach the last shop.

• Return -1 if the last shop cannot be reached.

Implement a stack using two queues to store integer values with specified functions.

• Use two queues to simulate stack operations efficiently.

• Maintain one queue for storing elements and another for temporary storage during push operation.

• Ensure to handle edge cases like empty stack and maximum size limit.

• Example: Push operation involves transferring elements from one queue to another before adding the new element.

Implement Merge Sort algorithm to sort a sequence of numbers in non-descending order.

• Divide the input array into two halves recursively until each array has only one element.

• Merge the sorted halves to produce a completely sorted array.

• Time complexity of Merge Sort is O(n log n).

• Example: Input: [3, 1, 4, 1, 5], Output: [1, 1, 3, 4, 5]

Check if a given graph is bipartite by dividing its vertices into two disjoint sets.

• Create two sets 'U' and 'V' to divide the vertices

• Check if every edge connects vertices from different sets

• Use graph traversal algorithms like BFS or DFS to determine bipartiteness

Find the length of the longest substring without repeating characters in a given string.

• Use a sliding window approach to keep track of the longest substring without repeating characters.

• Use a hashmap to store the index of each character in the string.

• Update the start index of the window when a repeating character is encountered.

• Calculate the maximum length of the window as you iterate through the string.

• Return the maximum length as the result.

Remove duplicate occurrences of characters in a given string.

• Use a hash set to keep track of characters seen so far.

• Iterate through the string and add non-duplicate characters to a new string.

• Return the new string as the result.

Virtual memory allows the operating system to use a combination of RAM and disk space to simulate more memory than is physically available. Cache implementation involves storing frequently accessed data in a smaller, faster memory for quicker access.

• Virtual memory allows programs to use more memory than physically available by swapping data between RAM and disk.

• Cache implementation involves storing frequently accessed data in a smaller, faster memory for quicker access.

• Exampl...read more

Binary search on rotated array involves finding a target element in a sorted array that has been rotated.

• Find the pivot point where the array is rotated

• Determine which half of the array the target element lies in

• Perform binary search on the appropriate half of the array