10+ Goldman Sachs Software Engineer Interview Questions and Answers

Serialization and deserialization of an N-ary tree involves converting the tree into a sequence of bits and reconstructing the original tree from this format.

• Serialize the N-ary tree by traversing it in level order and representing each node and its children using a space-separated sequence of integers.

• Deserialize the serialized tree by parsing the input sequence and reconstructing the tree structure based on the provided format.

• Use a queue data structure for deserialization ...read more

Design a constant time data structure for key-value mappings with operations like INSERT, DELETE, SEARCH, GET, GET_SIZE, and IS_EMPTY.

• Use a hash table to achieve constant time complexity for operations.

• Implement INSERT, DELETE, SEARCH, GET, GET_SIZE, and IS_EMPTY functions.

• Ensure key is a string and value is a positive integer.

• Return appropriate results based on the operation type.

• Handle edge cases like key not found or data structure being empty.

Given a Unix-style directory path, simplify it by following certain rules and return the simplified path.

• Use a stack to keep track of directories while iterating through the input path.

• Handle cases for '.', '..', and multiple slashes appropriately.

• Return the simplified path by joining the directories in the stack with '/' separator.

Design and implement a Least Recently Used (LRU) cache data structure that supports get and put operations with a specified capacity.

• Implement a doubly linked list to keep track of the order of keys based on their usage.

• Use a hashmap to store key-value pairs for quick access and updates.

• When a key is accessed or updated, move it to the front of the linked list to mark it as the most recently used.

• When the cache reaches its capacity, evict the least recently used item from the...read more

Find the maximum elements for each subarray of size K in a given array.

• Iterate through the array and maintain a deque to store the indices of elements in decreasing order.

• Pop elements from the deque that are out of the current window.

• Keep track of the maximum element in each subarray of size K.

• Return the maximum elements for each subarray.

Virtual memory is a memory management technique that allows a computer to use more memory than it physically has.

• Virtual memory uses a combination of RAM and hard disk space to store data.

• It allows programs to use more memory than is physically available.

• If a program tries to access memory that is not currently in RAM, it will be swapped in from the hard disk.

• Even if we had infinite RAM, virtual memory would still be necessary for certain tasks such as memory isolation and pr...read more

Find maximum length of subarray where max <= 2*min.

• Iterate through array and keep track of max and min values.

• Update max length when condition is met.

• Time complexity: O(n)

Virtual memory is a memory management technique that allows a computer to compensate for physical memory shortages by temporarily transferring data from RAM to disk storage.

• Virtual memory allows programs to use more memory than is physically available on the system.

• It helps in multitasking by allowing multiple programs to run simultaneously without running out of memory.

• Virtual memory uses a combination of RAM and disk space to store data that is not currently in use by progr...read more

Create a Binary Search Tree (BST) from an incoming stream of nodes.

• Start with an empty BST

• For each incoming node, compare it with the root node and insert it accordingly

• Repeat the process until all nodes are inserted

Implement LRU cache

• LRU stands for Least Recently Used

• It is a cache eviction policy that removes the least recently used item

• It can be implemented using a doubly linked list and a hash map

• Newly accessed items are moved to the front of the list

• When the cache is full, the item at the end of the list is removed

Trapping rainwater problem

• The problem involves calculating the amount of rainwater that can be trapped between bars in an elevation map

• Use two pointers approach to calculate the water trapped at each bar

• Keep track of the maximum height on the left and right of each bar to calculate the trapped water