400+ 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

Create a weather app that fetches and displays an image from a fixed URL upon button press.

• Use a button to trigger an API call to the fixed image URL.

• Handle the response to extract the image data.

• Display the image in a full-screen image view.

• Consider using libraries like Glide or Picasso for image loading.

• Ensure to handle errors, such as network issues or invalid responses.

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

Yes, I have worked on cloud technology and have knowledge of cloud architecture.

• I have experience working with cloud platforms such as Amazon Web Services (AWS) and Microsoft Azure.

• I have designed and implemented scalable and highly available cloud-based solutions.

• I am familiar with cloud architecture patterns like microservices, serverless computing, and containerization.

• I have utilized cloud services like Amazon S3 for storage, AWS Lambda for serverless computing, and AWS E...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

Design a screen to show 10 nearest restaurants in a list while keeping the UI uninterrupted.

• Use a scrollable list view to display the restaurants

• Implement a location-based search algorithm to find the nearest restaurants

• Include a search bar to allow users to search for specific restaurants

• Display relevant information for each restaurant such as name, rating, and distance

• Implement filters or sorting options to allow users to customize the list

• Consider using a map view to show ...read more

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

Check if any permutation of a string can form a palindrome by analyzing character frequencies.

• A palindrome reads the same forwards and backwards (e.g., 'racecar').

• For a string to have a permutation that is a palindrome, at most one character can have an odd frequency.

• Example: 'civic' can be rearranged to 'civic' (palindrome).

• Example: 'ivicc' can be rearranged to 'civic' (palindrome).

• Example: 'hello' cannot be rearranged to form a palindrome.

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.

Prints a linked list in a zigzag manner, alternating between left-to-right and right-to-left traversal.

• 1. Traverse the linked list level by level.

• 2. Use a flag to alternate the direction of printing for each level.

• 3. For odd levels, print from left to right; for even levels, print from right to left.

• 4. Example: For linked list 1 -> 2 -> 3 -> 4 -> 5, zigzag output would be: 1, 2, 3, 4, 5 (level 1), 5, 4, 3, 2 (level 2).

To transfer the Ball object from one thread to another in Android, we can use Handler or AsyncTask.

• Use Handler to post the Ball object from one thread to another

• Create a Handler in the receiving thread and use its post() method to receive the Ball object

• Alternatively, use AsyncTask to perform the transfer in the background thread and update the UI thread with the Ball object

Detecting a loop in a linked list and finding its starting point using Floyd's Cycle Detection Algorithm.

• Use Floyd's Tortoise and Hare algorithm: two pointers moving at different speeds.

• If they meet, a loop exists; otherwise, the list is acyclic.

• To find the starting point of the loop, reset one pointer to the head and move both pointers one step at a time.

• Example: For a list 1 -> 2 -> 3 -> 4 -> 5 -> 3 (loop back to 3), the starting point is 3.

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

Arrange players in a line based on match results: each wins against left, loses to right.

• Use a directed graph where each player is a node and edges represent wins.

• Topologically sort the graph to determine the order of players.

• Example: If A beats B and B beats C, the order is A, B, C.

• Ensure no cycles exist; if a cycle is found, the arrangement is impossible.

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

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

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.

Use a Trie data structure for efficient prefix matching of mobile number prefixes to identify operators.

• A Trie allows for efficient storage and retrieval of variable-length prefixes.

• Insert each operator's prefix into the Trie, e.g., '91' for Vodafone, '92' for Idea.

• To find the operator for a given mobile number, traverse the Trie based on the number's digits.

• The search stops when a matching prefix is found, returning the corresponding operator.

Design and implement a tic-tac-toe game with specific rules and requirements.

• Define the game board as a 2D array (3x3) to represent the grid.

• Implement functions to check for a win condition (three in a row).

• Create a function to handle player moves and validate input.

• Include a method to display the current state of the board.

• Add functionality for a computer player using a simple AI strategy.

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