SDE - 1 Intuit interview experience | Anonymous

Interview rounds

Round

Medium

Face to Face

Duration60 minutes

Interview date16 Nov 2015

Coding problem4

Technical round that lasted for around 60 minutes. The interviewer asked questions on data structures and OOPS concepts.

1. Permutations of a String

Moderate

15m average time

85% success

0/80

Asked in companies

You are given a string 'STR' consisting of lowercase English letters. Your task is to return all permutations of the given string in lexicographically increasing order.

String A is lexicographically less than string B, if either A is a prefix of B (and A ≠ B), or there exists such i (1 <= i <= min(|A|, |B|)), that A[i] < B[i], and for any j (1 <= j < i) A[i] = B[i]. Here |A| denotes the length of the string A.

For example :

If the string is “bca”, then its permutations in lexicographically increasing order are { “abc”, “acb”, “bac”, “bca”, “cab”, “cba” }.

Note:

Given string contains unique characters.

Problem approach

Trie data structure can be used to solve this question.
Firstly, construct a trie from the words
The second is, Add the letters to a has hset or a hash map if duplicate letters are allowed.
Three, navigate the trie, removing each letter from the set when it matches, then recurse with the next trie node and then add the letter back to the set, applying backtracking.

Try solving now

2. Greatest Common Divisor

Easy

15m average time

85% success

0/40

Asked in companies

You are given two numbers, ‘X’ and ‘Y’. Your task is to find the greatest common divisor of the given two numbers.

The Greatest Common Divisor of any two integers is the largest number that divides both integers.

For Example:

You are given ‘X’ as 20 and ‘Y’ as 15. The greatest common divisor, which divides both 15 and 20, is 5. Hence the answer is 5.

Problem approach

To find GCD of numbers more than two, it can be calculated by repeatedly taking the GCDs of pairs of numbers.
gcd(a, b, c) = gcd(a, gcd(b, c))
= gcd(gcd(a, b), c)
= gcd(gcd(a, c), b)
To calculate gcd of two numbers, Euclid's algorithm can be used.
Pseudo Code of the Algorithm-
Step 1: Let a, b be the two numbers
Step 2: a % b = R
Step 3: Let a = b and b = R
Step 4: Repeat Steps 2 and 3 until a% b > 0.
Step 5: GCD = b

Try solving now

3. OOPS Question

Difference between C, C++ and Java

Problem approach

1. The C programming language is a procedural language type while C++ is an object-oriented programming language type. Java is a Pure Object Oriented language.
2. C programming follows a top to down programming approach that focuses on the steps rather than the data. C++ follows a bottom-to-top approach that focuses on data rather than the overall procedure. Java follows a bottom-up approach.
3. C and C++ are platform dependent while Java is a platform independent language.

4. OOPS Question

Virtual keyword in C++

Problem approach

'Virtual' is a keyword preceding the normal declaration of a function. When the function is made virtual, C++ determines which function is to be invoked at the runtime based on the type of the object pointed by the base class pointer.

Round

Medium

Face to Face

Duration60 minutes

Interview date16 Nov 2015

Coding problem3

Technical round that lasted for around 60 minutes. The interviewer asked questions on data structures and question related to cloud computing(cloud computing was listed on my resume) .

1. LRU Cache Implementation

Moderate

25m average time

65% success

0/80

Asked in companies

Design and implement a data structure for Least Recently Used (LRU) cache to support the following operations:

1. get(key) - Return the value of the key if the key exists in the cache, otherwise return -1.

2. put(key, value), Insert the value in the cache if the key is not already present or update the value of the given key if the key is already present. When the cache reaches its capacity, it should invalidate the least recently used item before inserting the new item.

You will be given ‘Q’ queries. Each query will belong to one of these two types:

Type 0: for get(key) operation.
Type 1: for put(key, value) operation.

Note :

1. The cache is initialized with a capacity (the maximum number of unique keys it can hold at a time).

2. Access to an item or key is defined as a get or a put operation on the key. The least recently used key is the one with the oldest access time.

Problem approach

