CareerCup

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

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.

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

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

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.

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.

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

class student
{
  string id;
  ArrayList courses;
}

class Course
{
  string id;
  ArrayList students;
}

class En-roller
{
	public void enroll(Student s, course c)
	{
		s.courses.add(c);
		c.students.add(s);
	}
}

how about this solution for problem 10:05 PM
class Student
{
int id;
ArrayList<Course> courses ;
}

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

public void enroll(Student s, Course c)
{
s.courses.add(c);
c.students.add(s);
}

this is many to many relation right

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

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

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

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.

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

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.

a 2D array with courses and student mapping