1000+ Software Developer Interview Questions and Answers for Freshers

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.

• At each index, decide whether to include the current element in the subarray or start a new subarray.

• Use Kadane's algorithm to efficiently find the maximum subarray sum in O(N) time complexity.

The task is to find the duplicate element in an array of integers.

• Iterate through the array and keep track of the frequency of each element using a hash map.

• Return the element with a frequency greater than 1.

• Alternatively, sort the array and check for adjacent elements with the same value.

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

Arrange numbers in a sequence in 'N' rows with increasing order and repeating after 9.

• Iterate through each test case and for each row, print numbers in increasing order with a loop.

• Keep track of the current number to print and reset to 1 after reaching 9.

• Handle formatting to align numbers correctly in each row.

• Ensure to print the correct number of rows based on the input 'N'.

Determine the minimum number of pre-processing moves required to make two strings equal by swapping characters and replacing characters in one string.

• Iterate through both strings simultaneously and count the number of characters that need to be swapped.

• Consider all possible swaps and replacements to find the minimum number of pre-processing moves.

• If the lengths of the strings are different, it's impossible to make them equal.

• Handle edge cases like empty strings or strings wit...read more

Compute the number of valid permutations of integers from 0 to N-1 such that at least K positions satisfy ARR[I] = I.

• Use dynamic programming to solve the problem efficiently.

• Consider the cases where K is equal to N or N-1 separately.

• Modulo the result by 10^9 + 7 to avoid overflow issues.

The question asks to find the total amount of rainwater that can be trapped in the given elevation map.

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

• Calculate the amount of water that can be trapped on each bar by subtracting its height from the minimum of the maximum heights on both sides.

• Sum up the amount of water trapped on each bar to get the total amount of rainwater trapped.

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

Find the greatest common divisor (GCD) of two given numbers 'X' and 'Y'.

• Iterate from 1 to the minimum of X and Y, check if both X and Y are divisible by the current number, update GCD if true

• Use Euclidean algorithm to find GCD: GCD(X, Y) = GCD(Y, X % Y)

• If one of the numbers is 0, the other number is the GCD

• Handle edge cases like when one of the numbers is 0 or negative

Sort an array of 0s, 1s, and 2s in linear time with a single scan approach.

• Use three pointers to keep track of the positions of 0s, 1s, and 2s in the array.

• Iterate through the array once and swap elements based on their values and the pointers.

• After the single scan, the array will be sorted in place with 0s, 1s, and 2s in order.

Given an encrypted string with repeated substrings represented by counts, find the K'th character of the decrypted string.

• Parse the encrypted string to extract substrings and their counts

• Iterate through the substrings and counts to build the decrypted string

• Track the position in the decrypted string to find the K'th character

The task is to find the subarray with the maximum sum in a given array.

• Iterate through the array and keep track of the current sum and maximum sum seen so far.

• If the current sum becomes negative, reset it to 0 as it won't contribute to the maximum sum.

• Compare the maximum sum with the sum of the current subarray to update the result.

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

• Consider edge cases like empty array or array with only...read more

Determine if a valid balanced sequence can be achieved by replacing 'X's with suitable brackets.

• Iterate through the string and keep track of the count of opening and closing brackets.

• If at any point the count of closing brackets exceeds the count of opening brackets, return False.

• If all 'X's can be replaced to form a valid balanced sequence, return True.

The problem involves determining the minimum number of operations needed to make a binary string beautiful by ensuring it contains alternating 0s and 1s.

• Iterate through the binary string and count the number of operations needed to make it beautiful by flipping the bits as required.

• Keep track of the current bit and compare it with the next bit to determine if a flip operation is needed.

• Return the total number of operations needed for each test case.

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

Given an array representing number of buses at each bus stop, determine how many buses originate from each stop.

• Iterate through the array and for each element, increment the count of buses originating from the corresponding bus stop.

• Use an array to store the count of buses originating from each stop.

• Remember to consider the constraint of 1-based indexing for bus stops.

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

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

• Handle self-cycles and cells with no exit by checking arr[i] = i and arr[i] = -1 respectively.

• Output the length of the largest cycle found or -1 if no cycles exist.

Determine the maximum number of elements that can be made equal by performing at most K operations on an array of integers.

• Sort the array in non-decreasing order to easily identify the elements that need to be increased

• Calculate the difference between adjacent elements to determine the number of operations needed to make them equal

• Keep track of the total number of operations used and the maximum number of elements that can be made equal

Check if a permutation of one string is a substring of another string.

• Create a frequency map of characters in str1.

• Iterate through str2 with a window of size N and check if the frequency map matches.

• Return 'Yes' if a permutation is found, 'No' otherwise.

The task is to find the total number of ways to make change for a specified value using given denominations.

• Use dynamic programming to solve this problem efficiently.

• Create a 1D array to store the number of ways to make change for each value from 0 to the target value.

• Iterate through the denominations and update the array based on the current denomination.

• The final answer will be the value at the target index of the array.

Linear search algorithm to find the first occurrence of an integer in an array.

• Iterate through the array and compare each element with the target integer.

• Return the index if the target integer is found, else return -1.

• Time complexity is O(N) where N is the size of the array.

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.

The given string needs to be reversed word wise, keeping the individual words intact.

• Split the string into an array of words using a space as the delimiter.

• Reverse the array of words.

• Join the reversed array of words using a space as the separator to form the final reversed string.

