Morgan Stanley Interview Question
Java DevelopersCountry: India
Interview Type: Phone Interview
I have a suggested Data Structure. Please confirm if it works.
Use of Disjoint Sets. Courses and Students are maintained as separate sets. Relation between the two is defined as a directed edge between the two.
For eg if student S enrolls for a course C then there is a directed edge (S,C) in E(G).
Find operations from both sides will be in O(1) time as all nodes are directly connected. However worst time would be O(n) if a student is enrolled to all the courses.
You could use two HashMaps, one for StudentName -> Course List Lookup and one for Course Name -> Student List Lookup. Searching will be in O(1) for both cases.
Drawbacks: You use a lot of memory and you need to do bookkeeping if the courses of a student change (you have to update the entry in the Course Name Map). But this was not the question and searching cannot be better than O(1) I guess.
Yes, I also had similar question in interview and instead of course and student, I has name and TicketID combination. I also thought about 2 HashMaps and HashSet approach. But it was not appreciated as I have to load data entire data twice. I am just wondering what else could be another data structure that would be efficient for both type of queries.
A Graph with typed vertex could be an approach to consider -
///
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Map;
import java.util.Objects;
import java.util.Set;
import com.dey.ds.graph.course.Vertex1.Type;
public class CourseStudentGraph<Vertex>{
private Set<Vertex> students = new HashSet<Vertex>();
private Set<Vertex> courses = new HashSet<Vertex>();
private Map<Vertex,HashSet<Vertex>> adjecencyList;
public void addTwowayEdge(Vertex source,Vertex dest){
this.addEdge(source, dest);
this.addEdge(dest, source);
}
private void addEdge(Vertex source,Vertex dest){
Objects.requireNonNull(source,"Valid Student Please");
Objects.requireNonNull(dest,"Valid course Please");
if(null == adjecencyList){
adjecencyList = new HashMap<Vertex,HashSet<Vertex>>();
}
if(this.adjecencyList.get(source)==null){
HashSet<Vertex> set = new HashSet<Vertex>();
set.add(dest);
this.adjecencyList.put(source, set);
}else{
this.adjecencyList.get(source).add(dest);
}
students.add(source);
courses.add(dest);
}
public String toString(){
StringBuilder str = new StringBuilder();
Set<Vertex> keySet = this.adjecencyList.keySet();
Iterator<Vertex> itr = keySet.iterator();
while(itr.hasNext()){
Vertex source = itr.next();
HashSet<Vertex> neighbours = this.adjecencyList.get(source);
str.append(source).append("-->").append(neighbours).append("\n");
}
return str.toString();
}
public static final class Vertex<E extends Comparable<E>> implements Comparable<Vertex<E>> {
private final E data;
private final Type type;
enum Type{
Course{
public String toString(){
return "COURSE";
}
},
Student{
public String toString(){
return "STUDENT";
}
}
}
public Vertex(E e,Type type){
this.data = e;
this.type = type;
}
@Override
public int compareTo(Vertex<E> that) {
return this.data.compareTo(that.data);
}
@Override
public boolean equals(Object that){
if(that == null) throw new IllegalArgumentException("invalid object");
if(this.getClass() != that.getClass()) return false;
Vertex<?> v = (Vertex<?>)that;
if(v.data != this.data) return false;
return true;
}
@Override
public int hashCode(){
return this.hashCode();
}
@Override
public String toString(){
return this.data.toString()+"::"+this.type.toString();
}
}
public static void main(String...a){
CourseStudentGraph graph = new CourseStudentGraph();
Vertex<String> studentA = new Vertex<String>("A",Vertex.Type.Student);
Vertex<String> studentB = new Vertex<String>("B",Vertex.Type.Student);
Vertex<String> course1 = new Vertex<String>("Maths",Vertex.Type.Course);
Vertex<String> course2 = new Vertex<String>("DS and Algo",Vertex.Type.Course);
Vertex<String> course3 = new Vertex<String>("Physics",Vertex.Type.Course);
graph.addTwowayEdge(studentA, course1);
graph.addTwowayEdge(studentA, course2);
graph.addTwowayEdge(studentB, course1);
graph.addTwowayEdge(studentB, course2);
graph.addTwowayEdge(studentB, course3);
System.out.println(graph.toString());
}
}
\\\
A Graph with typed vertices could be an approach to consider
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Map;
import java.util.Objects;
import java.util.Set;
import com.dey.ds.graph.course.Vertex1.Type;
public class CourseStudentGraph<Vertex>{
private Set<Vertex> students = new HashSet<Vertex>();
private Set<Vertex> courses = new HashSet<Vertex>();
private Map<Vertex,HashSet<Vertex>> adjecencyList;
public void addTwowayEdge(Vertex source,Vertex dest){
this.addEdge(source, dest);
this.addEdge(dest, source);
}
private void addEdge(Vertex source,Vertex dest){
Objects.requireNonNull(source,"Valid Student Please");
Objects.requireNonNull(dest,"Valid course Please");
if(null == adjecencyList){
adjecencyList = new HashMap<Vertex,HashSet<Vertex>>();
}
if(this.adjecencyList.get(source)==null){
HashSet<Vertex> set = new HashSet<Vertex>();
set.add(dest);
this.adjecencyList.put(source, set);
}else{
this.adjecencyList.get(source).add(dest);
}
students.add(source);
courses.add(dest);
}
public String toString(){
StringBuilder str = new StringBuilder();
Set<Vertex> keySet = this.adjecencyList.keySet();
Iterator<Vertex> itr = keySet.iterator();
while(itr.hasNext()){
Vertex source = itr.next();
HashSet<Vertex> neighbours = this.adjecencyList.get(source);
str.append(source).append("-->").append(neighbours).append("\n");
}
return str.toString();
}
public static final class Vertex<E extends Comparable<E>> implements Comparable<Vertex<E>> {
private final E data;
private final Type type;
enum Type{
Course{
public String toString(){
return "COURSE";
}
},
Student{
public String toString(){
return "STUDENT";
}
}
}
public Vertex(E e,Type type){
this.data = e;
this.type = type;
}
@Override
public int compareTo(Vertex<E> that) {
return this.data.compareTo(that.data);
}
@Override
public boolean equals(Object that){
if(that == null) throw new IllegalArgumentException("invalid object");
if(this.getClass() != that.getClass()) return false;
Vertex<?> v = (Vertex<?>)that;
if(v.data != this.data) return false;
return true;
}
@Override
public int hashCode(){
return this.hashCode();
}
@Override
public String toString(){
return this.data.toString()+"::"+this.type.toString();
}
}
public static void main(String...a){
CourseStudentGraph graph = new CourseStudentGraph();
Vertex<String> studentA = new Vertex<String>("A",Vertex.Type.Student);
Vertex<String> studentB = new Vertex<String>("B",Vertex.Type.Student);
Vertex<String> course1 = new Vertex<String>("Maths",Vertex.Type.Course);
Vertex<String> course2 = new Vertex<String>("DS and Algo",Vertex.Type.Course);
Vertex<String> course3 = new Vertex<String>("Physics",Vertex.Type.Course);
graph.addTwowayEdge(studentA, course1);
graph.addTwowayEdge(studentA, course2);
graph.addTwowayEdge(studentB, course1);
graph.addTwowayEdge(studentB, course2);
graph.addTwowayEdge(studentB, course3);
System.out.println(graph.toString());
}
}
Well what you could do is create your own collection similar to HashMap. As HashMap is HashTable, I suggest you create a 2 dimensional table to store these buckets. While inserting, you would insert a Course and Student combination, so get Hash of both and store that Entry at that location. e.g. for a given Student and Course combination if Hash of Student object comes out to be 5 and for Course it comes out to be 8, store that Entry at [5][8] location. Yes we would need a bit more enhanced logic similar to HashMap to handle has collisions.
Now if someone wan't all Courses for a given student, you will pick the whole array at [5][] location. Complexity assuming there is zero hash collisions would be O(1) in both put and get.Yes there would be little overhead to convert that array to a collection by skipping nulls, but essentially you fetched that list immediately.
I would just explain another approach that came in my mind, I haven't yet thought about the details of implementation.
- AP May 03, 20151. But there can be the matrix representation to solve this problem. Where there will be one row corresponding to one entity (1 column for every name or every student) and one column for every ticketId or course.
2. Then set the corresponding bit to 1 if student have taken course (or ticket logged by name.)
3. Accessing the matrix row wise will give all tickets logged by name (or all courses taken by student)
4. Accessing the matrix column wise will give all all names who have logged by a ticket (or all students who have taken a course).
Time Complexity would be O(mn) when there are m distinct (students/names) and n distinct. (courses/tickets)
---------------------------------------------------------------------------------------------------------------
We can read data only once, create structure/class to store all attributes. Then traverse that list once to get distinct (students/names) and distinct (courses/tickets).
The tricky part could be finding out all unique (students/names) and all different (courses/tickets). Because, if we declare hash set for storing unique students and unique courses, that will be O(m+n) extra memory.
Still memory assignment will have the upper bound O(m * n) (memory required to store matrix. We can use boolen matrix to reduce memory requirement.)