uopspop

Untitled

Nov 3rd, 2020
902
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. package other;
  2.  
  3. public class interview_arrayshift_space_rolloinghash {
  4.     /**
  5.      * n = 5
  6.      * [1,2,3,4,5] or [5,4,3,2,1]
  7.      * [1,2,3,4,5]: true
  8.      * [3,4,5,1,2]: true
  9.      * *[4,5,1,2,3]: true
  10.      * [5,1,2,3,4]: true
  11.      * [5,4,1,2,3]: false
  12.      * *[3,2,1,5,4]: true
  13.      *
  14.      *
  15.      * Time BigO: n
  16.      * Space BigO: n
  17.      *
  18.      */
  19.  
  20.     public static void main (String[] args) {
  21.  
  22.  
  23. //        int[] ary = {1,2,3,4,5};
  24. //        int[] ary = {5,1,2,3,4};
  25.         int[] ary = {4,5,1,2,3};
  26. //        int[] ary = {5,4,1,2,3}; // false
  27. //        int[] ary = {4,5,6,7,8,1,2,3};
  28. //        int[] ary = {7,8,4,5,6,1,2,3}; // wrong: double downs
  29.  
  30. //        int[] ary = {5,4,3,2,1};
  31. //        int[] ary = {3,2,1,5,4};
  32. //        int[] ary = {7,6,5,4,3,2,1,9,8};
  33. //        int[] ary = {3,2,1,7,6,5,9,8}; // wrong: double ups
  34.  
  35.         // append the exact same array to the end
  36. //        int[] ary_2 = new int[ary.length * 2];
  37. //        for (int i = 0; i < ary.length; i++) {
  38. //            ary_2[i] = ary[i];
  39. //            ary_2[i + ary.length] = ary[i];
  40. //        }
  41.  
  42.         int hash_power = 31;
  43.  
  44.         // ascending
  45.         boolean is_asce_ok = check_asec(ary, hash_power);
  46.         System.out.println("is_asce_ok: " + is_asce_ok);
  47.  
  48.         // descending
  49.         boolean is_desc_ok = check_desc(ary, hash_power);
  50.         System.out.println("is_desc_ok: " + is_desc_ok);
  51.  
  52.     }
  53.  
  54.     private static long hash(int[] ary, int hash_power) {
  55.         long hash = 0l;
  56.         for (int i = 0; i < ary.length; i++) {
  57.             hash = hash * hash_power + ary[i]; // 左大右小
  58.         }
  59.         return hash;
  60.     }
  61.  
  62.     private static boolean check_asec(int[] ary, int hash_power) {
  63.         // create asec ary
  64.         int[] ary_asec_ok_ary =  new int[ary.length];
  65.         for (int i = 0; i < ary_asec_ok_ary.length; i++) {
  66.             ary_asec_ok_ary[i] = i + 1;
  67.         }
  68.         // calculate hash
  69.         long hash_asec_ok_value = hash(ary_asec_ok_ary, hash_power);
  70.         // check it
  71.         boolean is_asce_ok = check_result(ary, hash_asec_ok_value, "asec", hash_power);
  72.         return is_asce_ok;
  73.     }
  74.  
  75.     private static boolean check_desc(int[] ary, int hash_power) {
  76.         // create desc ary
  77.         int[] ary_desc_ok_ary =  new int[ary.length];
  78.         for (int i = 0; i < ary_desc_ok_ary.length; i++) {
  79.             ary_desc_ok_ary[i] = ary_desc_ok_ary.length - i; // ex. [5,4,3,2,1]
  80.         }
  81.         // calculate hash
  82.         long hash_desc_ok_value = hash(ary_desc_ok_ary, hash_power);
  83.         // check it
  84.         boolean is_desc_ok = check_result(ary, hash_desc_ok_value, "desc", hash_power);
  85.         return is_desc_ok;
  86.     }
  87.  
  88.     private static boolean check_result(int[] ary, long target_hash, String direction, int hash_power) {
  89.         boolean isAsecOK = false;
  90.         Long hash_val = null;
  91.         for (int i = 0; i < ary.length; i++) {
  92.             // calculate hash value
  93.             if (hash_val == null) {
  94.                 hash_val = hash(ary, hash_power);
  95.             }else {
  96.                 hash_val -= (long)(ary[i-1] * Math.pow(hash_power,ary.length-1)); // step01: remove the lest-most number
  97.                 hash_val *= hash_power; // step02: more ALL left
  98.                 hash_val += ary[i-1]; // step03: add the to the right-most place
  99.             }
  100.  
  101.             // check hash
  102.             if (hash_val == target_hash) {
  103.                 // if hash matched, check in details
  104.                 int i_ary_count = 0;
  105.                 int i_ary_tmp = i;
  106.                 while (true) {
  107.                     if (i_ary_count >= ary.length) {
  108.                         isAsecOK = true;
  109.                         break;
  110.                     }
  111.                     if (i_ary_tmp >= ary.length) {
  112.                         // % go around the array to the start
  113.                         i_ary_tmp = 0;
  114.                     };
  115.  
  116.                     /** main logic here **/
  117.                     if (direction.equals("asec")) {
  118.                         int val = i_ary_count + 1;
  119.                         if (ary[i_ary_tmp] != val) {
  120.                             isAsecOK = false;
  121.                             break;
  122.                         }
  123.                     }else if (direction.equals("desc")) {
  124.                         int val = ary.length - i_ary_count;
  125.                         if (ary[i_ary_tmp] != val) {
  126.                             isAsecOK = false;
  127.                             break;
  128.                         }
  129.                     }
  130.  
  131.                     i_ary_count++;
  132.                     i_ary_tmp++;
  133.  
  134.                 } // end of while
  135.             } // hash matched
  136.             if (isAsecOK) break;
  137.         }
  138.         return isAsecOK;
  139.     }
  140.  
  141. }
  142.  
RAW Paste Data

Adblocker detected! Please consider disabling it...

We've detected AdBlock Plus or some other adblocking software preventing Pastebin.com from fully loading.

We don't have any obnoxious sound, or popup ads, we actively block these annoying types of ads!

Please add Pastebin.com to your ad blocker whitelist or disable your adblocking software.

×