Tuesday, October 23, 2012

Microsoft: Find biggest number that can be formed from a list of unsorted numbers


  Microsoft Interview - Given an array of unsorted numbers (1 or 2 digits),
  Find the biggest number that can be created using these numbers
  For e.g. {6, 83, 12, 7, 16, 35}
  The biggest number that can be made is 83,7,6,35,16,12
 
Solution
  The idea is to create 2 maxheaps - one for one digit numbers
  The other for 2 digit numbers. Then compare and create final string.
 
  Extending this to any arbitary length is simple. Instead of using 2 maxheaps,
  use n maxheaps, where n is the length of the number with the maximum length.
  Compare and create can use N-way merge then, instead of simple if-else.

No comments:

Post a Comment

UA-36403895-1