Arcesium Software Developer Intern Interview Questions, Process, and Tips

Round duration - 45 minutes
Round difficulty - Medium

2 coding questions were given to solve in 45 minutes.

Q1. Left View Of a Binary Tree
You have been given a binary tree of integers. You are supposed to find the left view of the binary tree. The left view of a binary tree is the set of all nodes that are visible ...read more
Ans. 
A level order traversal based solution can be presented here. For each level, we need to print the first node i.e. the leftmost node of that level.
Steps :
1. Make a queue of node type and push the root node in the queue. 
2. While the queue is not empty, do :
2.1 Determine the current size of the queue. 
2.2 Run a for loop to traverse all nodes of the current level and do :
2.2.1 Remove the topmost node from the q...read more
Answered by CodingNinjas
View 2 more answers
Q2. Number of Islands
You have been given a non-empty grid consisting of only 0s and 1s. You have to find the number of islands in the given grid.
An island is a group of 1s (representing land) connected hor...read more
Ans. 
The question boils down to finding the number of connected components in an undirected graph. Now comparing the connected components of an undirected graph with this problem, the node of the graph will be the “1’s” (land) in the matrix. 
BFS or DFS can be used to solve this problem. In each BFS call, a component or a sub-graph is visited. We will call BFS on the next un-visited component. The number of calls to BFS...read more
Answered by CodingNinjas
View 2 more answers

Round duration - 60 minutes
Round difficulty - Medium

This was a 60 min technical interview round. The interviewer asked me to code 2 programming questions. 
Tip : Practice more to clear DSA problems. Medium level questions will be enough to clear the rounds.

Q1. Topological Sort
A Directed Acyclic Graph (DAG) is a directed graph that contains no cycles.
Topological Sorting of DAG is a linear ordering of vertices such that for every directed edge from vertex ‘u’...read more
Ans. 
Topological sorting of vertices of a Directed Acyclic Graph is an ordering of the vertices v1,v2,v3.....vn in such a way, that if there is an edge directed towards vertex vj from vertex vi , then vi comes before vj. Modified DFS can be used to solve topological sort problem. A stack can be used to implement it. Steps :
1. Make a stack to store the nodes and a Boolean array to mark all visited nodes initialized to false....read more
Answered by CodingNinjas
View 2 more answers
Q2. N-th Node From The End
You are given a Singly Linked List of integers. You have to find the N-th node from end.
For Example
If the given list is (1 -> -2 -> 0 -> 4) and N=2:
Then the 2nd nod...read more
Ans. 
A direct approach is to traverse the entire linked list and calculate its length. Traverse the list again and return the (length-N+1) node. But this approach involves two traversals of the linked list. 
To further optimize the solution, the question can be solved in one traversal only. Two pointers can be used here. Steps :
1. Initialize both the slow pointer and the fast pointer to the head node.
2. First, move fast...read more
Answered by CodingNinjas
View 2 more answers

Round duration - 45 minutes
Round difficulty - Medium

It was an online coding round where we were supposed to solve 2 coding questions in 45 minutes.

Q1. Maximum meetings
You are given the schedule of N meetings with their start time Start[i] and end time End[i]. But you have only 1 meeting room. So, you need to tell the meeting numbers you can organize in ...read more
Ans. 
Greedy approach can be applied to solve this problem. We sort the start and end time pairs for each meeting on the basis of the end time. Then we compare if the next meeting's start time is greater than the previous meeting's end time. If the start time is greater, we can count this meeting and we increase our meeting counter otherwise this meeting can't take place. In this manner, we traverse through all the meeting p...read more
Answered by CodingNinjas
View 1 more answer
Q2. Connect N Ropes With Minimum Cost
You have been given 'N' ropes of different lengths, we need to connect these ropes into one rope. The cost to connect two ropes is equal to sum of their lengths. W...read more
Ans. 
Concept of min heap can be applied here. In each iteration, we need to pick the rope with minimum length because the value picked first will be included in the final answer multiple times. Hence, for minimum cost, we pick the longer length ropes later. 
Approach :
First of all, build minHeap (priority queue) from the given array of rope length. 
In each iteration:
1) Extract two ropes with minimum length from the...read more
Answered by CodingNinjas
View 2 more answers

Round duration - 60 minutes
Round difficulty - Medium

The interview was conducted online. The interviewer asked me 2 programming questions and questions on OOPS concepts.

Q1. Bottom View Of Binary Tree
Given a binary tree, print its bottom view from left to right. Assume, the left and the right child make a 45-degree angle with the parent.
A binary tree is a tree in which eac...read more
Ans. 
The basic idea is to use modified pre-order traversal. In this modified pre-order traversal, we keep track of horizontal distance of the node being visited from the root. We also keep track of height of that node. During this traversal, we use an ordered map that stores node's horizontal distance as key and value as tuple (current node's value, current node's level) if the node being visited is the bottommost node seen...read more
Answered by CodingNinjas
View 3 more answers
Q2. Serialize/Deserialize The Binary Tree
You have been given a binary tree of integers. You are supposed to serialize and deserialize (refer to notes) the given binary tree. You can choose any algorithm to se...read more
Ans. 
DFS can be used for serializing and de-serializing. Process root node and then make recursive calls for left and right child.
For serializing the tree into a list : 
1. If node is null, store -1 in list to denote a null link. Return. 
2. Store the data at current node in list.
3. Call function recursively for left and right subtrees.
4. Return the list.
If we serialize using preorder traversal, apply the same preor...read more
Answered by CodingNinjas
View 1 more answer
Q3. OOPS Question
Virtual destructors in C++
Ans. 
Using a virtual destructor, we can release the memory allocated by a derived class object or instance. In addition, we can delete instances of the derived class using a base class object pointer. The base class destructor uses the virtual keyword so that both the base class and the derived class destructor will be called at run time. However, the derived class will be called first and then the base class to free up the
Answered by CodingNinjas
Add your answer

