Baidu Software Engineer Interview Questions and Answers

Round duration - 75 minutes
Round difficulty - Easy

This was the online round held at university. All students who met the eligibility criteria were called for the online test on hackerrank.

Q1. 
Anagram Difference Problem Statement
Given two strings, 'STR1' and 'STR2', of equal lengths, determine the minimum number of manipulations required to make the two strings anagrams of each other.
Input:
...read more
Ans. 
The problem involves finding the minimum number of manipulations required to make two strings anagrams of each other.
• Create frequency maps for both strings

• Find the absolute difference in frequencies of each character

• Sum up the absolute differences to get the total manipulations needed
Answered by AI
Add your answer

Round duration - 90 Minutes
Round difficulty - Medium

This round was technical round and the interview started with formal introduction and general questions.
After that We had a discussion on LRU Cache.
Followed by coding and set of data structure questions.

Q1. 
Gas Tank Problem Statement
You have a car with a gas tank of infinite capacity. There are 'N' gas stations located along a circular route, numbered from 0 to N-1. You begin your journey with an empty tank...read more
Ans. 
Find the starting gas station index to complete a circular route with gas and cost arrays.
• Iterate through gas stations, keeping track of total gas and total cost from each station

• If total gas is greater than or equal to total cost, update the starting station index

• Return the starting station index if a valid one is found, else return -1
Answered by AI
Add your answer

Round duration - 90 minutes
Round difficulty - Medium

This Round was DS and Algo round and it started with formal introduction, followed by 2 problems. We first dicussed the approach the time complexity and proper code covering all cases.

Q1. 
Boundary Traversal of Binary Tree
Given a binary tree of integers, your task is to print the boundary nodes of this binary tree in an anti-clockwise direction starting from the root node.
Input:
The fir...read more
Ans. 
Print the boundary nodes of a binary tree in an anti-clockwise direction starting from the root node.
• Traverse the left boundary nodes from the root to the leftmost leaf node.

• Traverse the leaf nodes from left to right.

• Traverse the right boundary nodes from the rightmost leaf node to the root.
Answered by AI
Add your answer
Q2. 
Maximum Sum of Two Non-Overlapping Subarrays
Given an integer array ARR and a positive integer K, your objective is to find two non-overlapping subarrays (contiguous) of length K each, such that their sum...read more
Ans. 
Find two non-overlapping subarrays of length K with maximum sum in an integer array.
• Iterate through the array to find all possible subarrays of length K.

• Calculate the sum of each pair of non-overlapping subarrays of length K.

• Keep track of the maximum sum obtained from the pairs of subarrays.
Answered by AI
Add your answer

Round duration - 30 minutes
Round difficulty - Easy

This was the Final Interview and it started with formal introduction and general HR questions. Then We discussed about the projects and the things written in my resume. The interviewer was very frank and this round was very interactive. He asked me about my college, my future plans, teachers, various subjects, why Expedia and questions like that.

Round duration - 120 minutes
Round difficulty - Easy

The test was divided into two parts : Section A had questions from Quantitative, C language, Logical and English. The second part had two coding questions.

Q1. 
Deletion in Circular Linked List Problem Statement
Given a Circular Singly Linked List of integers, and a specific value 'VAL', your task is to delete the first occurrence of this value in the linked list...read more
Ans. 
Delete the first occurrence of a specific value in a Circular Linked List.
• Traverse the circular linked list to find the value to be deleted.

• Update the pointers to skip the node containing the value.

• Handle edge cases like deleting the only node in the list.

• Return the modified circular linked list.
Answered by AI
Add your answer
Q2. 
LRU Cache Design Question
Design a data structure for a Least Recently Used (LRU) cache that supports the following operations:
1. get(key) - Return the value of the key if it exists in the cache; otherw...read more
Ans. 
Design a Least Recently Used (LRU) cache data structure that supports get and put operations with capacity constraints.
• Use a combination of a doubly linked list and a hashmap to efficiently implement the LRU cache.

• Keep track of the least recently used item and update it accordingly when new items are added.

• Ensure that the cache does not exceed its capacity by evicting the least recently used item when necessary.
Answered by AI
Add your answer

Round duration - 120 minutes
Round difficulty - Easy

Hello everyone! Expedia came to our campus for full time hiring of final year students. They had shortlisted candidates for the interviews by taking an online test comprised of four sections (Quantitative, C, Logical and English). Every section had a timer attached to it, so you need to think and answer quickly. Although, the questions were easy but cutoff was quite high. This round was followed by a coding round, comprised of two questions.

