Minimum substring window

1. /********************************************** Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n). For example, S = "ADOBECODEBANC" T = "ABC" Minimum window is "BANC". Note: If there is no such window in S that covers all characters in T, return the empty string "". If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S. ***********************************/ class Solution { public: string minWindow(string s, string t) { int n = s.size(); int m = t.size(); //two pointers, and two hashtable unordered_map<char,int> mytable; unordered_map<char,int> currtable; int count = 0; string result = ""; int minLen = INT_MAX; for(int i = 0;i mytable[t[i]]++; int left = 0; int right = 0; for(int right = 0;right

{ char c = s[right]; //move the right pointer if(mytable.find(c) != mytable.end())//found { if(currtable[c]// make all number from t being counted count++; currtable[c]++; } if(count == m) //found { char b = s[left]; // pay more attention to the following logic, how to move left pointer. while (mytable.find(b)==mytable.end() || currtable[b]> mytable[b]) { //found the character currtable[b]--; //go to next character left++; b = s[left]; } if((right-left+1) { minLen = right-left+1; result = s.substr(left,right-left+1); } } } return result; } };

binary search solution for minimum value in sorted array

Suppose a sorted array is rotated at some pivot unknown to you beforehand.
(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).
Find the minimum element.
You may assume no duplicate exists in the array.

 class Solution {
public:
    int findMin(vector& nums) {
        int low = 0;
        int n = nums.size();
        int high = n-1;
     
      while(low=nums[high])
      {
          int mid = low + (high-low)/2;
          //notes the index
          if(nums[mid]>nums[high]) low = mid+1;  //left sorted,search in right part
          else if(nums[mid]      }
      return nums[low];
    }
};



if there is duplicates in the rotated sorted array.

class Solution {
public:
    int findMin(vector& nums) {
        int low = 0;
        int n = nums.size();
        int high = n-1;
      
      while(low=nums[high])
      {
          int mid = low + (high-low)/2;
          //notes the index 
          if(nums[mid]>nums[high]) low = mid+1;  //right sorted
          else if(nums[mid]          else low = low+1;
      }
      return nums[low];
    }
};


search insert position

class Solution {
public:
    int searchInsert(vector& nums, int target) {
        int low = 0;
        int n = nums.size();
        int high = n-1;
      
          while(low          {
              int mid = low + (high-low)/2;
              //notes the index 
              if(nums[mid]              else 
                 high = mid; //right sorted,search in left part
          }
          return nums[low]    }
};

64bit and 32 bit

what is the 64bit processor
64-bit processor refers to a computing platform with 64-bit gates to the memory in terms of addressing, data buses, and registers. Generally speaking, the width of these gates defines how much data can be addressed to the memory of the processor in a single clock cycle. A simplistic interpretation would suggest that a 64-bit processor is capable of processing twice the amount of data a 32-bit counterpart can process per clock cycle. However, the system would not take advantage of these features if the required software drivers and application libraries were not implemented at the OS level.

64-bit versus 32-bit: Pros and Cons

　
Performance Enhancement
: 64-bit architecture comes with larger and more registers compared with its 32-bit counterpart. For example, ARMv8 improved the number of general-purpose registers from 16 as supported in ARMv7 to 31 registers. Registers are small and fast memory spaces (64 bits of length in the case of 64-bit) that the processor uses to hold instructions, storage addresses, bit sequences, or any other data information. They provide the fastest way to access and manipulate data, so the more and, most importantly, the wider the registers a processor can rely on, the better their performance. Although some applications, such as console-quality games, video encoding/decoding, photo editing, video streaming, data encryption, and database-intensive applications could take more advantage from 64-bit processing, the performance improves only slightly for the remaining applications. Current benchmarks show that the performance improvement with using 64-bit processing could be higher than 200% for, e.g., data encryption, while it could not exceed 10% for certain traditional applications.

Enhanced Security: A number of sensitive applications now use sophisticated encryption/decryption algorithms and require significant processing with accelerated advanced encryption standard (AES) and/or secure hash algorithms (SHA). AnandTech ran a number of benchmarks testing the performance of ARM 64-bit architecture versus 32-bit architecture and found that AES, now embedded in ARMv8, and SHA1 are the features to take most advantage of 64-bit implementation. In fact, the cryptographic tests conducted by AnandTech showed that 64-bit architecture offers 800% performance gain for AES and more than 240% for SHA1. The accelerated encryption/decryption performance means that applications could increasingly rely on sophisticated security standards without compromising the user experience.

Software Compatibility: Deploying 64-bit processors enables software compatibility across various device form factors. This means vendors could deploy the same applications (32-bit or 64-bit coded) across various devices. Mac developers, for example, will be able to compile ARM64 binaries from legacy Xcode.

Future-proofing: A 32-bit system is not optimized to use more than 4 GB of RAM. It does not efficiently use RAM resources beyond this limit unless it comes with physical address extensions (PAEs). Although PAEs allow the system to use more than 4 GB of RAM with 32-bit speed, the implementation of these extensions are difficult and power-demanding in a resource-constrained mobile environment. In contrast, 64-bit systems provide support to virtually unlimited amounts of RAM. This might look like there is no need for the use of 64-bit systems if RAM requirements are well below 4 GB in the mobile world. However, demand for memory for smartphones and tablets is increasing very rapidly. For example, iPhone RAM has increased about 8X from 2007 to 20012. With this in mind, and provided that smartphones will increasingly accommodate more advanced functions, it will not be surprising to see high-end smartphones coming with more than 4G of RAM by 2015. The industry will therefore have to prepare the market for such evolution and enable application developers and component manufacturers enough time to adapt their products to the new architecture. For these reasons, the majority of OSes targeting the high-end smartphone segment will have to comply with 64-bit architecture within the next cycle of their update if they need to keep up with advanced application performance requirements.

Fast Access to Storage: 64-bit addresses memory-mapped input/output, being faster and more efficient than 32-bit, mainly for large storage footprints.
However, there are also some issues related to implementing 64-bit processing over mobile phones, including:

Power Consumption: The fact that a 64-bit processor uses more and wider registers means the chip requires larger circuitry compared to its 32-bit counterpart, and this will likely make it more power-consuming. However, if the 64-bit chip runs on a 64-bit OS, then the power efficiency could be improved, as the OS executes the tasks in fewer cycles compared with the same task over a 32-bit chip running on a 32-bit or 64-bit OS. There is a general consensus that 64-bit chips could consume up to 10% more power than 32-bit chips, but this will depend on the implementation and the OS it runs on.

Increased BOM: Because 64-bit chips require more silicon and circuitry, they come in slightly larger form factors compared with 32-bit, provided they use the same semiconductor process (e.g., 28nm, 22nm). Mobile devices powered by 64-bit chips are likely to migrate to higher RAM capacity in the future. For better performance, they also require a 64-bit OS, but these OSes should be backward compatible with 32-bit architecture. This means the OS is likely to take more ROM space, as it needs to copy itself to comply with both 32-bit and 64-bit environments. All these elements will add more dollars to the overall BOM of the device. As a result, the implementation of 64-bit processing could add up to 15% of the total BOM of the mobile device. While this cost could be justified in the high-end segment because of performance enhancement, this will be hard to justify in the cost-sensitive market where 64-bit could add only minor enhancement to the overall performance of the device.

Compatibility: 32-bit hardware is not compatible with a 64-bit OS. This means once the OS is upgraded to 64-bit capabilities, it will not be able to run on 32-bit hardware. OS vendors will have to create 32-bit variants to be able to update existing devices with the new software.