Java Memory Dump

1. Using JVM option, Automatically when OutOfMemory happens.
    -XX:+HeapDumpOnOutOfMemoryError -XX:HeapDumpPath=/tmp/esDump.hprof
    if dump path is not specified, usually it will be in java.io.tmpdir. /tmp as a hint.

2. Using jmap  tools shipped with JDK. If you did not run out of file descriptors and still be able to connect to jvm.
    jmap -dump:live,format=b,file=/tmp/heap0409.bin 13419
    if live is not specified, entire memory will be dumped and that can be big and slow.

3. Using Linux gdb
    3.1 view memory map of a process
        cat /proc/{$pid}/maps
    3.2 gdb attach {$pid}
    3.3 issue dump memory command in gdb. need to removed - and add 0x before the memory ranged displayed in 3.1.
        dump memory /tmp/memdump 0x02079000 0x020b6000

        dump memory /tmp/memdump2 0x020b6000 0x02171000

4. Using JDK tools such JVisualVM, jconsole, java mission control etc. Server side accessibility need to be enabled

    4.1 enable server to be accessible

        4.1.1 jmx

        -Dcom.sun.management.jmxremote=true -Dcom.sun.management.jmxremote.port=9090 -Dcom.sun.management.jmxremote.ssl=false -Dcom.sun.management.jmxremote.authenticate=false -Djava.rmi.server.hostname={$ip to provide service} -Dcom.sun.management.jmxremote.rmi.port=9091

        4.1.2 jstatd

                #enable remote debug via jstatd 

                #Create jstatd.policy. put it in /root

grant codebase "file:/usr/lib/jvm/jdk1.8.0_191/lib/tools.jar" {

    permission java.security.AllPermission;

};

               #Start stated

              jstatd -p 9090 -J-Djava.security.policy=~jstatd.policy

              jstatd -p 9090 -J-Djava.security.policy=/root/jstat.policy -J-Djava.rmi.server.hostname={$ip as remote host}

    4.2 dump memory or thread in the tool

    4.3 view and analyze with same tool

Other useful tools usually used together

1. view tcp memory

#tcp_mem etc

cat /proc/sys/net/ipv4/tcp_mem

cat /proc/net/sockstat

2. lsof in a process

#found evidence of opening too many files.

#list open files

lsof -p $pid

lsof -a -i4 -i6 -itcp -p $pid

3. netstat for network and connections

netstat -a -n | grep tcp | grep 9200 

#view connection count from hosts

#check ip addresses 

netstat -nat | awk '{print $5}'| awk -F":" '{print $1}' | sort | uniq -c

#further on specific port

netstat -nat | grep 9200 |awk '{print $5}'| awk -F":" '{print $1}' | sort | uniq -c

4. network tuning under /proc/sys/net

#putting them all together. To make socket close quicker and fail quicker

echo 20 > /proc/sys/net/ipv4/tcp_fin_timeout

echo 30 > /proc/sys/net/ipv4/tcp_keepalive_intvl

echo 5 > /proc/sys/net/ipv4/tcp_keepalive_probes

cat /proc/sys/net/ipv4/tcp_fin_timeout

cat /proc/sys/net/ipv4/tcp_keepalive_intvl

cat /proc/sys/net/ipv4/tcp_keepalive_probes

5. turn on and off the swap file on linux

#fallocate -l 2G /swapfile

dd if=/dev/zero of=/swapfile bs=1024 count=2097152

chmod 600 /swapfile

mkswap /swapfile

swapon /swapfile

##enlarge to 8 gb from 2gb

swapoff /swapfile

#dd always works

dd if=/dev/zero of=/swapfile bs=1M count=6144 oflag=append conv=notrunc

mkswap /swapfile

swapon /swapfile

6. Enable core dump: 

ulimit -c unlimited

7. use crontab to collect information periodicaly.

#run every 10 minutes

*/10 * * * * /home/ama/indexerCheck.sh

Adding or Enlarging Swap file

#create a swap file, fallocate is not working

#fallocate -l 2G /swapfile

dd if=/dev/zero of=/swapfile bs=1024 count=2097152

chmod 600 /swapfile

mkswap /swapfile

