SDE - Intern

You are given an array ‘arr’ of size ‘N’ containing 0 and 1. You can swap any two adjacent elements. Your task is to find the minimum number of swaps such that the 0 are shifted to one side, and 1 shifted to the other.

For example:

For the given array ‘arr’ = {1,0,1,1} we can swap the first and second elements, and all 1s will be shifted to the right side and 0s to the left side. Hence a minimum number of operations required is 1.

You are given a relational schema R and a set of functional dependencies F.

A functional dependency is considered redundant if it can be derived from the remaining functional dependencies using Armstrong’s axioms.

Your task is to identify all redundant functional dependencies in the given set.

Write a program that simulates the Producer–Consumer problem using semaphores. The producer should add items to a bounded buffer, and the consumer should remove them, ensuring proper synchronization so that the producer does not add items when the buffer is full and the consumer does not remove items when the buffer is empty.

Given a table employees(emp_id, name, department, salary), write a PostgreSQL query to find the second-highest salary in each department. If a department has fewer than two employees, it should not appear in the result.

You are given two tables:

users(
    user_id INT PRIMARY KEY,
    name TEXT
)

transactions(
    txn_id INT PRIMARY KEY,
    user_id INT,
    amount NUMERIC,
    txn_time TIMESTAMP
)

Write a PostgreSQL query to identify users whose transaction amounts are strictly increasing for at least three consecutive transactions when ordered by txn_time.

Requirements:

• Only consider users who have at least three transactions.
• The increase must be strictly increasing (each transaction amount must be greater than the previous one).
• The transactions must be consecutive in time order for that user.

Return:

• user_id
• start_txn_id
• end_txn_id
• number_of_transactions_in_sequence

If a user has multiple valid sequences, return all of them.

The query should be optimized for large datasets (millions of transactions).

Design a real-time collaborative document editing system similar to Google Docs, where multiple users can edit the same document simultaneously and see updates with latency under 200 ms. The system should support around 100k concurrent users, maintain version history, and store documents reliably so that previous versions can be restored. It must handle edit conflicts when multiple users modify the same section while keeping the document state consistent for everyone.

The architecture should scale horizontally and include considerations for API design, data modeling, real-time communication (e.g., WebSockets), conflict resolution strategies such as Operational Transform or CRDT, caching and storage solutions, and handling offline edits with later synchronization.

Optimize a Function Using a Genetic Algorithm

You are given the mathematical function:

f(x) = x² × sin(x)

Your task is to implement a Genetic Algorithm to find the value of x in the range [-10, 10] that maximizes the function value.

Requirements

• Represent each candidate solution (x) as a chromosome.
• Initialize a population of random candidate values within the range [-10, 10].
• Implement the following Genetic Algorithm components:
• A fitness function based on the value of f(x)
• A selection method (e.g., tournament selection or roulette wheel)
• Crossover to generate offspring
• Mutation to introduce small random changes

Algorithm Conditions

• Run the algorithm for at least 100 generations.
• The population size should be ≤ 100.
• The mutation probability should be between 1% and 10%.
• The crossover probability should be between 60% and 90%.

Output

• Print the following:
• The best value of x found
• The maximum value of the function
• The generation number where the best solution was discovered.