This question asks to find the position of a target integer in a row-wise and column-wise sorted 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 as {i, j}

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

The task is to determine the minimum number of towers needed to stack cubes in a specific order.

• Iterate through the array of cubes and maintain a stack to keep track of towers.

• For each cube, check if it can be placed on an existing tower or start a new one.

• Update the stack based on the cube's size and count the number of towers needed.

• Return the minimum number of towers required.

• Example: For input N = 3, ARR = [3, 2, 1], the output should be 1.

Construct the largest number by concatenating positive integers in the array exactly once.

• Sort the array of integers in a way that the concatenation of the numbers forms the largest possible number.

• Use a custom comparator function to sort the numbers based on their concatenated values.

• Join the sorted array elements to form the final largest number.

Check if Ninja can create two teams with equal members given an integer N and its divisors.

• Iterate through all divisors of N and assign members to the first or second team based on whether the divisor is even or odd.

• Keep track of the total members in each team and check if they are equal at the end.

• Return true if the total members in both teams are equal, false otherwise.

Determine the minimum time required to paint all boards with given constraints.

• Use binary search to find the minimum and maximum possible time to paint all boards.

• Iterate through the boards and assign them to painters based on the time constraints.

• Calculate the total time taken to paint all boards with the assigned painters.

Count the number of structurally unique binary trees that can be constructed with given Dragon Balls.

• Use dynamic programming to solve this problem efficiently.

• The number of structurally unique binary trees can be calculated using Catalan numbers.

• For each test case, calculate the number of structurally unique binary trees modulo 10^9 + 7.

• Return the count of unique binary trees for each test case.

The problem requires assigning aggressive cows to stalls in a way that maximizes the minimum distance between any two cows.

• Sort the array of stall positions in ascending order.

• Use binary search to find the largest minimum distance between cows.

• Check if it is possible to assign cows with this minimum distance by iterating through the sorted array.

• If it is possible, update the maximum distance and continue binary search for a larger minimum distance.

• Return the maximum distance ...read more

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

• Implement a function to check if the given number is a perfect square.

• Check if 5*N^2 + 4 or 5*N^2 - 4 is a perfect square to determine Fibonacci membership.

• Return true if the number is a perfect square of 5*N^2 + 4 or 5*N^2 - 4, otherwise false.

Calculate the minimum number of left shift operations needed to achieve the longest common prefix between two strings.

• Apply left shift operations to string B to find the longest common prefix with string A

• Count the number of left shifts needed to achieve the longest common prefix

• Return the minimum number of left shift operations for each test case

Given N meetings with start and end times, find the maximum number of meetings that can be organized in a single room without overlap.

• Sort the meetings based on their end times.

• Iterate through the sorted meetings and select the next meeting that does not overlap with the current meeting.

• Keep track of the selected meetings and return their indices in the order they are organized.

The minimum number of operations needed to make all elements of the array equal by performing addition, multiplication, subtraction, or division on any element.

• Iterate through the array and find the maximum and minimum values

• Calculate the difference between the maximum and minimum values

• Check if the difference is divisible by the length of the array

• If divisible, return the difference divided by the length

• If not divisible, return the difference divided by the length plus one

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

Count distinct pairs in an array whose sum equals a given target.

• Use two pointers approach to iterate through the array and find pairs with sum equal to target.

• Keep track of visited pairs to avoid counting duplicates.

• Return -1 if no such pair exists with the given target.

Generate all possible combinations of balanced parentheses for a given number of pairs.

• Use backtracking to generate all possible combinations of balanced parentheses.

• Keep track of the number of open and close parentheses used in each combination.

• Recursively generate combinations by adding open parentheses if there are remaining, and close parentheses if the number of open parentheses is greater than the number of close parentheses.

Identify the duplicate integer in an array containing numbers between 1 and N-1.

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

• Return the element with a frequency greater than 1 as the duplicate integer.

• Time complexity can be optimized to O(N) using Floyd's Tortoise and Hare algorithm.

• Example: For input [1, 2, 3, 4, 4], the output should be 4.

Implement a function to find the index of a given integer in a singly linked list.

• Traverse the linked list while keeping track of the index of each element.

• Compare each element with the target integer 'N'.

• Return the index if 'N' is found, otherwise return -1.

• Handle cases where the list is empty or 'N' is not found.

• Consider the constraints on the number of test cases and the length of the linked list.

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

The challenge involves splitting an array into sub-arrays to minimize cost based on unique elements and repetitions.

• Iterate through the array and keep track of unique elements and repetitions

• Calculate cost for each sub-array based on the rules provided

• Sum up the costs for all sub-arrays to get the total minimum cost

Design a seating arrangement for a high-security meeting with specific table assignments for security personnel and guests.

• Create a loop to iterate through each row from 1 to N.

• Assign tables on either end of each row to security personnel.

• For rows with only one table, assign it to security personnel.

• Display the seating arrangement with the number of people at each table.

• Example: For 4 rows, the output pattern is 1, 11, 121, 1221.

Calculate uneaten carrots by rabbits with specific jumping factors.

• Iterate through each carrot and check if any rabbit jumps on it.

• Use the jumping factors to determine which carrots will be eaten.

• Subtract the eaten carrots from the total to get the uneaten carrots.

Reverse the order of elements in an array and display the reversed array.

• Iterate through the array from both ends and swap the elements until the middle is reached.

• Use a temporary variable to store the element being swapped.

• Print the reversed array after all elements have been swapped.