Round 1
Questions:
- Count the number of inversions in an array, where an inversion is when arr[i] > arr[j] for i < j.
- Explain how skip lists provide O(log n) search time and discuss the probability of height adjustment during insertion.
Candidate's Approach
No approach provided.
Interviewer's Feedback
No feedback provided.
Round 2
Questions:
- Solve the Josephus problem and list the persons in the order they are executed. (Don't solve using Fenwick or Segment Tree, expected time complexity is N√N.)
- Analyze the time complexity of the following nested loops:
int j; for (int i = 0; i < n; i = i + j) { for (j = 1; j <= k; j++) { // Constant Work } } - What are Python decorators, and how do they differ from metaclasses? Explain with an example of a metaclass that modifies class behavior.
Candidate's Approach
No approach provided.
Interviewer's Feedback
No feedback provided.
Round 3
Questions:
- Design a stack that supports the following operations:
push(x) - Add an element to the top of the stack. pop() - Remove the top element of the stack. top() - Retrieve the top element of the stack. getMin() - Retrieve the minimum element in constant time. getKthMin(k) - Retrieve the k-th minimum element in constant time. - Write a regular expression to match strings that start with a letter, contain exactly 3 digits in the middle, and end with one of the extensions .txt, .log, or .csv.
- Explain how the chroot command can improve security. How can it be exploited, and what are the best practices to mitigate these risks?
Candidate's Approach
No approach provided.
Interviewer's Feedback
No feedback provided.