diff --git a/src/com/android/managedprovisioning/task/DeleteNonRequiredAppsTask.java b/src/com/android/managedprovisioning/task/DeleteNonRequiredAppsTask.java
index 61a52db..8ea477e 100644
--- a/src/com/android/managedprovisioning/task/DeleteNonRequiredAppsTask.java
+++ b/src/com/android/managedprovisioning/task/DeleteNonRequiredAppsTask.java
@@ -20,6 +20,7 @@
 
 import android.content.Context;
 import android.content.pm.IPackageDeleteObserver;
+import android.content.pm.PackageInfo;
 import android.content.pm.PackageManager;
 
 import com.android.internal.annotations.VisibleForTesting;
@@ -28,6 +29,7 @@
 import com.android.managedprovisioning.model.ProvisioningParams;
 import com.android.managedprovisioning.task.nonrequiredapps.NonRequiredAppsLogic;
 
+import java.util.HashSet;
 import java.util.Set;
 import java.util.concurrent.atomic.AtomicInteger;
 
@@ -35,9 +37,9 @@
  * Deletes all non-required apps.
  *
  * This task may be run when a profile (both for managed device and managed profile) is created.
- * In that case the newProfile flag should be true.
+ * In that case the firstTimeCreation flag should be true.
  *
- * It should also be run after a system update with newProfile false. Note that only
+ * It should also be run after a system update with firstTimeCreation false. Note that only
  * newly installed system apps will be deleted.
  */
 public class DeleteNonRequiredAppsTask extends AbstractProvisioningTask {
@@ -72,6 +74,10 @@
     public void run(int userId) {
         Set<String> packagesToDelete = mLogic.getSystemAppsToRemove(userId);
         mLogic.maybeTakeSystemAppsSnapshot(userId);
+
+        // Remove all packages that are not currently installed
+        removeNonInstalledPackages(packagesToDelete, userId);
+
         if (packagesToDelete.isEmpty()) {
             success();
             return;
@@ -86,6 +92,23 @@
         }
     }
 
+    private void removeNonInstalledPackages(Set<String> packages, int userId) {
+        Set<String> toBeRemoved = new HashSet<>();
+        for (String packageName : packages) {
+            try {
+                PackageInfo info = mPm.getPackageInfoAsUser(
+                    packageName, 0 /* default flags */,
+                    userId);
+                if (info == null) {
+                    toBeRemoved.add(packageName);
+                }
+            } catch (PackageManager.NameNotFoundException e) {
+                toBeRemoved.add(packageName);
+            }
+        }
+        packages.removeAll(toBeRemoved);
+    }
+
     @Override
     public int getStatusMsgId() {
         return R.string.progress_delete_non_required_apps;
diff --git a/src/com/android/managedprovisioning/task/nonrequiredapps/NonRequiredAppsLogic.java b/src/com/android/managedprovisioning/task/nonrequiredapps/NonRequiredAppsLogic.java
index 0c39fc7..42668dc 100644
--- a/src/com/android/managedprovisioning/task/nonrequiredapps/NonRequiredAppsLogic.java
+++ b/src/com/android/managedprovisioning/task/nonrequiredapps/NonRequiredAppsLogic.java
@@ -22,7 +22,6 @@
 import android.app.AppGlobals;
 import android.content.Context;
 import android.content.pm.IPackageManager;
-import android.content.pm.PackageInfo;
 import android.content.pm.PackageManager;
 
 import com.android.internal.annotations.VisibleForTesting;
@@ -32,7 +31,6 @@
 import java.lang.annotation.Retention;
 import java.lang.annotation.RetentionPolicy;
 import java.util.Collections;
-import java.util.HashSet;
 import java.util.Set;
 
 /**
@@ -100,7 +98,7 @@
             return Collections.emptySet();
         }
 
-        // Start with all currently installed system apps
+        // Start with all system apps
         Set<String> newSystemApps = mUtils.getCurrentSystemApps(mIPackageManager, userId);
 
         // Remove the ones that were already present in the last snapshot only when OTA
@@ -114,9 +112,6 @@
         // Retain only new system apps
         packagesToDelete.retainAll(newSystemApps);
 
-        // Remove all packages that are not currently installed
-        removeNonInstalledPackages(packagesToDelete, userId);
-
         return packagesToDelete;
     }
 
@@ -126,23 +121,6 @@
         }
     }
 
-    private void removeNonInstalledPackages(Set<String> packages, int userId) {
-        Set<String> toBeRemoved = new HashSet<>();
-        for (String packageName : packages) {
-            try {
-                PackageInfo info = mPackageManager.getPackageInfoAsUser(
-                        packageName, 0 /* default flags */,
-                        userId);
-                if (info == null) {
-                    toBeRemoved.add(packageName);
-                }
-            } catch (PackageManager.NameNotFoundException e) {
-                toBeRemoved.add(packageName);
-            }
-        }
-        packages.removeAll(toBeRemoved);
-    }
-
     private boolean shouldDeleteSystemApps(int userId) {
         @Case int which = getCase(userId);
         return (Case.NEW_PROFILE_REMOVE_APPS == which) || (Case.OTA_REMOVE_APPS == which);
diff --git a/tests/instrumentation/src/com/android/managedprovisioning/task/CreateManagedProfileTaskTest.java b/tests/instrumentation/src/com/android/managedprovisioning/task/CreateManagedProfileTaskTest.java
index a6b48fe..8e33c0c 100644
--- a/tests/instrumentation/src/com/android/managedprovisioning/task/CreateManagedProfileTaskTest.java
+++ b/tests/instrumentation/src/com/android/managedprovisioning/task/CreateManagedProfileTaskTest.java
@@ -17,6 +17,8 @@
 package com.android.managedprovisioning.task;
 
 import static android.app.admin.DevicePolicyManager.ACTION_PROVISION_MANAGED_PROFILE;
+import static org.junit.Assert.assertEquals;
+import static org.mockito.AdditionalMatchers.aryEq;
 import static org.mockito.Matchers.any;
 import static org.mockito.Matchers.anyInt;
 import static org.mockito.Matchers.anyString;
@@ -33,6 +35,10 @@
 import com.android.managedprovisioning.model.ProvisioningParams;
 import com.android.managedprovisioning.task.nonrequiredapps.NonRequiredAppsLogic;
 
+import java.util.Arrays;
+import java.util.HashSet;
+import java.util.LinkedHashSet;
+
 import org.junit.Before;
 import org.junit.Test;
 import org.mockito.Mock;
@@ -47,6 +53,7 @@
             .setDeviceAdminPackageName(TEST_DPC_PACKAGE_NAME)
             .setProvisioningAction(ACTION_PROVISION_MANAGED_PROFILE)
             .build();
+    private static final String[] SYSTEM_APPS_TO_DELETE = {"app.a", "app.b"};
 
     private @Mock UserManager mUserManager;
     private @Mock NonRequiredAppsLogic mLogic;
@@ -59,13 +66,17 @@
         MockitoAnnotations.initMocks(this);
         mTask = new CreateManagedProfileTask(InstrumentationRegistry.getTargetContext(),
                 TEST_PARAMS, mCallback, mUserManager, mLogic);
+        // GIVEN that a set of system apps should not be installed on the new user
+        when(mLogic.getSystemAppsToRemove(TEST_PARENT_USER_ID))
+            .thenReturn(new LinkedHashSet<String>(Arrays.asList(SYSTEM_APPS_TO_DELETE)));
     }
 
     @Test
     public void testSuccess() {
         // GIVEN that a new profile can be created
         when(mUserManager.createProfileForUserEvenWhenDisallowed(
-                        anyString(), anyInt(), eq(TEST_PARENT_USER_ID), any(String[].class)))
+                        anyString(), anyInt(), eq(TEST_PARENT_USER_ID),
+                        aryEq(SYSTEM_APPS_TO_DELETE)))
                 .thenReturn(new UserInfo(TEST_USER_ID, null, 0));
 
         // WHEN the CreateManagedProfileTask is run
