20+ Expedia Group Software Developer Interview Questions and Answers

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.

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.

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

Convert a Binary Tree into a Doubly Linked List following Inorder Traversal.

• Perform Inorder Traversal of the Binary Tree to get the nodes in order.

• Create a Doubly Linked List by connecting the nodes in the order obtained from Inorder Traversal.

• Return the head of the Doubly Linked List as the output.

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.

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.

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.

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.

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.

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