Amazon Interview Question
Developer Program EngineersCountry: India
Interview Type: In-Person
I think we can we have hash within another hash. We can declare something like this
Hash<Integer,Hash<Integer,String>> studentCourse=new Hash<Integer,Hash<Integer,String>>();
Here 1st Integer represents Student ID and second Integer represent Course ID.
We can also represent this as a matrix of bits.
Example:
Students (S1, S2, S3),
Courses (C1, C2, C3, C4)
S1's Courses: C1, C2
S2's Courses: C2, C3
S3's Courses: C4, C1
Matrix can be (Students x Courses):
1 1 0 0
0 1 1 0
1 0 0 1
In this all operations asked in the question are : O(n). Strictly speaking, O(Courses) for course list (full or a student's) and O(Students) for Students list.
i'm thinking about a data structure more like a b-tree not exactly though.
since the relation is not commutative(every student has to be enrolled to some course,but every course need not have a student enrolled to it),
the root will branch into two nodes.
whatever key we enter,the root of the left subtree will contain all the student IDs as its keys and the root of the right subtree will contain all the course IDs as its keys.
whichever is first matched with the key we are passing,
indicates the node v have to enter to get the required info.
EX: the root contains all the IDs.
the root of the left subtree contains all the student IDs and the root of the right subtree contains all the course IDs.
suppose u want to all the courses enrolled to,by a student.
just search for the student ID.
the keys in left subtree are checked first and because there is a match,the values for the key (in this case,course IDs) are returned.
Let me know if this works.its just conceptual since its mentioned v can have our own data structures.
We have to have the relationship stored in some place. Since in the question its mentioned as graph, one can visualize the structure as bipartite graph, left nodes are students, right nodes are courses and edges are relations. For implementation, Student object will have an array of pointers to course and Course object will have an array of pointers to Students.
1) Any number divisible by 6 or 9 -> should be divisible by 3
i.e. if a number is divisible by 3 and is greater then 6 -> then blindly it's possible.
For example -> 6,9,12(6+6),15(9+6),18(9+9),21(6+6+9) etc ...
2)17 is a prime number , so we can devide the number by 17 , get the reminder , check if greater then equal to 6 and divisible by 3 .. :)
so code can be like
Check(int number)
{
if(number >= 6 && number mod 3 == 0) return true;
int reminder = number mod 17 ;
if(reminder >=6 && reminder mod 3 ==0) return true;
return false;
}
Moral -> Think logically :)
Tushar Gupta
i think multimap should be used for mapping student to courses and courses to student.a)O(no. of students) b)O(no. of courses) c)O(1) d)O(1)
- abhra October 26, 2011