## Morgan Stanley Interview Question for Java Developers

Country: India
Interview Type: Phone Interview

Comment hidden because of low score. Click to expand.
5
of 5 vote

I would just explain another approach that came in my mind, I haven't yet thought about the details of implementation.
1. 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.)

Comment hidden because of low score. Click to expand.
1
of 1 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0

Well, I suggested map based approach but was rejected in the first place, just as you mentioned, because of huge memory usage.

Comment hidden because of low score. Click to expand.
0
of 0 vote

HashMap<Course, HashSet<Student>> keyCourseValueStudents;
HashMap<Student, HashSet<Course>> keyStudentValueCourses;

Comment hidden because of low score. Click to expand.
0
of 0 vote

HashMap<Course, BST<Student>>

Get students registered for course - O(1)
Get courses registered by student - O(mlogn)

where m is the number of courses and n the number of students. We are using a hashmap of course to student as am assuming m < n (probably m << n), so mlogn < nlogm

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

we can use google's multimap which can associate a single key with multiple values using linked list unlike java's Map interface which replaces the value with the new value.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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>();

public void addTwowayEdge(Vertex source,Vertex dest){
}

private void addEdge(Vertex source,Vertex dest){
adjecencyList = new HashMap<Vertex,HashSet<Vertex>>();

}
HashSet<Vertex> set = new HashSet<Vertex>();
}else{
}
}

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);

System.out.println(graph.toString());
}

}
\\\

Comment hidden because of low score. Click to expand.
0
of 0 vote

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>();

public void addTwowayEdge(Vertex source,Vertex dest){
}

private void addEdge(Vertex source,Vertex dest){
adjecencyList = new HashMap<Vertex,HashSet<Vertex>>();

}
HashSet<Vertex> set = new HashSet<Vertex>();
}else{
}
}

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);

System.out.println(graph.toString());
}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````class student
{
string id;
ArrayList courses;
}

class Course
{
string id;
ArrayList students;
}

class En-roller
{
public void enroll(Student s, course c)
{
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

class Student
{
int id;
ArrayList<Course> courses ;
}

class Course
{
int id;
ArrayList<Student> students;
}

public void enroll(Student s, Course c)
{
}

this is many to many relation right

Comment hidden because of low score. Click to expand.
0
of 0 vote

this is a classic many to many relationship question, which can be resolved by introducing a weak entity like Year/Batch between Student and Course

Comment hidden because of low score. Click to expand.
0
of 0 vote

this can be achieve by using join class.
class student{}
class course{}

class join_std_couse{
List<student> students;
List<course> courses;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Need 2 LinkedHashMap -
i) StudentId --> List of CourseId
ii) CourseId --> List of StudentId

Comment hidden because of low score. Click to expand.
0
of 0 vote

Use 2D matrix, Row as the studentId and column as the course id.
This way its very easy to find the courses a student is enrolled and students which are enrolled in a subject.

Comment hidden because of low score. Click to expand.
0
of 0 vote

a 2D array with courses and student mapping

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.