Software Developer Intuit interview experience

Interview rounds

Round

Medium

Coding Test - Pen and paper

Duration60 minutes

Interview date18 May 2015

Coding problem4

This was a written round. Proper code with correct syntax to be written on paper.
There were 4 questions to be solved in 1 hour. Some questions needed test cases and time complexity to be answered as well.

1. Add two number as linked lists

Moderate

10m average time

80% success

0/80

Asked in companies

You have been given two singly Linked Lists, where each of them represents a positive number without any leading zeros.

Your task is to add these two numbers and print the summation in the form of a linked list.

Example:

If the first linked list is 1 -> 2 -> 3 -> 4 -> 5 -> NULL and the second linked list is 4 -> 5 -> NULL.

The two numbers represented by these two lists are 12345 and 45, respectively. So, adding these two numbers gives 12390. 

So, the linked list representation of this number is 1 -> 2 -> 3 -> 9 -> 0 -> NULL.

Problem approach

Elementary math can be used to solve this problem. For binary numbers, rules of addition need to be followed :
0 + 0 = 0
0 + 1 = 1
1 + 0 = 1
1 + 1 =10
The approach would be to consider node by node and calculate the sum digit by digit and keep track of the carry in a temporary variable. If after processing the most significant digit, the carry is non-zero, then make a new node for carry.
Steps:
1. Traverse the two linked lists.
2. In each iteration, add the numbers in the nodes of the linked lists
3. Find out the carry from the above rules to be added in the next iteration.
4. If the lists are unequal, then the smaller one will end before the longer. In this case, we will put only the remaining nodes of the longer list in the resultant list
The time complexity will be O(m+n) since we are iterating both the lists only once.

Try solving now

2. Minimum Number Of Operations To Reach X.

Moderate

25m average time

60% success

0/80

Asked in companies

You have been given an array/list ‘ARR’ of integers consisting of ‘N’ integers. You are also given an integer ‘X’. In one operation, you can either remove the leftmost or the rightmost element and add that to the sum of removed elements so far. Your task is to return the minimum number of operations such that the sum of removed elements becomes exactly ‘X’. If it is not possible return -1.

For Example :

Let’s say you have an array/list [1, 3, 5, 3] and ‘X’ is 7. 
We can first remove the rightmost element i.e. 3. The array becomes [1,3,5]. In the next step, we can remove the leftmost element i.e 1. The array becomes [3,5] and the sum of removed elements so far becomes 4. In the next step, we can remove the leftmost element i.e 3. The array becomes [5] and the sum of removed elements so far is 7. We have reached our target X i.e 7. Therefore the minimum number of operations to reach ‘X’ is 3.

Problem approach

A recursive approach can be followed to solve this question.
Make a recursive function with three parameters : current number , target and the current string (will store the sequence of operations). We start from 1 (As the current number) and "1" as the current string and try sequence of operations (multiplying by 3 or adding 5) and make next recursive calls after updating number and string.
There would be two base cases :
1. If the target number is achieved, then return the string formed.
2. If the current number is greater than target number, then target can never be achieved. In this case, return "Not Possible".

Try solving now

3. Product Of Array Except Self

Easy

26m average time

0/40

Asked in companies

You have been given an integer array/list (ARR) of size N. You have to return an array/list PRODUCT such that PRODUCT[i] is equal to the product of all the elements of ARR except ARR[i]

Note :

Each product can cross the integer limits, so we should take modulo of the operation. 

Take MOD = 10^9 + 7 to always stay in the limits.

Follow up :

Can you try solving the problem in O(1) space?

Problem approach

A direct solution to this question is to calculate the product of every element in the array. Then create a result array of the same length as the given array, such that for each element in result result[i] = product / arr[i]. This approach has a O(n) time complexity.
This question can also be solved without using division operator. On observing carefully,
For all i in the middle of the given array array (i.e., not at either end):
results[i] = arr[0] * ...... * arr[i-1] * arr[i + 1] * ...... * arr[n - 1]
Therefore, to get results[i], for any i, we calculate the product everything to the left and to the right of arr[i].
So, for implementation:
1. We make two arrays, prefix and suffix arrays. Prefix[i] will store the product of all elements from 0 to i-1. And suffix[i] will store the product of all elements from i+1 to n-1.
2. Construct a product array and traverse the array from start to end.
3. For every index i the output will be prefix[i] * suffix[i], the product of the array element except that element.

Try solving now

4. Sort a Stack

Easy

10m average time

90% success

0/40

Asked in companies

You’re given a stack consisting of 'N' integers. Your task is to sort this stack in descending order using recursion.

We can only use the following functions on this stack S.

is_empty(S) : Tests whether stack is empty or not.
push(S) : Adds a new element to the stack.
pop(S) : Removes top element from the stack.
top(S) : Returns value of the top element. Note that this function does not remove elements from the stack.

Note :

1) Use of any loop constructs like while, for..etc is not allowed. 
2) The stack may contain duplicate integers.
3) The stack may contain any integer i.e it may either be negative, positive or zero.

Problem approach

This problem can be solved using a temporary stack. Push and pop operations are carried out between the input stack and the temporary stack in such a way that the temporary stack contains the sorted input stack.
Steps :
1. Create a temporary stack say temp_stack.
2. Repeat the below steps until the input stack is not empty :
2.1 Pop an element from input stack , say ele.
2.2 While temp_stack is not empty and top of the temp_stack < eke, pop elements from temo_stack and push it to
the input stack
2.3 Push ele to the temp_stack
3. Return the temp_stack at last.
Time Complexity : O(N^2)
Space Complexity : O(N)

Try solving now

Round

Easy

Face to Face

Duration30 minutes

Interview date19 May 2015

Coding problem0

This was NOT an elimination round.
It was a problem solving team exercise to understand their way of working. The interviewers were making notes though during the exercise, don’t know if it affected our selection.

Round

Easy

Face to Face

Duration60 minutes

Interview date19 May 2015

Coding problem1

General questions based on resume, was asked to explain my internship project.
He asked questions on my written round. Asked me to find the bug in my code for 1st problem. He was extremely happy with me when I gave the correct answer.
He asked me for the code for the last problem since I hadn’t solved it.
Asked to reverse linked list using recursion, since I said I did by iteration earlier.
He had written code of second problem, I had to find bugs in it.
Discussion on quality engineering and developer profiles.

1. 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?

Problem approach

This can be solved both: recursively and iteratively.
The recursive approach is more intuitive. First reverse all the nodes after head. Then we need to set head to be the final node in the reversed list. We simply set its next node in the original list (head -> next) to point to it and sets its next to NULL. The recursive approach has a O(N) time complexity and auxiliary space complexity.
For solving the question in constant auxiliary space, iterative approach can be used. We maintain 3 pointers, current, next and previous, abbreviated as cur, n and prev respectively. All the events occur in a chain.
1. Assign prev=NULL, cur=head .
2. Next, repeat the below steps until no node is left to reverse:
1. Initialize n to be the node after cur. i.e. (n=cur->next)
2. Then make cur->next point to prev (next node pointer).
3. Then make prev now point to the cur node.
4. At last move cur also one node ahead to n.
The prev pointer will be the last non null node and hence the answer.

Try solving now

Round

Easy

HR Round

Duration30 minutes

Interview date19 May 2015

Coding problem0

This was more of a general discussion. She told me about what quality engineers do, how their role is more powerful. Asked me how you would test the Google page.
She was extremely impressed by my resume and asked me questions about my electives. She told me in this round itself that I was selected, only need to wait for the official announcement.