60+ Expedia Group Interview Questions and Answers

Implement a function to determine the 'Count and Say' sequence after N iterations.

• Iterate through each term in the sequence, describing the previous term to generate the next term.

• Use a count to keep track of consecutive digits and append the count and digit to the result string.

• Repeat this process for N iterations to get the sequence after N iterations.

Find the number of starting indices from which a Ninja can reach the last stone by following specific jump rules.

• Iterate through the array and keep track of the possible jumps for each index based on the rules provided.

• Use dynamic programming or a stack to efficiently calculate the number of starting indices.

• Consider edge cases where some indices may have no possible jumps.

• Example: For the input [10, 13, 12, 14, 15], the Ninja can start from indices 0 and 1 to reach the last ...read more

Calculate the probability that a knight remains on an N x N chessboard after making K moves.

• Use dynamic programming to calculate the probability of the knight staying on the board after each move.

• Consider all possible moves the knight can make from its current position.

• Keep track of the probabilities at each position on the board after each move.

• Normalize the probabilities at the end to get the final result.

• Example: For a 3x3 board and 2 moves, the probability of the knight s...read more

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.

The objective is to rearrange a string so that no two adjacent characters are identical. Return the rearranged string or 'NO SOLUTION'.

• Iterate through the string and count the frequency of each character.

• Create two lists, one for characters with odd frequency and one for characters with even frequency.

• If the count of characters with odd frequency is greater than 1, return 'NO SOLUTION'.

• Alternate between characters with even and odd frequency to create the rearranged string.

Find the length of the longest subarray with equal number of 0s and 1s in a given array of 0s and 1s.

• Iterate through the array and maintain a running count of the difference between the number of 0s and 1s encountered so far.

• Store the count values in a hashmap with the index as the key.

• If the same count is encountered again, calculate the length of the subarray between the two occurrences.

• Return the maximum length found across all counts.

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

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

Count the number of nodes within K-distance from marked nodes in a connected, undirected, acyclic graph.

• Create a graph using the given vertices and edges.

• Perform a BFS traversal starting from each marked node to find nodes within K-distance.

• Count the nodes within K-distance from all marked nodes and return the total count.

Reformat dates from 'Day Month Year' format to 'YYYY-MM-DD' format.

• Parse the input string to extract day, month, and year.

• Convert month to its numerical equivalent (e.g., 'Jan' to '01').

• Format the date in 'YYYY-MM-DD' format and output.

Count the number of distinct islands in a 2D array of 0s and 1s.

• Identify connected groups of 1s to form islands

• Check if islands can be translated to overlap without rotation or reflection

• Count the number of distinct islands based on the above criteria

Develop a function to remove all instances of a given character from a string.

• Iterate through the string character by character and skip the character to be removed.

• Build a new string by appending characters that are not equal to the given character.

• Return the final modified string.

• Handle edge cases like empty string or character not found in the string.

The problem involves counting the number of distinct ways to climb N stairs by taking 1 or 2 steps at a time.

• Use dynamic programming to solve the problem efficiently.

• Define a recursive function to calculate the number of ways to reach each stair.

• Consider base cases for 0 and 1 stairs.

• Use memoization to store intermediate results and avoid redundant calculations.

• Return the result modulo 10^9+7 to handle large values.

The problem involves determining the number of ways to partition a number into non-empty groups with specific constraints.

• Use dynamic programming to solve the problem efficiently.

• Consider the base cases when N = 0 or K = 0.

• Keep track of the number of ways to partition N into K groups satisfying the given conditions.

• Apply modulo 1e9 + 7 to the final result.

• Example: For input 5 3, the output is 2 as there are 2 ways to partition 5 into 3 groups.

Given an array of candidate names and their votes, find the candidate with the maximum votes, with tiebreaker based on lexicographical order.

• Iterate through the array of candidate names and keep track of the count of each candidate's votes.

• Find the candidate with the maximum votes. If there is a tie, return the lexicographically smaller name.

• Handle multiple test cases by repeating the process for each test case.

