1000+ Software Developer Intern Interview Questions and Answers

Find the length of the longest switching subarray in a given array of positive integers.

• Iterate through the array and keep track of the longest switching subarray found so far.

• Check if the numbers at even and odd positions are identical to determine a switching subarray.

• Return the length of the longest switching subarray.

• Example: For input [1, 4, 1, 4, 3, 2, 3, 0], the longest switching subarray is [1, 4, 1, 4] with length 4.

Count the total number of flips required in a binary matrix when encountering zeros.

• Iterate through the matrix and whenever a zero is encountered, flip all 1s in the corresponding row and column.

• Keep track of the total number of flips required.

• Return the total count of flips at the end.

Calculate the minimum number of stabs required to kill the king by reducing his health to zero.

• Iterate through each test case and calculate the minimum number of stabs required based on the given operations.

• For each test case, keep reducing the king's health using the first or second type of stab until it reaches zero.

• Consider the constraints provided to optimize the solution and handle edge cases.

• Example: For input 10, the minimum number of stabs required is 4 (10 -> 9 -> 3 ...read more

Find the minimum total cost to paint all houses such that no two adjacent houses have the same color.

• Use dynamic programming to keep track of the minimum cost of painting each house with each color while ensuring no two adjacent houses have the same color.

• At each house, calculate the minimum cost of painting it with each color based on the previous house's colors.

• Keep updating the minimum cost for each color at each house until reaching the last house.

• Return the minimum cost ...read more

Count the number of rectangles (excluding squares) that can be formed on an N x N chessboard.

• Calculate total rectangles using formula N*(N+1)*M*(M+1)/4 where M = N-1

• Subtract the number of squares (N*(N+1)*(2*N+1)/6) from total rectangles

• Return the count modulo 1000000007 for each test case

Implement Selection Sort algorithm to sort an array of non-negative integers in non-decreasing order.

• Iterate through the array and find the minimum element in the unsorted part.

• Swap the minimum element with the first element of the unsorted part.

• Repeat the process for the remaining unsorted part until the entire array is sorted.

Given two numbers represented as arrays, calculate their sum and return the result as an array.

• Iterate through the arrays from right to left, adding digits and carrying over if necessary

• Handle cases where one array is longer than the other by considering remaining digits

• Ensure the final sum array does not have any leading zeros

Swap two numbers without using a temporary variable.

• Use bitwise XOR operation to swap the values of X and Y without using a temporary variable.

• The XOR operation works by flipping the bits of the numbers.

• After swapping, X = X XOR Y and Y = X XOR Y.

• Finally, X = X XOR Y to get the original value of Y in X.

Distribute chocolates among students to minimize difference between largest and smallest packets.

• Sort the array of chocolates packets.

• Use sliding window technique to find the minimum difference between packets distributed to students.

• Return the minimum difference as the output.

The task is to determine whether a given linked list is circular or not.

• A linked list is circular if the next pointer of the last node points to the first node.

• An empty linked list is also considered circular.

• Check if any node has its next pointer equal to NULL.

• All the integers in the linked list are unique.

• The next pointer of a node with i'th integer is linked to the node with data (i+1)'th integer.

Remove nodes in a singly linked list with a greater value on the right.

• Traverse the linked list and compare each node's value with the values of nodes to its right.

• If a node has a greater value on the right, remove it from the linked list.

• Update the references of the previous node to skip the removed node.

Find the overall median of a matrix with sorted rows.

• Merge all elements of the matrix into a single sorted array

• Calculate the median of the merged array

• Handle odd number of elements by directly finding the middle element

Calculate the earliest day on which Ninja can buy all candies given the number of candy types, special offers, and Ninja's candy preferences.

• Iterate through each day and check if any special offers are available for the candies Ninja wants to buy.

• Keep track of the remaining candies Ninja needs to buy and the coins he has each day.

• Consider both regular price and sale price while making purchases.

• Return the earliest day on which Ninja can buy all candies.

Print a two-dimensional matrix in spiral order.

• Iterate through the matrix in a spiral order by keeping track of the boundaries.

• Print elements in the order: top row, right column, bottom row, left column.

• Repeat the process for inner submatrices until all elements are printed.

Given two binary trees T and S, determine if S is a subtree of T with the same structure and node values.

• Traverse both trees and check if S is a subtree of T at each node

• Use recursion to compare subtrees

• Handle edge cases like empty trees or null nodes

Count the number of triplets in a sorted doubly linked list such that their sum equals a given integer 'X'.

• Iterate through the linked list and for each node, use two pointers to find the other two nodes that sum up to 'X'.

• Keep track of the count of triplets found while traversing the list.

• Return the final count of triplets that sum up to 'X'.

Convert infix expression to postfix expression.

• Use a stack to keep track of operators and operands.

• Follow the rules of precedence for operators.

• Handle parentheses by pushing them onto the stack.

• Pop operators from the stack based on precedence.

• Append operands and operators to the postfix expression.

Count the total number of subsequences in which all elements are equal in an integer array.

• Iterate through the array and count the frequency of each element.

• Calculate the total number of subsequences for each element using the formula (frequency * (frequency + 1) / 2).

• Sum up the total number of subsequences for all elements and return the result modulo 10^9 + 7.

Find the length of the longest contiguous subarray with zero sum in an array of integers.

• Use a hashmap to store the prefix sum and its corresponding index.

• Iterate through the array and update the hashmap with the current sum and index.

• If the same sum is encountered again, the subarray between the two indices has a sum of zero.

Given two sorted arrays, find the path through common elements for maximum sum.

• Start with the array containing the smaller first common element

• Switch arrays at common elements to maximize the sum

• Continue adding elements until the end of the arrays

Determine if each number in the array has exactly 3 factors.

• Iterate through each number in the array and check if it has exactly 3 factors.

• Factors of a number can be found by iterating from 1 to the square root of the number.

• Count the number of factors and return 1 if it is exactly 3, else return 0.

Yes, this can be achieved by using a two-pointer approach to rearrange the array in-place.

• Use two pointers, one starting from the beginning and one from the end of the array.

• Swap elements at the two pointers if they are not in the correct order (negative before positive).

• Continue this process until the two pointers meet in the middle of the array.

Calculate the total amount of rainwater that can be trapped between given elevations in an array.

• Iterate through the array and calculate the maximum height on the left and right of each bar.

• Calculate the amount of water that can be trapped at each bar by taking the minimum of the maximum heights on the left and right.

• Sum up the trapped water at each bar to get the total trapped water for the entire array.

Connect ropes with minimum cost by merging smallest ropes first.

• Sort the array of rope lengths in ascending order.

• Merge the two smallest ropes at each step to minimize cost.

• Keep track of the total cost as you merge the ropes.

• Repeat the merging process until all ropes are connected.

• Return the total cost as the minimum cost to connect all ropes.

Create a new array with elements of given array in reverse order.

• Iterate through the given array in reverse order and copy elements to a new array.

• Ensure to handle edge cases like empty array or single element array.

• Use a temporary variable to swap elements for in-place reversal if required.

The problem involves finding the number of ways to achieve a target sum by rolling a given number of dice with a certain number of faces.

• Use dynamic programming to keep track of the number of ways to achieve each sum from 1 to the target sum.

• Iterate through the dice and faces to update the number of ways to reach each sum.

• Return the number of ways to achieve the target sum modulo 10^9 + 7.

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'.

The task is to find the in-order traversal of a given binary tree.

• Implement a recursive function to perform in-order traversal of the binary tree

• Start from the left subtree, then visit the root node, and finally visit the right subtree

• Use an array to store the values of the nodes in the in-order traversal

Find the Kth largest element in an array of distinct positive integers.

• Sort the array in non-increasing order and return the Kth element.

• Handle multiple test cases efficiently.

• Ensure all elements in the array are distinct.

The task is to find the maximum elements for each subarray of size K in a given array.

• Iterate through the array and maintain a deque of indices of the maximum elements in the current window of size K.

• For each new element, remove indices from the deque that are outside the current window.

• Add the index of the new element to the deque, and print the maximum element of the window if the first index in the deque is outside the window.

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.

• Handle cases where the node values can be negative.

• Ensure to consider only one path with the maximum sum.

Sort the list of strings based on the last character, then second last character, and so on.

• Iterate through each string in the list

• Sort the strings based on the last character first, then second last character, and so on

• Use a custom sorting function to achieve the required sorting order

Given a sorted matrix, find the position of a target integer in the matrix.

• Iterate through each row and column of the matrix

• Compare the target integer with the current element

• If the target integer is found, return the position

• If the target integer is not found, return {-1, -1}

Calculate the sum of nodes at the Kth level of a binary tree given the root.

• Traverse the binary tree level by level using BFS.

• Keep track of the current level while traversing.

• Sum the nodes at the Kth level and return the result.

The task is to find the maximum sum rectangle in a given matrix of integers.

• Iterate through all possible rectangles in the matrix

• Calculate the sum of each rectangle

• Keep track of the maximum sum rectangle found so far

• Return the maximum sum

The task is to find the minimum number of conference rooms required to organize all the meetings.

• Sort the meetings based on their start time.

• Initialize a priority queue to store the end times of the meetings in ascending order.

• Iterate through the sorted meetings and check if the start time of the current meeting is greater than the end time of the meeting at the top of the priority queue.

• If it is, remove the meeting from the priority queue.

• Add the end time of the current meet...read more

The minimum number of operations required to make all elements of the given array equal.

• Calculate the target value as the sum of all elements divided by the length of the array.

• Find the absolute difference between each element and the target value to determine the number of operations needed.

• Return the sum of all absolute differences as the minimum number of operations required.

Calculate the Nth term of a geometric progression series given the first term, common ratio, and term number.

• Use the formula for the Nth term of a GP series: A * (R^(N-1))

• Ensure to take the modulo 10^9 + 7 as the output

• Handle multiple test cases efficiently within the given time limit

Sort a Singly Linked List based on actual values instead of absolute values.

• Traverse the linked list and store the nodes in an array.

• Sort the array based on the actual values of the nodes.

• Reconstruct the linked list using the sorted array.

Given a dictionary of words and a continuous string, generate all possible sentences by inserting spaces.

• Use recursion to generate all possible combinations of words from the dictionary to form sentences.

• Check if a substring of the sentence matches any word in the dictionary, if so, recursively call the function with the remaining substring.

• Keep track of the current sentence being formed and add it to the result when the entire sentence is processed.

• Handle edge cases like emp...read more

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

Find the row with the maximum number of 1's in a grid of 0's and 1's.

• Iterate through each row of the grid and count the number of 1's in each row.

• Keep track of the row index with the maximum number of 1's seen so far.

• Return the index of the row with the maximum number of 1's.

Given an integer representing a binary sequence, find the maximum consecutive ones by flipping one bit.

• Iterate through the binary representation of the integer to find the longest sequence of ones.

• Track the positions of zeros to determine where to flip a bit for maximizing consecutive ones.

• Update the count of consecutive ones after flipping a zero to one.

• Return the maximum length of consecutive ones obtained by flipping one bit.

Calculate the probability that a knight remains on an N x N chessboard after making K moves.

• Use dynamic programming to calculate the probability of the knight staying on the board after each move.

• Consider all possible moves the knight can make from its current position.

• Keep track of the probabilities at each position on the board after each move.

• Normalize the probabilities at the end to get the final result accurate to six decimal places.

The goal is to determine the minimum number of scalar multiplications needed to multiply a chain of matrices together.

• Understand the matrix chain multiplication problem statement and how the dimensions of matrices are defined by the input array.

• Implement a dynamic programming approach to find the minimum cost of matrix multiplication.

• Consider the constraints provided and optimize the solution accordingly.

• Test the solution with different input arrays to ensure correctness.

• Focu...read more