Ola Cabs SDE (Software Development Engineer) Interview Questions and Answers

Program to calculate sum of level order tree

• Traverse the tree level by level using BFS

• Add the values of each level and return the sum

• Use a queue to store the nodes at each level

• Handle edge cases like empty tree or null root

Convert an expression to post-fix notation.

• Start with an empty stack.

• Scan the expression from left to right.

• If the scanned character is an operand, output it.

• If the scanned character is an operator, pop two operands from stack, output them in post-fix notation and push the result back.

• Repeat until the end of expression.

Find the maximum continuous sum in an array of integers.

• Use Kadane's algorithm to find the maximum subarray sum in linear time complexity.

• Initialize two variables, one for current maximum sum and another for overall maximum sum.

• Iterate through the array and update the variables accordingly.

• Example: For array [-2, 1, -3, 4, -1, 2, 1, -5, 4], the maximum continuous sum is 6 (from index 3 to 6).

Find the length of longest increasing subsequence in an array.

• Use dynamic programming to solve the problem efficiently.

• Maintain an array to store the length of longest increasing subsequence ending at each index.

• Traverse the array and update the array for each index.

• Return the maximum value in the array as the length of longest increasing subsequence.

Find maximum of every window of size K in an array

• Iterate through the array and maintain a deque of indices of elements in the current window

• Remove indices from the front of the deque if they are outside the current window

• Remove indices from the back of the deque if their corresponding elements are smaller than the current element

• The front of the deque will always contain the index of the maximum element in the current

Implement binary search in a semi-infinite array.

• Start with the first element and keep doubling the index until the target element is less than the current element.

• Perform binary search on the subarray from the last doubled index to the current index.

• If the target element is not found, repeat the process by doubling the last index and searching again.

• Handle edge cases where the target element is at the first index or n