Expedia Group Software Development Engineer Interview Questions and Answers

Round duration - 60 minutes
Round difficulty - Easy

There was 2 coding questions
Based on ds and algorithms

Q1. 
Minimum Number of Platforms Problem
Your task is to determine the minimum number of platforms required at a railway station so that no train has to wait.
Explanation:
Given two arrays:
• AT - represent...read more
Ans. 
Determine the minimum number of platforms needed at a railway station so that no train has to wait.
• Sort the arrival and departure times arrays in ascending order.

• Initialize two pointers, one for arrival times and one for departure times.

• Increment the platform count when a train arrives and decrement when it departs.

• Keep track of the maximum platform count needed.

• Return the maximum platform count as the minimum number o
Answered by AI
Add your answer
Q2. 
Minimum Number of Swaps to Achieve K-Periodic String
Given a string S of length N, an array A of length M consisting of lowercase letters, and a positive integer K, determine the minimum number of swaps r...read more
Ans. 
The minimum number of swaps required to make a string K-periodic by replacing characters with elements from an array.
• Iterate through the string and check if each character matches the character K positions ahead.

• Count the number of characters that need to be swapped to make the string K-periodic.

• Use the array elements to swap characters in the string.

• Return the total number of swaps needed for each test case.
Answered by AI
Add your answer

Round duration - 45 minutes
Round difficulty - Medium

It was good round they asked me about all the ds and algo basics 
With 2 problems by sharing the screeen

Q1. 
Number of Islands Problem Statement
You are provided with a 2-dimensional matrix having N rows and M columns, containing only 1s (land) and 0s (water). Your goal is to determine the number of islands in t...read more
Ans. 
Count the number of islands in a 2D matrix of 1s and 0s.
• Use Depth First Search (DFS) or Breadth First Search (BFS) to traverse the matrix and identify connected groups of 1s.

• Maintain a visited array to keep track of visited cells to avoid redundant traversal.

• Increment the island count each time a new island is encountered.

• Consider all eight possible directions for connectivity while traversing the matrix.

• Handle edge ca...read more
Answered by AI
Add your answer
Q2. 
Longest Increasing Subsequence Problem Statement
Given an array of integers with 'N' elements, determine the length of the longest subsequence where each element is greater than the previous element. This...read more
Ans. 
Find the length of the longest strictly increasing subsequence in an array of integers.
• Use dynamic programming to solve this problem efficiently.

• Initialize an array to store the length of the longest increasing subsequence ending at each index.

• Iterate through the array and update the length of the longest increasing subsequence for each element.

• Return the maximum value in the array as the result.
Answered by AI
Add your answer

Round duration - 50 minutes
Round difficulty - Medium

In this round, three questions were asked and all of them were based on DSA and a little bit about projects.

Q1. 
Minimum Jumps Problem Statement
Bob and his wife are in the famous 'Arcade' mall in the city of Berland. This mall has a unique way of moving between shops using trampolines. Each shop is laid out in a st...read more
Ans. 
Find the minimum number of jumps Bob needs to make from shop 0 to reach the final shop, or return -1 if impossible.
• Use BFS to traverse through the shops and keep track of the minimum jumps required.

• If at any point the current shop is unreachable (Arr[i] = 0), return -1.

• Optimize by using a visited array to avoid revisiting the same shop.
Answered by AI
Add your answer

Round duration - 25 Minutes
Round difficulty - Medium

Very friendly interviewer. Although waiting time was very high

Q1. 
Pair Sum Problem Statement
You are given an integer array 'ARR' of size 'N' and an integer 'S'. Your task is to find and return a list of all pairs of elements where each sum of a pair equals 'S'.
Note:
...read more
Ans. 
Find pairs of elements in an array that sum up to a given value, sorted in a specific order.
• Iterate through the array and for each element, check if the complement (S - current element) exists in a hash set.

• If the complement exists, add the pair to the result list.

• Sort the result list based on the criteria mentioned in the question.

• Return the sorted list of pairs.
Answered by AI
Add your answer

Round duration - 120 minutes
Round difficulty - Medium

10 min for debugging
40 min for problems(coding)
40 min for pyschometric
30 min for aptitude

Q1. 
Total Unique Paths Problem Statement
You are located at point ‘A’, the top-left corner of an M x N matrix, and your target is point ‘B’, the bottom-right corner of the same matrix. Your task is to calcula...read more
Ans. 
The task is to calculate the total number of unique paths from the top-left to bottom-right corner of an M x N matrix by moving only right or down.
• Use dynamic programming to solve this problem efficiently.

• Create a 2D array to store the number of unique paths for each cell in the matrix.

• Initialize the first row and first column with 1 as there is only one way to reach each cell in the first row and column.

• For each cell ...read more
Answered by AI
Add your answer
Q2. 
Most Frequent Word Problem Statement
You are given two strings 'A' and 'B' composed of words separated by spaces. Your task is to determine the most frequent and lexicographically smallest word in string ...read more
Ans. 
Find the most frequent and lexicographically smallest word in string 'A' that is not present in string 'B'.
• Split strings 'A' and 'B' into words

