Java List Interview Questions

1. Remove Elements from List 

Lets say if I have a list with 6 elements like this
   ["John", "Smith", "John", "Kris", "John", "Bob"]. Remove the elements from the list with the "John"

Easiest solution is to use iterator

e.g.

List<String> alist = new ArrayList<String>(Arrays.asList("John", "Smith", "John", "Kris", "John", "Bob"));
Iterator<String> iter = alist.iterator();
while(iter.hasNext()) {
String name = (String) iter.next();
if (name.equals("John")) iter.remove();
}
System.out.println("alist: " + alist);


Another solution is to use for loop with looping backwards

for (int i=alist.size()-1; i>=0; i--) {
String name = alist.get(i);
if (name.equals("John")) alist.remove(i);
}
System.out.println("alist: " + alist);

2. How to find an element from List with complexity O(1)

Lets say you have Person Class and with the id_, person obj is uniquely identified

class Person {
private int id_;
String name_;
String email_;

 public Person(int id) {
   id_ = id;
 }

public Person(int id, String name, String email) {
id_ = id;
name_ = name;
email_ = email;
}

public boolean equals(Object obj) {
if (obj == null || !(obj instanceof Person)) return false;
Person pobj = (Person) obj;
if (this.id_ == pobj.id_) return true;
else return false;
}

public int hashCode() {
return super.hashCode() + id_;
}

public String toString() {
return ReflectionToStringBuilder.toString(this, ToStringStyle.SHORT_PREFIX_STYLE);
}

}

List<Person> plist = new ArrayList<Person>();
Person p1 = new Person(123, "John Smith", "js@xyz.com");
Person p2 = new Person(124, "Bob Harris", "bh@xyz.com");
Person p3 = new Person(125, "Will Smith", "ws@xyz.com");

plist.add(p1); plist.add(p2); plist.add(p3);


You have reference to the very big person list (lets say plist) and you know the key of one object (lets say 124). How to retrieve the object with the key you have

one Option is to loop through the list and find it

public Person findPerson(List plist, int id) { 
  for (int i=0; i<plist.size(); i++) {
  Person p = plist.get(i);
  if (p.getId() == 124) {
    return p;
  }
}

This has the worst case complexity of O(n). The interviewer asked whether it can be improved with O(1). I said I don't know the answer as list complexity is O(n)

He told me the solution as follows

private Person getPerson(List<Person> plist, int id) {
Person p = new Person(id, "xy", "xy@xyz.com");
int idx = plist.indexOf(p);
return plist.get(idx);

}

but the big problem is list.indexOf(obj) has complexity of O(n). So his solution complexity O(n+1).