Goldman Sachs
300+ Interview Questions and Answers
Ninja and his friend playing a game in which his friend gave him a string ‘STR’ that can contain spaces and a List/Array ‘WORDS’ which is of type string containing ‘N’ strings of wor...read more
Given a text and a wildcard pattern of size N and M respectively, implement a wildcard pattern matching algorithm that finds if the wildcard pattern is matched with the text. The matchi...read more
A few days back, Ninja encountered a string containing characters from ‘A’ to ‘Z’ which indicated a secret message. For security purposes he encoded each character of the string to its numeric va...read more
Q4. Good old standard problem: Playing number game with your friend to select any of the number between 1 to 3. Whoever reaches 20 first, wins. You have to tell the strategy to win the game. Basically, you start wi...
read moreThe strategy is to always subtract the number chosen by the friend from 4 to ensure reaching 16 first.
Start with 20 and subtract the number chosen by the friend from 4.
Continue this strategy until reaching 16 before the friend reaches 17-19.
Ensure the friend ends up at any number between 17 to 19 before reaching 16.
Given an array/list of integer numbers 'CHOCOLATES' of size 'N', where each value of the array/list represents the number of chocolates in the packet. There are ‘M’ number of students and the t...read more
You have been given a gold mine represented by a 2-d matrix of size ('N' * 'M') 'N' rows and 'M' columns. Each field/cell in this mine contains a positive integer, the amount of gold in kgs.
In...read more
You have been given an array/list of strings 'STR_LIST'. You are supposed to return the strings as groups of anagrams such that strings belonging to a particular group are anagrams of one...read more
You are given two numbers, ‘X’ and ‘Y’. Your task is to find the greatest common divisor of the given two numbers.
The Greatest Common Divisor of any two integers is the largest number th...read more
Q9. Given a tank with liquid, and there are flows in and out, inflow is U and outflow is Kx, where x is current height of liquid in tank, all needed quantities given, what are the conditions for overflow and steady...
read moreConditions for overflow and steady state in a tank with inflow and outflow
Overflow occurs when the inflow rate is greater than the outflow rate
Steady state is achieved when the inflow rate equals the outflow rate
Overflow can be prevented by adjusting the inflow rate or increasing the outflow rate
Steady state can be maintained by balancing the inflow and outflow rates
You are given a string ‘text’ and a string ‘pattern’, your task is to find all occurrences of pattern in the string ‘text’ and return an array of indexes of all those ...read more
You are given an array/list ARR consisting of N integers. Your task is to find the maximum possible sum of a non-empty subarray(contagious) of this array.
Note: An array C is a subarray of a...read more
You have been given a circular path. There are N petrol pumps on this path that are numbered from 0 to N - 1 (Both inclusive). Each petrol pump has two values associated with it:
1)The amount of pe...read more
For a given Binary Tree of integers, replace each of its data with the depth of the tree.
Root is at depth 0, hence the root data is updated with 0. Replicate the same further going down ...read more
Q14. Given we have a (un)biased die, with given probabilities, and we toss it till we get a sum of 100 or more (basically if the sum crosses 100), and we stop. What is the most probable number you will get on the la...
read moreThe most probable number on the last toss is 6.
The probability of getting a sum of 100 or more is highest when the sum is 99.
The last toss will be made to reach the sum of 100, so the most probable number is the one that will take the sum closest to 100.
The sum of 94 can be achieved by rolling a 6 on the last toss, which is the most probable number.
Design and implement a data structure for Least Recently Used (LRU) cache to support the following operations:
1. get(key) - Return the value of the key if the key exists in the cache, o...read moreYou have been given a binary matrix of size 'N' * 'M' where each element is either 0 or 1. You are also given a source and a destination cell, both of them lie within the matrix....read more
Q17. Suppose a man starts at 0, and has to go to 20 on the number line. He can either move in steps of 1 or 2. How many number of ways can he do this? Extending this, if we know the number of ways for going from 0 t...
read moreCount number of ways to reach 20 on number line starting from 0 in steps of 1 or 2. Derive recursive formula for n+1.
Use dynamic programming to count number of ways for each step.
For each step, number of ways is sum of number of ways for previous 1 or 2 steps.
Recursive formula: ways[n+1] = ways[n] + ways[n-1]
Q18. If you are asked to play a game where you toss a fair coin again and again until you get consecutive heads and win Re. 1 or you get consecutive tails and lose and quit, how much will you be willing to pay to pl...
read moreI would be willing to pay 50 paise to play this game.
The expected value of the game is 50 paise.
This is because the probability of getting consecutive heads is 1/3 and the probability of getting consecutive tails is 1/4.
Therefore, the expected value of the game is (1/3 * 1) - (1/4 * 1) = 1/12 = 8.33 paise.
However, since the minimum amount that can be won is Re. 1, I would be willing to pay 50 paise to play the game.
Q19. There is an urn with n red balls and 1 black ball in it. You and your friend play a game where you take turns drawing from the urn. The player who draws the black ball first wins. Should you go first or second?
Go second. The probability of winning is higher when going second.
The probability of winning when going first is (1/n+1), while the probability of winning when going second is (n/n+1)
This is because the first player has a chance of drawing the black ball on their turn, while the second player has a chance of drawing the black ball on their turn or the first player's turn
For example, if there are 10 red balls and 1 black ball, the probability of winning when going first is 1/1...read more
Q20. Suppose there are N chocolates, and I pick a random one, and eat that chocolate and also everything to the right of it. I then continue this process with the remaining. How many ways are there to do this?
There are (N-1)! ways to eat chocolates from left to right.
The first chocolate can be chosen in N ways, the second in (N-1) ways, and so on.
However, since the order of chocolates eaten matters, we need to divide by the number of ways to order N chocolates, which is N!.
Therefore, the total number of ways to eat chocolates is (N-1)!
For example, if N=4, there are 3! = 6 ways to eat the chocolates.
Q21. Given 3 functions, f which gives the first day of the current month, g gives the next working day and h gives the previous working day, conpute the 3rd working day? Compute the 2nd working day of the previous m...
read moreCompute working days using given functions f, g, and h.
To compute the 3rd working day, apply function g three times to function f.
To compute the 2nd working day of the previous month, apply function h to function f, then apply function g twice.
To compute the 4th working day of the next month, apply function g four times to function f.
Q22. An IT sector multinational wants to expand its business into more countries. Suggest a strategy. This was the question given in the VC round by the Partner. It was followed by a lot of numerical and qualitative...
read moreTo expand into more countries, the IT sector multinational can adopt a market entry strategy that includes market research, partnerships, localization, and scalability.
Conduct thorough market research to identify potential countries for expansion
Establish strategic partnerships with local companies to leverage their knowledge and networks
Adapt products and services to meet the specific needs and preferences of each target market
Ensure scalability of operations to handle the i...read more
Given a cost matrix cost[][] and a position (m, n) in cost[][], write a function that returns cost of minimum cost path to reach (m, n) from (0, 0). Each cell of the matrix represents a cost to...read more
Given a string ’S’ consisting of lower case English letters, you are supposed to return the longest palindromic substring of ‘S’.
Note that in case of more than one longest palindro...read more
Q25. Suppose you and I are playing a dice game. The one who get the lesser number looses the games. The dice has n sides. If I start the game, what is the probablity of you winning?
Probability of winning a dice game where the one with lesser number wins.
The probability of winning depends on the number of sides on the dice.
If the dice has an odd number of sides, the probability of winning is higher for the second player.
If the dice has an even number of sides, the probability of winning is equal for both players.
Q26. There is a 2D plane with infinite parallel, vertical lines with a spacing of 1 unit between them. You drop a rod of length L randomly on the plane, with random position and orientation. What is the probability ...
read moreProbability of a randomly dropped rod of length L intersecting a line on a 2D plane with infinite parallel, vertical lines.
The probability depends on the length of the rod L.
The probability can be calculated using geometric probability.
The probability is 1 - (2L - 1) / infinity.
For example, if L = 1, the probability is 0.5.
If L = 2, the probability is 0.75.
Q27. Given a biased coin, how do you create an unbiased toss?
Flip the coin twice and consider the outcome as follows.
Flip the coin twice and consider the outcome as follows:
- If both flips are heads or both are tails, discard and flip again.
- If the first flip is heads and the second is tails, consider it as heads.
- If the first flip is tails and the second is heads, consider it as tails.
This method ensures a 50-50 chance of getting either heads or tails.
Alternatively, use a physical method to balance the weight distribution of the coi...read more
Q28. Given a number line, and we have a rod of length L. We drop the rod on the line, what is the probability that it covers an integer?
Probability of a rod of length L covering an integer on a number line.
The probability depends on the length of the rod and the distance between adjacent integers on the number line.
If the length of the rod is less than the distance between adjacent integers, the probability is zero.
If the length of the rod is greater than or equal to the distance between adjacent integers, the probability is (L - d)/d, where d is the distance between adjacent integers.
The probability can be c...read more
You have been given a linked list of integers. Your task is to write a function that deletes a node from a given position, 'POS'.
Note :
Assume that the Indexing for the linked lis...read moreOn an Island, there is an airport that has an unlimited number of identical air-planes. Each air-plane has a fuel capacity to allow it to fly exactly 1/2 way around the world, along a great circle. The pl...read more
Given two strings str1 and str2 and below operations that can performed on str1. Find minimum number of edits (operations) required to convert ‘str1’ into ‘str2’.
Insert
Remove
Replace
All of the abov...read more
Given a leaderboard of a game with the following ranking pattern:
The player with the highest score is ranked number 1 on the leaderboard.
Players who have equal scores receive the same ...read more
Design a HashSet without using any built-in hash table libraries.
Implement the following public functions :
1) Constructor: It initializes the data members as required. 2) add(value): It insert...read moreQ34. Supposed there is a party, with 9 people, each person wants to give gifts to 3 people and also wants a gift from them. Is this scenario possible? If not, when is this possible? Give me a general case
No, it is not possible for each person to give gifts to 3 people and receive a gift from them in a party of 9 people.
In this scenario, each person would need to receive 3 gifts, which is not possible if there are only 9 people.
This scenario would be possible if there were at least 10 people at the party.
In general, for a party of n people, each person can give gifts to n-1 people and receive gifts from n-1 people.
You are given a positive integer N and an equation 1/X + 1/Y = 1/N
You need to determine the count of all possible positive integral solutions (X, Y) for the above equation.
Note:
1. X and Y shoul...read moreYou are given an infinite supply of coins of each of denominations D = {D0, D1, D2, D3, ...... Dn-1}. You need to figure out the total number of ways W, in which you can make a change fo...read more
You are given an array/list 'ARR' of ‘N’ integers, and ‘Q’ queries. Each query can be of two types:
Given 2 integers ‘L’,’R’ ( L>=0 and R Given an index ‘i’ update the value of ARR[i] to a given int...read more
Given an index ‘i’ update the value of ARR[i] to a given int...read more
You have been given 'N' ropes of different lengths, we need to connect these ropes into one rope. The cost to connect two ropes is equal to sum of their lengths. We need to conn...read more
The problem is to connect N ropes of different lengths into one rope with minimum cost.
Sort the array of rope lengths in ascending order.
Initialize a variable to keep track of the total cost.
While there are more than one rope remaining, take the two shortest ropes and connect them.
Add the cost of connecting the two ropes to the total cost.
Replace the two shortest ropes with the connected rope.
Repeat the above steps until only one rope remains.
Return the total cost.
Every story has an Endgame. This is another such story.
Tony Stark and Thanos live in two different islands. Tony wants to reach Thanos's island in minimum time to save the world.
You are given a...read more
You are given the number ‘N’. The task is to find the number of ways to represent ‘N’ as a sum of two or more consecutive natural numbers.
Example:
N = 9 ‘9’...read moreYou are given a matrix 'MATRIX' of dimension 'N' x 'M'. Your task is to make all the elements of row 'i' and column 'j' equal to 0 if any element in the ith row or jth column of the matrix is 0.
Note...read more
The task is to modify a given matrix such that if any element in a row or column is 0, then make all elements in that row and column 0.
Iterate through the matrix and keep track of rows and columns that contain 0s
After the first iteration, iterate through the tracked rows and columns and set all elements to 0
Handle the case where the first row or column contains 0 separately
To solve with O(1) space complexity, use the first row and first column of the matrix to track the rows ...read more
Ninja wants to print two strings in a text editor but his keyword allows typing lowercase English letters and backspace only.
Ninja type ‘N’ characters given by string ‘STR1’ to print the first ...read more
You have been given an array/list 'HEIGHTS' of length ‘N. 'HEIGHTS' represents the histogram and each element of 'HEIGHTS' represents the height of the histogram bar. Consider th...read more
You have been given a 9x9 2d integer matrix 'MAT' representing a Sudoku puzzle. The empty cells of the Sudoku are filled with zeros, and the rest of the cells are filled with integers from 1 to 9. ...read more
You are given a string (STR) of length N.
Your task is to find the longest palindromic substring. If there is more than one palindromic substring with the maximum length, return the...read more
Q46. 1. What is the probability that a person starting at 1 and who takes single steps ahead/back with equal probabilities reach 0 before 100?
The probability is 1/2.
The person can either move forward or backward with equal probabilities.
The probability of reaching 0 before 100 is 1/2.
This is a simple random walk problem.
Q47. You have an n x n matrix in which all the rows and all the columns are sorted. Given an input number, describe an algorithm to search for the number in the matrix
Algorithm to search for a number in an n x n matrix with sorted rows and columns.
Start from the top-right corner of the matrix
If the current element is greater than the target, move left
If the current element is less than the target, move down
Repeat until the target is found or the bottom-left corner is reached
You are Harshad Mehta’s friend. He told you the price of a particular stock for the next ‘N’ days. You can either buy or sell a stock. Also, you can only complete at most 2-transactions. Find ...read more
You are given an arbitrary binary tree, a node of the tree, and an integer 'K'. You need to find all such nodes which have a distance K from the given node and return ...read more
You are given two strings, ‘A’ and ‘B’ each of length ‘N’. Your task is to print 1 if ‘A’ is similar to ‘B’.
Note :
String ‘A’ is said to be similar to string ‘B’ if and only if 1. ‘A’ is equal t...read moreThe task is to determine if two strings are similar based on the given conditions.
Check if the strings are equal, if yes, return 1
Divide both strings into two parts and check if any combination satisfies the similarity condition
If none of the conditions hold true, return 0
You are given a multi-level linked list of 'N' nodes, each node has a next and child pointer which may or may not point to a separate node. Flatten the multi-level linked list...read more
Ninja decided to travel to a city. Each house in the city is connected via roads with at most two houses and forms a binary tree-like structure such that Kth level can have at most 2 ^ K houses. ...read more
Why did you use NoSQL DB in your project? Why not an SQL? What's the difference between them?
We are given a sorted doubly-linked list which contains distinct positive integers, and an integer ‘X’. Print all such unique pairs from the given list so that their sum is equal to ‘X’.
Input format ...read more
You are given with an array of integers and an integer K. You have to find and print the count of all such pairs which have difference K.
Note: Take absolute difference between the elemen...read more
Given an array A[] consisting of N integers, the task is to find the total number of subsequence which contain only one distinct number repeated throughout the subsequence.
Examples:
Input: A[...read more
You are given an array (ARR) of length N, consisting of integers. You have to find the sum of the subarray (including empty subarray) having maximum sum among all subarrays.
A subarray is a ...read more
You are given a 2 - D matrix, ‘MAT’, which consists of only 0s and 1s. Every row of the matrix is interpreted as a binary number, and the sum of all these “binary number interpreted r...read more
You are given an arbitrary binary tree consisting of N nodes, where each node is associated with a certain value, and two node values, a and b, you need to check if these nodes are...read more
You are given a positive integer ‘N’. Your task is to print all prime numbers less than or equal to N.
Note: A prime number is a natural number that is divisible only by 1 and itself. Example ...read more
You are given a two-dimensional grid having 'N' rows and 'M' columns, consisting of upper case characters. You are also given a word 'WORD'. You have to find the number of occurrences of that word i...read more
There are ‘N’ people at a party. Each person has been assigned a unique id between 0 to 'N' - 1(both inclusive). A celebrity is a person who is known to everyone but does not know anyone at...read more
You have been given a Binary Tree of integers, find the minimum depth of this Binary Tree. The minimum depth of a Binary Tree is the number of nodes along the shortest path from th...read more
Given an array/list of integers, “POINTS” containing coordinates ('x', 'y') of ‘N’ points in 2D plane, sorted by x-values in non-decreasing order. You are supposed to find the maximu...read more
Given 'N' number of intervals, where each interval contains two integers denoting the boundaries of the interval. The task is to merge all the overlapping intervals and return the lis...read more
You have been given a sorted array/list ARR consisting of ‘N’ elements. You are also given an integer ‘K’.
Now, your task is to find the first and last occur...read more
Q67. Is the price of a barrier option more or less than a normal option?
The price of a barrier option is generally less than a normal option.
Barrier options have a condition that must be met for the option to be activated, which reduces the likelihood of the option being exercised.
This reduced likelihood of exercise means that barrier options are generally cheaper than normal options.
However, the price of a barrier option can vary depending on the specific conditions and terms of the option.
For example, a knock-in barrier option may be more expen...read more
Given a decimal number as N, the task is to convert N into an equivalent irreducible fraction.
An irreducible fraction is a fraction in which numerator and denominator a...read more
You are given ‘N’ types of umbrellas, where each umbrella can shelter some number of people. Given the number of people each umbrella can shelter in the array “UMBRELLA”, you need to determine the minim...read more
The second round again started with me introducing myself and I was asked out of all companies, Why Goldman Sachs? These are pretty standard question one must prepare. Further, he asked me if I had ...read more
You are given an array containing N non-negative integers. Your task is to partition this array into two subsets such that the ...read more
Given a string ‘str’ and a string ‘pat’. The string s has some wildcard characters i.e ‘?’ and ‘*’.
If any character is a ‘?’ we can replace that character with any other character. If a...read moreThere are 2 trees in a garden (tree "A" and "B") and on both trees are some birds.
The birds of tree A say to the birds of tree B that if one of you comes to our tree, then our population...read more
Aahad and Harshit always have fun by solving problems. Harshit took a sorted array and rotated it clockwise by an unknown amount. For example, he took a sorted array = [1, 2, 3, 4,...read more
Given a binary search tree and an integer ‘K’. Your task is to find the ‘K-th’ smallest element in the given BST( binary search tree).
BST ( binary search tree) -
If all the sma...read more
You have been given an integer array/list(arr) and a number 'Sum'. Find and return the total number of pairs in the array/list which when added, results equal to the 'Sum'.
Note:
G...read moreYou are given a binary search tree of integers with N nodes. You are also given references to two nodes P and Q from this BST.
Your task is to find the lowest common ancestor(LCA) of these two given...read more
Q78. You roll a die until the sum of all die rolls becomes at least 100. What is the most likely value of the last roll?
What is the most likely value of the last roll in a game where a die is rolled until the sum of all rolls is at least 100?
The last roll must be at least 4 to reach a sum of 100
The probability of rolling a 4, 5, or 6 is 1/2
The most likely value of the last roll is 4 or 5
What is UML modelling? and All the related diagrams like class diagram, sequence diagram
Q80. Given coordinates of some points, find a figure that encompasses all of the points. The figure should have the least possible area and be formed by joining points using straight lines. Convex Hull.
The Convex Hull is the smallest convex polygon that encloses all given points.
Sort the points based on their x-coordinate.
Find the upper hull by starting from the leftmost point and moving clockwise.
Find the lower hull by starting from the rightmost point and moving counterclockwise.
Combine the upper and lower hulls to form the convex hull.
Q81. If I have to buy fuel from you, what option would I buy?
You can buy fuel from us through our fuel card program.
We offer a fuel card program that allows you to purchase fuel from our network of stations.
Our fuel card program offers discounts and rewards for frequent users.
You can easily track your fuel expenses and usage through our online portal.
We also offer customized fuel solutions for businesses and fleets.
Our fuel is high-quality and meets all industry standards.
Q82. If we increase the volatility of the stock, how does the price of a call option change?
Increasing stock volatility increases the price of a call option.
Higher volatility means higher potential for the stock to move in the option holder's favor, increasing the option's value
The option's delta and gamma will also increase with higher volatility
Example: If a call option on a stock with a strike price of $50 has a premium of $2 when the stock has a volatility of 20%, increasing the volatility to 30% may increase the premium to $2.50 or higher
Given an undirected and disconnected graph G(V, E), containing 'V' vertices and 'E' edges, the information about edges is given using 'GRAPH' matrix, where i-th edge is between GRAPH[i][0] and GRAP...read more
You are given an array consisting of N non-negative integers, and an integer K denoting the length of a subarray, your task is to determine the maximum elements for each subarr...read more
You are given an array/list ‘ARR’ consisting of ‘N’ distinct integers arranged in ascending order. You are also given an integer ‘TARGET’. Your task is to count all the distinct pairs in ‘ARR’ such that...read more
You are given an array of 'N' integers, and a positive integer 'K'. You need to determine if it is possible to divide the array into 'K' non-empty subsets such that the sum of el...read more
You are given two strings S and X containing random characters. Your task is to find the smallest substring in S which contains all the characters present in X.
Example:
Let S = “abdd” and X = “b...read moreYou are given a linked list of 'N' nodes and an integer 'K'. You have to reverse the given linked list in groups of size K i.e if the list contains x nodes numbered from 1 to x, then you...read more
You are given a list of rectangles where each rectangle is represented by an array of four integers (i.e. Rectangle[i]=[x1, y1, x2, y2], where x1, y1 represents the bottom left point of the rectan...read more
Given an integer number ‘num’. Your task is to convert ‘num’ into a word.
Suppose the given number ‘num’ is ‘9823’ then you have to return a string “nine thousand eight hundred tw...read more
You are given a 'M' x 'N' matrix of characters, 'CHARACTER_MATRIX' and a string 'WORD'. Your task is to find and print all occurrences of the string in the given character matrix. You are a...read more
Q92. Given 10 balls which weigh the same, except for one, and a beam balance, what is the minimum number of weighs to find the odd ball?
The minimum number of weighs to find the odd ball is 4.
Divide the 10 balls into 3 groups of 3, 3, and 4.
Compare the weights of the two groups of 3 balls.
If the weights are equal, the odd ball is in the group of 4.
If the weights are unequal, the odd ball is in the lighter group of 3.
Divide the lighter group of 3 balls into individual balls and compare their weights.
The odd ball will be identified in the 4th weigh.
Q93. Given an island in the center of a lake, and you are standing outside the lake, how would you reach the center?
To reach the center of the island, one can use a boat or any other means to cross the lake.
Use a boat to reach the island
Swim across the lake if it's not too far
If the lake is frozen, walk or skate across the ice
If there is a bridge or causeway connecting the island, use it to reach the center
Prateek is a kindergarten teacher. He wants to give some candies to the children in his class. All the children stand in a line and each of them has a grade according to his or her performance in the cla...read more
There are ‘N’ horses running in ‘N’ different lanes numbered from 1 to ‘N’. You are given an array “FINISHTIME” containing ‘N’ integers where “FINISHTIME[i]” represents the time taken by the ith ho...read more
Given the head node of the singly linked list, return a pointer pointing to the middle of the linked list.
If there are an odd number of elements, return the middle element if there are eve...read more
You have given a Singly Linked List of integers, determine if it forms a cycle or not.
A cycle occurs when a node's next points back to a previous node in the list. The li...read more
You are given an array(PRICES) of stock prices for N consecutive days. Your task is to find the maximum profit that you can make by completing as many transactions as you like, where a ...read more
Ninja is now bored with numbers and is now playing with characters but hates when he gets repeated characters. Ninja is provided a string, and he wants to return the first unique ch...read more
Design and implement a data structure for Least Recently Used (LRU) cache to support the following operations:
1. get(key) - Return the value of the key if the key exists in the cache, otherwise return...read moreMore about working at Goldman Sachs
Top HR Questions asked in null
Interview Process at null
Top Interview Questions from Similar Companies
Reviews
Interviews
Salaries
Users/Month
Made with ❤️ in India. Trademarks belong to their respective owners. All rights reserved © 2024 Info Edge (India) Ltd.
