Question 1

How would you find the second highest salary from an Employee table?

Accepted Answer

Question 2

Explain the difference between HashMap and TreeMap in Java.

Accepted Answer

HashMap : backed by a hash table. O(1) average for get/put. No guaranteed order. Allows one null key. TreeMap : backed by a Red Black tree. O(log n) for get/put. Keys are sorted in natural order (or by Comparator). No null keys. Use HashMap when order doesn't matter and you need fastest access. Use TreeMap when you need sorted keys or range queries (e.g., subMap , headMap , tailMap ). In data engineering, TreeMap is useful for ordered event processing or maintaining sorted sliding windows.

Question 3

What is the time complexity of a binary search algorithm?

Accepted Answer

O(log n) time, O(1) space (iterative). Binary search halves the search space at each step — on a sorted array of n elements it takes at most log₂(n) comparisons. Pre condition: array must be sorted . Used in database index lookups (B tree search is O(log n)).

Question 4

How would you implement a shortest path algorithm in a graph?

Accepted Answer

Dijkstra's algorithm for weighted graphs with non negative edges — O((V + E) log V): BFS for unweighted graphs (O(V + E)). Bellman Ford when negative weights exist.

Question 5

What is denormalization, and when would you use it?

Accepted Answer

Denormalization is the deliberate introduction of redundancy into a schema by merging tables or pre joining data to improve read performance. When to use : In data warehouses / OLAP systems where read speed matters more than write efficiency When joins across many normalized tables are too slow for reporting In NoSQL stores where joins don't exist (embed related data in the document) Trade offs : faster reads, slower writes, data inconsistency risk if updates aren't applied everywhere. Example : instead of joining orders → customers → addresses , store customer name and shipping address directly in the orders table.

Question 6

How would you design a URL shortening service like Bitly?

Accepted Answer

Core components : 1. URL encoding : generate a 6 8 char alphanumeric key (base62 encode a counter or hash the URL) 2. Storage : url mapping(short key VARCHAR PK, long url TEXT, created at, expires at, user id) 3. Redirect service : lookup short key → 301/302 redirect to long url 4. Cache : Redis cache for hot short codes (most traffic is repeat redirects) 5. Analytics : async logging of click events (IP, timestamp, referrer) to Kafka → data warehouse Scale considerations : read heavy (100:1 read/write ratio) → optimize for reads via CDN + Redis. Use consistent hashing for distributed key generation to avoid collisions.

Question 7

What are the differences between CSV, ORC, Parquet, and AVRO file formats?

Accepted Answer

Format Layout Schema Compression Best For CSV Row None (schema on read) Poor Simple interchange, human readable AVRO Row Embedded (JSON schema) Good Kafka serialization, schema evolution, row level writes Parquet Columnar Embedded Excellent Analytical queries (column pruning, predicate pushdown) ORC Columnar Embedded Excellent Hive workloads; slightly better compression than Parquet Rule of thumb : use Parquet for data lake storage and Spark; AVRO for Kafka streaming; CSV only for external data exchange.

Question 8

How would you find the top 3 customers with the highest transaction volume in the last 90 days?

Accepted Answer

For ties at position 3, use DENSE RANK() :

Goldman Sachs Interview Questions