1500+ Associate Software Engineer Interview Questions and Answers

Convert a given infix expression to postfix expression.

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

• Follow the rules of precedence for operators (*, / have higher precedence than +, -).

• Handle parentheses by pushing them onto the stack and popping when closing parenthesis is encountered.

The problem involves finding the minimum number of direction changes needed to create a valid path from the top-left to the bottom-right corner of a 2D grid.

• Create a graph representation of the grid with directions as edges.

• Use a shortest path algorithm like Dijkstra or BFS to find the minimum number of changes needed.

• Handle edge cases like unreachable bottom-right corner or invalid input.

• Consider implementing a helper function to convert directions to movements for easier tr...read more

The problem involves finding the number of distinct ways to completely cover a 2xN board using 2x1 tiles.

• Use dynamic programming to solve the tiling problem efficiently.

• Define a recursive function to calculate the number of ways to tile the board.

• Consider both horizontal and vertical placements of tiles.

• Implement the function to handle large values of N by using modulo arithmetic.

• Optimize the solution to avoid redundant calculations.

The task is to decode an encoded string back to its original form by repeating the encoded string 'count' times.

• Parse the input string to extract the count and the encoded string within the brackets

• Use recursion to decode the encoded string by repeating it 'count' times

• Handle nested encoded strings by recursively decoding them

• Output the decoded string for each test case

Yes, by using the super() method in the derived class.

• super() method calls the base class method

• Derived class must inherit from the base class

• Example: class Derived(Base): def method(self): super().method()

Find sum of numbers in range 1 to m (both inclusive) not divisible by n. Return difference between sum of non-divisible and divisible numbers.

• Iterate through range 1 to m and check if number is divisible by n.

• If not divisible, add to sum of non-divisible numbers.

• If divisible, add to sum of divisible numbers.

• Return difference between sum of non-divisible and divisible numbers.

The task is to find the longest distances from a source node to all nodes in a weighted directed acyclic graph.

• Implement a function that takes the number of nodes, edges, source node, and edge weights as input.

• Use a topological sorting algorithm to traverse the graph and calculate the longest distances.

• Return an array of integers where each element represents the longest distance from the source node to the corresponding node.

The task is to find all the different possible substrings of size two that appear in a given string as contiguous substrings.

• Iterate through the string and extract substrings of size two

• Store the substrings in an array

• Return the array of substrings

The task is to find the first repeated character in a given string of lowercase English letters.

• Iterate through the string and keep track of characters seen so far in a set.

• If a character is already in the set, return it as the first repeated character.

• If no repeated character is found, return '%'.

The problem involves finding the size of the largest subtree that is also a Binary Search Tree in a given binary tree.

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

• Keep track of the size of the largest BST subtree encountered so far.

• Use recursion to solve the problem efficiently.

• Consider edge cases like empty tree or single node tree.

• Example: For input 1 2 3 4 -1 5 6 -1 7 -1 -1 -1 -1 -1 -1, the largest BST subtree has size 3.

Identify the first non-repeating character in a given string and return it, or '#' if none exists.

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

• Iterate through the string again to find the first character with frequency 1

• Return the first non-repeating character or '#' if none exists

Implement a function to convert a string to an integer, ignoring non-numeric characters and considering negative numbers.

• Iterate through the characters of the string and check if they are numeric.

• Handle negative numbers by checking the first character of the string.

• Ignore non-numeric characters while converting the string to an integer.

• Return 0 if there are no numbers in the string.

• Ensure the resulting number is within the given constraints.

The objective is to determine the maximum profit by scheduling jobs within their deadlines.

• Sort the jobs array based on the profit in descending order.

• Iterate through the sorted array and schedule jobs based on their deadlines.

• Keep track of the maximum profit achieved by scheduling jobs within their deadlines.

Check if a given string is a palindrome after removing special characters, spaces, and converting to lowercase.

• Remove special characters and spaces from the string

• Convert the string to lowercase

• Check if the modified string is a palindrome by comparing characters from start and end

The function checks whether a given graph is bipartite or not.

• A bipartite graph can be divided into two independent sets such that every edge connects a vertex from one set to the other.

