Update a property of all objects in a List/Collection/Array when at least one object satisfies a criteria using a single loop

Question

Here is the puzzle I was asked in an interview

There's a List of Employee objects. Update all the objects in the list to be eligibleForHike if at least one employee exists whose salary is less than x; otherwise update all of them in-eligibleForHike in a single iteration/loop

Requirements/Restrictions:

1. Streams should not be used
2. Only one pass/iteration/loop
3. Not allowed to used two loops (even though not nested and even though the time complexity would still be O(n)). Not sure why, but may be because it's a puzzle

Employee class

public class Employee {
   private String name;
   private Double salary;
   private Boolean eligibleForHike;
   //all getters and setters defined
}

My solution (not elegant) because of space complexity

public List<Employee> checkEligibility(List<Employee> employees, Double salary) {
   List<Employee> eligible = new ArrayList<>();
   List<Employee> inEligible = new ArrayList<>();
   boolean isEligibleForHike = false;
   employees.forEach(employee -> {
      Employee e1 = employee.clone();
      e1.setEligibleForHike(true);
      Employee e2 = employee.clone();
      e2.setEligibleForHike(false);
      eligible.add(e1);
      inEligible.add(e2);
      if(!isEligibleForHike && employee.getSalary() < salary) {
         isEligibleForHike = true;
      }
   });
   return isEligibleForHike ? eligible : inEligible;
}

Another solution I proposed is

public List<Employee> checkEligibility(List<Employee> employees, Double salary) {
    int i = 0;
    boolean isEligibleForHike = false;
    for(i = 0; i < employees.size(); i++) {
        if(!isEligibleForHike) {
            employees.get(i).setEligibleForHike(false);
            if(employees.get(i).getSalary() > salary) {
                i = 0;
                isEligibleForHike = true;
                employees.get(i).setEligibleForHike(true);
            }
        } else {
            employees.get(i).setEligibleForHike(true);
        }
    }
    return employees;
}

The interviewer was not satisfied with this solution either because I am resetting the index to 0, said the time is not O(n). I explained in determining the complexity, k (constant) doesn't matter. In worst case, it would be O(2*n) where 2 is k/constant, and the complexity still remains O(n)

But their explanation was if 500K records take 2 sec to process in O(n) case, in worst case, it would be 4 sec (i.e twice the original time taken)

Posting here to find a better solution to this problem, where the same List of objects can be updated in place and still use only one loop and order still O(n) not a factor of k (constant)

Answer 1

Solution: Have a reference which dictates the hikeEligibility which can be false by default. Iterate and assign the same reference to all the objects in the collection. If at least one item in the collection meets the criteria, set the value of hikeEligibility to true

 public List<Employee> checkAndUpdateHikeEligibility(List<Employee> employees, Double salary) {
     List<Employee> result = new ArrayList<>();
     Boolean isEligibleForHike = false;
     for(int i = 0; i < employees.size(); i++) {
         Employee e = employees.get(i);
         if(e.getSalary() < salary) {
             isEligibleForHike = true;
         }
         e.setEligibleForHike(isEligibleForHike);
         result.add(e);
     }
     return result;
 }