300+ Software Development Engineer Interview Questions and Answers

Find minimum vertices to place policemen in an acyclic graph of a city to cover all roads.

• Use Depth First Search (DFS) to traverse the graph

• Maintain a set of visited vertices to avoid revisiting

• For each unvisited vertex, place a policeman and mark all connected edges as covered

• Repeat until all edges are covered

• Return the minimum number of policemen placed

To search for contacts with duplicate names and numbers, create a search function that checks both fields.

• Create a function that takes a search term as input

• Iterate through the list of contacts

• Check if the search term exists in the Name field or Num field

• Return the contacts that match the search term

Find shortest path between 'S' and 'E' in a matrix filled with '0's and 'x's

• Use Breadth First Search (BFS) algorithm to find shortest path

• Create a visited matrix to keep track of visited cells

• Create a queue to store cells to be visited

• Start BFS from 'S' and keep track of distance to each cell

• When 'E' is found, return the distance to it

At least 10 rats are needed to figure out which bottle contains poison in an hour.

• Number the bottles from 1 to 1000.

• Use binary representation of the bottle numbers to assign each rat a unique combination of bottles to drink.

• For example, Rat 1 drinks from all bottles with a binary representation that has a 1 in the least significant bit (LSB).

• After an hour, the rats that die will indicate the binary representation of the poisoned bottle.

• By decoding the binary representation, t...read more

Find all permutations of a given string, handling duplicates.

• Use recursion to generate all possible permutations

• Use a hash set to keep track of already generated permutations

• Handle duplicates by skipping already generated permutations

• Time complexity is O(n!)

• Return an array of strings containing all permutations

Find minimum length substring of string a containing all characters of string b.

• Use sliding window approach

• Maintain a frequency map of characters in b

• Move the window until all characters of b are present

• Update the minimum length substring as you move the window

Pre-process a dictionary to output anagrams of a given string. Data structure, time and space complexity?

• Create a hash table with sorted string as key and list of anagrams as value

• Iterate through dictionary and sort each string, add to hash table

• To find anagrams of given string, sort it and look up in hash table

• Time complexity: O(n * klogk), space complexity: O(n)

• n = number of strings in dictionary, k = length of longest string

Find the number of elements shifted in a sorted array after shifting n elements from right to first.

• Find the index of the minimum element in the shifted array

• The number of elements shifted is equal to the index of the minimum element

• Use binary search to find the minimum element in O(log n) time

Find the first level in a complete binary tree where the height difference between left and right subtrees is more than 1.

• Traverse the binary tree level by level using breadth-first search

• For each level, calculate the height difference between the left and right subtrees

• Return the level number when the height difference is more than 1

Given an array of natural numbers, find the first missing natural number.

• Sort the array and iterate through it to find the first missing number.

• Use a hash set to keep track of the numbers present in the array.

• The first missing number will be the smallest positive integer not present in the array.

A HashMap is a data structure that stores key-value pairs and provides constant time complexity for basic operations.

• Implement a hash function to convert keys into array indices

• Create an array to store the key-value pairs

• Handle collisions using a technique like chaining or open addressing

• Implement methods like put(), get(), and remove() to interact with the HashMap

The question asks to find the similarity between two words by normalizing the length of the longest common subsequence (LCS) by the total length of the string.

• Implement a function that takes two words as input

• Find the length of the longest common subsequence (LCS) between the two words

• Normalize the length of LCS by dividing it by the total length of the string

• Return the normalized similarity value

Design process for new client requirements and technology decisions

• Gather requirements from client

• Analyze requirements and identify potential solutions

• Evaluate technologies and choose the best fit

• Create a design document outlining the solution

• Develop a prototype or proof of concept

• Test and refine the solution

• Implement and deploy the solution

• Provide ongoing support and maintenance

Prove that in-order traversal of a BST is always sorted and vice versa

• In-order traversal of a BST visits nodes in ascending order

• If a binary tree's in-order traversal is sorted, it is a BST

• A BST's left subtree contains only nodes with values less than its root

• A BST's right subtree contains only nodes with values greater than its root

To find least common ancestor of two nodes in a binary tree, traverse the tree from root to the nodes and store the paths. Then compare the paths to find the common ancestor.

• Traverse the binary tree from root to the two nodes and store the paths

• Compare the paths to find the common ancestor

• If the binary tree is a BST, compare the values of the nodes to find the common ancestor

• If one of the nodes is the ancestor of the other, return the ancestor node

Implement Facebook's 'People you may know' feature using BFS and mutual friend counter.

