Goldman Sachs Interview Question for Software Engineer / Developers






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

1) map: no need to have a hash function, don't need to handle collision, O (log N) insert and lookup, insert key/data in sorted order. If you need to find a max/min element, use map instead of hash table.


hash table: transforms a key into position within a table. O(1) lookup and insert in most cases, doesn't insert hashed key/data in sorted order


2) You need a good hash function (i.e. % prime #) to ensure the hash values are uniformly distributed. If collision occurs, you use separate chaining method (Good for full table), which is a linked list that chains element in the same slot, or use the probing method, which increases the position by some amount until an empty position is found (good for sparse table)

When the # of elements to table size ratio is greater than a threshold, then the hash table needs to be resized. You need to transfer the entries from old table to new table by recomputing their positions using the new hash function


3) Use a map, which also stores key/data pair, but doesn't need to statically allocate a huge hash table with many empty slots

- one2free December 06, 2007 | 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