@@ -76,13 +87,16 @@
         verifyNoMoreInteractions(mCallback);
         // THEN list of system apps in the new user should be saved
         verify(mLogic).maybeTakeSystemAppsSnapshot(TEST_USER_ID);
+        // THEN the id of the new profile should be returned by getProfileUserId
+        assertEquals(TEST_USER_ID, mTask.getProfileUserId());
     }
 
     @Test
     public void testError() {
         // GIVEN that a new profile can't be created
         when(mUserManager.createProfileForUserEvenWhenDisallowed(
-                        anyString(), anyInt(), eq(TEST_PARENT_USER_ID), any(String[].class)))
+                        anyString(), anyInt(), eq(TEST_PARENT_USER_ID),
+                        aryEq(SYSTEM_APPS_TO_DELETE)))
                 .thenReturn(null);
 
         // WHEN the CreateManagedProfileTask is run
diff --git a/tests/instrumentation/src/com/android/managedprovisioning/task/DeleteNonRequiredAppsTaskTest.java b/tests/instrumentation/src/com/android/managedprovisioning/task/DeleteNonRequiredAppsTaskTest.java
index e4a2b32..6e1b17c 100644
--- a/tests/instrumentation/src/com/android/managedprovisioning/task/DeleteNonRequiredAppsTaskTest.java
+++ b/tests/instrumentation/src/com/android/managedprovisioning/task/DeleteNonRequiredAppsTaskTest.java
@@ -26,6 +26,7 @@
 
 import android.content.Context;
 import android.content.pm.IPackageDeleteObserver;