Round duration - 45 minutes
Round difficulty - Hard

Timing (Between 6pm -7pm)
Environment was friendly and 2 coding questions were given.

Q1. Connect N Ropes With Minimum Cost
You have been given 'N' ropes of different lengths, we need to connect these ropes into one rope. The cost to connect two ropes is equal to sum of their lengths. W...read more
Ans. Brute Force Approach
Clearly, the rope which is picked up first will be having its length included more than once in the final cost. If we pick a rope of larger length earlier, then we will be adding some extra cost to our final result.
So, the idea is to pick ropes of smaller lengths initially to minimize the impact on our final cost.
So, each time we will be finding two smallest ropes, connecting them and
adding the resu...read more
Answered by CodingNinjas
View 1 more answer
Q2. Optimize Memory Usage
Alex has a computer with ‘K’ memory spaces. He has a list of ‘N’ different document downloads that he would like to do, each of which consumes some unique memory usage. He also has ‘M...read more
Ans. Brute Force
Firstly, we will check all the possible pairs exhaustively to find out the maximum permitted memory usage. Then, we will insert all optimal pairs into an array and return it.

 
The steps are as follows:
• Initialize max_usage as the largest number less than or equal to ‘K’ from either ‘game’ or ‘ download’ array. This is to check the corner case where only a game or download is chosen.
• Then we run a loop ‘i’ ...read more
Answered by CodingNinjas
View 1 more answer

Round duration - 40 minutes
Round difficulty - Medium

Timing (6pm -7 pm)
Environment was user friendly
In first 10-15 minutes He asked my current company’s work and some behavioral questions. Then he jumped to coding problems

Q1. Spiral Order Traversal of a Binary Tree
You have been given a binary tree of 'N' nodes. Print the Spiral Order traversal of this binary tree.
For example
For the given binary tree [1, 2, 3, -1, -...read more
Ans. Level Order Traversal
We can use level order traversal (recursive) to explore all levels of the tree. Also, at each level nodes should be printed in alternating order. 
 
For example - The first level of the tree should be printed in left to the right manner, the Second level of the tree should be printed in right to the left manner, Third again in left to right order and so on
 
So, we will use a Direction v...read more
Answered by CodingNinjas
View 1 more answer

Round duration - 45 minutes
Round difficulty - Hard

Round was scheduled in the early afternoon hours most probably from 1 to 2 on hackerrank.

Q1. BST to greater tree
Given a binary search tree of integers with N number of nodes. Your task is to convert it to a Greater Tree.
A Greater Tree is formed when data of every node of the original BST is ch...read more
Ans. Brute Force
• This is a basic brute force approach, in which for every single node, we will traverse the whole tree to find all the elements which are greater or equal to the current node.
• First, we will store all the nodes in an array or a similar data structure.
• Further, we will traverse the tree again and for each node of the tree, we will loop over the array and find the sum of all the elements which are greater than or...read more
Answered by CodingNinjas
View 2 more answers
Q2. Ninja and BInary String
Ninja is given a binary string ‘S’ of size ‘N’ by his friend, the task is to check if the binary string ‘S’ can be sorted in decreasing order by removing any number of the non-adjac...read more
Ans. Greedy
The idea here is to use the fact that while traversing from the end if we encounter 2 consecutive 1s then we can sort the string in decreasing order if and only if after the index which we have found 2 consecutive 1s we have-
• 0-1,1-0 adjacent pair characters- In this case, we can sort the string in decreasing order by removing 0’s from the string as they are not adjacent to each other. For example “1101011” we fin...read more
Answered by CodingNinjas
Add your answer

Round duration - 40 minutes
Round difficulty - Medium

This round was conducted on Code Share platform. I was shared the invitation link one day prior to the interview and also was told the name of my interviewer. I looked at the profile of the interviewer at linked.in and got a better understanding of what kind of person he was and prepared accordingly. The round was scheduled at 3 :00 pm on 25th August and I was eagerly waiting for the clock hands to reach 3 o'clock since morning and finally I went in front of him after wearing a white shirt and a black coat over it along with a tie over it.

Q1. Spiral Order Traversal of a Binary Tree
You have been given a binary tree of 'N' nodes. Print the Spiral Order traversal of this binary tree.
For example
For the given binary tree [1, 2, 3, -1, -...read more
Ans. Level Order Traversal
We can use level order traversal (recursive) to explore all levels of the tree. Also, at each level nodes should be printed in alternating order. 
 
For example - The first level of the tree should be printed in left to the right manner, the Second level of the tree should be printed in right to the left manner, Third again in left to right order and so on
 
So, we will use a Direction v...read more
Answered by CodingNinjas
View 1 more answer
Q2. Operating System Questions
Producer consumer problem and it's possible solution?
What is virtual memory and physical memory?
What is garbage collector?
Difference b/w thread and process.
Add your answer