swapon /swapfile

#also make it part of fstab

/etc/fstab

/swapfile swap swap defaults 0 0

##enlarge to 8 gb

swapoff /swapfile

dd if=/dev/zero of=/swapfile bs=1M count=6144 oflag=append conv=notrunc

mkswap /swapfile

swapon /swapfile

Finding substrings

Feature

substring can be thought as a feature, this kind of question is asking for find that feature in a string.

Not order related
https://www.lintcode.com/problem/minimum-window-substring/description
https://www.lintcode.com/submission/17057235/

It asks to find a shorted substring that contains all characters in target string. Here the feature is the counts of characters in target string, since order does not matter.

To solve this kind of problem, you will need two piece of data:
1. the feature, a statistics of characters in target string. it is counting in this problem
counters can be a hashmap or int array if character set is small and known.
2. a number that denotes if all unique characters has been processed. Every time when there is a match on a character's count, increase unique number count. When the total unique character counts are equal, it finds one window.

Algorithm:
1. calculate feature
2.check feature in string.
    2.1. To find feature string in a string, consider to use two pointers, Fix left position the first, run the right pointer to find a substring that covers the feature.
    2.2 when a substring containing the feature was found, change window by advance the left pointer
    2.3 track the shortest substring that has the feature
    2.4 continue 2.1 to find next substring that covers the feature

Some Keywords to use in Resume

achieved acted adapted
addressed adjusted administered
advised altered analyzed
arranged assembled assessed
audited balanced broadened
budgeted built calculated
calibrated catalogued categorized
chaired changed charted
checked classified coached
collated collected combined
communicated compared compiled
completed composed computed
conceived concluded conducted
configured considered consolidated
constructed contracted contrasted
controlled converted coordinated
corrected corresponded counseled
created critiqued cultivated
cut decided decreased
defined delegated delivered
demonstrated described designed
detected determined developed
devised diagnosed differentiated

directed discovered dispensed
displayed dissected distributed
diverted documented doubled
drafted drew edited
eliminated empathized encouraged
enforced enhanced enlarged
ensured established estimated
evaluated examined expanded
expedited explained expressed
extracted facilitated filed
finalized financed fixed
followed forecasted formulated
founded gathered gave
generated guided hired
hosted identified illustrated
implemented improved improvised
incorporated increased informed
initiated inspected installed
instituted instructed integrated
interacted interpreted interviewed
introduced invented investigated
itemized judged launched
learned lectured led
liaised listed located
maintained managed marked
marketed measured mediated
met minimized modeled
moderated modernized modified
monitored motivated narrated
navigated negotiated observed
obtained opened operated
ordered organized oriented
originated oversaw painted
patterned performed persuaded
photographed piloted planned
predicted prepared prescribed
presented printed processed
produced programmed projected
promoted proofread proposed
protected provided publicized
published purchased raised
received recommended reconciled
recorded recruited redesigned
reduced referred refined
rehabilitated related rendered
reorganized repaired reported
represented researched resolved
responded restored restructured
retrieved reviewed revised
revitalized saved scheduled
searched secured selected
separated served serviced
set sewed shaped
shared showed simplified
sized sketched sold
solved sorted specified
spliced split spoke
started streamlined strengthened
studied summarized supervised
supplied talked taught

tended tested traced
trained transcribed transformed
translated traveled treated
trimmed troubleshot tutored
uncovered unified updated
upgraded used utilized
verified weighed welded
widened wired won
wrote

Solution for The Cutting Complexity Challenge

Since the contest is over(seems I have a chance to get an ASML T-Shirt), the solution can be posted now.

Scarily, it takes me time to understand my own code when reviewing it.

https://app.codility.com/cert/view/certC5DTD8-E4TCUGZC2GSJYSWT/
https://app.codility.com/cert/view/certC5DTD8-E4TCUGZC2GSJYSWT/details/

Solution For Codility Cobaltum 2018

IncreasingSequences

Given two sequences of integers, count the minimum number of swaps (A[k], B[k]) needed to make both sequences increasing.