+import android.content.pm.PackageInfo;
 import android.content.pm.PackageManager;
 import android.os.RemoteException;
 import android.support.test.InstrumentationRegistry;
@@ -81,6 +82,7 @@
     public void testNoAppsToDelete() {
         // GIVEN that no apps should be deleted
         when(mLogic.getSystemAppsToRemove(TEST_USER_ID)).thenReturn(Collections.emptySet());
+        mPackageManager.setInstalledApps(setFromArray("app.a"));
 
         // WHEN running the task
         mTask.run(TEST_USER_ID);
@@ -101,6 +103,8 @@
         // GIVEN that some apps should be deleted
         when(mLogic.getSystemAppsToRemove(TEST_USER_ID))
                 .thenReturn(setFromArray("app.a", "app.b"));
+        // GIVEN that only app a is currently installed
+        mPackageManager.setInstalledApps(setFromArray("app.a", "app.c"));
 
         // WHEN running the task
         mTask.run(TEST_USER_ID);
@@ -113,13 +117,36 @@
         verifyNoMoreInteractions(mCallback);
 
         // THEN those apps should have been deleted
-        assertDeletedApps("app.a", "app.b");
+        assertDeletedApps("app.a");
+    }
+
+    @Test
+    public void testAllAppsAlreadyDeleted() {
+        // GIVEN that some apps should be deleted
+        when(mLogic.getSystemAppsToRemove(TEST_USER_ID))
+            .thenReturn(setFromArray("app.a", "app.b"));
+
+        // WHEN running the task
+        mTask.run(TEST_USER_ID);
+
+        // THEN maybe take snapshot should have been called
+        verify(mLogic).maybeTakeSystemAppsSnapshot(TEST_USER_ID);
+
+        // THEN success should be called
+        verify(mCallback).onSuccess(mTask);
+        verifyNoMoreInteractions(mCallback);
+
+        // THEN those apps should have been deleted
+        assertDeletedApps();
     }
 
     @Test
     public void testDeletionFailed() {
         // GIVEN that one app should be deleted
-        when(mLogic.getSystemAppsToRemove(TEST_USER_ID)).thenReturn(Collections.singleton("app.a"));
+        when(mLogic.getSystemAppsToRemove(TEST_USER_ID))
+            .thenReturn(setFromArray("app.a"));
+        mPackageManager.setInstalledApps(setFromArray("app.a"));
+
         // GIVEN that deletion fails
         mPackageManager.setDeletionSucceeds(false);
 
@@ -145,13 +172,19 @@
         assertEquals(setFromArray(appArray), mDeletedApps);
     }
 
