1000+ Software Developer Intern Interview Questions and Answers

Find sum of maximum and minimum elements in an array with least number of comparisons.

• Iterate through the array and compare elements in pairs to find maximum and minimum simultaneously.

• Keep track of current maximum and minimum as you iterate through the array.

• After iterating through the array, sum up the maximum and minimum found.

• Example: For input [1, 3, 5, 7, 9], compare 1 with 3, 5 with 7, and 3 with 9 to find min and max.

• Example: For input [-10, 4, 7, 19], compare -10 wit...read more

Given a river with fishes of different sizes and speeds, determine how many fishes survive after encounters.

• Iterate through the array of fishes and simulate encounters between fishes to determine survivors

• Use a stack to keep track of surviving fishes

• Compare sizes of fishes to determine which fish eats the other

Find the marker value needed for Kevin to eat at least 'M' fruits from 'N' buckets.

• Iterate through each test case and calculate the marker value needed based on the number of fruits in each bucket.

• Subtract the marker value from the number of fruits in each bucket and check if the total is at least 'M'.

• Return the highest possible marker value for each test case.

Find maximum elements for each subarray of size K in a given array of integers.

• Iterate through the array and maintain a deque to store the indices of elements in decreasing order.

• Pop elements from the deque if they are out of the current window.

• Keep track of the maximum element in each subarray of size K.

Given a sequence of room bookings and freeings, find the room that is booked the most times.

• Create a hashmap to store the count of each room booking.

• Iterate through the sequence of bookings and freeings, updating the count in the hashmap.

• Find the room with the highest count and return it. In case of a tie, return the lexicographically smaller room.

• Example: For input n = 6, Arr[] = {"+1A", "+3E", "-1A", "+4F", "+1A", "-3E"}, the output would be "1A".

Given empty pens, money, and costs, maximize usable pens by recycling and buying refills.

• Calculate total money after recycling pens

• Determine number of refills that can be bought with the money

• Combine refills with remaining pens to maximize usable pens

The problem requires updating an array based on a series of queries, where each query can either insert a value or perform a bitwise XOR operation on all elements.

• Use a loop to iterate through each query and update the array accordingly

• For type 1 query, append the value to the end of the array

• For type 2 query, perform a bitwise XOR operation on each element of the array with the given value

• Return the updated array after processing all the queries

Check if a given integer is a member of the Fibonacci series.

• Calculate Fibonacci numbers iteratively until reaching or exceeding the given integer N.

• Check if the last calculated Fibonacci number is equal to N.

• Return true if N is a Fibonacci number, otherwise return false.

The task is to find the Kth permutation of the sequence of first N natural numbers.

• Generate all possible permutations of the sequence of first N natural numbers

• Sort the permutations in lexicographical order

• Return the Kth permutation from the sorted list

Find K closest elements to X in a sorted array A.

• Use binary search to find the closest element to X in the array.

• Maintain two pointers to expand around the closest element to find K closest elements.

• Handle cases where two elements are equidistant by choosing the smaller one.

• Return the K closest elements in a new array.

Replace each node in a binary tree with its depth starting from root as 0.

• Traverse the binary tree in inorder fashion and update each node's data with its depth.

• Start with depth 0 for the root node and increment the depth as you go down the tree.

• Handle cases where nodes do not have left or right child by taking -1 in their place.

• Print the inorder traversal of the tree with updated node data representing the depth.

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.

Determine the minimum and maximum amounts of money needed to purchase all candies with a special offer.

• Iterate through the candy costs array to find the minimum and maximum costs.

• Consider the special offer of getting up to 'K' additional candies for free.

• Calculate the minimum cost by selecting the cheapest candies and taking free ones.

• Calculate the maximum cost by selecting the most expensive candies and taking free ones.

Calculate the sum of minimum and maximum elements of all subarrays of size K in an array.

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

• Keep track of the minimum and maximum elements in the current window and update the sum accordingly.

• Return the total sum of minimum and maximum elements for all subarrays of size K.

Given a sequence of non-negative integers representing the height of lines on a cartesian plane, find two lines that form a container with the maximum area of water.

• Use two pointers approach to find the maximum area

• Start with the widest container and gradually move the pointers towards each other

• Calculate the area at each step and update the maximum area

• The area is calculated as the minimum height of the two lines multiplied by the distance between them

The problem is to find the length of the smallest subarray in a given array with its sum greater than a given value.

• Iterate through the array and keep track of the current subarray sum

• If the current sum becomes greater than the given value, update the minimum subarray length

• If the current sum becomes negative, reset the sum and start a new subarray

• Return the minimum subarray length

Determine if a string consisting of '(' , ')' and '*' characters is valid based on given rules.