• Output the name of the winning candidate for each test case.

Find the third largest element in an array of distinct integers.

• Sort the array in descending order and return the element at index 2.

• Alternatively, keep track of the three largest elements while iterating through the array.

• Handle cases where there are less than 3 elements in the array.

Compare two version numbers to determine the latest version.

• Split the version numbers by '.' and compare each part from left to right.

• If a part in Version2 is greater than the corresponding part in Version1, Version2 is the latest.

• Handle cases where one version number has more parts than the other.

• Return 1 if Version1 is the latest, -1 if Version2 is the latest, and 0 if they are the same.

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.

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.

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.

• Constraints include the number of test cases, number of p...read more

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.

The problem involves transforming an array into specific elements using given operations. Find the minimum number of steps required.

• Iterate through the array and calculate the number of steps needed to transform each element into the desired value

• For each element, calculate the difference between the current value and the desired value, then determine the minimum number of steps required to reach that value

• Keep track of the total number of steps needed for each test case and ...read more

Search for integers in a rotated sorted array efficiently.

• Implement binary search to find the target integer in the rotated array.

• Handle the rotation while performing binary search.

• Return the index of the target integer if found, else return -1.

Find pairs of elements in an array that sum up to a given value, sorted in non-decreasing order.

• Use a hashmap to store the difference between the target sum and each element in the array.

• Iterate through the array and check if the current element's complement exists in the hashmap.

• Sort the pairs based on the first element and then the second element.

• Return the list of pairs that satisfy the sum condition.

Find the position of the rightmost set bit in a given number's binary representation.

• Convert the number to binary representation.

• Find the position of the rightmost set bit by counting from right to left.

• Return the position of the rightmost set bit.

Count the number of substrings consisting of only vowels in a given string.

• Iterate through all substrings of the input string.

• Check if each substring consists only of vowels.

• Increment a counter for each valid substring found.

• Return the final count as the output.

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.

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.

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.

Calculate the number of ways to distribute items among three people with constraints.

• Start by distributing one item to each person, then distribute the remaining items to one person.

• Use combinatorics to calculate the number of ways to distribute the remaining items to one person.

• Consider edge cases like when N is less than 3 or when N is equal to 3.

• Example: For N=7, distribute 1 item to each person and then distribute the remaining 4 items to one person in 4 ways.

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 edge cases like boundary conditions and handling of diagonals while traversing.

• Handle the input matrix efficiently to optimize the solution.

• Example...read more

Find duplicates in an array of integers within a specified range.

• Iterate through the array and keep track of the count of each element using a hashmap.

• Return elements with count greater than 1 as duplicates.

• Time complexity can be optimized to O(N) using a set to store duplicates.

Given N boxes with integer labels, remove M boxes to minimize distinct labels left.

• Iterate through the array and count the frequency of each label

• Sort the frequencies in descending order

• Remove M boxes with the highest frequencies to minimize distinct labels

To find and correct bugs in code, analyze problem statement, review code, use debugging tools, run test cases, and make necessary changes.

• Understand the problem statement and expected output

• Review the code for syntax errors, logical errors, and potential bugs

• Use debugging tools like breakpoints, print statements, and IDE features

• Run test cases to identify the bugs and verify the corrections

• Make necessary changes to the code based on the identified bugs

File system is stored on disk using data blocks and metadata, organized in a hierarchical structure.

• File system is stored on disk using data blocks and metadata

• Data blocks contain actual file data, while metadata stores information about files and directories

• File system is organized in a hierarchical structure with directories containing files and subdirectories

• File system uses a file allocation table (FAT) or an index to keep track of file locations on disk

To find and correct a bug in code, analyze problem statement, review code, use debugging tools, and test different scenarios.

• Understand the problem statement thoroughly to identify the expected behavior of the code.

• Review the code line by line to identify any syntax errors, logical errors, or potential bugs.

• Use debugging tools like breakpoints, print statements, or IDE debuggers to trace the flow of code execution.

• Test the code with different input scenarios to reproduce the ...read more