You have two sequences A and B consisting of integers, both of length N, and you would like them to be (strictly) increasing, i.e. for each K (0 ≤ K < N − 1), A[K] < A[K + 1] and B[K] < B[K + 1]. Thus, you need to modify the sequences, but the only manipulation you can perform is to swap an arbitrary element in sequence A with the corresponding element in sequence B. That is, both elements to be exchanged must occupy the same index position within each sequence.

For example, given A = [5, 3, 7, 7, 10] and B = [1, 6, 6, 9, 9], you can swap elements at positions 1 and 3, obtaining A = [5, 6, 7, 9, 10], B = [1, 3, 6, 7, 9].

Your goal is make both sequences increasing, using the smallest number of moves.

Write a function:

class Solution { public int solution(int[] A, int[] B); }

that, given two arrays A, B of length N, containing integers, returns the minimum number of swapping operations required to make the given arrays increasing. If it is impossible to achieve the goal, return −1.

For example, given:

A[0] = 5 B[0] = 1 A[1] = 3 B[1] = 6 A[2] = 7 B[2] = 6 A[3] = 7 B[3] = 9 A[4] = 10 B[4] = 9

your function should return 2, as explained above.

Given:

A[0] = 5 B[0] = 2 A[1] = -3 B[1] = 6 A[2] = 6 B[2] = -5 A[3] = 4 B[3] = 1 A[4] = 8 B[4] = 0

your function should return −1, since you cannot perform operations that would make the sequences become increasing.

Given:

A[0] = 1 B[0] = -2 A[1] = 5 B[1] = 0 A[2] = 6 B[2] = 2

your function should return 0, since the sequences are already increasing.

Assume that:

• N is an integer within the range [2..100,000];
• each element of arrays A, B is an integer within the range [−1,000,000,000..1,000,000,000];
• A and B have equal lengths.

Complexity:

• expected worst-case time complexity is O(N);
• expected worst-case space complexity is O(N) (not counting the storage required for input arguments).

Solution

This is actually same as LeetCode 801. Minimum Swaps To Make Sequences Increasing. Frankly, the medium difficulty challenge is a hard one to me. I treat the ones who did this in half hour genius if they never saw it before.

The only difference this one added is to return -1 if the two lists can not be made increasing.

public class Solution {
    public int minSwapPossibleFailure(int[] A, int[] B) {
        int swapRecord = 1, noswapRecord = 0;
        for (int i = 1; i < A.length; i++) {
            //A[i] and B[i] are out of order and they can not swap            if(A[i]<=A[i-1]&&A[i]<=B[i-1]||B[i]<=B[i-1]&&B[i]<=A[i-1]){
                return -1;
            }
            else if (A[i - 1] >= B[i] || B[i - 1] >= A[i]) {
                // In this case, the ith manipulation should be same as the i-1th manipulation                // fixRecord = fixRecord;                swapRecord++;
            } else if (A[i - 1] >= A[i] || B[i - 1] >= B[i]) {
                // In this case, the ith manipulation should be the opposite of the i-1th manipulation                int temp = swapRecord;
                swapRecord = noswapRecord + 1;
                noswapRecord = temp;
            } else {
                // Either swap or fix is OK. Let's keep the minimum one                int min = Math.min(swapRecord, noswapRecord);
                swapRecord = min + 1;
                noswapRecord = min;
            }
        }
        return Math.min(swapRecord, noswapRecord);
    }
}

Two Codility Golden Awards In A Row

The current one is hard. I will not include link to certificate since the challenge is not completed yet and solution can be viewed from link in the certificate.

The previous one is easier. Challenge and solution can be viewed by link in certificate.
https://app.codility.com/cert/view/certQ65CZN-VDK7QY36D8EJ7R7B/

Delete Healthy Recovery Partition on Windows 10

I wanted to expand a disk partition, but the free space was blocked by a small Healthy recovery partition, which could not be deleted by graphical Disk Management utility. A few search reveals diskpart Windows utility is a rescuer.

This is a link to original post. Below is a reference for my future use.

1. Open a command prompt as administrator.

2. Run Diskpart application by typing diskpart in the command prompt.

3. In the “diskpart” prompt, enter rescan command and press Enter key to re-scan all partitions, volumes and drives available.

4. Then type in list disk and press Enter key to show all hard disk drive available.

