CareerCup

Interviewer's solution to the 4th question

public int minUniqueSum(int[] A) {
int n = A.length;

int sum = A[0];
int prev = A[0];

for( int i = 1; i < n; i++ ) {
int curr = A[i];

if( prev >= curr ) {
curr = prev+1;
}
sum += curr;
prev = curr;
}

return sum;
}

Looking for interview experience sharing and mentors?
Visit A++ Coding Bootcamp at aonecode.com.

Taught by experienced engineers/interviewers from FB, Google and Uber,
our ONE TO ONE courses cover everything in an interview including
latest interview questions sorted by companies,
SYSTEM DESIGN Courses (highly recommended for people interviewing with FLAG)
ALGORITHMS (conquer DP, Graph, Greed and other advanced algo problems),
and mock interviews.

Our students got offers from G, U, FB, Amz, Yahoo and other top companies after a few weeks of training.

Welcome to email us aonecoding@gmail.com with any questions. Thanks for reading.

Q4: we will do following

public static int MinimumSumArray(int[] arr)
        {
            Array.Sort(arr);
            int currentMin = arr[0];
            int sum = arr[0];
            int currentElement = arr[0];
            int i = 1, j = 1;
            while (i < arr.Length)
            {
                if (arr[i] == currentElement)
                {
                    while (true)
                    {
                        if (j < arr.Length)
                        {
                            if (arr[j] == currentElement)
                            {
                                j++;
                            }
                            else if (arr[j] == currentMin+1)
                            {
                                while (j < arr.Length && arr[j] == currentMin + 1)
                                {
                                    j++;
                                }
                                currentMin++;
                            }
                            else
                            {
                                break;
                            }
                        }
                        else
                        {
                            currentMin++;
                            break;
                        }
                    }
                    arr[i] = currentMin;
        
                }
                else
                {
                    currentElement = arr[i];
                }
                sum += arr[i];
                i++;
                if (j < i)
                {
                    j = i;
                }
            }
            return sum;
        }

Complexity of this O(Nlog(N)) + O(1);

#!/usr/bin/ruby

def uniq_sum(input)
  until input.uniq.length == input.length
    input.sort!
    input.each.with_index do |e, i|
	  if i + 1 < input.length
		if input[i+1] == e
			input[i+1] += 1
		end
	  end
    end
  end
  input.inject(:+)
end