• Create a graph of users and their friends

• Perform BFS on the graph starting from the user in question

• For each friend of the user, increment a counter for their mutual friends

• Sort the list of potential friends by mutual friend count

• Exclude already connected friends and suggest top potential friends

Normalization is the process of organizing data in a database to reduce redundancy and dependency.

• 2NF eliminates partial dependencies by ensuring that non-key attributes depend on the entire primary key.

• 3NF eliminates transitive dependencies by ensuring that non-key attributes depend only on the primary key.

• BCNF eliminates overlapping candidate keys by ensuring that each determinant is a candidate key.

Find an element k in a sorted array such that Max(k) < n.

• Use binary search to find the largest element smaller than n

• Start with mid element and adjust search range based on comparison with n

• Return -1 if no such element exists

The backend technologies used are Java, Spring Boot, and MySQL. The front end technologies used are Angular and TypeScript.

• Backend: Java

• Backend Framework: Spring Boot

• Database: MySQL

• Frontend: Angular

• Frontend Language: TypeScript

To identify swapped nodes in a binary search tree, we need to perform an inorder traversal and compare adjacent nodes.

• Perform an inorder traversal of the binary search tree

• Compare each node with its adjacent node

• If a node is smaller than its previous node, mark it as a swapped node

• If two nodes are swapped, swap their values to restore the original binary search tree

Indexes are used to improve database performance by allowing faster data retrieval. Clustered indexes determine the physical order of data, while non-clustered indexes are separate structures.

• Indexes are used to speed up data retrieval in databases

• Clustered indexes determine the physical order of data in a table

• Non-clustered indexes are separate structures that point to the data in a table

• A table can have only one clustered index, but multiple non-clustered indexes

• Indexes can...read more

The function takes a binary tree as input and returns a doubly linked list of all the nodes at each level.

• Use a breadth-first search (BFS) algorithm to traverse the binary tree level by level.

• For each level, create a doubly linked list and add the nodes to it.

• Connect the doubly linked lists of each level to form the final result.

Interview question for Software Development Engineer position on Longest Palindromic Substring, Shortest path in Binary Maze, and Valid Stack Sequences.

• Longest Palindromic Substring - use dynamic programming to solve

• Shortest path in Binary Maze - use BFS algorithm to find the shortest path

• Valid Stack Sequences - simulate the stack push and pop operations to check if the given sequences are valid

Find the heavier ball from 8 identical balls using a balance weighting machine in least number of tries.

• Divide the balls into 3 groups of 3, 3, and 2 balls.

• Weigh the first two groups against each other.

• If they balance, the heavier ball is in the remaining group of 2 balls.

• If one group is heavier, weigh two balls from that group against each other.

• If they balance, the heavier ball is the remaining ball.

• If one ball is heavier, that is the heavier ball.

GET is used to request data from a specified resource, POST is used to submit data to be processed to a specified resource, PUT is used to update a resource, and PATCH is used to partially update a resource.

• GET requests data from a specified resource without changing it

• POST submits data to be processed to a specified resource

• PUT updates a resource with the data provided

• PATCH partially updates a resource with the data provided

Yes, we can use Breadth First Search (BFS) algorithm to determine if we can reach index 0 with the given operations.

• Use BFS algorithm to explore all possible paths starting from index 0.

• Keep track of visited indices to avoid infinite loops.

• If we reach an index with value 0, return true; otherwise, return false.

Detect loop in linked list and return node where loop starts.

• Use two pointers, one moving one node at a time and the other moving two nodes at a time

• If there is a loop, the two pointers will eventually meet at a node inside the loop

• Reset one of the pointers to the head of the linked list and move both pointers one node at a time

• The node where the two pointers meet is the start of the loop

An alternative to using a cursor to iterate row by row is to use a WHILE loop.

• Use a WHILE loop to iterate through rows

• Use a variable to keep track of the current row

• Exit the loop when there are no more rows to iterate through

Design ADT for chess game classes

• Create classes for pieces (king, queen, etc.), board, player, game

• Use inheritance to represent different types of pieces

• Implement methods for moving pieces, checking for checkmate, etc.

Given a matrix and value k, find k*k submatrix with maximum sum.

• Iterate over all submatrices of size k*k and calculate their sum.

• Keep track of the maximum sum and the corresponding submatrix.

• Use dynamic programming to optimize the solution.

• Time complexity can be reduced to O(m*n*k^2) using prefix sum technique.

Optimizing for binary search tree

