Monday, December 29, 2014

Next Character

/** 
* Return the smallest character that is strictly larger than the search character, 
* If no such character exists, return the smallest character in the array 
* @param sortedStr : sorted list of letters, sorted in ascending order. 
* @param c : character for which we are searching. 
* Given the following inputs we expect the corresponding output: 
* ['c', 'f', 'j', 'p', 'v'], 'a' => 'c' 
* ['c', 'f', 'j', 'p', 'v'], 'c' => 'f' 
* ['c', 'f', 'j', 'p', 'v'], 'k' => 'p' 
* ['c', 'f', 'j', 'p', 'v'], 'z' => 'c' // The wrap around case 
* ['c', 'f', 'k'], 'f' => 'k' 
* ['c', 'f', 'k'], 'c' => 'f' 
* ['c', 'f', 'k'], 'd' => 'f' 
*/
Click here for the original problem.
The problem doesn't clarify if duplicates are allowed in the array. So I wrote two.


public class SmallestCharacter {
 public char nextChar(char[] list, char c) {
  if (list == null || list.length == 0)
   throw new IllegalArgumentException("Null or empty list!");
  int start = 0;
  int end = list.length - 1;
  if (c < list[0] || c >= list[list.length - 1])
   return list[0];
  while (start < end) {
   int mid = (start + end) / 2;
   if (c == list[mid]) {
    //System.out.println(mid + ": " + list[mid]);
    return list[mid + 1];
   }
   else if (c < list[mid]) {
    //System.out.println("smaller: " + mid);
    end = mid - 1;
   }
   else {
    //System.out.println("greater: " + mid);
    start = mid + 1;
   }
  }
  if (list[start] == c)
   return list[start + 1];
  return list[start];
 }
}


Duplicates are allowed (not much difference though...)


public char nextChar2(char[] list, char c) {
  if (list == null || list.length == 0)
   throw new IllegalArgumentException("Null or empty list!");
  int start = 0;
  int end = list.length - 1;
  if (c < list[0] || c >= list[list.length - 1])
   return list[0];
  while (start < end) {
   int mid = (start + end) / 2;
   if (c == list[mid]) {
    if (list[mid + 1] > c)
     return list[mid + 1];
    else 
     start = mid + 1;
   }
   else if (c < list[mid]) {
    end = mid - 1;
   }
   else
    start = mid + 1;
  }
  if (list[start] == c)
   return list[start + 1];
  return list[start];
 }

No comments:

Post a Comment