111 questions from 10 interviews · updated from reports 2017-2022
About
Sabre is a travel technology company that provides software, data, and distribution systems for airlines, hotels, travel agencies, and other travel businesses. In India, it is known for hiring technical roles such as Associate Software Developer, SDE, and Associate Developer.
The roles that come up most are Associate Software Developer, SDE and Associate Developer. This covers 10 candidate interviews reported from 2017 to 2022. Most sat it at entry level (9 of 10 that recorded a level), with 1 internship interviews alongside. Among the 10 that recorded either route, arrivals split between campus drives (10, 100%). Most questions fall under CS fundamentals and DSA.
Ans. A stack removes the most recently added item first, while a queue removes the earliest added item first. This is usually called LIFO for stack and FIFO for queue. Stacks are used for function calls, undo, or parsing. Queues are used for scheduling, buffering, and breadth first search.
Ans. There is no single best sorting algorithm, because the choice depends on the data and constraints. In practice, Timsort is often best for general-purpose library sorting because it is stable, fast on real-world partially sorted data, and has O(n log n) worst-case time. Quicksort is fast on average but not always stable.
Ans. An articulation point is a vertex whose removal, along with its incident edges, increases the number of connected components in a graph. In an undirected connected graph, it is a critical connector. It can be found with DFS using discovery times and low-link values, with a special case for the DFS root.
Ans. There is no unique solution without the actual guesses and feedback. The method is to list all possible codes, then remove any code that would not give the same feedback for each guess. Repeat until one code remains. If several remain, the puzzle is under-specified; if none remain, the clues are inconsistent.
Ans. Operating system scheduling algorithms decide which ready process or thread gets the CPU next. Common types include First Come First Served, Shortest Job First, Priority Scheduling, Round Robin, and Multilevel Queue scheduling. The key trade off is balancing throughput, response time, waiting time, fairness, and avoiding starvation, often using preemption and time slices.
Ans. Use dynamic programming where dp[i][j] is the longest snake sequence ending at cell i, j. From each cell, extend from the top or left neighbour if its value differs by exactly 1, otherwise start length 1. Track the maximum and optionally parent pointers to print the path. Time is O(rows × columns), space is O(rows × columns).
Ans. Computer networks connect devices so they can exchange data using agreed protocols such as TCP/IP, HTTP, DNS and Ethernet. The key fundamentals are addressing with IP, routing between networks, reliable transport with TCP or faster best-effort transport with UDP, name resolution through DNS, and layered design using the OSI or TCP/IP model.
Ans. Use a one-dimensional DP array where dp[x] stores the minimum number of coins needed to make amount x. Initialise dp[0] to 0 and all other entries to infinity, then for each amount try every coin and update dp[x]. The answer is dp[amount], or -1 if unreachable. Time is O(amount × coins), space is O(amount).
Ans. Virtual memory is an operating system technique that gives each process the illusion of a large, private address space, using RAM plus disk storage when needed. RAM is the actual fast physical memory. The key difference is that virtual memory is an abstraction and management mechanism, while RAM is hardware.
Ans. A heap is a complete binary tree, usually stored in an array, where each parent obeys an order rule with its children. In a min heap, the parent is smaller; in a max heap, it is larger. Peek is O(1), insert and delete root are O(log n), and building a heap is O(n).
Ans. Implement a queue using an array by keeping two indices, front and rear, to track where to remove and insert elements. Enqueue inserts at rear and advances it, while dequeue removes from front and advances it. The key detail is to use a circular array so space is reused efficiently. Both operations take O(1) time.
Ans. Deadlock avoidance means granting resource requests only when the system can remain in a safe state. The main technique is the Banker’s algorithm, which checks available resources, current allocations and maximum future needs before approving a request. If no safe execution order exists, the request is delayed rather than granted.
Ans. A 15-puzzle instance is solvable if the parity condition holds: count inversions in the flattened board, ignoring the blank, and find the blank’s row counted from the bottom. For a 4 by 4 puzzle, it is solvable exactly when inversions plus that row number is odd. This takes O(16²) time.
Ans. Normalization is used in DBMS to organise data into well-structured tables, reducing redundancy and improving data integrity. Update anomaly means the same fact must be changed in many places. Insert anomaly means data cannot be added without unrelated data. Delete anomaly means removing one record accidentally removes useful information.
Ans. CPU scheduling decides which ready process gets the CPU next, using algorithms such as First Come First Served, Shortest Job First, Priority Scheduling, and Round Robin. Burst time is the CPU time a process needs before it blocks or finishes. Key measures are waiting time, turnaround time, response time, throughput, and fairness.
Ans. The ISO/OSI model is a seven-layer reference model for network communication, while the TCP/IP stack is the practical protocol suite used on the internet. OSI has physical, data link, network, transport, session, presentation and application layers. TCP/IP usually has link, internet, transport and application layers, combining several OSI responsibilities.
Ans. Use dynamic programming to find the largest square sub-matrix of 1s. Let dp[i][j] be the size of the largest all-1 square ending at cell i,j. If matrix[i][j] is 1, dp[i][j] is 1 plus the minimum of top, left and top-left. Track the maximum. Time is O(rows × cols).
Ans. Use a greedy scan: keep the farthest index reachable in the current jump range, and when you reach the end of that range, make one jump and extend the range. If the range cannot move further, the end is unreachable. This uses constant space and runs in O(n) time.
Ans. Insert at the head by linking the new node between the tail and current head, then make it the head. Insert in the middle by traversing to the target position and linking the new node between previous and current nodes. Update both next and prev links. Head insertion is constant time; middle insertion is linear time.
Ans. Use dynamic programming where each free cell stores the number of ways to reach it from the top or left. If the start or end is an obstacle, return 0. Use a one-dimensional array updated row by row, setting blocked cells to 0. Time is O(mn), space is O(n).
Ans. Database normalization organises data into related tables to reduce duplication and update errors, while denormalization deliberately adds some duplication to make reads faster or simpler. Normalization is needed for data integrity and maintainability. Denormalization is needed when joins or complex queries become too slow for real application performance needs.
Ans. A strong answer should show integrity, commitment, and maturity. Pick a situation where you had competing opportunities but honoured your current responsibility. Emphasise that you would not misuse company time or information, would follow policy, and would be transparent if you chose to pursue it. Interviewers listen for loyalty, professionalism, and ethical judgement.
Ans. Use dynamic programming by precomputing, for every index, the highest bar to its left and the highest bar to its right. Then the water above that index is min(leftMax, rightMax) minus its height, if positive. Sum this for all indices. This uses two arrays, runs in O(n) time and O(n) space.
Ans. Round Robin is reasonably efficient for everyday computers, mainly because it gives each process a fair time slice and keeps the system responsive. Its key weakness is context switching overhead: if the time quantum is too small, the CPU wastes time switching tasks; if too large, response time becomes poor. Modern systems use refined variants.
Ans. Normalization is organising database tables to reduce redundancy and avoid update, insert, and delete anomalies. Second Normal Form means the table is in 1NF and every non-key attribute depends on the whole primary key, not part of it. For example, in OrderLine(OrderId, ProductId, ProductName, Quantity), ProductName depends only on ProductId, so move it to Product.
Ans. ISPs connect your home or device to the wider internet and route your packets between networks. When you enter google.com, the browser uses DNS to find an IP address, opens a connection to that server, usually with TLS, sends an HTTP request, receives the response, and renders the page.
Ans. Use dynamic programming with a one dimensional array where dp[x] stores the number of ways to make sum x. Initialise dp[0] to 1, then for each coin, update sums from coin to target by adding dp[sum - coin]. Processing coins first avoids counting different orders separately. Time is O(coins × sum), space is O(sum).
Ans. For SJF, whenever the CPU is free, choose the arrived process with the shortest burst time and run it to completion. For SRTF, always run the arrived process with the least remaining time, preempting if a shorter job arrives. Use a min-heap by burst or remaining time. Complexity is O(n log n).
Ans. An airline booking website should let users search flights, compare fares, select seats, enter traveller details, pay securely, receive tickets, and manage cancellations or changes. The key design concern is inventory consistency: seats and prices change quickly, so booking should use temporary holds, payment timeouts, and reliable confirmation with airline systems.
Ans. Use GROUP BY to define one result row per entity, aggregate functions such as COUNT, SUM, AVG, MIN, or MAX to calculate values, and subqueries to filter or compare against derived results. For example, group orders by customer, sum totals, then use a subquery to keep customers above the overall average spend.
Ans. Deadlock is a state where processes wait forever for resources held by each other. Prevent it by breaking mutual exclusion, hold-and-wait, no-preemption, or circular-wait conditions. Banker’s Algorithm keeps Available, Allocation, Max, Need arrays, repeatedly finds a process whose Need fits Available, simulates release, and grants only safe requests. Complexity is about O(n²m).
Ans. Use dynamic programming, where each position stores the number of ways to decode the prefix up to that point. A single digit is valid if it is 1 to 9, and a two digit number is valid if it is 10 to 26. This gives O(n) time and O(1) space with rolling values.
Ans. Authentication proves who a user is, while authorization decides what they can access. JWTs are signed tokens often sent with requests, while cookies are browser-managed storage often used for sessions. SQL databases use structured tables and schemas; NoSQL is more flexible. Client-side rendering builds pages in the browser; server-side rendering sends ready HTML.
Ans. A strong answer should show maturity, not jealousy. Pick a situation where you stayed focused, delivered your own work well, and learned from others’ success. Emphasise fairness, team goals, feedback seeking, and readiness for future opportunities. Interviewers listen for resilience, professionalism, growth mindset, and low ego.
Ans. Greedy makes the best local choice at each step, such as Kruskal’s algorithm choosing the next smallest safe edge. Divide and Conquer splits a problem into independent smaller parts, solves them, then combines results, such as merge sort. For TSP, standard Divide and Conquer is not suitable because tours have global dependencies, so subproblem solutions may not combine optimally.
Ans. A strong answer shows maturity, not entitlement. Pick a situation where you accepted a decision, asked for feedback, and found a way to prove readiness. Emphasise respect for the manager’s judgement, curiosity about the missing trust or context, and proactive contribution. Interviewers listen for patience, accountability, and confidence without resentment.
Ans. Implement an array stack by storing items in an array and moving a top index on push and pop. Implement a linked list stack by adding and removing nodes at the head. Push, pop and peek are O(1) in both. Arrays use O(n) space with possible resizing, while linked lists use O(n) plus pointer overhead.
Ans. Assuming it rolls outside the larger circle without slipping, it completes 5 rotations. The centre of the small circle travels round a circle of radius R + R/4. Its path length is 2π(5R/4). Divide by the small circumference, 2π(R/4), giving 5.
Ans. Use BFS from the source and count all distinct nodes reached with distance 1 or 2, excluding the source itself. Store the graph as an adjacency list, track visited nodes with their distance, and do not expand nodes once distance is 2. The time complexity is O(V + E), limited in practice to the explored neighbourhood.
Ans. Count primes up to N, say p. There are exactly p prime indices and p prime numbers, so all prime numbers must occupy those prime positions. The number of valid permutations is p! multiplied by (N minus p)!. Use a sieve to count primes, then compute factorials. Time complexity is O(N log log N).
Ans. Sort the array and find the longest contiguous block where the two smallest values sum to more than the largest; its length is the answer. This works because, in sorted order, if the smallest two can form a triangle with the largest, every other triplet also can. Use two pointers after sorting, in O(n log n) time.
Ans. Use breadth first search from the source cell and stop when you first reach any edge cell. Put the source in a queue with distance 0, visit four neighbours only if they are inside the grid, not blocked, and unvisited. BFS guarantees the first edge reached is shortest. Time is O(rows × columns).
Ans. Scan every cell of the matrix; if it is a mine, copy '*', otherwise count mines in the eight neighbouring positions and store that count in the output matrix. Use a second M by N matrix for results and a fixed list of eight direction offsets. Time complexity is O(MN), with O(MN) extra space.
Ans. Use Disjoint Set Union to build connected components of related strings, then print each component as a group. For every string, generate patterns by replacing each position with a wildcard, such as cat to *at, c*t, ca*. Strings sharing a pattern differ by one character, so union them. Time is O(nL) average.
Ans. Put B in a hash set, scan A, and add values involved in pairs where the absolute difference is k, avoiding duplicate counting with another set. Then test whether the sum S can be made from exactly k primes using dynamic programming over prime count and sum. Print the set union if true, otherwise the set intersection. Expected time is O(m+n+kS times primes up to S).
Ans. Use recursive backtracking: keep an n by n board initialised to unvisited, place the knight at the start, then recursively try all eight knight moves. If a move stays inside the board and is unvisited, mark it with the step number and continue. If all squares are filled, return success. Worst time is O(8^(n²)).
Ans. Quicksort a doubly linked list by partitioning around a pivot node, usually the last node, then recursively sorting the sublists before and after it. Traverse from low to high, maintaining a boundary for smaller values and swapping node data when needed. After placing the pivot, recurse on both sides. Average time is O(n log n), worst case O(n²).
Ans. Java’s garbage collector automatically frees heap objects that are no longer reachable from live references. It typically starts from roots such as stacks, statics and registers, marks reachable objects, then reclaims or compacts the rest. In C++, I would build a simple mark-and-sweep collector using an allocation table and object reference lists, with linear time over allocated objects.
Ans. Preprocess the coin array with a prefix sum so each range query is answered in constant time instead of scanning the range. Store prefix[i] as the total coins up to index i, then answer [l, r] as prefix[r] minus prefix[l - 1]. Preprocessing is O(n), each query is O(1).
Ans. Try every possible position where S2 could appear in the final S1, and compute the cheapest palindrome consistent with that forced substring. For each mirrored pair, combine constraints from S2. If both sides require different characters, that position is impossible. Otherwise add the minimum replacements needed. Return the smallest cost, or -1. Time is O(n²) naively.
Ans. Try every possible placement of S2 in S1 and compute the cheapest palindrome consistent with that placement; return the minimum cost, or -1 if all placements conflict. For each mirrored pair, forced characters from S2 must match. If forced, count replacements to that character; otherwise unequal original characters cost one. Time is O(n(n-m+1)).
Ans. Run BFS from X and from Y over allowed moves, then choose the common reachable floor minimising max(distX[f], distY[f]). Each edge is A to A divided by a prime factor p where p < M. Store distances in maps or arrays. Complexity is proportional to reachable states times factorisation cost.
Ans. Track the possible range of unmatched opening brackets while scanning the string, treating a parenthesis after a colon as optional because it may be part of a smiley. Increase or decrease the range for normal brackets, clamp the minimum at zero, and reject if the maximum becomes negative. Accept if the minimum is zero at the end.
Ans. Model strings as nodes and build connected components. Group strings by length, connect two strings if their Hamming distance is one, then use DFS, BFS, or union find to find transitive chains. Finally scan the original input order and print each unprinted component in that order. Naive comparison costs O(N²L).
Ans. For a query X, Y, the special coins are at positions X, X+Y, X+2Y, up to N, so compute the sum or product over that arithmetic progression. Precompute suffix results for each small Y and residue class; for large Y, iterate directly. This gives about O((N+Q)√N) time and O(N√N) space.
Ans. TCP is connection-oriented and reliable, while UDP is connectionless and best-effort. TCP guarantees ordered delivery, retransmits lost data, and handles flow and congestion control, so it suits web pages, file transfer, and email. UDP has lower overhead and latency, so it suits streaming, gaming, voice calls, and DNS where speed matters more.
Ans. The OSI model has seven layers: physical, data link, network, transport, session, presentation and application. They describe how data moves from raw bits on a medium, through framing, routing and reliable delivery, up to user-facing protocols. The key idea is separation of concerns, so each layer provides services to the one above.
Ans. LRU, or Least Recently Used, is a replacement policy that evicts the item that has not been accessed for the longest time. It is used in caches, such as CPU caches, database buffer caches, operating system page replacement, and application caches. A common implementation uses a hash map plus a linked list for constant-time access and updates.
Ans. Round Robin Scheduling is a preemptive CPU scheduling algorithm where each ready process gets a fixed time slice, called a time quantum, in cyclic order. If a process does not finish in its slice, it is moved to the back of the ready queue. The key trade-off is fairness versus context-switching overhead.
Ans. ACID properties are the guarantees that make database transactions reliable: Atomicity, Consistency, Isolation and Durability. Atomicity means all or nothing, Consistency keeps valid rules, Isolation prevents concurrent transactions interfering, and Durability ensures committed changes survive crashes. They are essential for correctness in systems handling critical data.
No question matches those filters. Reset filters.
Showing 60 of 111 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 CS fundamentals (63%) and DSA (27%).
Candidate interviews show an average of 3.8 rounds per experience, with a typical sequence of Online test → Technical → Managerial → HR. Individual interview paths can vary.
Among questions with a recorded difficulty, the mix is easy 52%, medium 40%, hard 8%.