• Ensure the tree is balanced to maintain O(log n) search time

• Implement efficient insertion and deletion algorithms

• Use in-order traversal for sorted output

• Consider using AVL or Red-Black trees for self-balancing

• Avoid using recursion for large trees to prevent stack overflow

Shortest path in 2D matrix

• Use BFS or Dijkstra's algorithm

• Create a visited matrix to avoid revisiting cells

• Keep track of distance and path

• Consider obstacles or blocked cells

To detect the best day to buy and sell stock in an integer array representing stock prices and days in O(N).

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

• Calculate the profit by subtracting the current price from the minimum price.

• Update the maximum profit and best buy/sell days accordingly.

• Return the best buy and sell days to maximize profit.

Multiingule is not a known term. No extension is used for it.

• Multiingule is not a recognized term in software development.

• There is no file extension associated with multiingule.

• It is possible that the interviewer misspoke or meant to ask a different question.

User control is a reusable UI component that allows users to interact with an application. An extension of user control is a custom control that inherits from the user control.

• User control is a UI component that can be reused across an application

• It allows users to interact with an application

• An extension of user control is a custom control that inherits from the user control

• Custom controls can be created by adding additional functionality to the base user control

• Examples of ...read more

Code for subtitle syncing application

• Create a function to parse subtitle file and extract time stamps

• Create a function to parse video file and extract time stamps

• Calculate time difference between subtitle and video time stamps

• Adjust subtitle time stamps accordingly

• Output synced subtitle file

Print first 200 Fibonacci numbers in reverse order.

• Use an array to store the Fibonacci numbers

• Start with 0 and 1, then add the previous two numbers to get the next one

• Loop through the array in reverse order to print the numbers

Check if a binary tree is a BST or not and give time and space complexity.

• Traverse the tree in-order and check if the elements are in ascending order

• Keep track of the maximum value seen so far while traversing

• If any element violates the ascending order, return false

• Time complexity: O(n), Space complexity: O(h) where h is the height of the tree

Find the first occurrence of 1 in a sorted array of 0s and 1s.

• Use binary search to find the first occurrence of 1.

• If mid element is 1, check left subarray for first occurrence.

• If mid element is 0, check right subarray for first occurrence.

Sort an array of 0s, 1s, and 2s without using counting sort.

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

• Traverse the array and swap elements to their respective positions.

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

Count number of flips required to balance parentheses in a string

• Iterate through the string and keep track of open and close brackets

• If a close bracket is encountered without a corresponding open bracket, increment flip count

• Return the total number of flips required to balance the parentheses

Calculate the maximum absolute difference between the sums of any two levels in a binary tree.

• Traverse the binary tree level by level and calculate the sum of nodes at each level.

• Keep track of the maximum absolute difference between the sums of any two levels encountered so far.

• Return the maximum absolute difference found.

Use a hashmap to separate prime and non-prime numbers in an array of strings.

• Iterate through the array and convert each string to an integer.

• Use a hashmap to store prime and non-prime numbers based on their divisibility.

• Convert the hashmap back to separate arrays for prime and non-prime numbers.

Separate prime numbers from non-prime numbers in a linked list while preserving their order.

• Iterate through the linked list and separate prime numbers from non-prime numbers

• Create two separate linked lists for prime and non-prime numbers

• Maintain the order of numbers while separating them

• Example: Input: 1 -> 2 -> 3 -> 4 -> 5, Output: Prime: 2 -> 3 -> 5, Non-prime: 1 -> 4

Efficient way to search a given element in an array of integers with adjacent elements 1+ or 1- from each other.

• Use binary search algorithm to search the element in O(log n) time complexity.

• Check the middle element and compare it with the given element.

• If the middle element is greater than the given element, search in the left half of the array.

• If the middle element is smaller than the given element, search in the right half of the array.

• Repeat until the element is found or t...read more

Measure the height of a room using a thread.

• Tie one end of the thread to a known height point, such as a door handle.

• Hold the other end of the thread and let it hang down to the floor.

• Mark the point where the thread touches the floor.

• Repeat the process at different points in the room to get multiple measurements.

• Take the average of the measurements to estimate the height of the room.

Bean annotation is used in Spring Boot on class or method to indicate that a method produces a bean to be managed by the Spring container.

• Bean annotation is used on methods within a class to indicate that the method produces a bean to be managed by the Spring container.

• It can also be used at the class level to indicate that the class itself is a Spring bean.

• For example, @Bean annotation can be used on a method that creates and returns a DataSource bean in a configuration clas...read more