Goldman Sachs Data Structures & Algorithms Interview Questions

Alfred O. - "We can use dictionary to store cache items so that our read / write operations will be O(1). Each time we read or update an existing record, we have to ensure the item is moved to the back of the cache. This will allow us to evict the first item in the cache whenever the cache is full and we need to add new records also making our eviction O(1) Instead of normal dictionary, we will use ordered dictionary to store cache items. This will allow us to efficiently move items to back of the cache a"See full answer

Wayne W. - "def hasgoodsubarray(nums, k): if not nums: return False prefix = 0 table = set([0]) for i in range(len(nums)): prefix += nums[i] if prefix % k in table: return True table.add(prefix % k) return False `"See full answer

VContaineers - " Compare alternate houses i.e for each house starting from the third, calculate the maximum money that can be stolen up to that house by choosing between: Skipping the current house and taking the maximum money stolen up to the previous house. Robbing the current house and adding its value to the maximum money stolen up to the house two steps back. package main import ( "fmt" ) // rob function calculates the maximum money a robber can steal func maxRob(nums []int) int { ln"See full answer

Gaston B. - "Use a representative of each, e.g. sort the string and add it to the value of a hashmap> where we put all the words that belong to the same anagram together."See full answer

Anonymous Roadrunner - "def is_valid(s: str) -> bool: stack = [] closeToOpen = { ")" : "(", "]" : "[", "}" : "{" } for c in s: if c in closeToOpen: if stack and stack[-1] == closeToOpen[c]: stack.pop() else: return False else: stack.append(c) return True if not stack else False debug your code below print(is_valid("()[]")) `"See full answer

Komal S. - "a. Sort the array elements. b. take two pointers at index 0 and index Len-1; c. if the sum at the two pointers is target; break and return the pair d. if the sum is smaller, then move left pointer by 1 e. else move right pointer by 1; run the logic till the target is met or right pointer crosses the left pointer."See full answer

Divya R. - "public static Integer[] findLargest(int[] input, int m) { if(input==null || input.length==0) return null; PriorityQueue minHeap=new PriorityQueue(); for(int i:input) { if(minHeap.size()(int)top){ minHeap.poll(); minHeap.add(i); } } } Integer[] res=minHeap.toArray(new Integer[0]); Arrays.sort(res); return res; }"See full answer

Victor O. - " import java.util.*; class Solution { // Time Complexity: O(n^2) // Space Complexity: O(n) public static List> threeSum(int[] nums) { // Ensure that the array is sorted first Arrays.sort(nums); // Create the results list to return List> results = new ArrayList(); // Iterate over the length of nums for (int i = 0; i < nums.length-2; i++) { // We will have the first number in"See full answer

Cagdas A. - " class ListNode: def init(self, val=0, next=None): self.val = val self.next = next def has_cycle(head: ListNode) -> bool: pass # your code goes here if head is None: return False previousNodes = set() iter = head while iter: if iter.val in previousNodes: return True previousNodes.add(iter.val) iter = iter.next; return False debug your code below node1 = ListNode(1) node2 = ListNode(2) n"See full answer

Jerry O. - "\# Definition for a binary tree node. class TreeNode: def init(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right class Solution: def maxPathSum(self, root: TreeNode) -> int: self.max_sum = float('-inf')"See full answer

Manoj R. - "def traprainwater(height: List[int]) -> int: n = len(height) totalwaterlevel = 0 for i in range(n): j = i+1 while j = n: break rows = j - i -1 intrwaterlevel = min(height[j], height[i]) * rows for k in range(i+1, j): intrwaterlevel -= height[k] totalwaterlevel += intrwaterlevel i = j return totalwaterlevel"See full answer

Divya R. - "class Trie { private TrieNode root; public Trie() { root = new TrieNode(); } public void insert(String word) { TrieNode temp=root; for(int i=0; i<word.length(); i++) { if(!temp.children.containsKey(word.charAt(i))) { temp.children.put(word.charAt(i), new TrieNode()); } temp=temp.children.get(word.charAt(i)); } temp.isEndOfWord=true; } public boolean search(String word) { TrieNode temp=root; for(int i=0; i<word.length(); i++) { if(!temp.children.containsKey(word.charAt(i))) { return false; } temp"See full answer

Gabriele G. - "Less efficient version, yet effective for the interview: def is_palindrome(s: str) -> bool: dim = len(s) if dim str: dim = len(s) if dim < 2: return s left = 0 longest = "" while left < dim: righ"See full answer