## Goldman Sachs Technical Interview Questions: Freshers and Experienced

Multithreading is a Java feature that permits the execution of two or more sections of a program simultaneously to maximise CPU efficiency. In other words, it is the process of executing multiple threads at the same time. A thread is a component of such a program. Threads are hence lightweight processes within processes.

Threads can be formed using two different mechanisms:

• Extending the Thread class - We'll make a class that extends the java.lang.Thread class. The run() method of the Thread class is overridden by this class. The run() procedure is where a thread starts its life. To begin thread execution, we construct an object of our new class and use the start() method. Start() calls the Thread object's run() function.
• Bringing the Runnable Interface into Practice - We make a new class that implements the java.lang.Runnable interface and override the run() method of this. After that, we create a Thread object and call its start() method.

• Since threads use a shared memory space, it helps in saving memory.
• Threads are autonomous and many operations can be performed at the same time, which helps in saving time.

### 2. Explain hashCode() and equals() in Java.

HashMap is part of the Java collection framework. HashMap uses a technique known as hashing. Hashing is the process of converting an object into an integer value. Indexing and search speed are aided by the integer value. It is in charge of creating the map interface. It stores the data in a Key/Value pair. In HashMap, the node is represented as a class that holds an array of nodes. Internally, it uses an array and LinkedList data structure to hold Key and Value. There are four fields in HashMap.

• equals() is a function that compares two objects to see if they are equal. It compares the Key to see if they are equivalent. It belongs to the Object class and is a method. It is possible to override it. It is required to override the hashCode() method if you override the equals() method.
• hashCode() is an object class method. It returns the object's memory reference in integer form. The bucket number is determined by the value returned by the method. The address of the element within the map is represented by the bucket number. Null Key's hash code is 0.

### 3. Discuss the final keyword in Java.

In Java, the final keyword is used to restrict the user. The final keyword in Java can be used in a variety of situations. The final keyword could be used with a variable, method or class. Once a variable, function, or class has been declared final, it can only be assigned once. That is to say,

• Final variable: If you mark a variable as final, you won't be allowed to change its value (It will be constant).
• Final method: You can't override a method that has been marked as final.
• Final class: You can't extend a class that has been marked as final.

### 4. Differentiate between StringBuffer and StringBuilder classes in the context of Java.

