Samsung Research Software Engineer Interview Questions and Answers

Explaining the difference between DFS and BFS and coding an algorithm for trees and graphs.

• DFS (Depth First Search) explores as far as possible along each branch before backtracking. BFS (Breadth First Search) explores all the vertices at the same level before moving to the next level.

• DFS is useful for finding a path to a target node, while BFS is useful for finding the shortest path to a target node.

• DFS can be implemented using recursion or a stack, while BFS can be implemen...read more

I will approach a problem by breaking it down into smaller parts and analyzing each part individually.

• Identify the problem and its scope

• Gather all relevant information and data

• Break down the problem into smaller parts

• Analyze each part individually

• Develop a plan of action

• Implement the plan and monitor progress

• Make adjustments as necessary

Dijkstra's algorithm finds the shortest path in a graph from a starting node to all other nodes.

• Use a priority queue to keep track of the shortest distance to each node

• Initialize distances to all nodes as infinity except the starting node as 0

• Iterate through all nodes and update distances if a shorter path is found

• Repeat until all nodes are visited and shortest paths are calculated

The diameter of a tree is the longest path between any two nodes in the tree.

• Find the longest path between any two nodes in the tree.

• This can be done by running two depth-first searches (DFS) on the tree.

• The diameter of the tree is the length of the path found by the second DFS.

A binary tree is considered a binary search tree if the left subtree of a node contains only nodes with keys less than the node's key and the right subtree contains only nodes with keys greater than the node's key.

• Check if the left child of a node is less than the node's key and the right child is greater than the node's key

• Recursively check all nodes in the tree to ensure they follow the binary search tree property

• Inorder traversal of the tree should result in a sorted list ...read more

Dry run on a sample test involves mentally executing the code to understand its flow and output.

• Understand the code logic and variables

• Step through each line of code

• Keep track of variable values at each step

• Predict the output based on the code execution

To find common ancestors of 2 nodes in a tree, traverse from both nodes to root and store paths. Then find the intersection of paths.

• Traverse from both nodes to root and store paths

• Find the intersection of paths to get common ancestors