Efficient algorithm to print count and possible string outcomes of a given input string

Write an Efficient algorithm to print count and possible string outcomes of a given input string by retaining order and considering all characters during this process
Problem: given a input string as "0000" and following input scheme for the zeroes, print the possible outcomes by retaining order of the characters. input scheme: a "0" b "00" c "000" d "0000" example: "aaaa" is one string outcome and bb is another string outcome

Questions by taru22

Showing Answers 1 - 1 of 1 Answers

cfphpflex@gmail.com

  • Mar 21st, 2013
 

1. get string length
2. print length
3. for string 0000, its easy:
4. look at 0000 and quickly understand that each 0 in the string can only have 3 other possible 0 s to compare against and get a different string
5. Since changing the zeroes to any position does not yield a different string, the answer is 1
6. Code: for 0000 a bubble sort (inefficient) but gets the job done
see my code for bubble sort on GitHub https://github.com/cfphpflex/eztest2/blob/master/NimbleFish_Interview_BubbleSort_Problem_Solution.as

Code
  1.  ActionScript code:

  2.  

  3.  

  4.  

  5.  

  6.                 // function to swap values in array    

  7.                 function swap( a:int, b:int, arr:Array ):Array

  8.                         {   var tempItem:int = arr[a];                  // set temp for a position 1

  9.                                 arr[a]                   = arr[b];                      // reset value  on position 2

  10.                                 arr[b]                   = tempItem;            // reset value on position 1

  11.  

  12.                                 return arr;  // return array

  13.                         }

  14.  

  15.  

  16.                 // bubbleSwuap  function  to process array per problem logic   

  17.                 function bubbleSwap(arrayLen:int, arr:Array):Array  

  18.                         {

  19.                                 for (  var i:int = 0; i < ( arrayLen - 1); i++    )

  20.                                 {  // arrayLen minus 1 because we determined  number of passess is len - 1, final pass is not necessary, by pass meaning loop additionally, if the sorted

  21.  

  22.  

  23.                                         for (  var a:int = 0; a < (arrayLen - 1); a++    )

  24.                                         {  // arrayLen minus 1 because aray starts with 0 element position

  25.                                                 var b:int = a+1; // set  second element position

  26.  

  27.                                                 if (arr[b] < arr[a])   // if the element being swaped forward is greater than the next element position to the right, move it to the right by calling swap funciton

  28.                                                 {  

  29.                                                         arr = swap( a, b, arr );  //call swap function

  30.                                                 }

  31.                                                 else{  // break;  //  break loop  interferes with sorting larger seed arrays

  32.                                                 }  

  33.                                         }

  34.                                 }

  35.  

  36.                                 return arr;   // return array

  37.                                 //mx.controls.Alert.show(" Pass "+ i + "Final Bubble Sorted Array:     " +  arr );

  38.  

  39.                         }

  40.  

  41.  

  42.                  function alertShow(message, finalArray):void

  43.                         {    

  44.                             mx.controls.Alert.show(message + finalArray);

  45.  

  46.                         }

  47.  

  48.  

  49.  

  50.                             var arr:Array                       = new Array(2,500,300,99,77,180,5,33,3,22,1);   //  initial array

  51.                                 var arr2:Array                  = new Array(2,500,300,99,77,180,5,33,3,22,1);   //  for array DESCENDING  sort

  52.                                 var arrayLen:int                = arr.length;                                                                   // set aray length

  53.  

  54.                                 var finalArray:Array    = bubbleSwap(arrayLen, arr);            //  declare final Array variable calling bubbleSwap function and passing array and len arguments into it for copy

  55.  

  56.                                 var message:String =  "Final Bubble Sorted Array "   ;  // make a message

  57.                                 alertShow( message , finalArray );   // display alert message

  58.  

  59.                                 //var message2:String =  "Final Bubble Sorted Array "   ;  // make a message

  60.  

  61.                                 //arr2.sort(Array.DESCENDING | Array.CASEINSENSITIVE); // does not work

  62.  

  63.                                 //alertShow( message2, arr2 );   // display alert message

  64.  

  65.  

  66.                 }

  Was this answer useful?  Yes

Give your answer:

If you think the above answer is not correct, Please select a reason and add your answer below.

 

Related Answered Questions

 

Related Open Questions