Structure of an LRU Cache :
1) In practice, LRU cache is a kind of Queue — if an element is re accessed, it goes to the end of the eviction order
2) This queue will have a specific capacity as the cache has a limited size. Whenever a new element is brought in, it is added at the head of the queue. When eviction happens, it happens from the tail of the queue.
3) Hitting data in the cache must be done in constant time, which isn't possible in Queue! But, it is possible with Hash Map data structure
4) Removal of the least recently used element must be done in constant time, which means for the implementation of Queue, we'll use DoublyLinkedList instead of SingleLinkedList or an array.

LRU Algorithm :
The LRU algorithm is pretty easy! If the key is present in HashMap, it's a cache hit; else, it's a cache miss.
We'll follow two steps after a cache miss occurs:
1) Add a new element in front of the list.
2) Add a new entry in HashMap and refer to the head of the list.

And, we'll do two steps after a cache hit:
1) Remove the hit element and add it in front of the list.
2) Update HashMap with a new reference to the front of the list.

Try solving now

2. Delete Node In A Linked List

Easy

15m average time

80% success

0/40

Asked in companies

You are given a Singly Linked List of integers and a reference to the node to be deleted. Every node of the Linked List has a unique value written on it. Your task is to delete that node from the linked list.

A singly linked list is a linear data structure in which we can traverse only in one direction i.e. from Head to Tail. It consists of several nodes where each node contains some data and a reference to the next node.

Note:

• The reference to the head of the linked list is not given.
• The node to be deleted is not a tail node.
• The value of each node in the Linked List is unique.
• It is guaranteed that the node to be deleted is present in the linked list.

A sample Linked List-

Problem approach

The simple solution is to traverse the entire linked list till you reach the node to be deleted. And delete the node. But in this question, only the pointer to the node to be deleted is given.
So, we can achieve the same effect by instead removing the next node after copying its data into the node that we were asked to delete.
Steps :
1. Find out the next node of the pointer to the node that we have.
2. Copy the data from the next node to the node to be deleted.
3. Fix the link and delete the next node

Try solving now

3. Technical Question

Difference between IAAS, PAAS, SAAS

Problem approach

1. IaaS is an acronym for Infrastructure As A Service. PaaS is an acronym for Platform As A Service. SaaS is an acronym for Software As A Service.
2. The IaaS service provides its users with access to various resources like virtual storage and virtual machines. Using the PaaS services, users can get access to a runtime environment (for the development and deployment of applications and tools). The SaaS services give access to all of their services to the end-users, where it’s application hosting, storage, or any other services.
3. The network architects primarily use the IaaS. Developers mainly make use of PaaS. An end-user generally uses SaaS.
4. The IaaS is a service model. It functions to provide various visualized computing resources all over the internet. PaaS is a cloud computing model. It mainly delivers the tools required for developing various applications. SaaS is a service model for cloud computing services. They mainly host various software and make them available for the clients.

Round

Easy

Face to Face

Duration60 minutes

Interview date16 Nov 2015

Coding problem3

Technical round that lasted for around 60 minutes. The interviewer asked questions on data structures and question related to networking.

1. Insertion Sort in Linked List

Easy

10m average time

90% success

0/40

Asked in companies

You are given an arbitrary linked list consisting of 'N' nodes having integer values. You need to perform insertion sort on the linked list and print the final list in sorted order.

In other words, you are given a singly linked list, you need to perform insertion sort on it.

Insertion Sort is a sorting algorithm that removes one element from the input data, finds the location it belongs within the sorted list and inserts it there. It repeats until no input elements remain.

Problem approach

Steps :
1) If Linked list is empty then make the node as head and return it.
2) If the value to be inserted is smaller than the value of the head, then insert the node at the beginning and make it head.
3) Run a while loop and find the appropriate node after which the input node is to be inserted. To find the appropriate node start from the head, keep moving until you reach a node who's value is greater than the input node. Insert the node just before that node.
4) Insert the node after the appropriate node found in step 3.

Try solving now

2. Find Duplicates In Array

Easy

15m average time

90% success

0/40

Asked in companies

You are given an array/list 'ARR' consisting of N integers, which contains elements only in the range 0 to N - 1. Some of the elements may be repeated in 'ARR'. Your task is to find all such duplicate elements.

Note:

1. All the elements are in the range 0 to N - 1.
2. The elements may not be in sorted order.
3. You can return the duplicate elements in any order.
4. If there are no duplicates present then return an empty array.

