Software Developer Intuit interview experience

Interview rounds

Round

Hard

Online Coding Interview

Duration60 minutes

Interview date10 May 2017

Coding problem2

10 MCQs and 3 programming questions are given.
MCQs included questions asking the outputs of code snippets, algorithmic complexities.
Programming problems are tough.
I was able to solve only 1 problem completely and 1 partially.
Partial score is given for passing some test cases.
Tips: For programming problems code any solution(even brute force) if you are not able to come up with exact solution

1. LCA Of Binary Tree

Moderate

10m average time

90% success

0/80

Asked in companies

You have been given a Binary Tree of distinct integers and two nodes ‘X’ and ‘Y’. You are supposed to return the LCA (Lowest Common Ancestor) of ‘X’ and ‘Y’.

The LCA of ‘X’ and ‘Y’ in the binary tree is the shared ancestor of ‘X’ and ‘Y’ that is located farthest from the root.

Note :

You may assume that given ‘X’ and ‘Y’ definitely exist in the given binary tree.

For example :

For the given binary tree

LCA of ‘X’ and ‘Y’ is highlighted in yellow colour.

Problem approach

The recursive approach is to traverse the tree in a depth-first manner. The moment you encounter either of the nodes node1 or node2, return the node. The least common ancestor would then be the node for which both the subtree recursions return a non-NULL node. It can also be the node which itself is one of node1 or node2 and for which one of the subtree recursions returns that particular node.
Pseudo code :
LowestCommonAncestor(root, node1, node2) {
if(not root)
return NULL
if (root == node1 or root == node2)
return root
left = LowestCommonAncestor(root.left, node1, node2)
right = LowestCommonAncestor(root.right, node1, node2)
if(not left)
return right
else if(not right)
return left
else
return root
}

Try solving now

2. Design a stack that supports getMin() in O(1) time and O(1) extra space

Moderate

15m average time

85% success

0/80

Asked in companies

Create a stack data structure that allows operations such as push (adding an element), pop (removing the top element), top (retrieving the top element), and also provides a way to retrieve the minimum element in constant time.

Implement the following public functions :

1. push(data) :
This function should take one argument of type integer. It pushes the element into the stack and returns nothing.

2. pop() :
It pops the element from the top of the stack and returns nothing.

3. top() :
It returns the element being kept at the top of the stack.

4.  getMin() :
It returns the smallest element present in the stack.

Operations Performed on the Stack:

Query-1(Denoted by an integer 1): Pushes integer data to the stack. (push function)

Query-2(Denoted by an integer 2): Pops the data kept at the top of the stack. (pop function)

Query-3(Denoted by an integer 3): Fetches and returns the data being kept at the top of the stack. (top function)

Query-4(Denoted by an integer 4): Returns the smallest element present in the stack. (getMin() function)

Problem approach

Two stacks can be used to implement a min Stack. One stack can be used to store the actual stack elements and the other auxiliary stack is used to store minimum values. The top element of the auxiliary stack will always store the minimum at that point of time. Let us see how push() and pop() operations work.
Push(int x)
1) push x to the original stack (the stack with actual elements)
2) compare x with the top element of the auxiliary stack. Let the top element be y.
…..a) If x < y then push x to the auxiliary stack.
…..b) If x > y then push y to the auxiliary stack.
int Pop()
1) pop the top element from the auxiliary stack. This is necessary to update the auxiliary stack.
2) pop the top element from the original stack and return it.
int getMin()
1) Return the top element of the auxiliary stack.

The time Complexity for push, pop and getMin operation is O(1) and auxiliary space is O(n).

Try solving now

Round

Easy

Face to Face

Duration60 minutes

Interview date15 May 2017

Coding problem2

This was a technical interview round. I was able to solve all questions.

1. Number Of Pairs With Given Sum

Moderate

39m average time

60% success

0/80

Asked in companies

You have been given an integer array/list(arr) and a number 'Sum'. Find and return the total number of pairs in the array/list which when added, results equal to the 'Sum'.

Note:

Given array/list can contain duplicate elements.

(arr[i],arr[j]) and (arr[j],arr[i]) are considered same.

Problem approach

The problem can be solved in O(n) time using hashing. Use a hash map to check for the current array value. Check if target sum – current value exists in the map or not. If it exists, that means a pair with sum equal to target sum exists in the array.

Try solving now

2. OOPS Question

Explain all oops concepts.

Problem approach

The building blocks of OOPs are :
1.Classes & Objects : An Object can be defined as an entity that has a state and behavior. Class is basically a collection of objects which act as building blocks.
2.Abstraction : It helps in displaying the essential features without showing the details or the functionality to the user. It avoids unnecessary information or irrelevant details and shows only that specific part which the user wants to see.
3.Encapsulation: The wrapping up of data and functions together in a single unit is known as encapsulation. It can be achieved by making the data members' scope private and the member function’s scope public to access these data members.
4.Inheritance: Inheritance is the process in which two classes have an is-a relationship among each other and objects of one class acquire properties and features of the other class. The class which inherits the features is known as the child class, and the class whose features it inherited is called the parent class.
5.Polymorphism: Polymorphism is defined as the ability to take more than one form. It is a feature that provides a function or an operator with more than one definition. It can be implemented using function overloading, operator overload, function overriding, virtual function

Round

Hard

Face to Face

Duration60 minutes

Interview date15 May 2017

Coding problem3

I couldn't answer 3rd and 4th questions properly but gave some suboptimal solutions.
Tips: Answer multiple solutions trading off time and space complexities

1. Math Question

Calculate definite integral of a function in limits a to b

Problem approach

Boole’s rule can be used to calculate the approximate integral value of a given function f(x). Boole’s formula is given by:
[x1 to x5 ] f(x)dx = (2/45 * h * (7*f1 + 32*f2 + 12*f3 + 32*f4 + 7*f5) ) + Error term
The following steps can be followed to compute the integral of some function f(x) in the interval (a, b):
1.Find the value of n , which is the number of parts the interval is divided into.
2.Calculate the width, h = (b – a)/4.
3.Calculate the values of x1 to x5 as : X1 = a , x2 = a + h, x3 = a + 2*h , x4 = a + 3*h , x5 = a + 4*h
4.Consider y = f(x). Now find the values y1, y2, y3, y4 and y5 for the corresponding x1, x2, x3, x4 and x5 values.
5.Substitute all the values in Boole’s rule to calculate the integral value.

2. Closest Distance Pair

Easy

20m average time

0/40

Asked in companies

You are given an array containing 'N' points in the plane. The task is to find out the distance of the closest points.

Note :

Where distance between two points (x1, y1) and (x2, y2) is calculated as [(x1 - x2) ^ 2] + [(y1 - y2) ^ 2].

Problem approach

One direct solution could be to calculate the distance of all points from the given point, sort the distances and then choose the point with minimum distance.

Try solving now