10+ Ola Cabs Software Developer Interview Questions and Answers

Return all permutations of a given string in lexicographically increasing order.

• Use backtracking to generate all permutations of the string.

• Sort the permutations to get them in lexicographically increasing order.

• Ensure the string contains unique characters to avoid duplicate permutations.

Count and return the number of leaf nodes in a binary tree.

• Traverse the binary tree and count nodes with both left and right children as NULL.

• Use recursion to traverse the tree efficiently.

• Leaf nodes have no children, so check for NULL left and right children to identify them.

Diagonal traversal of a binary tree involves traversing nodes diagonally from top to bottom and left to right.

• Traverse the tree level by level, starting from the root node.

• For each level, keep track of the diagonal nodes and their children.

• Use a queue to store nodes at each level and traverse them accordingly.

• Example: For input 1 2 3 4 -1 5 6 -1 7 -1 -1 -1 -1 -1 -1, the diagonal traversal is 1 3 6 2 5 4 7.

Find the minimum number of taps to water an entire garden along the x-axis.

• Iterate over the taps and find the farthest point each tap can reach.

• Sort the taps based on their starting points and use a greedy approach to select the taps.

• Keep track of the farthest point reachable by the selected taps and the number of taps opened.

• Return the minimum number of taps needed to water the entire garden or -1 if it's impossible.

Design a Least Recently Used (LRU) cache data structure that supports get and put operations with capacity constraint.

• Use a combination of hashmap and doubly linked list to implement the LRU cache.

• Keep track of the least recently used item and evict it when the cache reaches its capacity.

• Update the position of an item in the cache whenever it is accessed or updated.

• Handle both get and put operations efficiently to maintain the LRU property.

• Ensure the time complexity of get an...read more

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 cases such as out of bounds indices and already visited cell...read more

The task is to find the Kth row of Pascal's Triangle given a non-negative integer K.

• Create an array to store the elements of the Kth row of Pascal's Triangle.

• Use the formula C(n, k) = C(n-1, k-1) + C(n-1, k) to calculate each element in the row.

• Return the array containing the Kth row of Pascal's Triangle.

Identify missing numbers within the range of smallest and largest elements in an array.

• Find the smallest and largest elements in the array.

• Generate a list of numbers within this range.

• Filter out the numbers present in the array.

• Return the missing numbers in sorted order.

Design a toll booth system for Ola cabs with necessary functions and data structures.

• Use a queue data structure to manage the order of vehicles waiting at the toll booth.

• Implement functions for vehicle entry, toll calculation, and exit.

• Store vehicle information such as license plate number, type of vehicle, and toll amount in a hash map.

• Utilize a priority queue to handle VIP or premium customers efficiently.

• Include a function to generate toll receipts for each transaction.

OLA app system design involves multiple components like user interface, driver matching algorithm, payment processing, etc.

• User interface for booking rides and tracking

• Driver matching algorithm based on location and availability

• Payment processing for seamless transactions

• Real-time tracking of rides for both users and drivers