Morgan Stanley Interview Question for Java Developers


Country: India
Interview Type: Phone Interview




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

Theoretically O(1) if no collisons are there. Worst case O(N) if you override hashcode to return the same value for all objects.

- Abhi January 28, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
3
of 3 vote

Same as the C /C+ it is data structure and it does not change with language.

Storage = O(1) // until no Collision
Retrival= O(1)..

- hprem991 January 28, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

@hprem:

How the storage is O(1) ... I think it would be O(n) because you are mapping a data with some key values. Tell me if i am wrong..

- techieDeep January 28, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@techDeep It is constant time i.e. O(1). Basically for looking into the key value pair, HashMap uses hashing which gives the precise address location of the 'bucket' which contains the Key.
For example, hashFunction(key)= Memory Location, which you can see is not dependent on n.
PS : it is not as simple as it appears in the example, its just for the sake of simplicity, but the process is essentialy O(1).

- Saurabh January 28, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@hprem:

Yes i understand but for size of m bucket you need some memory to store location of there buckets . Am i right?

- techieDeep January 28, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@techieDeep: they mean to say that storing one element takes O(1) time.

Of course storing all the elements will take O(n) space.

- Anonymous January 28, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@hprem
In c++, for find() in map, its log(n)

- Santhosh January 07, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

When there is a hash collision, then the maximum no of elements that can fit into the bucket /. bin is logn/loglogn. So, worst case cannot be O(n), it has to be O(logn/loglogn)

- Anonymous February 19, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Yes Abhi you are right. worrest case is O(N).

- Anonymous February 16, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

All operations on Hashtable or Hashmap are O(1) assuming the uniform distribution of the key in the table and avoiding the collision of the key. Avoiding collision and uniform distribution is all depends how hash function is well implemented which is very critical implementation. But the aim of this data structure is providing operations at O(1).
So if the hash function is really bad than the worst case will be O(N).

- MrA May 13, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

HashMap class in java use basically two data structure :
1. Array
2. Link-List.

Therefore on basis of hashing algorithms, if there is no collision happened in hash codes for any data, in that case data will go directly in array, that is why complexity will be O(1).

if collision happens in hash codes then data goes to Link-List , that's mean complexity will be O(n);

- Manoj Sharma October 01, 2013 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More