Associate Software Engineer

As soon as I saw the problem, I realized it was a DP question, and I already knew the approach.

The idea is to fill the DP table from bottom to top. For each rod of length i, starting from i = 1 to i = n, find the maximum value that can be obtained by cutting it into two pieces of lengths j and (i - j).

The question was related to subqueries and joins.

Step 1: Understand the relationships
Each row represents an employee and contains a reference to their manager using manager_id.
To compare an employee's salary with their manager’s, we need two rows from the same table — one for the employee and one for the manager.

Step 2: Use a SELF JOIN
We join the Employees table to itself:

One alias represents the employee (E1)

The other represents the manager (E2)

Join condition: E1.manager_id = E2.emp_id

Step 3: Compare salaries
Condition: E1.salary > E2.salary

Step 4: Write the query
Select the names of employees who earn more than their manager.

I solved the problem, but then he modified the question — for example, he asked me to add postorder traversal as well.

Approach:

Start with Preorder Traversal:

The first element in the preorder array is always the root of the tree (or subtree).

Find Root in Inorder:

Locate the root element (from preorder) in the inorder array. This divides the inorder array into:

Left part → Left Subtree

Right part → Right Subtree

Recursive Construction:

Recursively build the left subtree using the left part of the inorder array and the corresponding elements in the preorder array.

Recursively build the right subtree using the right part of the inorder array and the corresponding elements in the preorder array.

Use Indexing:

Maintain a global or reference index for preorder traversal (starting at 0).

Each time you pick an element from preorder, increment this index.

Optimize Inorder Lookup:

Use a hash map to store the index of each element in the inorder array for O(1) lookup.

Base Condition:

When start > end in the inorder range, return NULL.

Start by defining Normalization: a process used to remove redundancy and ensure data integrity.

• 1NF (First Normal Form): Ensure that each cell contains atomic (indivisible) values.
• 2NF (Second Normal Form): Ensure the table is in 1NF, and all non-key attributes are fully functionally dependent on the primary key.
• 3NF (Third Normal Form): Ensure the table is in 2NF, and there are no transitive dependencies.

Define both:

SQL: Structured data, relational schema, supports JOINs (e.g., MySQL, PostgreSQL).

NoSQL: Unstructured or semi-structured data, schema-less (e.g., MongoDB, Cassandra).

Use cases:

SQL: Banking systems, ERP applications.

NoSQL: Real-time analytics, social media platforms, IoT applications.

Ignore negative numbers and zeros.
Try to place each number at its correct index (value x at index x - 1) using in-place swaps.
After rearranging, iterate through the array:

The first index where arr[i] != i + 1 gives the answer as i + 1.

If all positions are correct, return n + 1.

The problem is solved in O(n) time and O(1) space.

Tip 1: Be confident.