RISC focuses on simplicity and efficiency, while CISC emphasizes complex instructions and flexibility.

• RISC uses a small set of simple instructions, while CISC uses a large set of complex instructions.

• RISC architectures have a uniform instruction format, while CISC architectures have variable-length instructions.

• RISC architectures rely on optimizing compilers for performance, while CISC architectures have hardware optimizations.

• Examples of RISC architectures include ARM and MI...read more

Given a number x, find the minimum number of operations (decrement by 1 or multiply by 2) to convert it to y.

• Use a breadth-first search (BFS) approach to explore all possible operations and find the minimum number of steps.

• Start with x and generate all possible next numbers by decrementing or multiplying by 2.

• Keep track of the number of steps taken to reach each number and stop when y is found.

• Use a queue to implement the BFS algorithm.

• Example: x = 10, y = 30. Possible steps:...read more

Create subarrays with sum = 0 from given array of integers.

• Iterate through the array and keep track of the running sum.

• Store the running sum in a hashmap and check if the current sum - any previous sum equals 0.

• If yes, then the subarray between those two indices has a sum of 0.

The question involves finding the pivot in a rotated sorted array using combinatorics and count sort.

• To find the pivot in a rotated sorted array, we can use a modified binary search algorithm.

• First, we compare the middle element with the first element to determine if the pivot is in the left or right half.

• Then, we continue dividing the array in half and adjusting the search range based on the pivot's location.

• Count sort is a sorting algorithm that works well when the range of...read more

Design a parking lot system with features like parking, retrieving, and tracking available spots.

• Create a ParkingLot class with attributes like total number of spots, available spots, and a list of parked vehicles.

• Implement methods for parking a vehicle, retrieving a vehicle, and tracking available spots.

• Use data structures like arrays or lists to manage parked vehicles and available spots.

• Consider implementing features like ticketing system, vehicle size restrictions, and pa...read more

Find the longest subsequence in an array with sum zero.

• Iterate through the array and keep track of the running sum.

• Store the running sum in a hashmap along with the index.

• If the same sum is encountered again, the subsequence between the two indices has a sum of zero.

Design a hotel booking system for managing reservations and availability.

• Use a database to store hotel information, room availability, and reservations.

• Implement user authentication and authorization for booking.

• Include a search feature for users to find available rooms based on their criteria.

• Allow users to make reservations, modify or cancel them.

• Send confirmation emails to users after successful bookings.

The question involves finding the sum of right leaf nodes and swapping nodes in groups of k.

• The sum of right leaf nodes can be found by traversing the tree and checking if a node is a right leaf node.

• Swapping nodes in groups of k can be done by iterating through the linked list and swapping the nodes in each group.

• Examples: For the sum of right leaf nodes, consider a binary tree with nodes 1, 2, 3, 4, 5. The sum would be 5. For swapping nodes in groups of k, consider a linked...read more

The question involves reversing nodes in groups of k and finding the sum of right leaf nodes.

• Implement a function to reverse nodes in groups of k

• Traverse the reversed linked list and find the sum of right leaf nodes

• Handle edge cases like when the number of nodes is not a multiple of k

LLD for a S3 or a storage based system involves designing the detailed architecture and components of the system.

• Define the data model including objects, metadata, and storage classes

• Design the system components like storage nodes, metadata servers, and access control mechanisms

• Consider scalability, fault tolerance, and data consistency in the design

• Implement features like versioning, encryption, and access control policies

• Optimize for performance and cost efficiency

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

• Calculate the longest path between two leaf nodes in the tree

• This can be done by finding the height of the left and right subtrees and adding them together

• The diameter of the tree is the maximum of either the diameter of the left subtree, the diameter of the right subtree, or the sum of the heights of the left and right subtrees

LLD for a storage based system involves designing the detailed architecture and components of the system to efficiently store and retrieve data.

• Identify the requirements for the storage system, including data types, volume, access patterns, and performance expectations.

• Design the data storage architecture, including data structures, indexing mechanisms, and storage technologies like databases or file systems.

