The OOPs questions were very direct and easy. In the database, I had no idea about NoSQL database uses other than key-value pairing. The coding question evolved during the interview. 1. No constraints: I gave a brute-force solution comparing each element to other elements if we get any repeating element, return it. T(n) = O(n^2); S(n) = O(1); array not disturbed 2. use less time I sorted the array and traversed through the array to find repeating elements. T(n) = O(N log N); S(n) = 1; array disturbed 3. use O(n) time I used another array of size k storing the count of the appeared elements, if I found any count greater than 1, I'll return it. T(n) = O(n); S(n) = O(n); array not disturbed 4. let say k > n same solution with maps instead of an array. T(n) = O(n); S(n) = O(n); array not disturbed 5. use O(n) time and O(1) space I looped through the array and marked the arr[arr[i]] with k+1+arr[arr[i]] so that i can know if i have visited/ seen this number earlier. if i find any arr[i] for which arr[arr[i]] > k then i'll return arr[i]; T(n) = O(n); S(n) = O(1); array disturbed 6. final constraint use O(N log N) time, O(1) space, and the array should not be disturbed Here I was stuck for around 5 minutes and then he gave me the first hint. "Think of k as an array, not as an index." I wasn't able to catch the hint and the interview ended. he gave me the solution by the binary search that I couldn't think of at the time of the interview. Basically the idea was to find if the count of the elements less than k/2 is greater then k/2 then the solution is in 1 to k/2, else is lying in k/2+1 to k and binary search so on.