Solution: Maximum Salary

Solutions for the Largest Concatenate Problem.

We'll cover the following


Recall the algorithm for this problem that works for single-digit numbers.

 yourSalaryyourSalary \leftarrow empty string
 while NumbersNumbers is not empty:
  maxNumbermaxNumber \leftarrow -\infty
  for each NumberNumber in NumbersNumbers:
   if numbernumber \geq maxNumbermaxNumber:
    maxNumbermaxNumber \leftarrow numbernumber
  append maxNumbermaxNumber from yourSalaryyourSalary
  remove maxNumbermaxNumber from NumbersNumbers
return yourSalaryyourSalary

As we already know, this algorithm does not always maximize your salary. For example, for an input consisting of two integers, 2323 and 33, it returns 233233, while the largest number is 323323.

Not to worry, all you need to do to maximize your salary is replace the line

 if numbernumbermaxNumbermaxNumber:

with the following line

 if IsBetter(number,maxNumber)IsBetter(number,maxNumber):

for an appropriately implemented function IsBetter. For example, IsBetter(3, 23) should return True.

Stop and think: How would you implement IsBetter?


Here is the code for the algorithm discussed above. Click the “Run” button to see how it works.

Level up your interview prep. Join Educative to access 80+ hands-on prep courses.