• Iterate through the string and keep track of the count of left parentheses, right parentheses, and stars.

• Use a stack to keep track of the positions of left parentheses.

• If at any point the count of right parentheses exceeds the count of left parentheses + stars, the string is invalid.

• If after iterating through the string, there are unmatched left parentheses, the string is invalid.

• If...read more

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 and its starting index

• Return the longest palindromic substring with the smallest start index

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 identify connected groups of 1s.

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

• Increment the island count each time a new island is encountered during traversal.

• Consider edge cases such as when the matrix is empty or when all cells are water (0s).

Determine the minimum number of operations to connect a graph by shifting edges between disconnected vertices.

• Use a disjoint set union (DSU) data structure to keep track of connected components.

• Count the number of connected components in the graph.

• The minimum number of operations required is equal to the number of connected components minus 1.

The problem asks to find the length of the longest substring without repeating characters in a given string.

• Use a sliding window approach to iterate through the string and keep track of the characters seen so far.

• Maintain a set to check for duplicate characters within the current substring.

• Update the maximum length of the substring whenever a duplicate character is encountered.

• Continue the process until the end of the string is reached.

• Return the maximum length of the substri...read more

The task is to count the number of occurrences of a given number in a sorted array.

• Use binary search to find the first and last occurrence of the given number in the array.

• Subtract the indices of the first and last occurrence to get the count.

• Handle the case when the number is not found in the array.

Given an array and a target sum, find all pairs of elements in the array that add up to the target sum.

• Create an empty list to store the pairs

• Iterate through the array and for each element, check if there is a complement (target sum minus the current element) in the array

• If a complement is found, add the pair (current element, complement) to the list

• Sort the list of pairs in non-decreasing order of their first value

• If two pairs have the same first value, sort them based on th...read more

Yes, the 0-1 Knapsack Problem can be solved using dynamic programming with a space complexity of O(W).

• Use dynamic programming to create a 2D array to store the maximum value that can be attained at each weight limit.

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

• The final answer will be the value at the last row and last column of the 2D array.

• Example: For the input (4, [2, 3, 4, 5], [3, 4, 5, 6], 5), the maxi...read more

DFS traversal to find connected components in an undirected and disconnected graph.

• Use Depth First Search (DFS) to traverse the graph and find connected components.

• Maintain a visited array to keep track of visited vertices.

• For each unvisited vertex, perform DFS to explore the connected component it belongs to.

• Print the vertices of each connected component in ascending order.

• Repeat the process until all vertices are visited and all connected components are identified.

Count distinct values obtained by applying bitwise OR operation on all possible subarrays of an array of positive integers.

• Use a set to store distinct values obtained by bitwise OR operation on all subarrays.

• Iterate through all subarrays efficiently to calculate distinct values.

• Optimize the solution to handle large input sizes efficiently.

• Handle bitwise OR operation on subarrays using bitwise operators.

• Consider using dynamic programming or sliding window technique for optimiz...read more

The problem involves finding the minimum number of jumps required to reach the last index of an array, where each element represents the maximum distance that can be jumped from that index.

• Start from index 0 and keep track of the farthest index that can be reached from each position.

• Update the current farthest index as the maximum of current farthest index and i + ARR[i].

• Increment the jump count when the current index reaches the previous farthest index.

• Continue this process ...read more

Find the length of the longest consecutive sequence in an unsorted array of integers.

• Iterate through the array and store all elements in a set for constant time lookups.

• For each element, check if it is the start of a sequence by looking for its previous number in the set.

• Update the length of the current sequence and the maximum length found so far.

• Return the maximum length of consecutive sequence found.

Find the minimum number of fountains to activate to water the entire garden.

• Iterate through the array to find the coverage of each fountain.

• Keep track of the farthest coverage reached by activating fountains.

• Activate the fountain that covers the farthest distance to minimize the number of fountains activated.

Find the maximum total booked minutes possible in a conference room for given meeting durations with a 15-minute break between meetings.

• Iterate through the list of meeting durations and calculate the maximum total booked minutes by considering the 15-minute break constraint.

• Keep track of the total booked minutes and skip consecutive meetings that violate the break constraint.

• Return the maximum total booked minutes for each test case.

Given stock prices, find the maximum profit from a single buy and sell action.

• Iterate through the array and keep track of the minimum price seen so far and the maximum profit achievable.

• Calculate the profit by subtracting the current price from the minimum price and update the maximum profit if needed.

• Return the maximum profit obtained after iterating through the array.

• Example: For prices = [2, 100, 150, 120], buy at 2 and sell at 150 for a profit of 148.

