SDE - Intern Goldman Sachs interview experience | Hashini Senthil

Interview rounds

Round

Medium

Online Coding Interview

Duration120 minutes

Interview date20 Jan 2022

Coding problem3

1. Puzzle

There are 25 horses among which you need to find out the fastest 3 horses. You can conduct a race among at most 5 to find out their relative speed. At no point, you can find out the actual speed of the horse in a race. Find out the minimum no. of races that are required to get the top 3 horses.

Problem approach

Make a group of 5 horses and run 5 races. Suppose five groups are [a, b, c, d, e] and the next alphabet is its rank in this group(of 5 horses) eg. d3 means horse in group d and has ranked 3rd in his group. [ 5 RACES DONE ]
a1 b1 c1 d1 e1
a2 b2 c2 d2 e2
a3 b3 c3 d3 e3
a4 b4 c4 d4 e4
a5 b5 c5 d5 e5

Now make a race of (a1,b1,c1,d1,e1).[RACE 6 DONE] suppose result is a1>b1>c1>d1>e1
which implies a1 must be FIRST.
b1 and c1 MAY BE(but not must be) 2nd and 3rd.
For the II position, the horse will be either b1 or a2
(we have to find the top 3 horses therefore we choose horses b1,b2,a2,a3, and c1 to race among them [RACE 7 DONE].

2. Find All Triplets With Zero Sum

Moderate

30m average time

50% success

0/80

Asked in companies

You are given an array Arr consisting of n integers, you need to find all the distinct triplets present in the array which adds up to zero.

An array is said to have a triplet {arr[i], arr[j], arr[k]} with 0 sum if there exists three indices i, j and k such that i!=j, j!=k and i!=k and arr[i] + arr[j] + arr[k] = 0.

Note :

1. You can return the list of values in any order. For example, if a valid triplet is {1, 2, -3}, then (2, -3, 1), (-3, 2, 1) etc is also valid triplet. Also, the ordering of different triplets can be random i.e if there are more than one valid triplets, you can return them in any order.
2. The elements in the array need not be distinct.
3. If no such triplet is present in the array, then return an empty list, and the output printed for such a test case will be "-1".

Problem approach

Run three loops and check one by one whether the sum of the three elements is zero or not. If the sum of three elements is zero then print elements otherwise print is not found.

Try solving now

3. Puzzle

The average age of a close-knit group of friends is 15 years old. That particular group is composed of ten individuals altogether. The addition of 5 new members has resulted in an increase of 1 year in the group's current average age. What is the age range that the new members fall into on average?

Round

Medium

Face to Face

Duration75 minutes

Interview date20 Jan 2022

Coding problem7

1. Sort linked list of 0s 1s 2s

Easy

10m average time

90% success

0/40

Asked in companies

Given a linked list of 'N' nodes, where each node has an integer value that can be 0, 1, or 2. You need to sort the linked list in non-decreasing order and the return the head of the sorted list.

Example:

Given linked list is 1 -> 0 -> 2 -> 1 -> 2. 
The sorted list for the given linked list will be 0 -> 1 -> 1 -> 2 -> 2.

Try solving now

2. Implement Trie

Hard

41m average time

0/120

Asked in companies

Implement Trie Data Structure to support these operations:

insert(word) - To insert a string "word" in Trie
search(word) - To check if string "word" is present in Trie or not.
startsWith(word) - To check if there is any string in the Trie that starts with the given prefix string "word".

Three type of queries denote these operations:

Type 1: To insert a string "word" in Trie.
1 word

Type 2: To check if the string "word" is present in Trie or not.
2 word

Type 3: To check if there is any string in the Trie that starts with the given prefix string "word".
3 word

Try solving now

3. Add Two Numbers

Moderate

20m average time

80% success

0/80

Asked in companies

You are given two non-negative numbers 'num1' and 'num2' represented in the form of linked lists.

The digits in the linked lists are stored in reverse order, i.e. starting from least significant digit (LSD) to the most significant digit (MSD), and each of their nodes contains a single digit.

Calculate the sum of the two numbers and return the head of the sum list.

Example :

Input:
'num1' : 1 -> 2 -> 3 -> NULL
'num2' : 4 -> 5 -> 6 -> NULL

Output: 5 -> 7 -> 9 -> NULL

Explanation: 'num1' represents the number 321 and 'num2' represents 654. Their sum is 975.

Problem approach

Following are the steps.
1) Calculate the sizes of the given two linked lists.
2) If sizes are the same, then calculate the sum using recursion. Hold all nodes in the recursion call stack till the rightmost node, calculate the sum of the rightmost nodes, and forward carry to the left side.
3) If the size is not the same, then follow the below steps:
….a) Calculate the difference of sizes of two linked lists. Let the difference be diff
….b) Move different nodes ahead in the bigger linked list. Now use step 2 to calculate the sum of the smaller list and right sub-list (of the same size) of a larger list. Also, store the carry of this sum.
….c) Calculate the sum of the carry (calculated in the previous step) with the remaining left sub-list of a larger list. Nodes of this sum are added at the beginning of the sum list obtained in the previous step.