+
     class FakePackageManager extends MockPackageManager {
         private boolean mDeletionSucceeds = true;
+        private Set<String> mInstalledApps = new HashSet<>();
 
         void setDeletionSucceeds(boolean deletionSucceeds) {
             mDeletionSucceeds = deletionSucceeds;
         }
 
+        void setInstalledApps(Set<String> set) {
+            mInstalledApps = set;
+        }
+
         @Override
         public void deletePackageAsUser(String packageName, IPackageDeleteObserver observer,
                 int flags, int userId) {
@@ -167,6 +200,7 @@
             } else {
                 resultCode = PackageManager.DELETE_FAILED_INTERNAL_ERROR;
             }
+            assertTrue(mInstalledApps.remove(packageName));
 
             try {
                 observer.packageDeleted(packageName, resultCode);
@@ -174,5 +208,14 @@
                 fail(e.toString());
             }
         }
+
+        @Override
+        public PackageInfo getPackageInfoAsUser(String pkg, int flag, int userId)
+                throws NameNotFoundException {
+            if (mInstalledApps.contains(pkg) && userId == TEST_USER_ID) {
+                return new PackageInfo();
+            }
+            throw new NameNotFoundException();
+        }
     }
 }
diff --git a/tests/instrumentation/src/com/android/managedprovisioning/task/nonrequiredapps/NonRequiredAppsLogicTest.java b/tests/instrumentation/src/com/android/managedprovisioning/task/nonrequiredapps/NonRequiredAppsLogicTest.java
index 14a0cc3..b0839e3 100644
--- a/tests/instrumentation/src/com/android/managedprovisioning/task/nonrequiredapps/NonRequiredAppsLogicTest.java
+++ b/tests/instrumentation/src/com/android/managedprovisioning/task/nonrequiredapps/NonRequiredAppsLogicTest.java
@@ -20,13 +20,11 @@
 import static org.junit.Assert.assertEquals;
 import static org.junit.Assert.assertTrue;
 import static org.mockito.Matchers.anyInt;
-import static org.mockito.Matchers.eq;
 import static org.mockito.Mockito.never;
 import static org.mockito.Mockito.verify;
 import static org.mockito.Mockito.when;
 
 import android.content.pm.IPackageManager;
-import android.content.pm.PackageInfo;
 import android.content.pm.PackageManager;
 import android.support.test.filters.SmallTest;
 
@@ -51,12 +49,10 @@
     private static final int TEST_USER_ID = 123;
     private static final String[] APPS = {
             "app.a", "app.b", "app.c", "app.d", "app.e", "app.f", "app.g", "app.h",
-            "app.i", "app.j", "app.k", "app.l", "app.m", "app.n", "app.o", "app.p",
     };
-    private static final int[] SNAPSHOT_APPS = {0, 1, 2, 3, 4, 5, 6, 7};
-    private static final int[] SYSTEM_APPS = {0, 1, 2, 3, 8, 9, 10, 11};
-    private static final int[] INSTALLED_APPS = {0, 1, 4, 5, 8, 9, 12, 13};
-    private static final int[] BLACKLIST_APPS = {0, 2, 4, 6, 8, 10, 12, 14};
+    private static final int[] SNAPSHOT_APPS = {0, 1, 2, 3};
+    private static final int[] SYSTEM_APPS = {0, 1, 4, 5};
+    private static final int[] BLACKLIST_APPS = {0, 2, 4, 6};
 
     @Mock private PackageManager mPackageManager;
     @Mock private IPackageManager mIPackageManager;
@@ -88,14 +84,15 @@
         initializeApps();
 
         // THEN getSystemAppsToRemove should return a non-empty list with the only app to removed
