SDE - 1 Snapdeal interview experience | Anonymous

Interview rounds

Round

Medium

Online Coding Interview

Duration60 minutes

Interview date14 May 2015

Coding problem1

This test had 24 questions, 22 MCQs based on Quantitative Analysis and Technical Output based questions. 2 Questions were DSA based programming questions.

1. The Skyline Problem

Hard

15m average time

85% success

0/120

Asked in companies

You are given 'N' rectangular buildings in a 2-dimensional city. Your task is to compute the skyline of these buildings, eliminating hidden lines return the skyline formed by these buildings collectively. A city's skyline is the outer contour of the silhouette formed by all the buildings in that city when viewed from a distance. The geometric information of each building is given in the array of buildings where BUILDINGS[i] = [LEFT_i, RIGHT_i, HEIGHT_i]:

-> LEFT_i is the x coordinate of the left edge of the ith building.

-> RIGHT_i is the x coordinate of the right edge of the ith building.

-> HEIGHT_i is the height of the ith building.

You may assume all buildings are perfect rectangles grounded on an absolutely flat surface at height 0.

The skyline should be represented as a list of "key points" sorted by their x-coordinate in the form [[x1, y1], [x2, y2], ...]. Each key point is the left endpoint of some horizontal segment in the skyline except the last point in the list, which always has a y-coordinate 0 and is used to mark the skyline's termination where the rightmost building ends. Any ground between the leftmost and rightmost buildings should be part of the skyline's contour.

Note:

There must be no consecutive horizontal lines of equal height in the output skyline. For instance, [...,[2 3], [4 5], [7 5], [11 5], [12 7],...] is not acceptable; the three lines of height 5 should be merged into one in the final output.

As such: [..., [2 3], [4 5], [12 7],...]. 

Also, the buildings are sorted by a non-decreasing order.

For more clarification see sample case 1.

Try solving now

Round

Medium

Coding Test - Pen and paper

Duration60 minutes

Interview date14 May 2015

Coding problem3

3 coding questions were given. Only function to be written (no main())

1. Balanced parentheses

Moderate

10m average time

90% success

0/80

Asked in companies

Given an integer ‘N’ representing the number of pairs of parentheses, Find all the possible combinations of balanced parentheses with the given number of pairs of parentheses.

Note :

Conditions for valid parentheses:
1. All open brackets must be closed by the closing brackets.

2. Open brackets must be closed in the correct order.

For Example :