5. Select the disk that contains the partition you want to remove. Normally, with just 1 hard disk, it will be disk 0. So the command will be:

Select disk 0

Finish by Enter key.

6. Type list partition and press Enter key to show all available and created partition in the disk selected.

7. Select the partition that wanted to be deleted by using the following command, followed by Enter key:

Select partition x

Where x is the number of the recovery partition to be removed and unlocked its space. Be careful with the number of this partition, as wrong number may get data wipes off.

8. Finally, type in delete partition override and press Enter key.

Shell: Check if symbolic link

This function checks if given path has symbolic link within it.

checkSymbolicLink()
{
    if [ ! -d $1 ]; then
        return 1
    fi
    pushd $1 1>/dev/null
    cdir=$(pwd)
    while [ $cdir != '/' ]
    do
        if [ -h $cdir ]
        then
            return 0
        fi
        cd .. 1>/dev/null
        cdir=$(pwd)
    done
    popd 1>/dev/null
    return 1
}

To get real path, whether the path is real of symbolic, use realpath command.

A Note on .ssh folder

When I made a not wise decision to change /root and its content as fully accessible to other users while still logging in as root user, the other users were refused to log in as root through ssh. They could log in back after I revoked the write permission on /root folder.

Checking the /var/log/secure, it said
xx sshd[xxx]: Authentication refused: bad ownership or modes for directory /root

Based on this, further google search reveals .ssh folder does not like to be writable by group users.

Here is a suggestion to .ssh folder to make sure the access to it is mostly limited to owner itself:

chmod 700 ~/.ssh
chmod 600 ~/.ssh/authorized_keys

Amazon's solutions to What I've being doing

Green grass is what Predix.io has been doing, edge to cloud, digital twin etc.
http://www.allthingsdistributed.com/2017/06/unlocking-value-device-data-aws-greengrass.html

Glue is my work of data management workbench in Bitstew.
http://docs.aws.amazon.com/glue/latest/dg/what-is-glue.html

It's a little scary when I first learned this. They are so similar and Amazon is so influential and I worried they will surpass us. 

At the end of day, I convinced myself that at least what I have been doing is cutting edge technologies and I want to do harder to make it better than Amazon's.

Weird IT Conventions (draft)

Frankly, for many of these so called conventions, I just want to swear. They just got your mind so twisted, so unsure about their meanings and so much more to remember.

Where to start? how about foo? foo... let's forget about it, I will never make up some examples with this name.

1. Parameter names of command line tools.
- usually is short form of it. -- is full form of it.
for example, -a is same as --attributes if a parameter is called attributes.

2. single and double quotes. ' and "

In many circumstances, these two a interchangeable, You can use 'xxx"xxx' to have a double quote in result string, or you can use "xxx'xxx" to have a single quote in your result string.

But in Unix world, single quote means everything within it is as is. Double quote means pretty much same thing, but with exceptions, except $, \ and !, which can have special meaning and allow something such as substitute a variable with its value.

This is a scenario that same symbol has different meanings in several popular coding environment, which gives you hard time by paying special attention to them.

OAuth2 Notes

very hard to understand if you just check it from different web sources: people simply had wrong understanding or assumption on it.

OAuth:
it is not authentication nor authorization, it is about delegation protocol that is scalable.
I delegate access to someone to do something for me.

Client id: client should be registered with oauth server the first. along its id, usually there is a redirect_uri.
redirect_uri: is uased to verify the request is valid, and used to send authentication code back if the app is a web application.

access token: like session. used for secured api calls
refresh token: like a password to get new access token.

by reference token: reference is stored somewhere, it will convert reference to by value token for accessing apis
by value token: token will full information.

bearer token: like cash, when you spend it, no body ask for identification
holder of key token: like credit card. asking for identification. not shared by other users.

id token is for client to build a meaningful session between its client app and server app.
access token is meant for apis.

four roles:

user/me, client/application, authorization server/oauth server, resource server/where api or data is

steps:typical scenario

