Goldman Online Test

Whole test was divided into 2 sections and given 1 hour to complete both the sections. section 1: 10 MCQs and two coding questions - 50 minutes section 2: 2 personality questions - 10 minutes

Section 1.1 - MCQs

Q1. Stacks

Suppose you've stack based implementation of the infix to postfix conversion algorithm. Which of the following input expressions would require maximim memory to hold the elements (operators and paranthesis) that the algorithm would push onto the stack during the conversion process? on stack during conversion process?

---

Pick ONE option:

1 + 2 ( 3 - 4 ) / ( 5 + 6 )

1 + 23 - 4 / 5

( 1 + 2 ) ( ( 3 - 4 ) / ( 5 + 6 ) )

12 + ( 3 - 4 ) / ( 5 + 6 )

Q2. Selection Sort

Given:

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        min_idx = i
        for j in range(i+1, n):
            if arr[min_idx] > arr[j]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
        

---

What is the role of inner loop in the given code?
Pick ONE option:

To swap the current element with the smallest element in the unsorted portion of the array

To compare each element with its adjacent element and swap them if necessary

To iterate over the entire array and sort the elements

To partition the array into two halves and sort them seperately

Q3. AVL Tree

Which of the following are true about AVL tree?
i) For large data sets, insertion takes same amount of time for AVL tree and Red-Black tree
ii) An AVL tree is an optimised binary search tree
iii) A Red-Black tree can be used as input for all applications of AVL tree
iv) Search operations are massievely faster on the AVL tree than on Red-Black tree

---

Pick ONE option:

Only i and ii

Only i and iii

Only ii and iv

Only ii and iii

Q4. Binary Search Tree - Preorder

What is the preorder traversal of the BST created by following numbers:
8, 3, 10, 1, 6, 14, 4, 7, 13

---

Pick ONE option:

8, 10, 14, 13, 3, 1, 6, 4, 7

8, 3, 1, 6, 4, 7, 10, 14, 13

8, 3, 10, 1, 6, 4, 7, 14, 13

8, 3, 1, 6, 4, 7, 10, 13, 14

Q5. Safe Sequence

Here P0, P1, P2, P3 are processes and R1, R2, R3 are resources R1 has 2 instances, R2 has 3 instances and R3 has 2 instances

If link is between resource and process then it means that resource is needed by that process
If link is between resource instances and process then it means that resource instance is allocated to that process

---

Consider the following snapshot of a system with 4 processes and 3 resource types. Which of the following is a safe sequence?
Pick ONE option:

P0, P1, P2, P3

P1, P0, P3, P2

P2, P0, P1, P3

None of the above options

Q6. Dinner Menu

Aryan plans to host a dinner for his friends at a restaurant. He deecides to keep 1 starter and 2 main course dishes for lunch. From the menu he realizes that there are only 25 ways to fulfill his requirement.

---

What can be the total number of dishes available on the menu?
Pick ONE option:

8

5

6

7

Q7. Hoffman Coding

Given the frequencies of letters in a message

Letter	Frequency
A	15
B	19
C	22
D	23
E	26
F	45

---

After using Hoffman coding, how many bits will saved in the messagePick ONE option:

300

800

796

125

Q8. Number problem

Number of 5 digit numbers N > 50000 with exactly one 6 and one 9, with 9 always to the left of 6 are

---

How many such numbers are there?Pick ONE option:

120

240

480

960

note

I don't remember the options for the question, Need to be updated later

info

Questions 9 & 10 are on OOPs concepts and I forgot the questions and options will update them later

Section 1.2 - Coding

Question 1

You can find the question here

Consider a binary tree of N nodes (1 Root and N-1 descendants). A node in this tree is called a Magic parent if the sum of one subtree (either left or right) of the node is even, and the sum of the other is odd. The nodes having only one or no child nodes can never be magic parents. The tree is represented as a series of relationships of each node to the Root node such as L, R, LL, LR.. and so on, where each node is left (L) to Root or left-left (LL) or right-left (RL) to Root and so on. Write a program to find all the Magic parents in the tree, and print their sum as the output.

Input Format: The first line of input contains an integer, N number of nodes in the tree The second line of input contains an Integer root which is the root of the tree.

The next N-1 lines of input contain a string, S, and an integer, X separated by a single white space where X is a node in the tree and S is the relation between Root and X.

Output Format: The output contains the sum of all the Magic parent nodes in the tree

Sample Input:

9
11
L 23
R 44
LL 13
LR 9
RL 22
RR 7
RLL 6
RLR 15

Sample Output:

33

Question 2

An NxN matrix is filled with only X and Ys alternatively. Top-left corner indexed as (1,1) is X and then every alternate row and column is filled with X and Y respectively. If N = 4

X	Y	X	Y
Y	X	Y	X
X	Y	X	Y
Y	X	Y	X

There are three query types

1. X a b - Change the value at (a,b) to X
2. Y a b - Change the value at (a,b) to Y
3. C a b - Count the number of Xs and Ys in the submatrix from (a,b) to bottom-right corner and print them separated by a space

Input Format: The first line of input contains an integer, N, the size of the matrix. The next line contains an integer, Q, the number of queries. The next Q lines contain a query of the form X a b or Y a b or C a b where a and b are the row and column indices of the matrix.

Sample Input:

5
3
X 1 1
C 1 1
Y 1 1

Sample Output:

5 4

info

function was in the format

void solve(int N, int Q, char q[], int a[], int b[]) {
    // Your code here
}

note

No need to take input or anything, we just need to complete the given function

Section 2 - Subjective

This section was given last 10 minutes with word limit of 200 per question.

Question 1

You've undertaken one challenging project with your friend. Till now it's going well and on time. Due to some urgent work, your friend has to leave the project. You have to complete the project alone. What will you do? How will you manage the project? What will you do to complete the project on time?

Question 2

Summarize one incident where your excitement and interest bore fruitiful and amazing results in a project that changed helped you.