()()()() is a valid parentheses.
)()()( is not a valid parentheses.

Problem approach

A stack can be used to solve this question.
We traverse the given string s and if we:
1. see open bracket we put it to stack
2. see closed bracket, then it must be equal to bracket in the top of our stack, so we check it and if it is true, we remove this pair of brackets.
3. In the end, if and only if we have empty stack, we have valid string.
Complexity: time complexity is O(n): we put and pop each element of string from our stack only once. Space complexity is O(n).

Try solving now

2. Maximum Subarray Sum

Moderate

25m average time

75% success

0/80

Asked in companies

Given an array of numbers, find the maximum sum of any contiguous subarray of the array.

For example, given the array [34, -50, 42, 14, -5, 86], the maximum sum would be 137, since we would take elements 42, 14, -5, and 86.

Given the array [-5, -1, -8, -9], the maximum sum would be -1.

Follow up: Do this in O(N) time.

Problem approach

The direct approach to solve this problem is to run two for loops and for every subarray check if it is the maximum sum possible.
Time complexity: O(N^2), Where N is the size of the array.
Space complexity: O(1)
The efficient approach is to use Kadane's algorithm. It calculates the maximum sum subarray ending at a particular index by using the maximum sum subarray ending at the previous position.
Steps :
Declare two variables : currSum which stores maximum sum ending here and maxSum which stores maximum sum so far.
Initialize currSum = 0 and maxSum = INT_MIN.
Now, traverse the array and add the value of the current element to currSum and check :
1. If currSum > maxSum, update maxSum equals to currSum.
2. If currSum < 0, make currSum equal to zero.
Finally, print the value of maxSum.

Try solving now

3. Validate BST

Moderate

25m average time

0/80

Asked in companies

You have been given a binary tree of integers with N number of nodes. Your task is to check if that input tree is a BST (Binary Search Tree) or not.

A binary search tree (BST) is a binary tree data structure which has the following properties.

• The left subtree of a node contains only nodes with data less than the node’s data.
• The right subtree of a node contains only nodes with data greater than the node’s data.
• Both the left and right subtrees must also be binary search trees.

Example :

Answer :

Level 1: 

All the nodes in the left subtree of 4 (2, 1, 3) are smaller 
than 4, all the nodes in the right subtree of the 4 (5) are 
larger than 4.

Level 2 :

For node 2:
All the nodes in the left subtree of 2 (1) are smaller than 
2, all the nodes in the right subtree of the 2 (3) are larger than 2.
For node 5:
The left and right subtrees for node 5 are empty.

Level 3:

For node 1:
The left and right subtrees for node 1 are empty.
For node 3:
The left and right subtrees for node 3 are empty.

Because all the nodes follow the property of a binary search tree, the above tree is a binary search tree.

Problem approach

A simple O(N) approach for this question would be to do an inorder traversal of the tree and store all the values in a temporary array. Next, check if the array is sorted in ascending order or not. If it is sorted, the given tree is a BST.
The above approach uses an auxiliary array. In order to avoid using auxiliary array, maintain track of the previously visited node in a variable prev. So, do an inorder traversal of the tree and store the value of the previously visited node in prev. If the value of the current node is less than prev, then the given tree is not a BST.

Try solving now

Round

Easy

Face to Face

Duration60 minutes

Interview date14 May 2015

Coding problem8

This was the first technical round.
Detailed Discussion on projects -> Note : He didn’t ask anything related to the content of my project but the actual use of the project in the real time world , the pros and cons of it , the scope in future , where is the technology applied presently etc

1. Ninja and Two Sorted Arrays

Moderate

15m average time

85% success

0/80

Asked in companies

Ninja has been given two sorted integer arrays/lists ‘ARR1’ and ‘ARR2’ of size ‘M’ and ‘N’. Ninja has to merge these sorted arrays/lists into ‘ARR1’ as one sorted array. You may have to assume that ‘ARR1’ has a size equal to ‘M’ + ‘N’ such that ‘ARR1’ has enough space to add all the elements of ‘ARR2’ in ‘ARR1’.

For example:

‘ARR1’ = [3 6 9 0 0]
‘ARR2’ = [4 10]
After merging the ‘ARR1’ and ‘ARR2’ in ‘ARR1’. 
‘ARR1’ = [3 4 6 9 10]

Problem approach

Algorithm:

Let first array be mPlusN[] and other array be N[]
1) Move m elements of mPlusN[] to end.
2) Start from nth element of mPlusN[] and 0th element of N[] and merge them into mPlusN[].
Time Complexity: O(m+n)

Try solving now

2. DS Question

Difference in B Tree and B+ Tree

Problem approach

1. In the B tree, all the keys and records are stored in both internal as well as leaf nodes. In the B+ tree, keys are the indexes stored in the internal nodes and records are stored in the leaf nodes.
2. In B tree, keys cannot be repeatedly stored, which means that there is no duplication of keys or records. In the B+ tree, there can be redundancy in the occurrence of the keys. In this case, the records are stored in the leaf nodes, whereas the keys are stored in the internal nodes, so redundant keys can be present in the internal nodes.
3. In the Btree, leaf nodes are not linked to each other. In B+ tree, the leaf nodes are linked to each other to provide the sequential access.
4. In Btree, searching is not very efficient because the records are either stored in leaf or internal nodes. In B+ tree, searching is very efficient or quicker because all the records are stored in the leaf nodes.
5. Deletion of internal nodes is very slow in B Tree and a time-consuming process as we need to consider the child of the deleted key also. Deletion in B+ tree is very fast because all the records are stored in the leaf nodes so we do not have to consider the child of the node.
6. In Btree, sequential access is not possible. In the B+ tree, all the leaf nodes are connected to each other through a pointer, so sequential access is possible.

3. DBMS Question

Why Indexing is used in a database?

Problem approach

An index is a schema object that contains an entry for each value that appears in the indexed column(s) of the table or cluster and provides direct, fast access to rows. Indexes allow the database application to find data fast; without reading the whole table
The users cannot see the indexes, they are just used to speed up searches/queries.
Note: Updating a table with indexes takes more time than updating a table without (because the indexes also need an update). So you should only create indexes on columns (and tables) that will be frequently searched against.

4. DBMS Question

What is Multilevel Indexing?

Problem approach

With the growth of the size of the database, indices also grow. As the index is stored in the main memory, a single-level index might become too large a size to store with multiple disk accesses. The multilevel indexing segregates the main block into various smaller blocks so that the same can stored in a single block. The outer blocks are divided into inner blocks which in turn are pointed to the data blocks. This can be easily stored in the main memory with fewer overheads.

5. Networking Question

What is DNS?

Problem approach

