Question: Goldman Sach Coding Round | SDE, London | 8th August 2020

Entering edit mode

Format

Time : 3 hours
2 Coding Question, 10 MCQ based mostly on Maths
Math MCQ topics
- Permutation & Combination
- Probability
- Linear Algebra
- Matrices
- Basic differentiation
- Basic Geometry

Remarks

Even though it was 3 hour test officially, everything was solved in 1 hour. Easy Coding Questions.
Content Outline

Test Outline
Coding Question 1 with solution
Coding Question 2 with solution
10 MCQ without answers
10 MCQ solution
10 MCQ with Answer Keys

Special thanks to AlgoUniversity for mentorship, especially Manas Sir, Swapnil Sir and Nikita Mam.

Test Outline

Coding Question 1

Solution
Pretty straightforward, copy given list of numbers and sort them. Comparing sorted list of numbers to original given sequence, number of mismatching positions, is obviously our required answer.
C++ Code (AC - passed all 22 test cases)

Coding Question 2

Solution
Given matrix is simply Square matrix representing adjacency matrix. Converted this into Adjacency list (not required though). Now I maintained a vis[] array to keep track of people that we have already processed. I loop over every person, check if we have processed this person, if not I call a DFS from that person. In the DFS, I simply go on processing his unprocessed friends and marking them in vis[]. So a single DFS call processes all people belonging to the group in which our person, on we started DFS on, belongs to. We won't initiate DFS from loop where we initiated our DFS more than once for every group. So, essentially number of times we have to call DFS represents number of total groups and that is exactly our answer.
C++ Code (AC - All 23 test cases passed)

10 MCQ without answers

Use this section to attempt solving problems by yourself. In next section is answer key for all these MCQs, followed by last section describing thought process to reach every answer and mentions few hacks.

10 MCQ Answer Key

These answers are 100% correct. Still, @Manas sir please cross verify Q8, Q10, Q11. Also, if anyone has better solutions than mine, please feel free to add them as Answers.

10 MCQ Solutions

Tip/Hack
More than 50% questions were googl-able or computable. Here are links to useful computation resources

WolframAlpha - World's best computation engine hands down!
- I used it to confirm my answer to complicated equation graphing question on calculus Q6
- Don't under-estimate its power to solve, compute or even understand multi-line problems! Just try it if you are stuck.
Matrix Calculator - Best resource for any computation related to Matrix
- I used it to save my time computing 5^th power of a matrix, so instead of matrix exponentiation I used this matrix calculator in Q7

Q3

Pre-Requisite Topic(s) : Expectations, Linearity of Expectation (optional)

Solution
Let A be expected score of first dice.
Let B be expected score of second dice.
Both A and B are independent events.
Expectation(A) = Expectation(B) = 3.5 { Reason - Dice can have value between [1,6], so expectation is simply average of 1 and 6 }
Expectation(A.B) = Expectation(A) x Expectation(B) = 3.5² = 49/4.

Q4

Pre-Requisite Topic(s) : Permutation & Combination

Solution
Answer is obviously, Probability = (Favourable ways of choosing 13 cards as per Question) / (Total ways of choosing 13 cards)
Probability = ^{(52 - 4x4)}C₁₃ / ⁵²C₁₃. Why (52 - 4x4)? Because we can't choose any of aces, kings, queen or jack and each of these can come in 4 suits.

I computed this value quickly using WolframAlpha which gave answer 0.0036
There might possibly be a better way to compute, but computing factorials and reducing it to fraction is cakewalk with WolframAlpha.

Q5

Pre-Requisite Topic(s) : Logic, Pigeon Hole Principle (optional / overkill)

Solution
In worst case, you can pick first three socks of all different color. The 4^th socks will then surely complete a pair of socks with same color!

Q6

Pre-Requisite Topic(s) : Calculus, Asymptote

Solution
This is an excellent question where Wolfram Alpha actually literally solved the probelm!!
Here I used WolframAlpha to generate graphs of each option and then figured out correct option!

Option 1
Option 2
Option 3
Option 4

Now we observe what is asked in the question. We want to put x = +infinity, and it should be linear. From graph we see, it is the case only in option 2, bingo!

Q7

Pre-Requisite Topic(s) : Matrices, Matrix Exponentiation(optional)

Solution
In practice I saved time and scope of manual error using Matrix Calculator I shared in link above.
Actual fastest solution to compute will be using same idea that we use in computing A^B in O(log N). Repeated squaring this time applied to matrix this time! so we can compute final matrix in just 3 matrix multiplication instead of naive 5.
Also note, we have to do only 2 multiplication completely, for 3rd we can just compute any single value and that should be sufficient! Reason? All options have different elements, so with one computation we can figure out correct answer!

Q8

Pre-Requisite Topic(s) : Probability, Bernoulli Theorem

Solution
My solution isn't perfectly correct even though answer should be correct. Please write in answer you correct solution (probably using bernoulli theorem)
Let X be total number of times coin is flipped till we get 4 Heads. Clearly, X^th coin toss result in 4^th Head.
Probability of Heads = 1/3. So in terms of expectation, out of X flips, exactly 1/3^rd flips should be heads.

=> X * (1/3) = 4
=> X = 12.

That means, 12-4 = 8 is number of expected tails.

Q9

Pre-Requisite Topic(s) : Probability

Solution
Infinite tiles, can cause confusion about how to approach the problem. But the key insight that solves that problem is this simple observation - Whereever you throw the circular disk, its center is going to lie inside some particular square.

So we reduced the problem to this simpler version - Given a square of unit size, a disc of 1/10 unit radius is thrown such that its center lies within the square. Find probability that any portion of circle doesn't go outside square!

Now this reduced problem is very easy to solve. Center should lie within a smaller square of size (1- 1/10 - 1/10) units = (4/5) units.
=> Probability = (4/5)² / (1)² = 0.64.

Q10

Q11

Pre-Requisite Topic(s) : Matrices

Solution
This solution needs verification.
I took, N = 3 and put values (x, y) = (10,20) and computed value of 3x3 matrix's determinant by using Matrix calculator and none of the first three options matched.

Q12

Q13

Pre-Requisite Topic(s) : Geometry, Calculas (Optional), Probability

Solution

ADD COMMENT • link