Problem approach

One approach could be to use a Hash map. Store the count of each element of array in a hash table and later check in Hash table if any element has count more than 1 and print those elements. This approach would have a time and space complexity as O(n).
To solve the question in constant space, array can be used as a hash map. While Traversing the array, for every element a , increase the value at index [a%n] by n. So, for every arr[i], arr[i] would be greater than N only if i has appeared more than once. Thus, after processing the array, traverse the array again and print all elements where arr[i]/n > 1.

Try solving now

3. Technical Question

Difference between Web 2.0 and Web 1.0

Problem approach

1. Web 2.0 is very dynamic while Web 1.0 is static.
2. Web 1.0 is mostly for browsing content while Web 2.0 allows for more tasks.
3. The flow of information in Web 1.0 is linear while that of Web 2.0 is not.

Round

Easy

HR Round

Duration40 minutes

Interview date16 Nov 2015

Coding problem2

The Interviewer asked me questions to know more about me. He also asked a puzzle.

1. Basic HR Questions

1. Explain a project listed on my resume.
2. A thorough scan of my resume and in depth coverage of all the projects and technologies listed on it
3. Which domain would I be interested to work in?

Problem approach

Tip 1 : Be sure to do your homework on the organization and its culture before the interview.
Tip 2 : Employers want to understand how you use your time and energy to stay productive and efficient. Be sure to emphasize that you adhere to deadlines and take them seriously.
Tip 3 : Talk about a relevant incident that made you keen on the profession you are pursuing and follow up by discussing your education. Know your resume well.

2. Puzzle

Find the fastest 3 horses

Problem approach

1. Divide the 25 horses into groups of 5, and race the horses in each group. (5 races)
2. Take the winner from each group and race those 5 horses. The winner of this race is the fastest horse overall. (1 race)
Notation : Label the 5 groups from step one as a, b, c, d, e to correspond to horses finishing 1st, 2nd, 3rd, 4th, and 5th in step two. Write a subscript to identify the order that the horse finished in the group, so a2 means the horse that finished 2nd place in group a.
3. Do one more race with horses a2, a3, b1, b2, c1. That is, race the second and third fastest from group a, the fastest and second fastest from group b, and the fastest from group c. The top 2 horses in this race are the 2nd and 3rd fastest horses overall. (1 race)

SDE - 1

Interview preparation journey

Interview rounds

1. Permutations of a String

You are given a string 'STR' consisting of lowercase English letters. Your task is to return all permutations of the given string in lexicographically increasing order.

String A is lexicographically less than string B, if either A is a prefix of B (and A ≠ B), or there exists such i (1 <= i <= min(|A|, |B|)), that A[i] < B[i], and for any j (1 <= j < i) A[i] = B[i]. Here |A| denotes the length of the string A.

For example :

Note:

2. Greatest Common Divisor

You are given two numbers, ‘X’ and ‘Y’. Your task is to find the greatest common divisor of the given two numbers.

The Greatest Common Divisor of any two integers is the largest number that divides both integers.

For Example:

3. OOPS Question

4. OOPS Question

1. LRU Cache Implementation

Design and implement a data structure for Least Recently Used (LRU) cache to support the following operations:

You will be given ‘Q’ queries. Each query will belong to one of these two types:

Note :

2. Delete Node In A Linked List

You are given a Singly Linked List of integers and a reference to the node to be deleted. Every node of the Linked List has a unique value written on it. Your task is to delete that node from the linked list.

A singly linked list is a linear data structure in which we can traverse only in one direction i.e. from Head to Tail. It consists of several nodes where each node contains some data and a reference to the next node.

Note:

A sample Linked List-

3. Technical Question

1. Insertion Sort in Linked List

You are given an arbitrary linked list consisting of 'N' nodes having integer values. You need to perform insertion sort on the linked list and print the final list in sorted order.

In other words, you are given a singly linked list, you need to perform insertion sort on it.

2. Find Duplicates In Array

You are given an array/list 'ARR' consisting of N integers, which contains elements only in the range 0 to N - 1. Some of the elements may be repeated in 'ARR'. Your task is to find all such duplicate elements.

Note:

3. Technical Question

1. Basic HR Questions

2. Puzzle