• Define the data access and retrieval mechanisms, such as APIs, proto...read more

Zigzag level order traversal of tree involves traversing the tree level by level in a zigzag pattern.

• Use a queue to perform level order traversal of the tree

• Alternate between left to right and right to left traversal for each level

• Store the nodes at each level in separate arrays

Apache Spark is a distributed computing framework for big data processing.

• Apache Spark is an open-source distributed computing framework.

• It provides an interface for programming entire clusters with implicit data parallelism and fault tolerance.

• Spark uses in-memory processing for speed and can run on Hadoop, Mesos, Kubernetes, or in standalone mode.

• It supports multiple programming languages like Scala, Java, Python, and R.

• Spark has libraries for SQL, streaming, machine learni...read more

Find the maximum length of increasing subsequence in an array of strings.

• Use dynamic programming to keep track of the length of increasing subsequences ending at each index.

• Iterate through the array and update the length of increasing subsequences.

• Return the maximum length found.

A cloud storage service like Google Drive for storing and sharing files

• Allow users to upload, store, and organize files in folders

• Provide sharing options for files and folders with permissions

• Include collaboration features like real-time editing and commenting

• Offer integration with other services like Google Docs, Sheets, and Slides

The left view of a binary tree is the set of nodes visible when the tree is viewed from the left side.

• Traverse the tree in a level order manner and keep track of the first node at each level.

• Use a queue to store nodes at each level and update the left view nodes accordingly.

• Example: For a binary tree with root node 1, left child 2, and right child 3, the left view would be [1, 2].

Destination packages are pre-planned travel itineraries that include accommodation, transportation, and activities.

• Destination packages are designed to provide a hassle-free travel experience.

• They can be customized based on the traveler's preferences and budget.

• Popular destination packages include beach vacations, city breaks, and adventure trips.

• They often include guided tours, meals, and tickets to attractions.

• Destination packages can be booked through travel agencies or on...read more

A cinema API is a software interface that allows developers to access and interact with cinema-related data and services.

• Provides information about movies, showtimes, theaters, and ticket availability

• Allows users to search for movies, view trailers, and book tickets

• May include features like seat selection, payment processing, and user reviews

• Can integrate with external services like payment gateways and movie databases

A vector is a dynamic array that can resize itself as needed.

• A vector is typically implemented using a dynamically allocated array.

• It provides constant time access to elements using index.

• Vectors can grow in size by reallocating memory when needed.

• Example: vector vec;

• Example: vec.push_back(10);

Reverse a linked list by changing the pointers direction.

• Start with three pointers: current, previous, and next.

• Iterate through the linked list, updating the pointers to reverse the direction.

• Update the head pointer to the last node to complete the reversal.

Resume points are concise descriptions of your work experience, skills, and achievements listed on your resume.

• Resume points should be clear, specific, and quantifiable.

• Use action verbs to start each point, such as 'developed', 'implemented', 'analyzed'.

• Include relevant metrics or results to demonstrate impact, such as 'increased sales by 20%' or 'reduced processing time by 30%'.

Build a system for generating and managing Tiny URLs

• Use a unique identifier for each long URL to generate a short URL

• Store the mapping of short URL to long URL in a database

• Implement a redirect mechanism to redirect users from short URL to long URL

• Consider adding expiration dates for short URLs to manage storage

• Implement analytics to track usage of short URLs

Extensive experience in designing, implementing, and managing cloud-based solutions.

• Designed and implemented scalable cloud architectures using AWS, Azure, or Google Cloud

• Managed cloud infrastructure for high-traffic web applications

• Experience with containerization technologies like Docker and Kubernetes

• Implemented serverless computing solutions using AWS Lambda or Azure Functions

Managed a large-scale software development program for a financial services company.

• Led a team of 20 developers and testers in delivering a new online banking platform

• Implemented Agile methodologies such as Scrum to improve project efficiency

• Collaborated with stakeholders to define project scope and prioritize features

• Managed project budget and resources to ensure on-time delivery