--client asks authorization erver for accessing resources on resource server,
--authorization server says sure if user agreed. it redirect client to user login page
--user signs in authorizatoin to complete authorization. once the authenticcation is successful, authorization server issues an authentication code to client app via redirect_uri.
--client app uses authentication code, its clilent id, and secrect to ask for an access token.
--client app now uses access token to access resources owned by user/on behalf of user.
--resource server can call authorization server to check if the token is valid. usually it does not need to and it simply check if the signature is trustable.
--resource server then provides resources to client app if token is valid.

it usually works with openid. after user logging in, the authorization server also returns id token that contains information about the user.
client app(server end) uses this id token to build an user session between client app's client and server.

in microservice, let each service understand JWT. and pass around JWT when it needs to call out for other services.

ID token is JWT token, JWT can also be access token.

token can expire, usually a refresh token is given at same time for client app to renew access token.

about exchanging token.
https://www.youtube.com/watch?v=1ZX7554l8hY

token has access scope
access token can be in bearer header, query string or payload, depending on oauth provider.

Client:
confidential client: web server etc
public client: model app, javascript in useragent etc

grant type:
two legged:
client credentials: accessing own resources.
    you provie client id and client secret/password to get access token.
    usually used on server side since it is OK when you can hide the client secret in server side configuration or code.
 
resource owner credentials:
    this is user strongly trust client app, and give out its own user and password to client app.

implicit:usually in javascript code
    https://tools.ietf.org/html/rfc6749#section-4.2
    It is designed for applications that access APIs only while the user is present at the application
 
    client app directs user to auth server to express authentication
    oauth server redirect res owner back to client app along with access token
    client app uses access token to access res user's resources on behalf of user
    it does not have refresh token since the client app is not authenticated.it was driven directly by user himself.
    (authentication code is for server that is proxy of user.)
    since access token is viewiable to user on same computer, it's required to be passed only within secured transport.
 
redirect_uri is defined as part of client login in oauth server, it includes redirect_uri as optional configuration. redirect_uri is
a mean of verification in implicit grant, not a mean of communication. but it is mean of communication in authentication code grant.
 
 
 
three-legged:
    authentication code: accessing other's resources

About Hash

Hash table

This is a key-value look up data structure.

You can think it is an Array coupled with hash function. Hash function takes in key and output an integer as index in array, then it stores the key and value under the index.

Key is required to be stored for the reason of collision hanlding. Key's equals() function is used to determine a key that is in hash collision.

Hashtable is roughly same as HashMap in Java, except it's multi-thread safe and does not allow null key and null value.

Hash Set

In java it is a hash table that stores key itself as its look up value.

Hash Map

This is a hash table, but not thread safe and allow null key and null value.


Collision

solution is collision is linear probing and (separate) chaining, as well as doubling hashing. linear probing can lead to a problem of clustering (major drawback of linear probing) when a lot of collisions happen. chaining is a solution Java is using.

double hashing use a fomular with second hash function involved when first hash function has a collision.

Tried to google Java or XSLT solution to convert XML to tabular data format, butcould not find an easy to understand or to use one. So that I made one myself.

https://github.com/shijiema/JavaXmlTabulator

Java Xml Tabulator

Converting XML to tabular form of data in pure Java implementation. No third party library required.
For am Xml such as

<Relations>
 <Relationship p1="v1">some text
     <id>1</id>
  <Type>OneToMany</Type>other text
  <Weight>1.0</Weight>
  <Score>100.0</Score>
 </Relationship>
 <Relationship>
  <id>2</id>   noise 3
  <Type>ManytoOne</Type>
  <Weight>1.0</Weight>
  <Score>90.0</Score>
 </Relationship>
</Relations>

It will convert it to a flatten version of data that if iterating, looks like this:

[Relations_Relationship, Relations_Relationship_Score, Relations_Relationship_Type, Relations_Relationship_Weight, Relations_Relationship_id, Relations_Relationship_p1]
[some textother text, 100.0, OneToMany, 1.0, 1, v1]
[noise 3, 90.0, ManytoOne, 1.0, 2, null]

It has two ways to access transformed data.
First method is through its iterator() method, which will return each row as List. First row is header and subsequent rows are body content. Headers and body content have been aligned.
Second method is through its getHeaders() and getBody() if partial data access is what is wanted.

Algorithm

Observations:

