Data Engineer || MoEngage || 2 YOE
Summary
I recently interviewed for a Data Engineer position at MoEngage, which included a DSA round where I was asked to implement the 'Shuffle an Array' problem. Despite discussing several approaches for the solution, my candidacy was ultimately rejected.
Full Experience
I received a call from MoEngage HR regarding a Data Engineer opening. The interview process was described as having one DSA round, one System Design round, and one HR round. My first round was the DSA round. The interviewer provided a link to the LeetCode problem 'Shuffle an Array' and asked me to explain my approach and write code while discussing it. Initially, I proposed a brute-force idea of generating all permutations, but after discussing its time complexity, we agreed it wouldn't be an optimal solution. I then proceeded to explain multiple other approaches:
- Approach 1: Generate two random indices (using a random function) in the range [1, n], swap the elements at those indices, and then return the array.
- Approach 2: Iterate through the array. For each current index i, generate a random index j (typically within the range of elements not yet processed, e.g., [i, n-1]) and swap the elements at nums[i] and nums[j].
- Approach 3: Insert all elements into a HashSet (as in Java) and then randomly remove elements one by one to form the shuffled array. I did mention that this approach might not guarantee equal likelihood of all permutations.
Interview Questions (1)
The interviewer shared a link to the LeetCode problem 'Shuffle an Array'. The task was to design an algorithm to randomly shuffle an integer array, ensuring that all permutations of the array are equally likely. I needed to implement the Solution class with the following methods:
Solution(int[] nums): Initializes the object with the integer arraynums.int[] reset(): Resets the array to its original configuration and returns it.int[] shuffle(): Returns a random shuffling of the array.