297 questions from 35 interviews · updated from reports 2014-2023
About
Expedia Group is an online travel company that runs websites and apps for booking hotels, flights, car rentals, vacation rentals, and travel packages. In India, it commonly hires software engineers, software engineering interns, and SDE interns for its technical teams.
The roles that come up most are Software Engineer, Software Engineering Intern and SDE Intern. This covers 35 candidate interviews reported from 2014 to 2023. The largest group sat it at internship level (14 of 35 that recorded a level). Among the 25 that recorded either route, arrivals split between campus drives (16, 64%) and off-campus applications (9, 36%). Most questions fall under DSA and CS fundamentals.
Ans. Scan the string once, count consecutive equal characters, and append each character followed by its count to a result builder when the character changes. Use a mutable string builder or list to avoid repeated string concatenation. After the loop, append the final run. This takes O(n) time and O(n) space.
Ans. Use the Dutch National Flag approach with three pointers: low, mid, and high. Scan once, swapping 0s to the front, 2s to the back, and leaving 1s in the middle. This sorts the array in place with O(n) time complexity and O(1) extra space.
Ans. Copy the HashMap entries into a list, sort that list using a comparator on each entry’s value, then insert the sorted entries into a LinkedHashMap to preserve iteration order. A HashMap itself cannot stay sorted. The sorting takes O(n log n) time and O(n) extra space.
Ans. Implement an LRU cache with a hash map from key to list node and a doubly linked list ordered by recent use. On get, return the value and move the node to the front. On put, update or insert at the front. If capacity is exceeded, remove the tail. Both operations are O(1).
Ans. Build a service with create and redirect APIs, storing short code to long URL mappings in a durable key-value store. Generate codes using a unique ID encoded in Base62, or random codes with collision checks. The critical detail is read scalability: cache popular mappings and make redirects fast, while writes can be slower.
Ans. EJB 3 is a much simpler, annotation driven POJO model, while EJB 2 uses heavier component classes, home interfaces, remote/local interfaces, and verbose XML deployment descriptors. The biggest practical difference is that EJB 3 reduces boilerplate and configuration, adds dependency injection, and replaces EJB 2 entity beans with JPA persistence.
Ans. The diamond problem in C++ happens when a class inherits from two classes that both inherit from the same base class. The final derived class can contain two separate copies of the base, causing ambiguity when accessing base members. The usual fix is virtual inheritance, which shares one common base subobject.
Ans. Private inheritance means a class inherits from another class but does not expose that inheritance to users of the derived class. In C++, the base class’s public and protected members become private in the derived class. It is usually used for implementation reuse, not to model an “is a” relationship.
Ans. Print the first node visible at each depth when the tree is viewed from the left. Do a level order traversal using a queue, and for each level print the first node removed from the queue. This visits every node once, so the time complexity is O(n), with O(w) space for the queue.
Ans. AWS provides on-demand cloud services such as compute, storage, databases, networking, analytics, machine learning, security, and deployment tools. Its main benefit is elasticity: teams can scale resources up or down quickly, pay only for what they use, improve availability across regions, and avoid managing much physical infrastructure.
Ans. Traverse the matrix layer by layer using four boundaries: top, bottom, left, and right. Print the top row, right column, bottom row, and left column, then move the boundaries inward. No extra data structure is needed apart from the output. Time complexity is O(mn), and space is O(1).
Ans. Use level order traversal and print the last node seen at each level. Keep a queue of nodes, process one level at a time using the current queue size, and record or print the node when it is the last in that level. Time complexity is O(n), and space complexity is O(w).
Ans. Use the Boyer Moore voting algorithm to find the majority element in one pass. Keep a candidate and a count: set the candidate when count is zero, increment for matches, decrement otherwise. If a majority is not guaranteed, verify the candidate with a second pass. Time is O(n), space is O(1).
Ans. Use level order traversal with a horizontal distance for each node, root at 0, left child minus 1 and right child plus 1. Store nodes in a map from distance to list, appending as visited. Finally print lists by increasing distance. Time is O(n log k) with an ordered map.
Ans. Two-Phase Locking is a concurrency control rule where a transaction first acquires all needed locks, then releases locks, with no new locks allowed after any release. The key detail is that 2PL ensures conflict-serialisable schedules. In practice, strict 2PL holds write locks until commit or rollback, reducing cascading aborts.
Ans. Rollback in ActiveMQ is usually handled by using transacted JMS sessions or XA transactions, then calling rollback when processing fails so the broker redelivers the message. The key detail is configuring redelivery policy and a dead letter queue, so repeated failures do not cause infinite retries and poison messages are isolated.
Ans. Create two mutex locks and two threads, where thread A locks mutex 1 then waits for mutex 2, while thread B locks mutex 2 then waits for mutex 1. The key detail is inconsistent lock ordering. The data structures are two mutex objects, and the work is O(1) before both threads block forever.
Ans. A binary tree is foldable if its left and right subtrees have the same structure when mirrored, ignoring node values. Recursively compare the left child of one side with the right child of the other, and vice versa. If both are null, match; if only one is null, fail. Time is O(n), space is O(h).
Ans. Choose a real example where the conflict affected delivery, not just personalities. Emphasise that you listened to both sides, clarified facts, kept focus on the shared goal, and helped agree a practical next step. Interviewers listen for maturity, calm communication, accountability, and a positive outcome or lesson learned.
Ans. I solve medium array problems by first identifying the pattern: two pointers, sliding window, prefix sums, sorting, hashing, or binary search. The key detail is choosing the invariant, such as a valid window or stored prefix result. Most solutions run in O(n) or O(n log n) time with O(1) to O(n) space.
Ans. Reverse it recursively by popping the top element, reversing the remaining stack, then inserting the popped element at the bottom. The key operation is “insert at bottom”, also done recursively by emptying the stack temporarily and pushing items back. This uses no extra data structure, but uses O(n) call stack space and O(n²) time.
Ans. Solve medium string problems by identifying the pattern first: sliding window, two pointers, hashing, stack, trie, or dynamic programming. The key detail is choosing the right state to track, such as character counts, last seen positions, prefixes, or palindrome bounds. Most efficient solutions run in O(n) or O(n log n) time.
Ans. Use Floyd’s slow and fast pointer method to detect the loop, then remove it by finding the node where the cycle starts and setting the previous node’s next pointer to null. After slow and fast meet, move one pointer to head and advance both one step at a time. Time is O(n), space is O(1).
Ans. Assuming each wire takes 60 minutes to burn, light the first wire at both ends and the second at one end. The first wire burns out in 30 minutes. At that moment, light the other end of the second wire. Its remaining burn time is 30 minutes, so burning from both ends takes 15 more minutes: 45 total.
Ans. Use a queue to process each diagonal: start with the root, print nodes while moving right, and whenever a node has a left child, add it to the queue for the next diagonal. Repeat until the queue is empty. This visits every node once, so time is O(n) and extra space is O(n).
Ans. Rearrange it as first, last, second, second last, and so on by splitting the list, reversing the second half, then merging both halves alternately. Use slow and fast pointers to find the middle, reverse the second half in place, and relink nodes one by one. This takes O(n) time and O(1) extra space.
Ans. A binary tree is foldable if its left and right subtrees are mirror images in structure, ignoring node values. Recursively compare the root’s left and right children: both null is true, exactly one null is false, otherwise compare outer and inner pairs. This takes O(n) time and O(h) recursion stack space.
Ans. Use an inorder traversal and relink nodes as you visit them, treating left as previous and right as next. Keep two pointers: head for the first node and prev for the last processed node. For each visited node, connect prev.right to it and it.left to prev. Time is O(n), space is O(h).
Ans. A semaphore is a synchronisation variable used to control access to shared resources, typically through wait and signal operations. The critical section problem is about ensuring only one process or thread enters code that accesses shared data at a time. The key requirements are mutual exclusion, progress, and bounded waiting.
Ans. DSU is used to maintain disjoint groups and answer whether two elements are in the same component. Store a parent array and usually rank or size; find returns the representative with path compression, and union joins two representatives. With union by rank or size, operations are almost constant time, O(α(n)).
Ans. Cover product selection, payment, dispensing, change, cancellation, refunds, inventory, and error handling. Test exact payment, overpayment, insufficient funds, out of stock items, invalid codes, coin rejection, card failure, power recovery, concurrent selections, and restocking. Most important is verifying state transitions so money and inventory stay consistent after every success or failure.
Ans. Traverse the tree level by level, alternating the output direction at each level. Use a queue to process nodes in breadth first order, track the current level size, collect that level’s values, and reverse or append in opposite direction based on a boolean flag. Time is O(n), space is O(w).
Ans. Count indices where the sum of elements to the left equals the sum of elements to the right. Compute the total sum first, then scan once while maintaining a running left sum; the right sum is total minus left sum minus current element. No extra data structure is needed. Time is O(n), space is O(1).
Ans. Use DFS to count each connected group of land cells as one island. Scan every cell, and when you find unvisited land, increment the count and run DFS to mark all connected land in four directions. Use the grid itself or a visited set. Time is O(rows × columns), space is O(rows × columns) worst case.
Ans. Virtual functions are member functions declared for runtime overriding, and dynamic polymorphism is the ability to call the derived class version through a base class pointer or reference. In languages like C++, this is usually implemented with a virtual table, so the actual object type decides which function runs at runtime.
Ans. Use a patience sorting approach: maintain an array tails, where tails[i] is the smallest possible tail value of an increasing subsequence of length i + 1. For each number, binary search its position in tails and replace or append it. The length of tails is the LIS length. Time complexity is O(n log n).
Ans. Find the lowest common ancestor of the two nodes, then build the path from the first node up to the ancestor and from the ancestor down to the second node. A common approach is DFS with parent pointers or root-to-node lists. Time is O(n), with O(h) to O(n) extra space.
Ans. I solved concurrency issues by making shared state explicit and protecting it with transactions, locks, and idempotent operations. The key fix was moving critical updates into a single database transaction with row-level locking, so two workers could not update the same record inconsistently. I also added retries and tests for race conditions.
Ans. I have used Factory, Strategy, Observer, Singleton, Repository and Dependency Injection in production projects. The most useful has been Strategy, for separating interchangeable business rules, such as pricing or validation, without large conditional blocks. I try to use patterns only when they simplify change, not just to make the design look formal.
Ans. The Decorator pattern adds behaviour to an object by wrapping it in another object with the same interface. Implement it with a component interface, a concrete component, and decorator classes holding a reference to a component. Each decorator forwards calls and adds work before or after. Call overhead is O(n) for n wrappers.
Ans. Identify slow SQL queries using query logs, database monitoring, and execution plans, then optimise the highest impact ones first. The key detail is to inspect the execution plan to find full table scans, bad joins, missing indexes, or poor estimates. Common fixes include adding indexes, rewriting queries, reducing returned rows, and updating statistics.
Ans. Use level order traversal with a queue, but reverse the direction of values on alternate levels. Process one level at a time, store its values in a temporary list, append left to right or right to left depending on a boolean flag, then flip it. Time complexity is O(n), space is O(n).
Ans. A Segment Tree answers range queries by storing aggregate values, such as sum, minimum, or maximum, for intervals in a binary tree. Build it over the array, where each node represents a segment and combines its children. Query by visiting only overlapping segments. Build is O(n), queries and point updates are O(log n).
Ans. Use an enum Singleton with one value, INSTANCE, and put the singleton methods on it. Java guarantees enum instances are created once, safely published, and protected against reflection and deserialisation issues. Access is constant time, with no locking cost after class loading, making it the simplest thread-safe Singleton.
Ans. A compiler assigns memory by using each variable’s type, size, alignment, scope and lifetime to decide where it will live and how it will be addressed. Global and static variables get fixed storage, local variables usually get stack-frame offsets, and dynamically allocated objects are managed at runtime on the heap.
Ans. Use a greedy scan and return the first index from which the tour is possible. Keep current fuel balance and start at 0. For each pump, add petrol minus distance to next pump. If balance becomes negative, no earlier pump can start the tour, so set start to next pump and reset balance. Overall O(n) time and O(1) space.
Ans. Detect deadlocks with thread dumps or ThreadMXBean, prevent them by enforcing a fixed lock order and using timed tryLock, and resolve them by releasing resources, interrupting timed lock waits, or restarting affected threads or the process. The key detail is avoiding circular wait, since Java cannot safely kill a thread holding a monitor.
Ans. Use multi-source BFS starting from all initially rotten oranges, and count levels as minutes. Put every rotten orange in a queue, spread to adjacent fresh oranges, and decrement the fresh count. The result is the BFS time if no fresh oranges remain, otherwise return -1. Time complexity is O(rows times columns).
Ans. Use a private constructor, a private static volatile instance field, and a public static getInstance method that checks instance for null before and inside a synchronised block. The second check prevents multiple creations when threads race. volatile is essential because it prevents unsafe publication and instruction reordering. Access is O(1).
Ans. Synchronise in-memory caches using publish-subscribe invalidation, update events, a shared distributed cache, gossip protocols, or change data capture from the source of truth. The key detail is consistency: most systems prefer invalidating changed keys over pushing full values, because it is simpler, reduces stale reads, and avoids conflict handling between nodes.
Ans. The JVM runs bytecode using a class loader, runtime memory areas and an execution engine with an interpreter and JIT compiler. Memory is split into heap, stack, method area, program counter and native method stack. Objects live on the heap, and garbage collection automatically reclaims unreachable objects, usually generationally.
Ans. Use level order traversal with a horizontal distance for each node, root at 0, left child minus 1 and right child plus 1. Store the first node seen for each distance in a map, because it is the topmost. Finally print map values from smallest to largest distance. Time is O(n log n).
Ans. Maintain two variables, current minimum and current maximum, and update them whenever a new integer arrives. Initialise both with the first value in the stream. For each later value, compare it with the current minimum and maximum and replace if needed. Each update is O(1) time and O(1) space.
Ans. Iterate through the list and reverse K nodes at a time by changing next pointers. Keep prev, current and next pointers for each group, connect the previous group’s tail to the new head, and continue. Use only pointer variables, so space is O(1), and time is O(n). If fewer than K remain, follow the stated requirement.
Ans. Choose a real design that solved a clear business or user problem and needed stakeholder buy-in. Emphasise your reasoning, trade-offs, evidence, and how you handled objections. Interviewers listen for structured thinking, collaboration, practical constraints, and impact after approval, not just that people liked your idea.
Ans. The size of a Trie can be optimised by storing each node’s children in a hash map instead of a fixed-size array. This keeps only existing edges, so sparse nodes use much less memory. Lookup and insertion remain proportional to the key length on average, with hash map overhead.
Ans. Yes. Since gcd(13, 9) = 1, 6 is measurable. Fill the 9-litre jar and pour into the 13-litre jar. Fill 9 again, top up 13, leaving 5. Empty 13, pour in 5. Fill 9, top up 13, leaving 1. Empty 13, pour in 1. Fill 9, top up 13, leaving exactly 6.
Ans. A strong answer uses a real example where you stayed accountable without blaming others. Pick a situation with deadlines, dependencies, and visible impact. Emphasise early communication, clarifying what is needed, offering help, escalating appropriately, and finding workarounds. Interviewers listen for ownership, judgement, collaboration, and calm handling of pressure.
Ans. Light the first rope at both ends and the second rope at one end at the same time. The first rope will finish in 30 seconds. At that moment, light the other end of the second rope. It has 30 seconds of burn time left, so burning from both ends finishes in 15 seconds. Total: 45 seconds.
Ans. Read the question first, then scan the passage or sentence for the exact evidence needed. For comprehension, answer only from the text, not outside knowledge. For grammar and vocabulary, check context, tone, tense, subject-verb agreement and word meaning. Eliminate clearly wrong options, then choose the option best supported by the wording.
No question matches those filters. Reset filters.
Showing 60 of 297 questions. Ranked by how often the same question came back across interviews.
A spoken interview built from these questions, scored when you finish; the feedback is yours.
Start practisingWhen you are ready, record The One: a single interview hiring teams watch, so you stop repeating first rounds.
Candidate interviews most often cover DSA (55%) and CS fundamentals (32%).
Candidate interviews show an average of 3.8 rounds per experience, with a typical sequence of Online test → Technical → Technical → HR. Individual interview paths can vary.
Among questions with a recorded difficulty, the mix is easy 41%, medium 52%, hard 6%.