1. non-repeat elements in XML could be treated as parent node's attributes
2. repeat element in XML usually means multiple rows after being flattened
3. path from root to node makes the columns in tabular format

tablify(){
    with XML tree,
    1. merge non-repeat elements to their parents
        1.1 from leaf to root, merge non-repeat children element to its parent as its parent's attributes. this includes both text and its attributes
            attribute name for child node is child node element name; attribute value for child node element is child node's text value
            attribute name for child node attributes are child node element name + child node attribute name; value is child element attribute value
        1.2 remove these children from their parents
        1.3 repeat 1.1 and 1.2 until no more such children exists
    2. make node production from leaf to root
        2.1 for a node, make its equivalent node production
                2.1.1 leaf node's children node is null
                2.1.2 rows of repeat children element 1 * rows repeat children element 2 * rows repeat children element n
                2.1.3 insert this parent node to head of each produced row from 2.1.1

        2.2 do 2.1 for all parent nodes(null node's parent is the leaf node), but stop at root element
        2.3 do 2.1 for root element(this is because different path has different depth, they have to wait to do final production)
    3. in each row in final node production, convert node to columns
        3.1 node column name = path to node; node value = text content in node
        3.2 node attribute column name = path to node + attribute name; node attribute column value = attribute value
        (this works well for non-repeat node wrapped as parent node's attribute)
    4.return key-value paired node production
}

• Shi Jie Ma - Initial work

Note: Statistics, Data mining, Maching learning and Artifical integgligence

Reading from http://stats.stackexchange.com/questions/5026/what-is-the-difference-between-data-mining-statistics-machine-learning-and-ai

 'unsupervised' (we don't know the answer--discovery) or 'supervised' (we know the answer--prediction

• Statistics quantifies numbers
• Data Mining explains patterns
• Machine Learning predicts with models
• Artificial Intelligence behaves and reasons

Recursion: Davis' Staircase

Recursion, if computation is repeated, memorization can be used to make it linear. Some of them, if asking summary of something, DP can usually be used to solve it.

In this post, I am providing DP solution instead of recursion, which should be easily be written with memorization as an optimization.

Davis has staircases in his house and he likes to climb each staircase , , or steps at a time. Being a very precocious child, he wonders how many ways there are to reach the top of the staircase.
Given the respective heights for each of the staircases in his house, find and print the number of ways he can climb each staircase on a new line.

Input Format

The first line contains a single integer, , denoting the number of staircases in his house.
Each line of the subsequent lines contains a single integer, , denoting the height of staircase .

Constraints

• 
  
• 
  

Subtasks

• for of the maximum score.

Output Format

For each staircase, print the number of ways Davis can climb it in a new line.

Sample Input

3
1
3
7

Sample Output

1
4
44

Explanation

Let's calculate the number of ways of climbing the first two of the Davis' staircases:

1. The first staircase only has step, so there is only one way for him to climb it (i.e., by jumping step). Thus, we print on a new line.
2. The second staircase has steps and he can climb it in any of the four following ways:
   
   1. 
      
   2. 
      
   3. 
      
   4. 
      

Thus, we print on a new line.

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

public class Solution { static void numWays(int n){ //let dp[i] is num ways to reach stair i. //each dp[i] is an accumulation of ways to reach to there int dp[] = new int[n+1]; //assuming you are at nth stair, to reach there //you can step 1 from n-1th stair //or step 2 from n-2th stair or //step 3 from n-3th stair //so you have that many ways to reach to nth stair. //adding them up is the ways to reach to nth stair //dp[3]=dp[2]+dp[1]+dp[0]; /* to reach to stair 1, you have one way:dp[1]=1=dp[0] to reach to stair 2, you have: 1 from dp[0], that is 1 way,2. from dp[1], that's 1 way. to reach to stair 3, you can : 1. dp[0]->dp[3],2.dp[2]->dp[3],3. dp[1]->dp[3] whatever you use to reach dp[2] now contributes to dp[3] */ if(n==1){ System.out.println(1); }else if(n==2){ System.out.println(2); }else{ dp[0]=1;//0 is base dp[1]=1;dp[2]=dp[1]+dp[0]; for(int i=3;i<=n;i++){ dp[i]=dp[i-1]+dp[i-2]+dp[i-3]; } System.out.println(dp[n]); } } public static void main(String[] args) { Scanner in = new Scanner(System.in); int s = in.nextInt(); for(int a0 = 0; a0 < s; a0++){ int n = in.nextInt(); numWays(n); } } }

Coin Change-- number of ways

Given a number of dollars, , and a list of dollar values for  distinct coins, , find and print the number of different ways you can make change for  dollars if each coin is available in an infinite quantity.

Hints:

• You can solve this problem recursively, but you must optimize your solution to eliminate overlapping subproblems using Dynamic Programming if you wish to pass all test cases. More specifically, think of ways to store the checked solutions and use the stored values to avoid repeatedly calculating the same values.
• Think about the degenerate cases: 
  
  • How many ways can you make change for  dollars?
  • How many ways can you make change for less than  dollars if you have no coins?
• If you are having trouble defining the storage for your precomputed values, then think about it in terms of the base case .

Input Format

The first line contain two space-separated integers describing the respective values of  and .
The second line contains  space-separated integers describing the respective values of , where each integer denotes the dollar value of a distinct coin available in an infinite quantity.

Constraints

• The list of coins contains  distinct integers where each integer denotes the dollar value of a coin available in an infinite quantity.

Output Format

Print a single integer denoting the number of ways we can make change for  dollars using an infinite supply of our  types of coins.

Sample Input 0

4 3
1 2 3 

Sample Output 0

4

Explanation 0
For  and  there are four solutions:

Thus, we print  on a new line.

Sample Input 1

10 4
2 5 3 6

Sample Output 1

5

Explanation 1
For  and  there are five solutions:

Thus, we print  on a new line.

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

package dp; import java.util.Scanner; /** * first successful story by analyzing it and coming up an algorithm by myself * --even though I saw this question before, I basically forgot. * Them came up a acceptable solution within 15 minutes. * * Cheers to myself. * @author Andrew Ma * */ public class CoinChangeNumOfWays { public static long makeChange(int[] coins, int money) { //I assumes 0 denom having 0 solutions to any amount of money //also assumes any denom having 0 solution to 0 amount of money //it turns out to be right! to be brave to make assumptions! //making room for 0 denom and 0 amount of money long dp[][] = new long[coins.length+1][money+1]; //initialization the known solutions //0 denom for(int i=0;i<money+1;i++){ dp[0][i]=0;//no solution for each money value } //0 money value for(int i=0;i<coins.length+1;i++){ dp[i][0]=0;//no coin can do 0 change } //then build up values towards to final solution //c and m here are for dp array's dimensions /* * define dp[c][m] as accumulated solutions at c and m * dp[c][m]= * 1. dp[c-1][m]. when money value is less than denom, then get solution from last denom * --here it needs to have a 0 denom * 2. dp[c-1][m]+1. when money value equals denom value, we get one more solution * 3. dp[c-1][m] + dp[c][m-coins[c-1]]. when money valus is greater than denom value, * it adds up accumulation from previous denom and same denom for meney value * not including this denom. * damn, when did I become so able to analyze? I guess drawing it out and practice on paper or white board * really helped to see one's thoughts and then you just need to write the code to reflect the thoughts. * and you are confident that you are able to write code to reflect your thoughts. */ for(int c=1;c<coins.length+1;c++){ for(int m=1;m<money+1;m++){ //when it comes to refer values in coins, c need to be converted back to 0 based if(m<coins[c-1]){ //no change at this, copy the last denom's accumulated solutions dp[c][m] = dp[c-1][m]; } else if(m==coins[c-1]){ //we get one more solution dp[c][m] = dp[c-1][m] +1; } else //if (m>coins[c-1]) { //then it is last denom's accumulated solution + lesser value's accumulated solution dp[c][m] = dp[c-1][m] + dp[c][m-coins[c-1]]; } } } return dp[coins.length][money]; } public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); int m = in.nextInt(); int coins[] = new int[m]; for(int coins_i=0; coins_i < m; coins_i++){ coins[coins_i] = in.nextInt(); } System.out.println(makeChange(coins, n)); } }