Convert a decimal number to base 58 using a specific alphabet.

• Iterate through each test case and convert the decimal number to base 58 using the given alphabet.

• Handle the conversion by dividing the number by 58 and taking the remainder to find the corresponding base 58 character.

• Build the base 58 representation by appending the characters in reverse order.

• Output the final base 58 representation for each test case.

Implement a function to determine the 'Count and Say' sequence after N iterations.

• Iterate through each term in the sequence, describing the previous term to generate the next term.

• Use a count to keep track of consecutive digits and append the count and digit to the result string.

• Repeat this process for N iterations to get the sequence after N iterations.

Find the minimum cost to reach the destination via train using given ticket costs for each pair of stations.

• Create a 2D array to store the costs from each station to the final destination.

• Use dynamic programming to calculate the minimum cost to reach each station.

• Iterate through the stations and update the minimum cost based on the previous stations.

• Return the minimum cost to reach the final station.

The Flood Fill Algorithm is used to change the color of a particular region in an image and all its adjacent same-colored pixels.

• The image is represented as a 2D array of positive integers

• The starting pixel and new color are given

• Adjacent pixels are connected in up, down, left, or right directions

• Diagonal pixels are not considered adjacent

• Implement the Flood Fill Algorithm to replace the color of the given pixel and its adjacent same-colored pixels with the new color

• Repeat th...read more

Find the Kth smallest and largest elements in an array.

• Sort the array and return the Kth element for smallest and (N-K+1)th element for largest.

• Use a priority queue to efficiently find the Kth smallest and largest elements.

• Handle edge cases where K is equal to 1 or N.

Multiply two numbers represented as linked lists and return the resultant multiplied linked list.

• Create a function that takes two linked lists as input and returns the product as a linked list

• Traverse both linked lists to extract the numbers, multiply them, and create a new linked list for the product

• Handle carry over while multiplying digits and adding to the result linked list

The task is to find the minimum number of deletions needed in a string to ensure each character appears a unique number of times.

• Iterate through the string and count the frequency of each character

• Track the frequencies in a hashmap

• Identify the characters with duplicate frequencies and calculate the minimum deletions needed

• Return the minimum number of deletions for each test case

Identify the length of the largest cycle in a maze represented by cells and an array of integers.

• Iterate through each cell and find cycles using DFS or Floyd's Tortoise and Hare algorithm.

• Keep track of visited cells and cycle lengths to identify the largest cycle.

• If a cell has no exit (-1), mark it as visited to avoid infinite loops.

Find the minimum distance Santa must travel to distribute 'K' gifts to 'K' different children standing in a straight line.

• Sort the array 'distance' in ascending order to simplify the problem.

• Calculate the distance between each adjacent child and find the minimum sum of distances for 'K' gifts.

• Keep track of the minimum sum of distances as you iterate through the array.

The task is to find the length of the longest increasing subsequence in a given array.

• Iterate through the array and keep track of the longest increasing subsequence length at each index.

• Use dynamic programming to store the lengths of increasing subsequences ending at each index.

• Return the maximum length from the dynamic programming array.

This question is about finding the position of the last person surviving in a circle of N people, where each person kills the Kth person in a clockwise direction.

• Implement a function that takes the number of test cases, N, and K as input

• For each test case, simulate the killing process by iterating through the circle and skipping K-1 people

• Keep track of the position of the last person surviving and return it as the output

The task is to select 'N' - 1 roads in a country with 'N' states, such that the tourist bus can travel to every state at least once at minimum cost.

• The problem can be solved using a minimum spanning tree algorithm, such as Kruskal's algorithm or Prim's algorithm.

• Create a graph representation of the country using the given roads and their costs.

• Apply the minimum spanning tree algorithm to find the minimum cost roads that connect all the states.

• Print the selected roads and thei...read more

The task is to determine the number of ways to paint a fence with 'N' posts using 'K' different colors, with the constraint that not more than two adjacent posts have the same color.

• Use dynamic programming to solve the problem efficiently.

• Consider the cases where the last two posts have the same color and different colors separately.

• Keep track of the number of ways to paint the fence at each post using a 2D array.

• Apply modulo 10^9 + 7 to avoid overflow issues.

• Return the final...read more

The task is to determine if a given 9x9 matrix can be filled with digits 1-9 to form a valid Sudoku solution.

• Iterate through each cell in the matrix.

• For each empty cell, try filling it with a digit from 1-9 and check if it satisfies the Sudoku conditions.

• Use helper functions to check if the digit is valid in the current row, column, and sub-matrix.

• If a valid digit is found, recursively fill the next empty cell.

• If all cells are filled and the Sudoku conditions are satisfied, r...read more