Q1. 
Problem: Deletion in Circular Linked List
You are provided with a Circular Linked List of integers and a specific integer, referred to as 'key'.
Your task is to implement a function that locates the spec...read more
Ans. 
Implement a function to delete a specific key from a Circular Linked List of integers.
• Traverse the Circular Linked List to find the key to be deleted.

• Adjust the pointers to remove the node containing the key.

• Handle the case where the Circular Linked List becomes empty after deletion.

• Return -1 if the Circular Linked List is empty after deletion.
Answered by AI
Add your answer
Q2. 
Page Faults Identification Problem Statement
In computing, a page fault occurs when a process accesses a memory page that is not currently mapped by the memory management unit. To handle new pages being b...read more
Ans. 
The problem involves determining the number of page faults using the Least Recently Used (LRU) replacement algorithm.
• Page faults occur when a process accesses a memory page not currently mapped by the memory management unit.

• Page replacement algorithm like LRU is used to decide which existing page should be replaced.

• The goal is to calculate the number of page faults based on the given input sequences and memory capacity...read more
Answered by AI
Add your answer

Round duration - 60 minutes
Round difficulty - Easy

The man who was taking my first round was my alumni. He started-off by asking my introduction and then gave me 2 programming questions to code. He then navigated on to my Codechef profile and asked a question that I did in the June 14 Long Contest. I explained him and he was satisfied. 
Tips : You don’t have to answer the stuffs quickly, rather you need to develop some test cases and have some discussion regarding the structure of the problem, and then answer.

Q1. 
Cycle Detection in a Singly Linked List
Determine if a given singly linked list of integers forms a cycle or not.
A cycle in a linked list occurs when a node's next points back to a previous node in the ...read more
Ans. 
Detect if a singly linked list forms a cycle by checking if a node's next points back to a previous node.
• Traverse the linked list using two pointers, one moving one step at a time and the other moving two steps at a time.

• If the two pointers meet at any point, it indicates the presence of a cycle in the linked list.

• Use Floyd's Cycle Detection Algorithm for efficient detection of cycles in a linked list.
Answered by AI
Add your answer
Q2. 
Closest Sum Problem Statement
Given an array of integers ARR of size N and an integer target, find three integers in ARR such that their sum is closest to the target. If there are two closest sums, return...read more
Ans. 
Find three integers in an array whose sum is closest to a given target, return the smallest sum if there are two closest sums.
• Iterate through all possible triplets in the array to find the sum closest to the target.

• Keep track of the closest sum found so far and update it if a closer sum is found.

• Return the closest sum at the end of the iteration.
Answered by AI
Add your answer

Round duration - 60 Minutes
Round difficulty - Medium

This round was purely based on Data Structures and Algorithms . One has to be fairly comfortable in solving Algorithmic problems to pass this round . Both the questions asked were quite common and luckily I had already prepared them from CodeStudio and LeetCode.

Q1. 
Binary Tree Traversals Problem Statement
Given a Binary Tree with 'N' nodes, where each node holds an integer value, your task is to compute the In-Order, Pre-Order, and Post-Order traversals of the binar...read more
Ans. 
Compute the In-Order, Pre-Order, and Post-Order traversals of a Binary Tree given in level-order format.
• Implement functions to perform In-Order, Pre-Order, and Post-Order traversals of a Binary Tree.

• Use level-order input to construct the Binary Tree.

• Traverse the Binary Tree recursively to generate the required traversals.

• Ensure proper handling of null nodes represented by -1 in the input.

• Return the three traversals as ...read more
Answered by AI
Add your answer
Q2. 
Reverse Linked List Problem Statement
Given a Singly Linked List of integers, your task is to reverse the Linked List by altering the links between the nodes.
Input:
The first line of input is an intege...read more
Ans. 
Reverse a singly linked list by altering the links between nodes.
• Iterate through the linked list and reverse the links between nodes

• Use three pointers to keep track of the current, previous, and next nodes

• Update the links between nodes to reverse the list

• Return the head of the reversed linked list
Answered by AI
Add your answer

Round duration - 45 Minutes
Round difficulty - Medium

This round basically tested some concepts from Data Structures and File Manipulation .

Q1. 
Intersection of Two Arrays Problem Statement
Given two arrays A and B with sizes N and M respectively, both sorted in non-decreasing order, determine their intersection.
The intersection of two arrays in...read more
Ans. 
The problem involves finding the intersection of two sorted arrays efficiently.
• Use two pointers to iterate through both arrays simultaneously.

• Compare elements at the pointers and move the pointers accordingly.

• Handle cases where elements are equal and update the intersection array.

• Return the intersection array as the result.
Answered by AI
Add your answer