• Count frequency of each word in 'A'

• Check if word is not in 'B' and is the most frequent and lexicographically smallest

• Return the word or -1 if no such word exists
Answered by AI
Add your answer

Round duration - 90 Minutes
Round difficulty - Easy

timing was 4 pm . we connected on amazon chime. Initially he asked me a few things from resume then moved on to problem solving.

Q1. 
Number of Islands Problem Statement
You are provided with a 2-dimensional matrix having N rows and M columns, containing only 1s (land) and 0s (water). Your goal is to determine the number of islands in t...read more
Ans. 
Count the number of islands in a 2D matrix of 1s and 0s.
• Use Depth First Search (DFS) or Breadth First Search (BFS) to traverse the matrix and identify connected groups of 1s.

• Maintain a visited array to keep track of visited cells to avoid redundant traversal.

• Increment the island count each time a new island is encountered.

• Consider all eight possible directions for connectivity while traversing the matrix.

• Handle edge ca...read more
Answered by AI
Add your answer
Q2. 
Largest Rectangle in Histogram Problem Statement
You are given an array/list HEIGHTS of length N, where each element represents the height of a histogram bar. The width of each bar is considered to be 1.
...read more
Ans. 
Find the area of the largest rectangle that can be formed within the bounds of a given histogram.
• Iterate through the histogram bars and maintain a stack to keep track of increasing heights.

• Calculate the area of the rectangle formed by each bar as the smallest height in the stack times the width.

• Update the maximum area found so far and return it as the result.
Answered by AI
Add your answer

Round duration - 90 minutes
Round difficulty - Easy

This is a written round on paper for everyone. Three coding questions were given. Two out of three must be correct covering every single edge case to qualify for the next round. Only the most optimal solution was to be considered. 

Q1. 
Maximum Subarray Sum Problem Statement
Given an array arr of length N consisting of integers, find the sum of the subarray (including empty subarray) with the maximum sum among all subarrays.
Explanation...read more
Ans. 
Find the sum of the subarray with the maximum sum among all subarrays in an array of integers.
• Iterate through the array and keep track of the maximum sum subarray encountered so far.

• Use Kadane's algorithm to efficiently find the maximum subarray sum.

• Consider the sum of an empty subarray as 0.

• Example: For input arr = [-2, 1, -3, 4, -1], the maximum subarray sum is 4.
Answered by AI
Add your answer
Q2. 
Connecting Ropes with Minimum Cost
You are given 'N' ropes, each of varying lengths. The task is to connect all ropes into one single rope. The cost of connecting two ropes is the sum of their lengths. Yo...read more
Ans. 
Connect ropes with minimum cost by merging two smallest ropes at a time.
• Sort the array of rope lengths in ascending order.

• Merge the two smallest ropes at a time and update the cost.

• Repeat the process until all ropes are merged.

• Return the total cost as the minimum cost to connect all ropes.
Answered by AI
Add your answer
Q3. 
Left View of a Binary Tree Problem Statement
Given a binary tree, your task is to print the left view of the tree.
Example:
Input:
The input will be in level order form, with node values separated by a...read more
Ans. 
Print the left view of a binary tree given in level order form.
• Traverse the tree level by level and print the first node encountered at each level

• Use a queue to perform level order traversal

• Keep track of the level while traversing the tree
Answered by AI
Add your answer

Round duration - 50 minutes
Round difficulty - Easy

This was face to face interview round.

Q1. 
Finding Triplets in a Binary Tree Problem Statement
You are given a Binary Tree of integers and an integer 'X'. Your task is to find all the triplets in the tree whose sum is strictly greater than 'X'. Th...read more
Ans. 
Find all triplets in a binary tree whose sum is greater than a given integer X, with a grandparent-parent-child relationship.
• Traverse the binary tree to find all possible triplets with the required relationship.

• Keep track of the sum of each triplet and compare it with the given integer X.

• Return the triplets that satisfy the condition in any order.

• Ensure each triplet follows the format (grand-parent, parent, child).
Answered by AI
Add your answer
Q2. 
Loot Houses Problem Statement
A thief is planning to steal from several houses along a street. Each house has a certain amount of money stashed. However, the thief cannot loot two adjacent houses. Determi...read more
Ans. 
Determine the maximum amount of money a thief can steal from houses without looting two consecutive houses.
• Use dynamic programming to keep track of the maximum amount of money that can be stolen up to each house.

• At each house, the thief can either choose to steal from the current house or skip it and steal from the previous house.

• The maximum amount of money that can be stolen at the current house is the maximum of the ...read more
Answered by AI
Add your answer

Round duration - 60 minutes
Round difficulty - Easy

This was face to face interview round.

Round duration - 90 minutes
Round difficulty - Medium

Q1. 
Pythagorean Triplet Detection
Determine whether an array contains a Pythagorean triplet. A Pythagorean triplet exists if there are three integers x, y, z such that x² + y² = z² within the array.
Input:
...read more
Ans. 
Detect if an array contains a Pythagorean triplet.
• Iterate through all possible triplets in the array and check if they form a Pythagorean triplet.