-        // being the one that is installed, a current system app, non required
-        assertEquals(getSetFromArray(new int[] { 0, 8 }),
+        // being the one that is a current system app and non required
+        assertEquals(getSetFromArray(new int[] { 0, 4 }),
                 logic.getSystemAppsToRemove(TEST_USER_ID));
     }
 
     @Test
     public void testGetSystemAppsToRemove_OtaLeave() throws Exception {
-        // GIVEN that an OTA occurs and that system apps should not be deleted
+        // GIVEN that an OTA occurs and that system apps should not be deleted (indicated by the
+        // fact that no snapshot currently exists)
         final NonRequiredAppsLogic logic = createLogic(false, false);
         // GIVEN that a combination of apps is present
         initializeApps();
@@ -108,15 +105,16 @@
 
     @Test
     public void testGetSystemAppsToRemove_OtaDelete() throws Exception {
-        // GIVEN that an OTA occurs and that system apps should be deleted
+        // GIVEN that an OTA occurs and that system apps should be deleted (indicated by the fact
+        // that a snapshot currently exists)
         final NonRequiredAppsLogic logic = createLogic(false, false);
         // GIVEN that a combination of apps is present
         initializeApps();
 
         // THEN getSystemAppsToRemove should return a non-empty list with the only app to removed
-        // being the one that is installed, a current system app, non required and not in the last
+        // being the one that is a current system app, non required and not in the last
         // snapshot.
-        assertEquals(Collections.singleton(APPS[8]), logic.getSystemAppsToRemove(TEST_USER_ID));
+        assertEquals(Collections.singleton(APPS[4]), logic.getSystemAppsToRemove(TEST_USER_ID));
     }
 
     @Test
@@ -145,9 +143,9 @@
 
     @Test
     public void testMaybeTakeSnapshot_OtaLeave() {
-        // GIVEN that an OTA occurs and that system apps should not be deleted
+        // GIVEN that an OTA occurs and that system apps should not be deleted (indicated by the
+        // fact that no snapshot currently exists)
         final NonRequiredAppsLogic logic = createLogic(false, false);
-        // GIVEN that no snapshot currently exists
         when(mSnapshot.hasSnapshot(TEST_USER_ID)).thenReturn(false);
 
         // WHEN calling maybeTakeSystemAppsSnapshot
@@ -159,9 +157,9 @@
 
     @Test
     public void testMaybeTakeSnapshot_OtaDelete() {
-        // GIVEN that an OTA occurs and that system apps should be deleted
+        // GIVEN that an OTA occurs and that system apps should be deleted (indicated by the fact
+        // that a snapshot currently exists)
         final NonRequiredAppsLogic logic = createLogic(false, false);
-        // GIVEN that a snapshot currently exists
         when(mSnapshot.hasSnapshot(TEST_USER_ID)).thenReturn(true);
 
         // WHEN calling maybeTakeSystemAppsSnapshot
@@ -175,7 +173,6 @@
         setCurrentSystemApps(getSetFromArray(SYSTEM_APPS));
         setLastSnapshot(getSetFromArray(SNAPSHOT_APPS));
         setNonRequiredApps(getSetFromArray(BLACKLIST_APPS));
-        setInstalledApps(getSetFromArray(INSTALLED_APPS));
     }
 
     private void setCurrentSystemApps(Set<String> set) {
@@ -191,13 +188,6 @@
         when(mProvider.getNonRequiredApps(TEST_USER_ID)).thenReturn(set);
     }
 
-    private void setInstalledApps(Set<String> set) throws Exception {
-        for (String pkg : set) {
-            when(mPackageManager.getPackageInfoAsUser(eq(pkg), anyInt(), eq(TEST_USER_ID)))
-                    .thenReturn(new PackageInfo());
-        }
-    }
-
     private Set<String> getSetFromArray(int[] ids) {
         Set<String> set = new HashSet<>(ids.length);
         for (int id : ids) {