Online Assessment
Questions:
-
Question 1 (Easy): You will have a stream of numbers as input and you have to print output in sequence if all the prior numbers exist in the input stream.
- Example:
- Input:
3 1 2 6 5 4
- Output:
[[1],[2,3],[4,5,6]]
- Input:
- Solution: Use a set to keep track of numbers that have already been received and use another variable called
start = 1
. Ifstart
is present in the set, keep adding it into the output and increasestart
by 1. - Verdict: All test cases passed.
- Example:
-
Question 2 (Medium): You are given an array of integers. You have to make packets from its elements. A packet can contain at most 2 elements and cannot be empty. You have to tell the maximum number of packets that can be created where the sum of elements in each packet is equal among all packets.
- Example:
- Input:
1 4 3 2 2 6
- Output:
3
(Packets:[4]
,[2,2]
,[1,3]
)
- Input:
- Solution: Sort the input array. The maximum sum of two elements cannot exceed
2 * max_element
of the array. Check for every sum starting from2 * max_element
. Use upper bound to find that sum in the array and use an approach like two-sum to find how many pairs you can make out of it. - Verdict: All test cases passed.
- Example:
Round 1
Questions:
-
Question 1 (Easy): Find Next Greater Element
- Follow-up: What if the array is circular?
- Solution: This is a standard question. We can solve it using a stack while traversing the array from reverse. For the follow-up, we can append the array to itself and then apply the same algorithm.
- Complexity: Discussed with the interviewer.
-
Question 2 (Easy): Number of Islands
- Follow-up: There are two matrices given, A and B. An island in B counts as a valid island only if it is entirely within an island in A.
- Solution: This is also a standard question. We can solve it using DFS and BFS. For the follow-up, check if there is any
i,j
whereB[i][j] == 1
andA[i][j] == 0
. Use BFS or DFS traversal on B to mark that island as 0, then apply the original algorithm in the second pass. - Complexity: Discussed with the interviewer.
Candidate's Approach
The candidate effectively utilized standard algorithms for both questions, demonstrating a solid understanding of data structures like stacks and traversal methods like DFS and BFS. The candidate was able to articulate the solutions clearly and discuss the complexities involved.
Interviewer's Feedback
The interviewer was satisfied with the candidate's solutions and explanations, indicating a good grasp of the concepts.
Round 2
Questions:
-
Question 1 (Medium): Implement a class named
NumberPool
which consists of two methods:checkout()
andcheckin()
.checkout()
will give the minimum number present in the pool and pop it out, whilecheckin()
will insert the given number back into the pool.- Solution: Initially provided a brute force solution using a min priority queue. Suggested an optimization using a set to track numbers that have been popped out and iterating from 1 to INT_MAX to find the next available number.
- Follow-up: Discussed another approach using a doubly linked list.
-
Question 2 (Medium): Reorganize String
- Solution: Used a priority queue approach to append the character with the maximum frequency and reduce its frequency by one, pushing it back into the queue while blocking the last appended character.
- Complexity: Initially stated as O(N log N) but corrected to O(N log(26)) due to the limited number of characters. The interviewer challenged the candidate to find a linear time complexity solution, which the candidate could not provide.
Candidate's Approach
The candidate demonstrated a good understanding of data structures and algorithms, initially providing a brute force solution and then optimizing it. However, they struggled to find a linear time complexity solution for the second question.
Interviewer's Feedback
The interviewer seemed satisfied with the candidate's initial approaches but encouraged them to think of more efficient solutions, particularly for the second question.