Snapdeal
30+ DS Group Interview Questions and Answers
Q1. Closest Pair of Points Problem Statement
Given an array containing 'N' points in a plane, your task is to find the distance between the closest pair of points.
Explanation:
The distance between two points, (x1,...read more
Find the distance between the closest pair of points in a plane given an array of points.
Calculate the distance between each pair of points using the formula provided.
Keep track of the minimum distance found so far.
Optimize the solution to avoid unnecessary calculations by considering only relevant pairs.
Consider using a data structure like a priority queue or sorting to improve efficiency.
Handle edge cases like when there are only two points in the array.
Q2. Count Unique Rectangles in Grid
Given a grid with 'M' rows and 'N' columns, calculate the total number of unique rectangles that can be formed within the grid using its rows and columns.
Input:
The first line c...read more
Calculate the total number of unique rectangles that can be formed within a grid using its rows and columns.
Iterate through all possible combinations of rows and columns to calculate the number of unique rectangles
Use the formula (M * (M + 1) / 2) * (N * (N + 1) / 2) to find the total number of rectangles
Return the total number of unique rectangles for each test case
Q3. You have a deck of 10 cards.You take one card out and put it on table and put next card in the end of deck.You repeat this sequence till all cards are on the table.Sequence formed on the table is 1,2,3,4,5…10....
read moreReconstruct original sequence of cards given a specific sequence of cards placed on table.
The last card placed on the table must be 10.
The second last card placed on the table must be 5 or 6.
The first card placed on the table must be either 1 or 2.
Use trial and error method to reconstruct the original sequence.
Q4. LCA of Binary Tree Problem Statement
You are given a binary tree consisting of distinct integers and two nodes, X
and Y
. Your task is to find and return the Lowest Common Ancestor (LCA) of these two nodes.
The ...read more
Find the Lowest Common Ancestor (LCA) of two nodes in a binary tree.
Traverse the binary tree to find the paths from the root to nodes X and Y.
Compare the paths to find the last common node, which is the LCA.
Handle cases where one node is an ancestor of the other.
Consider edge cases like when X or Y is the root node.
Implement a recursive or iterative solution to find the LCA efficiently.
Q5. Find All Anagrams in a String
Given a string STR
and a non-empty string PTR
, your task is to identify all starting indices of PTR
’s anagrams in STR
.
Explanation:
An anagram of a string is another string that co...read more
Identify all starting indices of anagrams of a given string in another string.
Iterate through the main string using a sliding window approach.
Use a hashmap to keep track of characters in the anagram string.
Compare the hashmap of the anagram string with the current window of characters in the main string.
If the hashmaps match, add the starting index of the window to the result array.
Q6. Find Pair with Given Sum in BST
You are provided with a Binary Search Tree (BST) and a target value 'K'. Your task is to determine if there exist two unique elements in the BST such that their sum equals the ta...read more
Given a Binary Search Tree and a target value, determine if there exist two unique elements in the BST such that their sum equals the target.
Traverse the BST in-order to get a sorted array of elements.
Use two pointers approach to find the pair with the given sum.
Consider edge cases like null nodes and duplicate elements.
Q7. Zig Zag Tree Traversal Problem Statement
Given a binary tree, compute the zigzag level order traversal of the nodes' values. In a zigzag traversal, start at the root node and traverse from left to right at the ...read more
Zig Zag Tree Traversal involves alternating directions while traversing a binary tree level by level.
Implement a level order traversal of the binary tree.
Alternate the direction of traversal for each level.
Use a queue data structure to keep track of nodes at each level.
Handle null nodes appropriately to maintain the zigzag pattern.
Example: For input 1 2 3 4 -1 5 6 -1 7 -1 -1 -1 -1 -1 -1, the output should be 1 3 2 4 5 6 7.
Q8. Subtree Check in Binary Trees
You are given two binary trees, T and S. Your task is to determine whether tree S is a subtree of tree T, meaning S must match the structure and node values of some subtree in T.
I...read more
The task is to determine whether tree S is a subtree of tree T, matching structure and node values.
Parse the input level order traversal of both trees T and S
Check if tree S is a subtree of tree T by comparing their structures and node values
Output 'true' if S is a subtree of T, otherwise 'false'
Q9. Largest Rectangular Area In A Histogram
Given an array HEIGHTS
of length N
, where each element represents the height of a histogram bar and the width of each bar is 1, determine the area of the largest rectangl...read more
Find the largest rectangular area in a histogram given the heights of the bars.
Use a stack to keep track of the indices of the bars in non-decreasing order of heights.
Calculate the area of the rectangle with each bar as the smallest bar and update the maximum area.
Handle the case when the stack is not empty after processing all bars to calculate the remaining areas.
Example: For HEIGHTS = [2, 1, 5, 6, 2, 3], the largest rectangle has an area of 10.
Q10. Reverse a Linked List Problem Statement
You are given a Singly Linked List of integers. Your task is to reverse the Linked List by changing the links between nodes.
Input:
The first line of input contains a sin...read more
Reverse a given singly linked list by changing the links between nodes.
Iterate through the linked list and reverse the links between nodes.
Keep track of the previous, current, and next nodes while reversing the links.
Update the head of the linked list to point to the last node after reversal.
Q11. Linked List Cycle Detection
Determine if a given singly linked list of integers forms a cycle.
Explanation:
A cycle in a linked list occurs when a node's next reference points back to a previous node in the lis...read more
Detect if a singly linked list forms a cycle by checking if a node's next reference points back to a previous node.
Use two pointers, one moving at double the speed of the other, to detect a cycle.
If the two pointers meet at any point, there is a cycle in the linked list.
If one of the pointers reaches the end of the list (null), there is no cycle.
Q12. Inorder Traversal of Binary Tree Without Recursion
Given a Binary Tree consisting of 'N' nodes with integer values, your task is to perform an In-Order traversal of the tree without using recursion.
Input:
The ...read more
Perform in-order traversal of a binary tree without recursion.
Use a stack to simulate the recursive process of in-order traversal
Start with the root node and keep traversing left until reaching a null node, then pop from stack and move to right node
Keep track of visited nodes to avoid revisiting them
Return the in-order traversal list
Q13. Search in a Row-wise and Column-wise Sorted Matrix Problem Statement
You are given an N * N matrix of integers where each row and each column is sorted in increasing order. Your task is to find the position of ...read more
Given a sorted N * N matrix, find the position of a target integer 'X'.
Start from the top-right corner of the matrix and compare the target with the current element.
Based on the comparison, move left or down in the matrix to narrow down the search.
Repeat the process until the target is found or the search goes out of bounds.
Return the position of the target if found, else return {-1, -1}.
Q14. There is a file which contains ip addresses and corresponding url. Example 192.168.1.15 www.abc.com 10.255.255.40 ----- You have to return the subnet mask of the ip and the url after “www.” Output 192.168.1 abc...
read moreJava function to return subnet mask of IP and URL after www.
Read the file and store IP addresses and URLs in separate arrays
Use regex to extract subnet mask from IP address
Use substring to extract URL after www.
Return subnet mask and URL as separate strings
Q15. Nth Fibonacci Problem Statement
Calculate the Nth term of the Fibonacci series, denoted as F(n), using the formula: F(n) = F(n-1) + F(n-2)
where F(1) = 1
and F(2) = 1
.
Input:
The first line of each test case co...read more
Calculate the Nth term of the Fibonacci series using a recursive formula.
Use the formula F(n) = F(n-1) + F(n-2) to calculate the Nth Fibonacci number.
Start with base cases F(1) = 1 and F(2) = 1.
Continue recursively calculating Fibonacci numbers until reaching the desired N.
Ensure to handle edge cases and constraints such as 1 ≤ N ≤ 10000.
Q16. How would you design DBMS for Snapdeal’s website’s shoe section. Now if you want to further break it into Sports and Casual Shoe would you break the DB into two or add another entity?
For Snapdeal's shoe section, I would design a DBMS with separate entities for Sports and Casual Shoes.
Create a main entity for shoes with attributes like brand, size, color, etc.
Create separate entities for Sports and Casual Shoes with attributes specific to each category.
Link the Sports and Casual Shoe entities to the main Shoe entity using a foreign key.
Use indexing and normalization techniques to optimize performance and reduce redundancy.
Consider implementing a search fea...read more
Pick a fruit from the jar labeled 'Apples and Oranges' to correctly label all jars.
Pick a fruit from the jar labeled 'Apples and Oranges'.
If you pick an apple, label the jar as 'Apples'.
If you pick an orange, label the jar as 'Oranges'.
Label the remaining jars accordingly based on the above information.
Q18. You are given two ropes.Each rope takes exactly 1 hour to burn. How will you measure period of 45 minutes
Burn one rope from both ends and the other rope from one end.
Light one rope from both ends and the other rope from one end.
When the first rope burns completely, 30 minutes have passed.
Then, immediately light the other end of the second rope.
When the second rope burns completely, 15 more minutes have passed.
Total time elapsed is 45 minutes.
Q19. There are two sorted arrays. First one is of size m+n containing only ‘first’ m elements. Another one is of size n and contains n elements. Merge these two arrays into the first array of size m+n such that the...
read moreMerge two sorted arrays into one sorted array of larger size
Create a new array of size m+n
Compare the last elements of both arrays and insert the larger one at the end of the new array
Repeat until all elements are merged
If any elements are left in the smaller array, insert them at the beginning of the new array
Time complexity: O(m+n)
Example: arr1=[1,3,5,7,0,0,0], arr2=[2,4,6], output=[1,2,3,4,5,6,7]
Q20. Variation of -----/ Given a dictionary of words and a number n. Find count of all words in dictionary that can be formed by given number n
The question asks to find the count of words in a dictionary that can be formed by a given number.
Iterate through each word in the dictionary
Check if the characters in the word can be formed using the given number
Increment the count if the word can be formed
Q21. DNS – Domain name servers : what are they , how do they operate?
DNS servers translate domain names into IP addresses to enable communication between devices on the internet.
DNS servers act as a phone book for the internet, translating domain names into IP addresses.
When a user types a domain name into their browser, the browser sends a request to a DNS server to resolve the domain name into an IP address.
DNS servers operate in a hierarchical system, with root servers at the top, followed by top-level domain servers, and then authoritative...read more
Q22. Lowest Common Ancestor of two nodes in binary tree.I wrote code for this.Then interviewer drew a tree and asked to print stacktrace on it
Finding lowest common ancestor of two nodes in binary tree
Traverse the tree from root to both nodes and store the paths in separate arrays
Compare the paths to find the last common node
Return the last common node as the lowest common ancestor
Use recursion to traverse the tree efficiently
Q23. Find LCM of all numbers from 1 to n. Give an algorithm, then correctly estimate the time complexity
Algorithm to find LCM of all numbers from 1 to n and its time complexity
Find prime factors of all numbers from 1 to n
For each prime factor, find the highest power it appears in any number from 1 to n
Multiply all prime factors raised to their highest power to get LCM
Time complexity: O(n*log(log(n)))
Q24. There is four digit number in aabb form and it is a perfect square.Find out the number
The number is 7744.
The number must end in 00 or 44.
The square root of the number must be a whole number.
The only possible number is 7744.
Q25. A linked list contains loop.Find the length of non looped linked list
To find the length of non-looped linked list, we need to traverse the list and count the number of nodes.
Traverse the linked list using a pointer and count the number of nodes until the end of the list is reached.
If a loop is encountered, break out of the loop and continue counting until the end of the list.
Return the count as the length of the non-looped linked list.
Q26. A simple program to check whether a number is palindrome or not
A program to check if a number is a palindrome or not.
Convert the number to a string
Reverse the string
Compare the original and reversed string
If they are the same, the number is a palindrome
Use two identical wires to measure 45 minutes by burning them at different ends.
Burn one end of the first wire and both ends of the second wire simultaneously.
When the first wire burns completely (30 minutes), light the other end of the second wire.
When the second wire burns completely (15 minutes), 45 minutes have passed.
Q28. What are inner join and outer join in sql
Inner join returns only the matching rows between two tables, while outer join returns all rows from one table and matching rows from the other.
Inner join combines rows from two tables based on a matching column.
Outer join returns all rows from one table and matching rows from the other.
Left outer join returns all rows from the left table and matching rows from the right table.
Right outer join returns all rows from the right table and matching rows from the left table.
Full ou...read more
Q29. Two linked list are merging at a point.Find merging point
To find the merging point of two linked lists
Traverse both linked lists and find their lengths
Move the pointer of the longer list by the difference in lengths
Traverse both lists simultaneously until they meet at the merging point
Q30. SQL vs NoSQL. Why NoSQL
NoSQL databases are flexible, scalable, and can handle large amounts of unstructured data.
NoSQL databases are schema-less, allowing for easy and flexible data modeling.
They can handle large amounts of unstructured data, making them suitable for big data applications.
NoSQL databases are highly scalable and can easily handle high traffic and large user bases.
They provide horizontal scalability by distributing data across multiple servers.
NoSQL databases are often used in real-t...read more
Q31. Number of rectangles in MxN matrix
The number of rectangles in an MxN matrix can be calculated using a formula.
The formula is (M * (M + 1) * N * (N + 1)) / 4
The matrix can be divided into smaller sub-matrices to count the rectangles
The number of rectangles can also be calculated by counting all possible pairs of rows and columns
Q32. Find square root of a number
To find square root of a number, use Math.sqrt() function in JavaScript.
Use Math.sqrt() function in JavaScript to find square root of a number.
For example, Math.sqrt(16) will return 4.
If the number is negative, Math.sqrt() will return NaN.
An outer join combines rows from two tables even if there is no match between the columns being joined.
Returns all rows from both tables, filling in missing values with NULL
Useful for finding unmatched rows between two tables
Types of outer joins include LEFT OUTER JOIN, RIGHT OUTER JOIN, and FULL OUTER JOIN
Inner Join is a SQL operation that combines rows from two tables based on a related column between them.
Inner Join returns only the rows that have matching values in both tables.
It is used to retrieve data that exists in both tables.
Example: SELECT * FROM table1 INNER JOIN table2 ON table1.column = table2.column;
Q35. Reverse linked list without recursion
Reverse a linked list iteratively
Create three pointers: prev, curr, and next
Initialize prev to null and curr to head
Loop through the list and set next to curr's next node
Set curr's next node to prev
Move prev and curr one step forward
Return prev as the new head
Interview Process at DS Group
Top Software Developer Interview Questions from Similar Companies
Reviews
Interviews
Salaries
Users/Month