Top Google Coding Question and Answer for Software Engineer Interview 2024
Let's start your Google software developer SDE interview preparation along with answers!
In this blog, we can provide you with the coding questions historically associated with Google interviews. Keep in mind that Google is known for asking a mix of algorithmic, data structure, and system design questions. However, Ringing Door can offer you a list of commonly asked coding questions that were popular in Google technical interviews and provide general advice on how to approach them. Keep in mind that the specifics may change over time, so it's crucial to stay updated with the latest trends and interview experiences shared by candidates.
Common coding questions and answers for Google software engineering interviews include:
Question 1:
Write code to check if three given binary trees are identical.
Python
class TreeNode:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def are_identical_trees(root1, root2, root3):
if not root1 and not root2 and not root3:
return True
if not root1 or not root2 or not root3:
return False
return (
root1.value == root2.value == root3.value and
are_identical_trees(root1.left, root2.left, root3.left) and
are_identical_trees(root1.right, root2.right, root3.right)
)
# Example usage:
# Construct three binary trees
tree1 = TreeNode(1)
tree1.left = TreeNode(2)
tree1.right = TreeNode(3)
tree2 = TreeNode(1)
tree2.left = TreeNode(2)
tree2.right = TreeNode(3)
tree3 = TreeNode(1)
tree3.left = TreeNode(2)
tree3.right = TreeNode(4)
# Check if the trees are identical
result = are_identical_trees(tree1, tree2, tree3)
if result:
print("The trees are identical.")
else:
print("The trees are not identical.")
In this code, the TreeNode class is used to represent the nodes of the binary tree. The are_identical_trees function recursively checks if the corresponding nodes of the three trees are equal and continue checking the left and right subtrees.
In the example usage, tree1 and tree2 are identical, while tree3 is different. The code will output "The trees are not identical."
Question 2:
Python
class ListNode:
def __init__(self, value=0, next=None):
self.value = value
self.next = next
def reverse_linked_list(head):
prev = None
current = head
while current is not None:
next_node = current.next
current.next = prev
prev = current
current = next_node
return prev
def print_linked_list(head):
current = head
while current is not None:
print(current.value, end=" -> ")
current = current.next
print("None")
# Example usage:
# Construct a sample linked list
original_head = ListNode(1)
original_head.next = ListNode(2)
original_head.next.next = ListNode(3)
original_head.next.next.next = ListNode(4)
print("Original Linked List:")
print_linked_list(original_head)
# Reverse the linked list
reversed_head = reverse_linked_list(original_head)
print("\nReversed Linked List:")
print_linked_list(reversed_head)
In this code, the ListNode class is used to represent nodes in the linked list. The reverse_linked_list function reverses the linked list by iterating through each node and reversing the direction of the pointers. The print_linked_list function is used to print the linked list for visualization.
In the example usage, the original linked list is created with values 1, 2, 3, and 4. The program then prints the original linked list, reverses it, and prints the reversed linked list. The output will show the reversed order of the linked list nodes.
Question 3:
Write a code to find the longest sequence in a binary tree.
To find the longest sequence in a binary tree, you can perform a depth-first search (DFS) traversal while keeping track of the current sequence length.
Here's a Python program that demonstrates this approach:
Python
class TreeNode:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def longest_sequence(root):
if not root:
return 0
def dfs(node, parent_value, current_length):
if not node:
return current_length
if node.value == parent_value + 1:
current_length += 1
else:
current_length = 1
left_length = dfs(node.left, node.value, current_length)
right_length = dfs(node.right, node.value, current_length)
return max(current_length, left_length, right_length)
return dfs(root, float('-inf'), 0)
# Example usage:
# Construct a sample binary tree
tree = TreeNode(1)
tree.left = TreeNode(2)
tree.right = TreeNode(3)
tree.left.left = TreeNode(4)
tree.left.right = TreeNode(5)
tree.right.right = TreeNode(6)
tree.right.right.left = TreeNode(7)
result = longest_sequence(tree)
print("The length of the longest sequence in the binary tree is:", result)
In this code, the TreeNode class represents the nodes of the binary tree. The longest_sequence function uses a depth-first search (DFS) approach to traverse the tree, keeping track of the current sequence length. The dfs helper function recursively explores the left and right subtrees while updating the sequence length based on the conditions.
In the example usage, the program constructs a sample binary tree and calculates the length of the longest sequence. The output will indicate the length of the longest sequence in the provided binary tree.
Question 4:
How to Traverse a Binary Search Tree?
Traversing a Binary Search Tree (BST) involves visiting each node in a specific order.
There are three common methods for traversing a binary search tree: In-order, Pre-order, and Post-order.
In-order Traversal:
- Traverse the left subtree.
- Visit the current node.
- Traverse the right subtree.
In Python, an in-order traversal can be implemented using recursion:
def in_order_traversal(node):
if node:
in_order_traversal(node.left)
print(node.value, end=" ")
in_order_traversal(node.right)
Pre-order Traversal:
- Visit the current node.
- Traverse the left subtree.
- Traverse the right subtree.
In Python:
def pre_order_traversal(node):
if node:
print(node.value, end=" ")
pre_order_traversal(node.left)
pre_order_traversal(node.right)
Post-order Traversal:
- Traverse the left subtree.
- Traverse the right subtree.
- Visit the current node.
In Python:
def post_order_traversal(node):
if node:
post_order_traversal(node.left)
post_order_traversal(node.right)
print(node.value, end=" ")
Here's a simple example of a BST node and its traversal:
class TreeNode:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
# Example Binary Search Tree
root = TreeNode(10)
root.left = TreeNode(5)
root.right = TreeNode(15)
root.left.left = TreeNode(3)
root.left.right = TreeNode(7)
root.right.right = TreeNode(20)
# In-order traversal
print("In-order Traversal:")
in_order_traversal(root)
print()
# Pre-order traversal
print("Pre-order Traversal:")
pre_order_traversal(root)
print()
# Post-order traversal
print("Post-order Traversal:")
post_order_traversal(root)
In this example, the BST has nodes with values 10, 5, 15, 3, 7, and 20. The three traversal methods are applied to the tree,
and the output shows the order in which the nodes are visited for each traversal.
Top Google Software Engineer (SDE) Interview Questions and Answers 2024
Google Software Engineer Summer Intern 2023 in India
Deloitte hiring Analyst Trainee for 2023 Batch Freshers | 6 LPA
Zoho Hiring Technical Support Engineer Freshers | Zoho Jobs
TCS MBA Off Campus Hiring 2022, 2023 | TCS | India
Accenture Bulk Hiring | 4.5 LPA | Accenture Off Campus Drive 2023