The Domain Name System (DNS) is the phonebook of the Internet. Humans access information online through domain names, like nytimes.com or espn.com. Web browsers interact through Internet Protocol (IP) addresses. DNS translates domain names to IP addresses so browsers can load Internet resources.
Each device connected to the Internet has a unique IP address which other machines use to find the device. DNS servers eliminate the need for humans to memorize IP addresses such as 192.168.1.1 (in IPv4), or more complex newer alphanumeric IP addresses such as 2400:cb00:2048:1::c629:d7a2 (in IPv6).

6. Networking Question

What is a recursive and iterative query?

Problem approach

A recursive query is a kind of query, in which the DNS server, who received your query will do all the job of fetching the answer, and giving it back to you. During this process, the DNS server might also query other DNS server's in the internet on your behalf, for the answer.
In an iterative query, the name server, will not go and fetch the complete answer for your query, but will give back a referral to other DNS server's, which might have the answer.

7. Networking Question

What is a Proxy server?

Problem approach

A proxy server acts as a gateway between you and the internet. It’s an intermediary server separating end users from the websites they browse. Proxy servers provide varying levels of functionality, security, and privacy depending on your use case, needs, or company policy. If you’re using a proxy server, internet traffic flows through the proxy server on its way to the address you requested. The request then comes back through that same proxy server (there are exceptions to this rule), and then the proxy server forwards the data received from the website to you.

8. Networking Question

Under which server are mail servers maintained?

Problem approach

Under authoritative servers

Round

Easy

Face to Face

Duration60 minutes

Interview date14 May 2015

Coding problem4

Technical Interview round with questions on Coding and OOPS.

1. System Design Question

Design a placement software.Requirements : a)Choose a group of panelists for a particular college. b) panelists have different expertise c) colleges may have engineering , arts , science sections as well d) A panelist can be out for recruitment max 3 days in a fortnight

Problem approach

Tip 1: Firstly, remember that the system design round is extremely open-ended and there’s no such thing as a standard answer. Even for the same question, you’ll have a totally different discussion with different interviewers.
Tip 2: Before you jump into the solution always clarify all the assumptions you’re making at the beginning of the interview. Ask questions to identify the scope of the system. This will clear the initial doubt, and you will get to know what are the specific detail interviewer wants to consider in this service.
Tip 3: Design your structure and functions according to the requirements and try to convey your thoughts properly to the interviewer so that you do not mess up while implementing the idea .

2. Square root (decimal)

Easy

10m average time

90% success

0/40

Asked in companies

You have been given two integers 'N' and 'D', Your task is to find the square root of the number 'N' with precision up to 'D' decimal places i.e. the difference between your answer and the correct answer should be less than 10 ^ (-D).

For example if N = 10 and D = 3, then your answer will be 3.162.

Problem approach

The Simple Approach is to find the floor of the square root, try with all-natural numbers starting from 1. Continue incrementing the number until the square of that number is greater than the given number.
Algorithm:
1. Create a variable (counter) i and take care of some base cases, i.e when the given number is 0 or 1.
2. Run a loop until i*i <= n , where n is the given number. Increment i by 1.
3. The floor of the square root of the number is i – 1
Time Complexity: O(√ n).
The Better Approach would be to use Binary Search. The idea is to find the largest integer i whose square is less than or equal to the given number. The values of i * i is monotonically increasing, so the problem can be solved using binary search.
Algorithm:
1. Take care of some base cases, i.e when the given number is 0 or 1.
2. Create some variables, lowerbound l = 0, upperbound r = n, where n is the given number, mid and ans to store the answer.
3. Run a loop until l <= r , the search space vanishes
4. Check if the square of mid (mid = (l + r)/2 ) is less than or equal to n, If yes then search for a larger value in second half of search space, i.e l = mid + 1, update ans = mid
5. Else if the square of mid is more than n then search for a smaller value in first half of search space, i.e r = mid – 1.
6. Print the value of answer.
Time Complexity : O(logn)

Try solving now

3. OOPS Question

OOPS Concepts in C++

Problem approach

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

4. OOPS Question

What is the abstract keyword in Java?

Problem approach

The abstract keyword is used to achieve abstraction in Java. It is a non-access modifier which is used to create abstract class and method. The role of an abstract class is to contain abstract methods. However, it may also contain non-abstract methods. The method which is declared with abstract keyword and doesn't have any implementation is known as an abstract method.

Round

Easy

HR Round

Duration30 minutes

Interview date14 May 2015

Coding problem1

If you have made till here that means you are selected. The HR guy in Snapdeal is the coolest HR I have met .He asked me name of the companies that have hired me till now. Non-typical HR questions followed.

1. Basic HR Questions

Q1. Introduction
Q2. Your strengths and weaknesses
Q3. Why Snapdeal?

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.