Try solving now

4. System Design

Write a Low Level Design for a chess game. (Learn)

5. Count vowels, consonants, and spaces

Easy

10m average time

90% success

0/40

Asked in companies

Given a string, write a program to count the number of vowels, consonants, and spaces in that string.

EXAMPLE :

Input: ‘N’= 25, ‘s’ =”Take u forward is Awesome”
Output: 10 11 4

Try solving now

6. Check If The String Is A Palindrome

Easy

10m average time

90% success

0/40

Asked in companies

You are given a string 'S'. Your task is to check whether the string is palindrome or not. For checking palindrome, consider alphabets and numbers only and ignore the symbols and whitespaces.

Note :

String 'S' is NOT case sensitive.

Example :

Let S = “c1 O$d@eeD o1c”.
If we ignore the special characters, whitespaces and convert all uppercase letters to lowercase, we get S = “c1odeedo1c”, which is a palindrome. Hence, the given string is also a palindrome.

Problem approach

Run a loop from starting to length/2 and check the first character to the last character of the string second to the second last one and so on …. If any character mismatches, the string won’t be a palindrome.

Try solving now

7. Reverse Linked List

Moderate

15m average time

85% success

0/80

Asked in companies

Given a singly linked list of integers. Your task is to return the head of the reversed linked list.

For example:

The given linked list is 1 -> 2 -> 3 -> 4-> NULL. Then the reverse linked list is 4 -> 3 -> 2 -> 1 -> NULL and the head of the reversed linked list will be 4.

Follow Up :

Can you solve this problem in O(N) time and O(1) space complexity?

Try solving now

Round

Hard

Face to Face

Duration90 minutes

Interview date20 Jan 2022

Coding problem4

1. Insertion in AVL Tree

Moderate

20m average time

80% success

0/80

Asked in companies

Ninja has to implement an ‘AVL_TREE’ from scratch.

He is given ‘N’ values, representing the values of nodes to be inserted. Ninja has to insert these values into the ‘AVL_TREE’ and return its root after inserting all the nodes.

Note: An ‘AVL_TREE’ is a self-balancing Binary Search Tree (BST) where the difference between heights of left and right subtrees cannot be more than one for all nodes.

For example:

Problem approach

Let the newly inserted node be w

Perform standard BST insert for w.
Starting from w, travel up and find the first unbalanced node. Let z be the first unbalanced node, y be the child of z that comes on the path from w to z and x be the grandchild of z that comes on the path from w to z.
Re-balance the tree by performing appropriate rotations on the subtree rooted with z. There can be 4 possible cases that need to be handled as x, y, and z can be arranged in 4 ways.
Following are the possible 4 arrangements:
y is the left child of z and x is the left child of y (Left Left Case)
y is the left child of z and x is the right child of y (Left Right Case)
y is the right child of z and x is the right child of y (Right Right Case)
y is the right child of z and x is the left child of y (Right Left Case)

Try solving now

2. Theory Questions

1. What are the functions that the compiler gives you by default?

Problem approach

Tip 1: Prepare and be strong in object-oriented programming

3. Puzzle

There is a fort and there is a wall surrounding it. The gap between the wall and the fort is 20m. The space between the wall and fort is a deep hollow. You are given two planks of size 20m how would reach the fort

4. Puzzle

There are four persons - say A, B, C, and D. Each can hold either 6, 7, or 8 balls in hand. If one has 6 or 8, the person speaks the truth. If a person holds seven balls, they lie. When asked about the total number of balls, the replies from A, B, C, and D are A - 25, B - 26, C - 27, and D - 28; Only one is telling the truth. Who is telling the truth? What is the actual number of balls?