• Use a nested loop to generate all possible combinations of three numbers in the array.

• Check if the sum of squares of two numbers is equal to the square of the third number.
Answered by AI
Add your answer

Round duration - 60 minutes
Round difficulty - Medium

Q1. 
Find Pair Sum Equal to K
Given an integer array arr and an integer 'Sum', find and return the total number of pairs in the array which, when added together, result in the 'Sum'.
Note:
The array can cont...read more
Ans. 
Find total number of pairs in array that sum to given value.
• Use a hashmap to store frequency of each element in the array.

• Iterate through the array and check if (Sum - current element) exists in the hashmap.

• Increment count of pairs if found and update hashmap accordingly.
Answered by AI
Add your answer

Round duration - 60 minutes
Round difficulty - Medium

Q1. 
Find the Next Smaller Palindrome
You are provided with a number N, expressed as a string S, which is a palindrome. The task is to determine the largest number strictly less than N that is also a palindrom...read more
Ans. 
Find the largest palindrome number strictly less than the given palindrome number.
• Iterate from the middle towards the start of the number and copy the digits to the left side to create the next smaller palindrome.

• Handle cases where the middle digit is not 0 by decrementing it and mirroring the left side to the right side.

• If the number is all 9s, change the first and last digits to 1 and fill the middle with 0s.
Answered by AI
Add your answer
Q2. 
Kth Largest Number in a Stream Problem Statement
Design a data structure that can handle an infinite stream of numbers and efficiently return the k-th largest number at any given time.
Explanation:
You ...read more
Ans. 
Design a data structure to efficiently return the k-th largest number from an infinite stream of numbers.
• Implement a max heap to store the numbers in the stream.

• Keep the heap size limited to k to efficiently find the k-th largest number.

• Update the heap when adding new numbers or querying for the k-th largest number.
Answered by AI
Add your answer

Round duration - 60 minutes
Round difficulty - Medium

Q1. 
Trapping Rain Water Problem Statement
You are given a long type array/list ARR of size N, representing an elevation map. The value ARR[i] denotes the elevation of the ith bar. Your task is to determine th...read more
Ans. 
Calculate the total amount of rainwater that can be trapped between given elevations in an array.
• Iterate through the array and calculate the maximum height on the left and right of each bar.

• Calculate the amount of water that can be trapped at each bar by taking the minimum of the maximum heights on the left and right.

• Sum up the trapped water at each bar to get the total trapped water for the entire array.
Answered by AI
Add your answer
Q2. 
Chemical Formula Problem Statement
Given a chemical formula as a string, return the count of each atom present in the compound.
Explanation:
• An atomic element starts with an uppercase letter followed ...read more
Add your answer

E-commerce

Round duration - 90 Minutes
Round difficulty - Medium

Interview started at 11:00 am. It was an online round. During the coding round I submitted optimized solution and got full acceptance of the solutions.

Q1. 
Detect Cycle in a Directed Graph
You are provided with a directed graph composed of 'N' nodes. You have a matrix called 'EDGES' with dimensions M x 2, which specifies the 'M' edges in the graph. Each edge...read more
Ans. 
Detect cycle in a directed graph using depth-first search (DFS) algorithm.
• Use DFS to traverse the graph and detect back edges indicating a cycle.

• Maintain a visited array to keep track of visited nodes during traversal.

• If a node is visited again during traversal and it is not the parent node, then a cycle exists.

• Return true if a cycle is detected, false otherwise.
Answered by AI
Add your answer

Round duration - 80 Minutes
Round difficulty - Medium

Interview started at 10:00 am. Interview went well, I was able to connect with the interviewer and enjoyed the whole interview

Q1. 
Next Smallest Palindrome Problem Statement
Find the next smallest palindrome strictly greater than a given number 'N' represented as a string 'S'.
Explanation:
You are given a number in string format, a...read more
Ans. 
Find the next smallest palindrome greater than a given number represented as a string.
• Convert the string to an integer, find the next greater palindrome, and convert it back to a string.

• Handle cases where the number is a palindrome or has all digits as '9'.

• Consider both odd and even length numbers when finding the next palindrome.
Answered by AI
Add your answer

Round duration - 80 Minutes
Round difficulty - Medium

Interview started at 11:00 am. Interview went well.

Q1. 
Boundary Traversal of a Binary Tree
Given a binary tree of integers, your task is to return the boundary nodes of the tree in Anti-Clockwise direction starting from the root node.
Input:
The first line ...read more
Ans. 
Return the boundary nodes of a binary tree in Anti-Clockwise direction starting from the root node.
• Traverse the left boundary nodes in a top-down manner

• Traverse the leaf nodes from left to right

• Traverse the right boundary nodes in a bottom-up manner

• Handle cases where duplicates occur in the boundary nodes

• Implement the function without printing as printing is already managed
Answered by AI
Add your answer