Search in Rotated 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).
You are given a target value to search. If found in the array return its index, otherwise return -1.
You may assume no duplicate exists in the array.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

public class Solution { //this is a more general binary search, it handles sorted array too public int search(int[] nums, int target) { int l=0,r=nums.length-1; if(nums.length==1&&nums[0]==target)return 0; while(l<=r){//so it can process situation of two numbers int mid=l+(r-l)/2; if(nums[mid]==target)return mid; //in a rotated array, there must be one half is sorted //we try to identify the sorted part out and start from dealng with it because it is easier if(nums[mid]<=nums[r]){ //sorted part is right array if(target>nums[mid]&&target<=nums[r]) l=mid+1;//we know mid is not the selection because otherwise it's returned else//it's not in right, then it is in left r=mid-1; }else{//then sorted part is in left if(target>=nums[l]&&target<nums[mid])//it is within sorted left array r=mid - 1; else//if not, it is in right part l = mid+1; } } return -1; } }

Made a recursive version of it.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

public int search(int[] nums, int target) { return searchRec(nums,target,0,nums.length-1); } public int searchRec(int[] nums, int target,int left, int right) { if(nums.length==1&&nums[0]==target)return 0; if(left>=right){ if(nums[left]==target)return left; else return -1; } int mid=left+(right-left)/2; if(nums[mid]==target)return mid; //in a rotated array, there must be one half is sorted //we try to identify the sorted part out and start from dealng with it because it is easier if(nums[mid]<=nums[right]){ //sorted part is right array if(target>nums[mid]&&target<=nums[right]) return searchRec(nums,target,mid+1,right);//we know mid is not the selection because otherwise it's returned else//it's not in right, then it is in left return searchRec(nums,target,left,mid-1); }else{//then sorted part is in left if(target>=nums[left]&&target<nums[mid])//it is within sorted left array return searchRec(nums,target,left,mid - 1); else//if not, it is in right part return searchRec(nums,target,mid+1,right); } }

Find Minimum in Rotated 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.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

public class Solution { public int findMin(int[] nums) { if (nums == null || nums.length == 0) { return 0; } int l = 0; int r = nums.length - 1; while (l+1 < r) {//deal with one or two numbers int mid = l + (r - l) / 2; if (nums[l] < nums[r]) {//sorted, no rotation return nums[l]; } else if (nums[mid] < nums[r]) {//right is sorted,pivot point is in left, //get rid of right array by redefining r r = mid; } else if (nums[l] < nums[mid]) {//left is sorted, pivot is in right, //redefine left point by move left to mid l = mid; } } return Math.min(nums[l], nums[r]); } }

Number of even numbers

Given a start number and end number, figure out how many even numbers in between them.

1. you can do bruteforce ways to loop through numbers between them and count the even numbers.
2. or, thinking of there will be one even number within two consecutive numbers, you can come out a fomlar:

 if(e-s+1 is even) then
    return (e-s+1)/2;
 else{
    if(s is even) then
      return (e-s+2)/2;//borrow a number to make it even count
   else
      return (e-s)/2;
}

for example: 2 to 4, 4-2+1 is odd number , so that (4-2+2)/2=2.
3 to 5, (5-3)/2=1

3 to 7, (7-3+1)=5, it is even, and 3 is even, so (7-3)/2=2.

3. an easier to understand formula:
observe
n : even, odd
1 : 0, 1
2: 1, 1
3: 1, 2
4: 2, 2
5: 2, 3
6: 3, 3
7: 3, 4
etc 

first of all, for one number n, 
n is even: the number of even and odd numbers is n/2 and n/2 respectively. 
     even: n/2     odd: (n)/2
n is odd: the number of even and odd numbers is (n-1)/2 and (n+1)/2 respectively. 
    even: (n-1)/2  odd:(n+1)/2
 


if giving a range, you can calculate them separately, then minus smaller ones from bigger ones:


int countEvenNumbers(int s, int e){
    int more = e%2==0?e/2:(e-1) /2;
    int less=s%2==0?s/2:(s-1)/2;
    return more -less;
}

KnapSack, repeat selection

This is similar to coin change problem when it allows multiple selections on items.

Given a list of  integers, , and another integer,  representing the expected sum. Select zero or more numbers from  such that the sum of these numbers is as near as possible, but not exceeding, to the expected sum ().

Note

• Each element of  can be selected multiple times.
• If no element is selected then the sum is 0.

Input Format

The first line contains  the number of test cases.
Each test case comprises of two lines. First line contains two integers,  , representing the length of list  and expected sum, respectively. Second line consists of  space separated integers, , representing the elements of list .

Constraints

Output Format

Output  lines, the maximum sum for each test case which is as near as possible, but not exceeding, to the expected sum (k).

Sample Input

2
3 12
1 6 9
5 9
3 4 4 4 8

Sample Output

12
9

Explanation

In the first test case, one can pick {6, 6}. In the second, we can pick {3,3,3}.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55

package dp; import java.util.Scanner; public class KanpSack { public static void main(String[] args) { /* * Enter your code here. Read input from STDIN. Print output to STDOUT. * Your class should be named Solution. */ Scanner in = new Scanner(System.in); int t = in.nextInt(); in.nextLine(); for (int i = 0; i < t; i++) { int n = in.nextInt(); int k = in.nextInt(); in.nextLine(); int[] arr = new int[n]; for (int j = 0; j < n; j++) { arr[j] = in.nextInt(); } in.nextLine(); process(arr, k); } in.close(); } private static void process(int[] arr, int k) { int max = maxSum(arr, k); System.out.println(max); } private static int maxSum(int[] arr, int k) { if (arr == null || arr.length == 0) return 0; int[] dpSums = new int[k + 1]; dpSums[0] = 0; // for each sum form small to big for (int i = 1; i <= k; i++) { // for each possible selections, better from small to large for (int j = 0; j < arr.length; j++) { if (arr[j] <= i) {// when available selection is less or equal // than current sum // figure out maximum sum the selections can come up // second part is important, it is previous sum with // possible selection dpSums[i] = Math .max(dpSums[i], arr[j] + dpSums[i - arr[j]]); } } } return dpSums[k]; } }

Web Service Revisiting

Nowadays, it is so easy to write web services in Java by using annotations. Recalling my old days between 2003 and 2005 to compose SOAP messages and parsing it by plain Java code, then in 2006 rescued by Axis, nothing of those can be compared by the easiness provided by JAX-WS and JAX-RS, along with JAXB. All you need to do is just annotations.

And built in JDK, you do not even need to have a web server. Endpoint.publish itself can start your web service and allow you to interact with it.

Here's a very simple example of converting one of my algorithm practice to SOAP style web service.

Java code with annotations. Endpoint in main method publish it as web service and waits for it to be invoked. This is probably the simplest way of debugging a web service if you run it in debug mode.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85

package string; import java.util.Arrays; import java.util.Objects; import javax.jws.WebMethod; import javax.jws.WebService; import javax.xml.ws.Endpoint; /** 1.If last characters of two strings are same, nothing much to do. Ignore last characters and get count for remaining strings. So we recur for lengths m-1 and n-1. 2. Else (If last characters are not same), we consider all operations on ‘str1′, consider all three operations on last character of first string, recursively compute minimum cost for all three operations and take minimum of three values. Insert: Recur for m and n-1 Remove: Recur for m-1 and n Replace: Recur for m-1 and n-1 https://en.wikipedia.org/wiki/Levenshtein_distance * @author Andrew Ma * */ @WebService public class EditDistance { static int min(int x, int y, int z){ return Math.min(x,Math.min(y, z)); } /** * bottom up dp. advancing to here after understanding the recursive algorithm * @param s1 * @param s2 * @return */ @WebMethod(operationName="getEditDistance") public int editDistanceDP(String s1, String s2){ Objects.requireNonNull(s1); Objects.requireNonNull(s2); // if(s1.length()==0)return s2.length(); // if(s2.length()==0)return s1.length(); //i,j means difference so far up to i-1 in s1 and j-1 in s2 // so the last examined positions are last characters in both string, in dp[][], that is dp[m][n] int[][] dp = new int[s1.length()+1][s2.length()+1]; for (int i=0; i<=s1.length(); i++) { for (int j=0; j<=s2.length(); j++) { if(i==0) dp[i][j]=j; else if (j==0) dp[i][j]=i; //when it runs to here , i and j would be greater than 0 //i-1 and j-1 are real index to strings //0 is just for dp[][] else if (s1.charAt(i-1)==s2.charAt(j-1)) dp[i][j] = dp[i-1][j-1]; else{ //edit operation happens on s1 dp[i][j] = 1+min( dp[i][j-1],//remove:means i skip one to next dp[i-1][j],//insert: means i keeps same, j goes to next one dp[i-1][j-1]//replace: both skip one ); } } } return dp[s1.length()][s2.length()]; } public static void main(String[] args) { String s1 = "andrewma"; String s2 = "andyMa"; int[][] dp = new int[s1.length()+1][s2.length()+1]; for(int i=0;i<dp.length;i++) Arrays.fill(dp[i], -1); System.out.println(editDistanceRecursive(s1, s2, s1.length(), s2.length())); System.out.println(editDistanceRecursiveDP(s1, s2, s1.length(), s2.length(),dp)); //System.out.println(editDistanceDP(s1, s2)); System.out.println(editDistanceDPWiki(s1, s2)); Endpoint.publish("http://localhost:88/editDistance", new EditDistance()); } }

Usually when you deploy it to some app server such as glassfish, web interface will be generated for you for testing. With this simple method, there's no tester interface except the wsdl and xsd. You can use postman to easily compose a message according to wsdl and xsd to interact with web service just deployed.

Below is a sample SOAP message composed by hand and executed in postman. The name space and message format were parsed from wsdl and xsd being used in wsdl.


   
   
       
            abcdedfg
            abcdfg
       
   


Here is response:



   
       
            2
       
   


Developing RESTful web service has similar experience when I tried with jersey a year ago. a nice thing is you can easily use browser or curl to test the service.