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


  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();
      Employee e2 = employee.clone();
      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) {
            if(employees.get(i).getSalary() > salary) {
                i = 0;
                isEligibleForHike = true;
        } else {
    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)

  • $\begingroup$ I don't think it's possible. I bet the interviewer has some solution in their head but it's is wrong $\endgroup$
    – user253751
    Sep 29, 2022 at 22:01
  • 2
    $\begingroup$ (Double salary sounds agreeable.) $\endgroup$
    – greybeard
    Sep 30, 2022 at 5:19
  • $\begingroup$ Language-specific questions are a poor fit for this forum. The next best thing would perhaps be stackoverflow.com . PS To "solve" this I'd consider suspending every Employee object's determineHikability method until we know whether to hike or not, that is, we've found one whose salary is below x or we've reached the end of the list. Various synchronisation mechanisms could be used to achieve that. $\endgroup$
    – Kai
    Sep 30, 2022 at 5:22
  • $\begingroup$ (checkEligibility() is named misleadingly for modifying elements. The second proposal uses one flag more than necessary.) $\endgroup$
    – greybeard
    Sep 30, 2022 at 5:24
  • $\begingroup$ Are you even allowed to modify the Employee class? If so, the way I see for this to be accomplished in single-pass is to use a mutable object (Boolean objects are immutable) shared by all employee that will represent the eligibility of everyone for increase. Set this object's value to true and continue, while an employee is eligible, else once an ineligible employee is found, set the object to false and stop. $\endgroup$
    – Russel
    Sep 30, 2022 at 8:58

1 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;
     return result;

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.