Android testing - Problems caused by state persisting across application instances

When running android connected device tests, state that persists across application instances, such as permissions and files stored by the application, cause tests to interfere with each other.

For example, if I want to write a test for application behaviour when I deny runtime permissions and another test for application behaviour when I allow runtime permissions, then I must be very careful that the tests run in the correct order. If the allow test ran before the deny test, then the deny test would fail, because the permissions settings would already have been granted.

Another example, in a shopping app, the application may store the contents of the basket in the apps internal file storage to allow the basket to survive application termination and reboots. Testing the behaviour of the shopping basket then becomes very difficult, as the tests interfere with each other.

What is the solution to this problem?