Software Developer Zoho Corporation interview experience

Interview rounds

Round

Medium

Coding Test - Pen and paper

Duration240 minutes

Interview date24 Nov 2015

Coding problem4

There were 2 tests. The first test consisted of 30 questions, 10 from section 1 based on Aptitude and Logical Reasoning and 20 from section 2 based on OOPS and C/C++.
The second test : I solved 1 problem in C and remaining problems in Java. I used OOPS in better way so it got me additional points.

1. Running Median

Hard

46m average time

50% success

0/120

Asked in companies

You are given a stream of 'N' integers. For every 'i-th' integer added to the running list of integers, print the resulting median.

Print only the integer part of the median.

Problem approach

To solve this question, the concept of heaps can be used. Two heaps can be maintained: a max heap for storing lower half of the numbers and a min heap for storing greater half of the numbers.
Process each element one by one :
Step 1: To add an element to one of the heaps:
Condition : Check if next item is smaller than maxHeap root add it to maxHeap,else add it to minHeap
Step 2: Balance the heaps (after this step heaps will be either balanced or one of them will contain 1 more item)
Condition : If number of elements in one of the heaps is greater than the other by more than 1, remove the root element from the one containing more elements and add to the other one
Step 3: Now to calculate median:
If the heaps contain equal amount of elements;
median = (root of maxHeap + root of minHeap)/2
Else
median = root of the heap with more elements

The time complexity of this approach would be O(nlogn) and auxiliary space complexity is O(n).

Try solving now

2. First non repeating character

Easy

15m average time

80% success

0/40

Asked in companies

Ninja is now bored with numbers and is now playing with characters but hates when he gets repeated characters. Ninja is provided a string, and he wants to return the first unique character in the string.The string will contain characters only from the English alphabet set, i.e., ('A' - 'Z') and ('a' - 'z'). If there is no non-repeating character, print the first character of the string. If there is no non-repeating character, return the first character of the string.

Problem approach

This problem can be solved using the hashing concept. The objective is to run over the string and record how many times each character appears in it in a hash map. Then we run over the string again, this time using the hash map as a reference to see if any of the characters are unique. If the character is unique, return the index.
Time Complexity: O(N)
The above approach requires two traversals of the string. To solve the question in a single traversal only, along with storing the count of a character store the index a particular character was encountered the first time. So when it comes to finding the first non-repeating character, just scan the hash map, instead of the string and return the character with occurrences as 1 and least index in the string.

Try solving now

3. 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 reaccessed, 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 HashMap 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.

Tip : This is a very frequently asked question in interview and its implementation also gets quite cumbersome if you are doing it for the first time so better knock this question off before your SDE-interviews.

Try solving now

4. Split Array With the Same Average

Hard

15m average time

85% success

0/120

Asked in companies

A group of ninjas want to play a game of tag but they can only do that if each team has the same average strength of abilities among the two divided teams. You are given a list (array named ‘strengths’) of the strengths of the group of ninjas represented by numbers (integers). You have to determine whether those ninjas can be regrouped into two different teams such that the average strength of the two teams formed is equal.

Note:

You have to move each ninja of given strength from the given list into two separate teams (list) ‘Team_A’ and ‘Team_B’ such that the average strengths of ‘Team_A’ == ‘Team_B’. There has to be at least one member in each team since they cannot play the game without that.

For Example:

Input : [1, 7, 15, 29, 11, 9]
Output : [9, 15] [1, 7, 11, 29]

Explanation: The average strengths of both the teams is 12

Problem approach

The brute force solution is to run two loops and find subarrays whose averages are equal.
Time Complexity : O(N^2)

An Efficient solution would be to find sum of array elements. Initialize leftsum as zero. Run a loop and find leftsum by adding elements of array. For rightsum, we subtract leftsum from total sum then we find rightsum and find average of leftsum and rightsum as according to their index.

1) Compute sum of all array elements. Let the total sum be "sum"
2) Initialize leftsum = 0.
3) Run a loop for i=0 to n-1.
a) leftsum = leftsum + arr[i]
b) rightsum = sum - leftsum
c) If average of left and right are equal, print the current index as output.

Try solving now

Round

Hard

Face to Face

Duration60 minutes

Interview date24 Nov 2015

Coding problem1

This was a technical round where I was asked 1 DSA problem.

1. Spell Checker

Hard

50m average time

50% success

0/120

Asked in companies

You are given a list of strings, ‘DICTIONARY[]’ that represents the correct spelling of words and a query string ‘QUERY’ that may have incorrect spelling. You have to check whether the spelling of the string ‘QUERY’ is correct or not. If not, then return the list of suggestions from the list ‘DICTIONARY’. Otherwise, return an empty list which will be internally interpreted as the correct string.

Note:

1) The suggested correct strings for the string  ‘QUERY’ will be all those strings present in the ‘DICTIONARY[]’ that have the prefix same as the longest prefix of string ‘QUERY’.

2) The ‘DICTIONARY[]’ contains only distinct strings.

For example:

Given 'DICTIONARY[]' = {“ninja”, “ninjas”, “nineteen”, “ninny”} and query = “ninjk”. Since “ninjk” is not present in the ‘DICTIONARY[]’, it is an incorrect string. The suggested current spellings for “ninjk” are “ninja” and “ninjas”. It is because “ninj” is the longest prefix of “ninjk” which is present as the prefix in ‘DICTIONARY’.

Problem approach

Trie data structure can be used to solve this problem.
The idea is to traverse the array of string, and insert the string into the Trie such that each node of the Trie contains the character of the string and a boolean value to check if the character is the last character of the string or not.
Steps :
• Initialize a Trie, such that each node of the Trie consists of a character of a string and a boolean value to check if the character is the last character of the string or not.
• Traverse the array of strings and insert all the strings into the Trie.
• Finally, traverse the string key. For every ith character, check if the character is present in the Trie or not. If found to be true, then move to the next node of the Trie.
• Otherwise, print all possible strings whose prefix is the string key.

Time Complexity: O(N * M), where M is the maximum length of the string
Auxiliary Space: O(N * 256)

Try solving now

Round

Easy

HR Round

Duration30 minutes

Interview date24 Nov 2015

Coding problem1

HR round with typical behavioral problems.

1. Basic HR Questions

1. Why did not you choose BE?
2. Tell me about Zoho?
3. Tell me about your family
4. If you get more salary in another company, what will you do?
5. What is your aim?
6 Do you have any idea for Higher Studies?
7. Anything you need to ask me?

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.
Tip 4 : Since everybody in the interview panel is from tech background, here too you can expect some technical questions. No coding in most of the cases but some discussions over the design can surely happen.