SDE - 1 MAQ Software interview experience | Anonymous

Interview rounds

Round

Medium

Coding Test - Pen and paper

Duration30 minutes

Interview date21 May 2015

Coding problem1

This was a MCQ round. 30 ques in 30 mins consisting of difficult quantitative aptitude questions were to be solved.

1. Puzzle

There are 25 horses among which you need to find out the fastest 3 horses. You can conduct 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 which are required to get the top 3 horses.

Problem approach

The answer is 7.
Explanation:
Divide the horses into group of 5 (A,B,C,D,E) and conduct 5 races to find 5 fastest horses .
Now conduct a race among these to find the fastest horse (Let’s say it’s from group E) .and let’s also assume that fastest horse from group D came 2nd and C came 3rd. Total 6 races done. Now the second fastest horse can be the one who came second in the group E which gave us the fastest horse or the one which came second in 6th race. Similarly the 3rd fastest horse can be
the either fastest horse from group D and C ,or the horses which came 2nd and 3rd in group E or the horse which came second in group D. Conduct a race among these 5 horses and you will get the result in final and 7th race.

Round

Medium

Coding Test - Pen and paper

Duration60 minutes

Interview date21 May 2015

Coding problem2

In this test round, 2 coding questions were given. Either write the code or pseudo code

1. N Queens

Hard

55m average time

35% success

0/120

Asked in companies

You are given an integer 'N'. For a given 'N' x 'N' chessboard, find a way to place 'N' queens such that no queen can attack any other queen on the chessboard.

A queen can be killed when it lies in the same row, or same column, or the same diagonal of any of the other queens. You have to print all such configurations.

Problem approach

DFS can be used to solve this problem. The idea is to place queens in different columns one by one, starting from the leftmost column. As we cannot place 2 queens in the same column, when we place the queen in the nth column and if its valid position, dfs again starting n+1 th column and try placing the next queen in all the rows of n+1th column and find a valid position. If no valid queen row found in n+1th row, backtrack and go to nth column, and change the queen position to the next row and repeat the process.

Try solving now

2. Sort 0 1 2

Easy

22m average time

0/40

Asked in companies

You have been given an integer array/list(ARR) of size 'N'. It only contains 0s, 1s and 2s. Write a solution to sort this array/list.

Note :

Try to solve the problem in 'Single Scan'. ' Single Scan' refers to iterating over the array/list just once or to put it in other words, you will be visiting each element in the array/list just once.

Problem approach

The simple approach is to simply count the number of 0’s, 1’s, and 2’s. Then, place all 0’s at the beginning of the array followed by 1’s and 2's. The time complexity of this approach would be O(n) and space complexity O(1).
However, the approach requires two traversals of the array. The question can also be solved in a single scan of the array by maintaining the correct order of 0’s, 1’s, and 2’s using variables.
We divide the array into four groups using three pointers. Let us name these pointers as low, mid, and high.
1. a[0…low-1] only zeroes
2. a[low..mid-1] only ones
3. a[mid…high] unknown
4. a[high+1..n-1] only twos
Algorithm :
1. Initialise three pointers low = 0, mid = 0 and high = n -1
2. Run a while loop until mid<=high :
2.1 If (a[mid] ==0), then swap the element with the element low and increment low and mid (low++ and mid++).
2.2 If (a[mid] ==1), then increment mid (mid++).
2.3 If (a[mid] ==2), then swap it with an element in high range and decrement high (high--).

Try solving now

Round

Easy

Face to Face

Duration60 minutes

Interview date21 May 2015

Coding problem2

This was a technical round with questions on DSA.

1. Reverse Words In A String

Easy

10m average time

90% success

0/40

Asked in companies

You are given a string 'str' of length 'N'.

Your task is to reverse the original string word by word.

There can be multiple spaces between two words and there can be leading or trailing spaces but in the output reversed string you need to put a single space between two words, and your reversed string should not contain leading or trailing spaces.

Example :

If the given input string is "Welcome to Coding Ninjas", then you should return "Ninjas Coding to Welcome" as the reversed string has only a single space between two words and there is no leading or trailing space.

Problem approach

Steps :
1. Reverse the individual words of the given string one by one.
2. Then, reverse the whole string from start to end to get the desired output.
Time Complexity : O(n)

Try solving now

2. Circularly Linked

Easy

15m average time

85% success

0/40

Asked in companies

You are given the head of a linked list containing integers, You need to find out whether the given linked list is circular or not.

Note :

1. A linked list is said to be circular if it has no node having its next pointer equal to NULL and all the nodes form a circle i.e. the next pointer of last node points to the first node.
2. An empty linked will also be considered as circular.
3. All the integers in the linked list are unique.
4. In the input, the next pointer of a node with i’th integer is linked to the node with data (i+1)’th integer (If (i+1)’th node exists). If there is no such (i+1)’th integer then the next pointer of such node is set to NULL.

Problem approach

The idea is to store head of the linked list and traverse it. If we reach NULL, linked list is not circular. If reach head again, linked list is circular.

Pseudocode:
isCircular(Node head)
{
// An empty linked list is circular
if (head is NULL)
return true

// Next of head
declare a node nd pointing to next of head

// This loop would stop in both cases (1) If Circular (2) Not circular
while (nd is not NULL and nd is not head) do :
update nd to next of nd (nd -> next)

// If loop stopped because of circular condition
return (node == head)
}

Try solving now

Round

Easy

HR Round

Duration30 minutes

Interview date21 May 2015

Coding problem1

HR round with typical behavioral problems.

1. Basic HR Questions

Q1. Tell me about your self, your family background
Q2. What is your dream company ?
Q3. Why do you want to join MAQ ?
Q4. What skills of yours makes you suitable for this job ?

Problem approach

Tip 1 : The cross questioning can go intense some time, think before you speak.

Tip 2 : Be open minded and answer whatever you are thinking, in these rounds I feel it is important to have opinion.

Tip 3 : Context of questions can be switched, pay attention to the details. It is okay to ask questions in these round, like what are the projects currently the company is investing, which team you are mentoring. How all is the work environment etc.