Worked under Govt. Contractor Interview Questions and Answers

Round duration - 75 minutes
Round difficulty - Medium

This was an online coding round where we had 2 questions to solve under 75 minutes. I found both the questions to be of Easy to Medium level of difficulty.

Q1. 
Line Reflection Problem Statement
You are given several sets of points on a 2D plane, each set represented as a list of coordinates. Your task is to determine if there exists a line parallel to the Y-axis...read more
Ans. 
The task is to determine if there exists a line parallel to the Y-axis that reflects given points symmetrically.
• Iterate through each test case and check if a vertical reflection line exists for the given points

• Calculate the midpoint of the x-coordinates and check if it reflects the points symmetrically

• Consider edge cases where points are on the reflection line or have the same x-coordinate
Answered by AI
Add your answer
Q2. 
Number of Islands Problem Statement
You are provided with a 2-dimensional matrix having N rows and M columns, containing only 1s (land) and 0s (water). Your goal is to determine the number of islands in t...read more
Ans. 
Count the number of islands in a 2D matrix of 1s and 0s.
• Iterate through the matrix and perform depth-first search (DFS) to find connected 1s.

• Mark visited cells to avoid redundant traversal.

• Increment island count whenever a new island is encountered.
Answered by AI
Add your answer

Round duration - 60 minutes
Round difficulty - Medium

This round had 2 coding questions followed by some questions from DBMS.

Q1. 
Largest Rectangle in Histogram Problem Statement
You are given an array/list HEIGHTS of length N, where each element represents the height of a histogram bar. The width of each bar is considered to be 1.
...read more
Ans. 
Find the area of the largest rectangle that can be formed within the bounds of a given histogram.
• Iterate through the histogram bars and calculate the area of the largest rectangle that can be formed using each bar as the height.

• Use a stack to keep track of the indices of the bars in non-decreasing order of height.

• Pop elements from the stack and calculate the area until a smaller height bar is encountered.

• Update the max...read more
Answered by AI
Add your answer
Q2. 
Valid Parentheses Problem Statement
Given a string 'STR' consisting solely of the characters “{”, “}”, “(”, “)”, “[” and “]”, determine if the parentheses are balanced.
Input:
The first line contains an...read more
Ans. 
The task is to determine if a given string consisting of parentheses is balanced or not.
• Iterate through the characters of the string and use a stack to keep track of opening parentheses.

• If an opening parenthesis is encountered, push it onto the stack.

• If a closing parenthesis is encountered, check if it matches the top of the stack. If it does, pop the stack, else the string is not balanced.

• At the end, if the stack is e...read more
Answered by AI
Add your answer
Q3. Can you explain the concept of ACID properties in DBMS?
Ans. 
ACID properties in DBMS ensure data integrity and consistency in transactions.
• Atomicity: All operations in a transaction are completed successfully or none at all.

• Consistency: Data is always in a valid state before and after a transaction.

• Isolation: Transactions are isolated from each other to prevent interference.

• Durability: Once a transaction is committed, changes are permanent and survive system failures.

• Example: If...read more
Answered by AI
Add your answer
Q4. Can you explain the different levels of data abstraction in a DBMS?
Ans. 
Levels of data abstraction in a DBMS refer to the different views of data provided to users and applications.
• Physical level: Deals with how data is stored on the storage media. Example: data blocks, pages, indexes.

• Logical level: Focuses on how data is represented to users. Example: tables, views, constraints.

• View level: Provides a customized view of the database for specific users or applications. Example: queries, rep
Answered by AI
Add your answer

Round duration - 60 minutes
Round difficulty - Medium

Standard DS/Algo round with 2 coding questions followed by 2 interesting puzzles.

Q1. 
Cycle Detection in Undirected Graph Problem Statement
You are provided with an undirected graph containing 'N' vertices and 'M' edges. The vertices are numbered from 1 to 'N'. Your objective is to determi...read more
Ans. 
Detect if an undirected graph contains a cycle by exploring all possible paths.
• Use Depth First Search (DFS) algorithm to traverse the graph and detect cycles.

• Maintain a visited set to keep track of visited vertices and a parent pointer to avoid visiting the same vertex twice.

• If a visited vertex is encountered that is not the parent of the current vertex, a cycle is present.

• Consider edge cases like disconnected graphs a
Answered by AI
Add your answer
Q2. 
Maximum 1s in a Row Problem
Given a matrix ARR with dimensions N * M, consisting only of 0s and 1s where each row is sorted, determine the index of the row that contains the highest number of 1s. If multi...read more
Ans. 
Find the row with the maximum number of 1s in a sorted matrix.
• Iterate through each row of the matrix and count the number of 1s in each row

• Keep track of the row index with the maximum number of 1s

• Return the index of the row with the highest count of 1s
Answered by AI
Add your answer
Q3. You have two wires of different lengths, each taking different amounts of time to burn completely. How can you use these wires to measure a specific duration of time?
Ans. 
By lighting both wires at the same time, the shorter wire will burn out first, allowing you to measure a specific duration of time.
• Light both wires at the same time

• Measure the time it takes for the shorter wire to burn out completely

• The remaining length of the longer wire will indicate the specific duration of time
Answered by AI
Add your answer
Q4. You have 3 ants located at the corners of a triangle. The challenge is to determine the movement pattern of the ants if they all start moving towards each other. What will be the outcome?
Add your answer

Q1. About salary negotiantion, communication skill
Add your answer
Q2. Abt company overview.communication skill
Add your answer