• We can use graph coloring algorithm to check if the graph is bipartite.

• Start by coloring the first vertex with one color and all its neighbors with the other color.

• Continue coloring the remaining vertices, making sure that no adjacent vertices have the same color.

• If at any point, we find that ...read more

The task is to determine the minimum number of platforms needed at a railway station based on arrival and departure times of trains.

• Sort the arrival and departure times in ascending order.

• Use two pointers to keep track of overlapping schedules.

• Increment platform count when a new train arrives before the previous one departs.

Find the longest palindromic substring in a given string, returning the rightmost one if multiple substrings are of the same length.

• Iterate through each character in the string and expand around it to check for palindromes

• Keep track of the longest palindromic substring found so far

• Return the rightmost longest palindromic substring

Identify numbers where sum of number and its digits equals given integer N.

• Iterate through numbers from 1 to N and check if sum of number and its digits equals N

• Use a helper function to calculate sum of digits for a given number

• Return the numbers that satisfy the condition in increasing order, else return -1

Count the total number of palindromic substrings in a given string.

• Iterate through each character in the string and expand around it to find palindromic substrings.

• Use dynamic programming to store the results of subproblems to avoid redundant calculations.

• Consider both odd-length and even-length palindromes while counting.

• Example: For input 'abbc', the palindromic substrings are ['a', 'b', 'b', 'c', 'bb'], totaling 5.

Implement a function to return the spiral order traversal of a binary tree.

• Traverse the binary tree in a spiral order, alternating between left to right and right to left.

• Use a queue to keep track of nodes at each level and a stack to reverse the order when necessary.

• Handle null nodes appropriately to maintain the spiral order traversal.

• Example: For input 1 2 3 -1 -1 4 5, the output should be 1 3 2 4 5.

Count the frequency of each word in a given string.

• Split the input string by spaces to get individual words.

• Use a hashmap to store the frequency of each word.

• Iterate through the words and update the hashmap accordingly.

• Print the unique words and their frequencies from the hashmap.

Abstract classes and interfaces in inheritance allow for defining common behavior and function signatures, while function overloading and overriding enable polymorphism.

• Abstract classes are classes that cannot be instantiated and may contain abstract methods that must be implemented by subclasses.

• Interfaces are similar to abstract classes but can only contain method signatures and constants, with no method implementations.

• Function overloading refers to having multiple methods...read more

Detect and remove loop in a singly linked list in place with O(n) time complexity and O(1) space complexity.

• Use Floyd's Cycle Detection Algorithm to identify the loop in the linked list.

• Once the loop is detected, use two pointers approach to find the start of the loop.

• Adjust the pointers to remove the loop and return the modified linked list.

• Example: For input 5 2 and 1 2 3 4 5, output should be 1 2 3 4 5.

Implement a priority queue using a heap data structure by completing the provided functions: push(), pop(), getMaxElement(), and isEmpty().

• Understand the operations: push() to insert element, pop() to remove largest element, getMaxElement() to return largest element, and isEmpty() to check if queue is empty.

• Implement a heap data structure to maintain the priority queue.

• Handle different types of queries based on the input provided.

• Ensure correct output for each type 3 query.

• Te...read more

Calculate the Nth Fibonacci number efficiently using dynamic programming.

• Use dynamic programming to store previously calculated Fibonacci numbers to avoid redundant calculations.

• Start with base cases F(1) and F(2) as 1, then iterate to calculate subsequent Fibonacci numbers.

• Return the Nth Fibonacci number as the final result.

Generate power set of a sorted array of integers with individually sorted subsets.

• Iterate through all possible combinations using bitwise operations.

• Sort each subset before adding it to the power set.

• Handle empty subset separately.

Detect if an array contains a Pythagorean triplet by checking if there are three integers x, y, and z such that x^2 + y^2 = z^2.

• Iterate through all possible combinations of three integers in the array and check if x^2 + y^2 = z^2.

• Use a nested loop to generate all possible combinations efficiently.

• Return 'yes' if a Pythagorean triplet is found, otherwise return 'no'.