I initially had two rounds of telephonic interviews. The questions were based on algorithms, data structures, and coding areas, such as efficiently determining if a singly linked list represents a palindrome, heap-related questions, designing a data structure for an LRU cache, and one simple dynamic programming question. For the DP question, given a 2D array where each cell consists of either 'WATER' or 'LAND', and a cell (say (i,j)), we should print the continuous stretch of area surrounding this cell containing 'LAND'.

Later, I had five onsite interviews:

Algo/DS Round:

1. Given a node in a binary tree, print all nodes that are k units away from this node. The nodes can be parents, children, siblings, etc.
2. Given a boolean expression with n predicates separated by n-1 operators (&, |, or ^). Based on how you group the expression with parentheses, the value will be evaluated to True or False. Design an algorithm to count the number of such combinations that will evaluate to True.

Coding Round: Implement LRU Cache. I was given a laptop and asked to code it in an editor of my choice. The goal was to write well-designed, syntactically correct, modular code. I chose to implement this in C++ and managed to produce working code in 45 minutes.

Design Round: OO Design: Design the Snake and Ladder game.

DB Design: Design a schema for an n-ary tree where each node has information for a certain set of attributes among name, age, address, value, etc. The table should also store hierarchy information (parent-child info). Afterward, I was asked to write SQL queries for: a. Printing all parents of a given node (using a recursive CTE). b. Printing all nodes that have exactly two children.

Bar Raiser Round: I was asked to explain the projects and technologies I worked on. The discussion focused on the problems I had solved. I was given one problem related to an Order Management System, and the interviewer asked me to make the search service extensible. For instance, if a new category service like 'apparel' were introduced, the search results should also include these results along with existing ones. This required implementing the Strategy pattern.

Hiring Manager: This was a general discussion based around analytics, tools, and ETL frameworks that I had worked on.

Given a boolean expression with n predicates separated by n-1 operators, where each operator can be either '&', '|', or '^'. Based on how you group the expression with parentheses, the value will be evaluated to True or False.

Design an algorithm to count the number of combinations that will evaluate to True.