Strings are Java objects that are internally supported by a char array. Strings are immutable because arrays are immutable (they can't grow). Every time you make a change to a String, a new String is produced. Java, on the other hand, has a number of classes that can be used to manipulate strings. StringBuffer and StringBuilder are two such classes.

### 5. Explain the internal architecture of Java Virtual Machine (JVM).

The JVM (Java Virtual Machine) is a run-time engine that allows Java applications to run. The JVM is the program that executes the main method in java programming. JVM is a component of JRE (Java Runtime Environment).

WORA refers to Java programmes (Write Once Run Anywhere). This means that a programmer can write Java code on one system and expect it to operate without modification on any other Java-enabled device. All of this is feasible because of JVM.

When we compile a .java file, the Java compiler creates .class files (byte-code files) with the same class names as the .java file. When we run this.class file, it goes through a series of phases. These steps sum up the JVM as a whole.

The execution engine scans the byte-code line by line, extracts data and information from various memory areas, and then executes the instructions. The Java Native Interface (JNI) is a user interface that interacts with Native Method Libraries and provides native libraries (C, C++) for execution. It allows JVM to call C/C++ libraries and be called by C/C++ libraries that are hardware-specific. Native Method Libraries are a set of Native Libraries (C, C++) that the Execution Engine requires.

### 6. What is Garbage Collection in Java?

Garbage collection is the process of examining heap memory, determining which items are in use and which are not, and then eliminating the objects that aren't.

An in-use object, also known as a referenced object, signifies that it is still referenced by some portion of your program. An unreferenced object, also known as an unused object, is one that is no longer referenced by any portion of your program. An unreferenced object's memory can thus be reclaimed. The most significant benefit of garbage collection is that it relieves us of a load of manual memory allocation and deallocation, allowing us to focus on the problem at hand.

Once we've made an object garbage-collectable, the garbage collector won't be able to destroy it right away. Only the object is destroyed when JVM executes the Garbage Collector program. However, we cannot predict when JVM will execute the Garbage Collector. We can also ask JVM to run Garbage Collector on our behalf. It can be done in two ways:

• Using the System.gc() method: The static method gc() in the System class is used to ask the JVM to launch the Garbage Collector.
• Using the Runtime.getRuntime().gc() method: The Runtime class allows an application to communicate with the JVM it is executing on. As a result, we can ask JVM to run Garbage Collector by calling its gc() method.

### 7. What is the difference between an interface and abstract class in Java?

For classes and methods, the abstract keyword is a non-access modifier. An abstract class is a special kind of class that can't be used to create objects (to access it, it must be inherited from another class). Talking about an abstract method, it has no body and it can only be used in an abstract class. The subclass provides the body (inherited from).

In Java, an interface is a blueprint for a class. It features abstract methods and static constants. In Java, the interface is a means of achieving abstraction. The Java interface can only have abstract methods, not method bodies. In Java, it is used to achieve abstraction as well as multiple inheritances. To put it another way, interfaces can have abstract methods and variables. It isn't allowed to have a method body.

The differences between the two have been tabulated below:

### 8. How can you implement static and dynamic polymorphism in C++?

Polymorphism refers to the fact that something exists in multiple forms. Polymorphism, in simple terms, is the ability of a message to be displayed in multiple formats. On the basis of the time it takes to resolve the procedure call, it can be characterised in two ways.

• Static polymorphism means that a function's invocation (call) is resolved at compile time. Overloading can be used to accomplish this.
• Function overloading: Overloading of functions occurs when there are numerous functions with the same name but distinct parameters. Changes in the number of arguments or the kind of arguments can cause functions to become overloaded.
• Operator overloading: C++ also allows you to overload operators. For example, we can use the string class's operator ('+') to concatenate two strings. This is the addition operator, and its job is to add two operands. So, when the operator '+' is used between integer and string operands, it adds them together, and when it is used between string operands, it concatenates them.
• Dynamic polymorphism refers to the resolution of a function call at runtime. In C++, it is implemented using the function Overriding in inheritance.
• Function overriding: Function overriding, on the other side, comes into the picture when a derived class defines one of the base class's members functions. That base function is asserted to be overridden.

### 9. What are the differences between pointers and reference variables in C++?

In C++, a pointer is a variable that keeps track of the memory address of another variable.

A reference is an alias for a variable that already exists. A reference to a variable that has been initialised cannot be modified to refer to another variable. As a result, a reference is analogous to a const pointer.

Pointer

• Any time after a pointer is declared, it can be initialised to any value.
 int x = 6;
// some code
int *ptr = &x;

A reference is supposed to be initialized at its time of declaration.

int x = 6;
int &ref = x;
• It is possible to assign a pointer point to a NULL value. NULL references are not allowed.
• A * must be used to dereference pointers. References can be referred to simply by their names.
• A pointer can be altered to point to any similar-type variable. For example:
int x = 6;
int *ptr;
ptr = &x;
int y = 7;
ptr = &y;

A reference to a variable object cannot be modified once it has been initialised to a variable.

### 10. Can a constructor be private in C++?

A constructor is a particular member function of a class that is responsible for initialising the class's objects. When a class object is created in C++, the constructor is automatically invoked. Constructors are typically defined in the public section of a class. So, the question is whether construction can be defined in the class's private section. The answer to this is a yes. A constructor can be defined in the class's private section.

The ways to use a constructor in the private section of the class:

• We can use the friend class if we don't want that class to be instantiated by anyone else except a friend class.
• If we need to create a singleton class, we can utilise the Singleton design pattern. This signifies that the system is driven by a single item or a small number of objects, rather than multiple objects of the same class.
• Because constructors have the same name as classes, different constructors are distinguished by their argument lists; however, if there are many constructors, an implementation might become error-prone. The Named Constructor Idiom requires you to declare all of the class's constructors in the private or protected sections, and then build public static functions to retrieve the class's objects.

### 11. What is a Red-Black Tree in context to data structures?

A red-black tree is a self-balancing binary search tree with one extra bit at each node, which is commonly read as the colour (red or black). These colours are used to keep the tree balanced as insertions and deletions are made. The tree's balance isn't ideal, but it's good enough to cut down on searching time and keep it around O(log n), where n is the total number of nodes in the tree. Rudolf Bayer invented this tree in 1972.

It's worth noting that, because each node only needs 1 bit of memory to store the colour information, these trees have the same memory footprint as a traditional (uncoloured) binary search tree.

Points to remember:

• Every node of a red-black tree has a colour, which is either red or black.
• The tree's root is always black.
• There are no red nodes that are next to one other (A red node is not allowed to have a red parent or red child).
• There is the same number of black nodes on every path from a node (including root) to any of its descendant's NULL nodes.

### 12. Explain BFS (Breadth First Search) vs DFS (Depth First Search) in context of graph traversal.

•  Breadth-First Search (BFS) is a vertex-based method that begins at the root of the tree and traverses all nodes at the current depth level before moving on to nodes at the next depth level. It employs a Queue data structure that follows the first-in, first-out principle. In BFS, one vertex is visited and marked at a time, then its neighbours are visited and placed in the queue.
• Depth First Search (DFS) is an edge-based approach. It employs the Stack data structure and operates in two stages: first, visited vertices are pushed into the stack, and subsequently, if no vertices are present, visited vertices are popped.

### 13. What is Binet's formula in context to the Fibonacci series?

For computing the nth Fibonacci number, there is a simple mathematical procedure called Binet's formula that does not require the calculation of the preceding numbers. Hence, we can find out the nth fibonacci number in constant time, without using recursion or iteration.

It features the Golden Ratio (x) (ratio of any two successive Fibonacci numbers):

### 14. Given a 2D matrix with n rows and m columns, your task is to print the elements of the matrix in a zigzag manner as shown in the image below :

For example,
Input:
1 2
3 4

Output:
1 2 3 4

Input:
1 2 3
4 5 6
7 8 9

Output:
1 2 4 7 5 3 6 8 9

### Approach:

The strategy is straightforward. We will keep iterating over each diagonal element one by one and change the direction based on the previous match.

#include<bits/stdc++.h>
using namespace std;

// function to print the matrix in a zigzag pattern
void zigZagTraversal(vector<vector<int>> arr, int n, int m)
{
int cur_row = 0, cur_col = 0; //denotes the current row and column

// false denotes cur_col needs to be incremented, true denotes cur_row needs to be incremented
bool flag = false;

// Printing matrix of lower half zig-zag pattern
int mn = min(m, n);
for (int length = 1; length <= mn; ++length) {
for (int i = 0; i < length; ++i) {
cout << arr[cur_row][cur_col] << " ";

if (i + 1 == length)
break;
// If flag is true we increment cur_row and decrement cur_col else decrement cur_row and increment cur_col
if (flag == true){
cur_row = cur_row + 1;
cur_col = cur_col - 1;
}
else{
cur_row = cur_row - 1;
cur_col = cur_col + 1;
}
}

if (length == mn)
break;

// We update cur_row or cur_col value according to the last increment
if (flag){
cur_row = cur_row + 1;
flag = false;
}
else{
cur_col = cur_col + 1;
flag = true;
}
}

// Updating the indexes of cur_row and cur_col variable
if (cur_row == 0) {
if (cur_col == m - 1)
cur_row = cur_row + 1;
else
cur_col = cur_col + 1;
flag = 1;
}
else {
if (cur_row == n - 1)
cur_col = cur_col + 1;
else
cur_row = cur_row + 1;
flag = 0;
}

// Printing the next half zig-zag pattern
int mx = max(m, n) - 1;
for (int length, diagonal = mx; diagonal > 0; --diagonal) {

if (diagonal > mn)
length = mn;
else
length = diagonal;

for (int i = 0; i < length; ++i) {
cout << arr[cur_row][cur_col] << " ";

if (i + 1 == length)
break;

// We update cur_row or cur_col value according to the last increment
if (flag == true){
cur_row = cur_row + 1;
cur_col = cur_col - 1;
}
else{
cur_col = cur_col + 1;
cur_row = cur_row - 1;
}
}

// Updating the cur_row and cur_col variables
if (cur_row == 0 || cur_col == m - 1) {
if (cur_col == m - 1)
cur_row = cur_row + 1;
else
cur_col = cur_col + 1;

flag = true;
}

else if (cur_col == 0 || cur_row == n - 1) {
if (cur_row == n - 1)
cur_col = cur_col + 1;
else
cur_row = cur_row + 1;

flag = false;
}
}
}

int main()
{
vector<vector<int>> arr = vector<vector<int>>(3, vector<int>(3, 0));
for(int i = 0; i < 3; i ++)
{
for(int j = 0; j < 3; j ++)
arr[i][j] = 3 * i + (j + 1);
}
zigZagTraversal(arr, 3, 3);

return 0;
}

Explanation:

We follow a simulation approach in the above code. First, we print the elements in the first upper half of the matrix. Then, we print the elements of the lower half of the matrix. We iterate each diagonal one by one and print its elements.

### 15. You are given a number N. You need to check if it can be written as a sum of k prime numbers.

For example,
Input :
N = 5, k = 2

Output :
True

Explanation :
10 can be written as 5 + 5

Input :
N = 2, k = 2

Output :
False

### Approach:

We use the Goldbach Conjecture for solving this problem. Goldbach’s conjecture states that every even integer (greater than 2) can be represented as the sum of two primes.

When N >= 2k and k = 1:

The answer will be True if and only if N is a prime number

When N >= 2K and K = 2:

If N is an even number the answer will be Yes(Goldbach’s conjecture)

If N is odd the answer will be No if N-2 is not a prime number and Yes if N-2 is a prime number.

This is because we know odd + odd = even and even + odd = odd. So when N is odd, and K = 2 one number must be 2 as it is the only even prime number so now the answer depends on whether N-2 is odd or not.

When N >= 2K and K >= 3:

The answer will always be True. This is because when N is even N – 2*(K-2) is also, even so, N – 2*(K – 2) can be written as the sum of two prime numbers p, q and N can be written as 2, 2 …..K – 2 times, p, q.

When N is odd N – 3 -2*(K – 3) is even so it can be written as the sum of two prime numbers p, q and N can be written as 2, 2 …..K-3 times, 3, p, q

 // function to check if a number is prime
bool checkPrime(int x)
{
for (int i = 2; i * i <= x; i++)
if (x % i == 0)
return false;
return true;
}
bool checkSumOfKPrimes(int N, int k)
{
// We return false if N < 2*k
if (N < 2*k)
return false;

// If k = 1 we check if N is prime or not
if (k == 1)
return checkPrime(N);

if (k == 2)
{
// if N is even the answer is true;
if (N % 2 == 0)
return true;

// If N is odd, we check if N - 2 is prime or not
return checkPrime(N - 2);
}

// If k >= 3, we return true;
return true;
}

Explanation:

In the above code, we created a function checkPrime which takes one input parameter and we check if the given input is a prime number or not. We also created a function checkSumOfKPrimes which takes two input parameters N and k. In the function, we check if N can be represented as a sum of k prime numbers using the conditions of the Goldman Conjecture.

### 16. Given an array whose elements denote the price of a stock on the ith day, find the maximum profit that you can make by purchasing and selling those stocks. No stock can be bought unless the previously bought stock has been sold.

For example,
If the array is 100, 180, 260, 310, 40, 535, 695
Then, the output will be 765

Explanation of the above test case:
The maximum profit can be achieved by buying on day 0 and selling on day 3 and then buying on day 4 and selling on day 6.

### Approach:

In our approach, we will iterate through each of the prices of the stock starting  from day 1 and check if its price is greater than the previous day’s price. This is because there is no limit on the number of transactions being made. For example, buying a stock on day 1 and selling on day 4 is equivalent to buying a stock on day 1, selling on day 2, buying on day 2, selling on day 3, buying on day 3, selling on day 4.

Code:

 #include<bits/stdc++.h>
using namespace std;
//function to calculate the maximum profit attainable
int maximiseProfit(int prices[], int size)
{
int maximumProfit = 0; // stores the maximum profit
for(int i = 1; i < size; i ++)
{
if(prices[i] - prices[i - 1] > 0)
maximumProfit += prices[i] - prices[i - 1];
}
return maximiseProfit;
}
int main()
{
int prices[] = { 100, 180, 260, 310, 40, 535, 695 };
int size = sizeof(prices) / sizeof(prices[0]);
cout << maximiseProfit(prices, size) << endl;
return 0;
}

Explanation:

In the above code, the function maximiseProfit calculates the maximum profit attainable on the given set of stock prices. We iterate over the array and add up any difference in which an element is greater than its preceding element.

### 17. Given an array of strings, you need to remove strings which are anagrams of strings preceding them in the given array. You need to return the remaining strings in sorted order.

For example,
Input :
“tea”, “ate”, “anagram”, “eat”, “gramaan”

Output :
“anagram”, “tea”

Explanation :
The words "ate" and "eat" are anagrams of the word "tea."
Due to the fact that "gramaan" is an anagram of "anagram," the array becomes ["anagram", "tea"].

### Approach:

We can simply sort and compare the given two strings to see if they are anagrams or not. We may also use a hashmap to see if a string has appeared or not. Make an auxiliary array to store the generated strings, as well as a hashmap to keep track of the string we've found thus far. Then iterate through the array's supplied string, sort the current string, and look it up in the hashmap.

If the current text is not found in the hashmap, insert the sorted string arr[i] in the resultant array. After that, sort the array and print each string.

Code:

 void uniqueAnagrams(string arr[], int n)
{

vector<string> result;

//to keep track of already encountered sorted string
unordered_set<string> found;

for (int i = 0; i < n; i++) {

string cur_word = arr[i];

// sorting the current string
sort(begin(cur_word), end(cur_word));

// Checking if the current sorted string is present in the data structure already
if (found.find(cur_word) == found.end()) {

result.push_back(arr[i]);
found.insert(cur_word);
}
}

sort(begin(result), end(result));

for (int i = 0; i < result.size(); ++i) {
cout << result[i] << " ";
}
}

Explanation:

In the above code, we created a function uniqueAnagrams, which removes all the duplicate anagrams and prints the sorted array. We take the help of a hashmap to store each visited string in its sorted form. If the current string is not found in the hash map, we push it in the answer vector. At last we sort the answer vector and then display the resultant vector.

### 18. Explain the working of AJAX.

Ajax (Asynchronous JavaScript and XML) is a set of web development approaches that generate asynchronous web applications using various client-side web technologies. Web applications that use Ajax can transmit and get data from a server asynchronously (in the background) without interfering with the existing page's appearance and behaviour.

The XMLHttpRequest Object is used by Ajax to communicate with the server. The user submits a request using the User Interface, and a JavaScript call is made to the XMLHttpRequest Object, which then sends an XMLHttp request to the XMLHttpRequest Object. At that point, the server interacts with the database via php, servlet, ASP.net, and other technologies. The data is retrieved, and the server transmits it to the XMLHttpRequest Callback method in the form of XML or Jason data. The Data then is presented on the browser using HTML and CSS.

### 19. Explain processes and threads in context of OS.

A process is a running program that serves as the foundation for all computations. The process is not the same as programming code, although it is very similar. In contrast to the programme, which is regarded as a 'passive' entity, a process is a 'active' entity. Hardware state, memory and CPU are among the attributes held by the process.

Within a process, a thread is a single sequence stream. Threads have the same properties as the process, which is why they're referred to as lightweight processes. Threads are executed one after the other, giving the appearance that they are running in parallel. Each thread has a unique state. Each thread has:

• A program counter
• A register set
• A stack space

Threads are dependent on each other since they share the code, data and OS resources.

### 20. What is a join in SQL?

Joins in SQL join rows from two or more tables based on a shared column. The different categories of joins are:

• INNER JOIN returns rows when both tables have a match.
• LEFT JOIN returns all rows from the left table, even if the right table has no matches.
• RIGHT JOIN returns all rows from the right table, even if the left table doesn't have any matches.
• FULL OUTER JOIN returns rows when one of the tables has a match.
• SELF JOIN is a SQL statement that joins a table to itself as if it were two tables, temporarily renaming at least one table.
• CARTESIAN JOIN (CROSS JOIN) returns the Cartesian product of two or more joined tables' sets of records.