How to increase chance of you getting hired if you are not a native to that country?

If it's any consolation you are far from alone in this situation and chances are good that it is nothing to do with you personally or your skills.

I can't speak for Canada or Japan but from a European perspective the legislative barriers to hiring a non-EU citizen can be quite high for companies so it often isn't as simple as whether the company wants to hire you or not.

In order to hire a non-EU citizen (or more specifically one with out an existing work permit/right to work via family/marriage or whatever) a company has to "sponsor" the candidate for the visa process.

This is perhaps best described as a bureaucratic nightmare - it takes a significant amount of time (typically this can be ~ 2 months, allegedly it can be as low as three weeks but I've never seen it happen) and effort to apply to sponsor and the outcome is by no means guaranteed.

Depending on the country (it varies between different bits of Europe) this process can involve:

• Providing travel dates and proof of paid travel
• Providing proof of health insurance
• Proof of ID documents (typically a passport)
• Proof of sustainable long-term accommodation

If the application is denied then tough luck, the company doesn't get to employ you and has wasted both the time and money they invested in doing it - cost varies depending on country and length of stay but in the UK it starts at £1000 for stays of less than 12 months and rises to £5000 if it's for the maximum five years, you don't get the job and everyone has to start all over again.

And the chances of the application getting denied are insanely high - the company has to demonstrate that they have been unable to satisfactorily fill the position with an EU citizen, and that means ALL of Europe, not just their own country or that the specific candidate is truly exceptional and posseses qualities that would be difficult to find "locally" - and even then some countries heavily restrict which types of job and what industries can be considered.

The odds are slightly better if your occupation is on the country's "shortage list" (each EU/EEA country maintains it's own) and the cost is reduced too but the conditions for being approved remain the same. Note that being on the "shortage list" is not the same thing as there merely being high demand for those workers, supply has to be low too and typically to make it on the list the occupation (and sometimes the occupation as applied to a specific industry) has to also be considered "economically crucial". So looking on the countries jobs boards and seeing x hundred vacancies for Android developers is largely meaningless by itself.

So all things considered it shouldn't be a surprise that many EU companies don't even entertain the notion (all of this applies to typical "skilled" permanent jobs - temporary, seasonal, and certain niche occupations such as entertainment, sports, etc. are considered differently but none of that is relevant to you OP so I won't bore you with it)

From my own experiences (on the company side in the UK, not as a candidate) the company had been struggling to fill a fairly specialized position for several months (there were less than half a dozen companies in the country that did this particular type of work) and eventually reached the point where we had two viable candidates. By far the preferred candidate was a Chinese national and the hiring manager and in fact everyone in management was keen to hire them so HR made inquiries about sponsoring them for a work permit and were advised that even with the difficulty we had finding suitable candidates, the specialized nature of the job, and the the stand-out nature of the candidate that our chances of getting it approved were effectively zero.

More specifically for your case I note from your post that you are an Android developer, this isn't on the UK's shortage list (and hasn't been at any point in the last 7 years) so for now at least the UK is probably a complete non-starter for you, although post-Brexit who can say but I wouldn't hold out much hope there.

EDIT: I may as well add in the Canadian knowledge I do have in case it's useful

Canada:

Without knowing your exact circumstances I can't say for sure but you may be eligible for what they call an "Employer Specific Work Permit", similar to the EU work permits these require you to work for a specific company who have agreed to sponsor you.

Again this is another adventure in red tape! (although not as horrible as the EU one)

Before a Canadian company can hire a foreign worker they first have to complete a "Labour Market Impact Assessment" (basically showing that what they are doing doesn't hurt Canadian employment prospects) and have that approved, if successful this is then valid for a maximum of 6 months - if they don't hire a foreign worker to start in this time it's back to square one.

Once they have made an offer to the foreign candidate the candidate then needs to apply for the Work Permit, the exact criteria for acceptance vary but in general terms you have to:

• prove you will leave Canada when your work permit expires (they can be extended but you have to prove you will leave if they don't)
• show that you have enough money to take care of yourself and any family members/dependents during your stay in Canada (and to return home once it expires)
• obey the law and have no record of criminal activity (they may require a certification of this from your home country's polce)
• not be a danger to Canada’s security
• be in good health (may require you to have a medical exam)
• not plan to work for an employer listed with the status “ineligible” (if the employer has breached conditions for employing foreign workers in the past they may be banned from doing so for a period of time)
• not plan to work for an employer who offers..erm..(there's no nice way of putting this..)adultservices
• provide any other documents they ask for to prove you can enter the country (this can be almost anything - it's the catch all clause)

Although you can't apply for the work permit before you have the offer with an employer with an LMIA it would probably help your case when applying to Canadian employers if you were able to provide them with some evidence to suggest that you would meet these criteria (as then they know that it's not just going to be kicked straight out if they decide to make an offer) but there's still no guarantee and remember that you're still asking them to take on and administrative and compliance burden that they wouldn't face with a local candidate so you need to be persuasive that you are worth the effort.