Data Structures Interview Questions
- 0of 0 votes
AnswersYou are given three type of data sets.
- sonesh May 08, 2017 in United States
Type 1
Data size: 4 billion
Distinct Data: 1000
Type 2
Data Size: 4 billion
Distinct Data: 2 billion
Type 3
Data Size: 1000
Each Data is of length 100 million byte
What kind of data structure would you use to answer search/insert/remove queries for each data types?| Report Duplicate | Flag | PURGE
Bloomberg LP Software Engineer / Developer Data Structures - 0of 0 votes
AnswersPerform an efficient DeepCopy of a linked list whose node is like below:
public class Node { public int Value {get;set;} public Node Next{get;set;} public Node Random{get;set;} }
The Random field points to any random node in the list.
- Abcd April 20, 2017 in United States| Report Duplicate | Flag | PURGE
Amazon Software Developer Data Structures - 3of 3 votes
AnswersGiven the following set of strings, write a function that stores this information.
- JSDUDE April 19, 2017 in United States
// /Electronics/Computers/Graphics Cards
// /Electronics/Computers/Graphics Cards
// /Electronics/Computers/SSDs
// /Electronics/Computers/Graphics Cards
// /Electronics/Computers/SSDs
// /Electronics/TVs
// /Electronics/Computers/Graphics Cards
// /Electronics/TVs
// /Electronics/TVs
// /Garden
// /Automotive/Parts
Your datastructure should be able to provide information as such:
// / = 11
// /Electronics = 9
// /Electronics/Computers = 6
// /Electronics/Computers/Graphics Cards = 4
// /Electronics/TVs = 3
// etc
// ["/Electronics/Computers/Graphics Cards", "/Garden"]| Report Duplicate | Flag | PURGE
NVIDIA Senior Software Development Engineer Data Structures Trees and Graphs - 1of 3 votes
AnswersGiven array of length n, having element 0 to n-1.
- DATA April 11, 2017 in United States
you are allowed to swap adjacent element only if Absolute difference of two element is equal to 1.
Is it possible to sort array.
If yes print sorted output.| Report Duplicate | Flag | PURGE
Yahoo Backend Developer Arrays Data Structures Math & Computation Online Test - 15of 15 votes
AnswersImplement a stack that in addition to push and pop has a function that returns the min value of the stack.
- theProgrammer April 10, 2017 in United States for Alexa
I came up with a O(logn) solution, but he wanted a O(1) for the whole algorithm.| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Data Structures - 0of 0 votes
AnswersDesign a data structure to support following operation:
- Priyanka April 04, 2017 in India
Insert, delete, search and min difference
Time complexity of finding min Difference should be less than O(log n).| Report Duplicate | Flag | PURGE
Directi Software Engineer Data Structures - 0of 2 votes
AnswersThere is an island surrounded by oil mines. You will be given n companies and m oil mines having values. You have to distribute the mines to "n" companies in fair manner. Remember the companies can have oil mines adjacent to each other and not in between of each others.After distributing them compute the differnce of oil mines from the company getting highest and company getting lowest. This number should be minimum.(then only the distribution can be termed as fair).
- sunny.1rn12cs113 March 26, 2017 in India
Example
Input
2
2 4
6 13 10 2
2 4
6 10 13 2
output
5
1| Report Duplicate | Flag | PURGE
Samsung Java Developer Data Structures - 0of 0 votes
AnswerWrite findMin, findNext of BST tree node has parent pointer also. http://www.geeksforgeeks.org/find-the-minimum-element-in-a-binary-search-tree/
- John4jobs March 17, 2017 in United States
http://www.geeksforgeeks.org/inorder-successor-in-binary-search-tree/| Report Duplicate | Flag | PURGE
Arista Networks Developer Program Engineer Data Structures - 0of 0 votes
AnswerWe have a List of FlightRoute
public static class FlightRoute { String from; String to; int time; .... }
and write a function to find Shortest Path: findShorestPath(String start, String end, List<FlightRoute>routes)
- ewrhoqpqheow March 16, 2017 in United States| Report Duplicate | Flag | PURGE
Facebook SDE1 Data Structures - 1of 1 vote
Answers1. Difference between arrays and link list
- JSDUDE March 08, 2017 in United States for Alexa
1.1 How to prepend each of the above with extra data
2. Hash-table. What datastructure to use to create one. How to resolve collision| Report Duplicate | Flag | PURGE
Amazon Software Developer Data Structures - 0of 0 votes
Answers
- xankar February 26, 2017 in United Statesimport java.time.Duration; import java.time.LocalTime; import java.util.List; import java.util.Map; // Your goal is to write business logic for a very simple Restaurant booking system // You are encouraged to refactor exisiting code, create other classes, write helper methods etc // You also need to make sure that the implementation works correctly class Reservation { public String name; public int partySize; public LocalTime startTime; } class Table { public int tableNumber; public int maxPartySize; } class Restaurant { public List<Table> tables; public LocalTime openTime; public LocalTime closeTime; public Map<Integer, Duration> reservationDurationsPerPartySize; // Returns a Table if Reservation could be booked, null otherwise // Booking rules: // 1) Reservation could be made only when the Restaurant is open. // 2) Only one Reservation can be seatted a Table at any time. // 3) Reservation can be seatted only at a Table of the same or a bigger size. // 4) Reservation should stay on the same Table for the whole Duration. // 5) Reservation Duration is determined by PartySize. public Table bookReservation(Reservation reservation) { //TODO: } }
| Report Duplicate | Flag | PURGE
Opentable Backend Developer Algorithm Data Structures Java Problem Solving - 0of 0 votes
AnswersGiven set of N number of points/Co-ordinates[(x1,y1),(x2,y2), (x3,y3), (x4,y4), (x5,y5), etc] find if any of them form square.
- xankar February 26, 2017 in United States| Report Duplicate | Flag | PURGE
Pure Storage Backend Developer Algorithm Data Structures Java - 2of 2 votes
Answersgiven preorder traversal [5,3,2,4,8,7,9] of a BST, how do we identify the leaf nodes without building the tree ?
- Raj February 16, 2017 in United States
@Anonymous Thanks for the reply!
Please try other use cases like, only single leaf node| Report Duplicate | Flag | PURGE
Facebook Software Engineer Data Structures - 1of 1 vote
AnswersGiven a set of possibly overlapping rectangles in different levels (All of which are "not rotated", can be uniformly represented as (left-bottom,right-top) tuplets), return a minimal set of (non-rotated) non-overlapping rectangles, that occupy the same area.
- hulk February 09, 2017
The rectangle at lower level has more priority than at higher levels.| Report Duplicate | Flag | PURGE
Facebook Software Developer Algorithm Data Structures - 0of 0 votes
AnswersA binary tree and a number, say k are given. Print every path in the tree with sum of the nodes in the path as k.(A path can start from any node and end at any node, i.e. they need not be root node and leaf node; and negative numbers can also be there in the tree)
- SIVA R February 07, 2017 in India| Report Duplicate | Flag | PURGE
Amazon SDE1 Data Structures - 0of 0 votes
AnswersDesign Amazon Recommendations Feature. Focus on designing how would you store and make it accessible fast? What would be class design like for the class which would provide list of products which people bought similar to a given product? How would you test that class?
- Anonymous February 07, 2017| Report Duplicate | Flag | PURGE
Amazon SDE-2 Data Structures Database Object Oriented Design - 1of 1 vote
AnswersGiven an integer target and binary tree (not a binary search tree!) each of whose nodes contains an integer (which may be positive or negative), find the set of all subtrees whose sum equals the given target. The sum of a subtree is just the sum of the integers contained in its nodes. Note that the subtree does not have to contain all child nodes - it can be any set of connected nodes.
- Aloo February 03, 2017 in India| Report Duplicate | Flag | PURGE
SDE1 Data Structures - 0of 0 votes
AnswersGive a large multi MB byte file in memory, a system handles delete requests for segments typically of the order of bytes. The system has a constraint that individual purge requests of byte segments are expensive, so that the no. of purges are a minimum.
- naveentmani January 21, 2017 in United States for AWS
Eg. a 5 MB file receives delete requests for offsets (1, 100), (250, 550),(1000, 1200), (400, 600), (800, 900), (1100, 1150)
Effective delete requests - (1, 100) , (250, 600), (800, 900), (1000, 1200)
The users of the system always go by the absolute byte ordering of the file. Eg. if byte 1 is deleted, the users of the system will reference the actual byte 2 as byte 2.
What data structure would you use to store these intervals such that the following operations are efficient 1. Looking up an interval 2. Inserting a new interval that has no overlap with existing ones 3. Inserting a new interval that has partial overlaps with existing intervals. This would involve collapsing the existing intervals with the new interval to form a single large interval. Eg. Interval cache: {(1, 100), (250, 550), (1000, 1200)} , new interval : (400, 700) -> Interval cache: {(1,100), (250, 700), (1000, 1200)}| Report Duplicate | Flag | PURGE
Amazon SDE-2 Data Structures - 2of 2 votes
AnswersPrint the longest path from root to leaf in a Binary tree (Basically the nodes that lie on the height path).
- abhinavg.stack January 08, 2017 in United States| Report Duplicate | Flag | PURGE
Amazon Backend Developer Data Structures - 0of 0 votes
Answerspublic interface FirstCommonAncestor {
/**
* Given two nodes of a tree,
* method should return the deepest common ancestor of those nodes.
*
* A
* / \
* B C
* / \ \
* D E H
* / \
* G F
*
* commonAncestor(D, F) = B
* commonAncestor(C, G) = A
* commonAncestor(E, B) = B
*/
Node commonAncestor(Node one, Node two);
}
- BeingUpfront December 01, 2016 in United Statesclass Node { final Node parent; final Node left; final Node right; public Node(Node parent, Node left, Node right) { this.parent = parent; this.left = left; this.right = right; } boolean isRoot() { return parent == null; } }
| Report Duplicate | Flag | PURGE
Linkedin Senior Software Development Engineer Data Structures - 1of 1 vote
AnswersYou are given a function getNum() that returns a random number in the range 1 to 10 million with repetitions. However, it may also return -1 when it no longer provides numbers. Write a function that calls getNum() continuously until it returns -1 (if a repetition, should not store it); as soon as u see -1, stop calling getnum() and print all the numbers seen so far in a sorted way. Condition: You have got very limited memory to work with.
- Shankar November 20, 2016 in United States| Report Duplicate | Flag | PURGE
Microsoft Software Developer Data Structures - 0of 0 votes
AnswersWhat data structure would you use to store the entries of a sparse matrix?
- Brookekelseyryan November 05, 2016 in United States| Report Duplicate | Flag | PURGE
Facebook Software Engineer Data Structures - 0of 0 votes
Answers(Priority Scheduling) In some systems, a priority is associated with each process and the CPU is allocated to the process with the highest priority (small value). Equal priority processes are scheduled in FIFO order. Define a suitable data structure, and then write a simulation program for the system described above. The program should display the following menu: 1. Add a New Process. 2. Serve a Process. 3. Display Information about Waiting Process. 4. Number of Waiting Process 5. Exit menu Hints: You have to adjust the QUEUE ADT in implementation level to be suitable for solving this problem. The process should have the following fields: process ID and priority.
- ayasaadtaha October 29, 2016 in cairo| Report Duplicate | Flag | PURGE
Data Structures - 0of 0 votes
AnswersAdd a node to sorted circular linked list
- Blank October 29, 2016 in United States for Infrastructure| Report Duplicate | Flag | PURGE
Salesforce Intern Data Structures - 0of 0 votes
AnswersNone actually understands how garbage collection works, albeit people ask this in the interviews. Nonetheless, we are going to ask you something very similar. Here is the problem.
Take an array of bytes, perhaps 1MB in size.
Implement these two operations:ptr_structure = alloc ( amount_of_storage ) freeed = free ( ptr_structure )
Now, here is your problem. alloc must allocate contiguous storage. If it is not possible, you need to compact ( defragment ) memory. So, you need to implicitly write a :
defragment() // defragments memory
Worse is coming. Even imagining you have written a stop the world defragmenter, after you reallocate, how the ptr_structures would actually work?
- NoOne October 14, 2016 in India
Solve this whole problem.
Time allocated was 1 hour. Face to face, panel with 2 interviewers.| Report Duplicate | Flag | PURGE
SDET Algorithm Assembly Computer Architecture & Low Level Computer Science Data Structures - 0of 0 votes
AnswerAs you know, every OS comes up with this tiny application called the calculator. It is good. Now, here is our problem. If we try to implement the function
def calculate( operand, operator, operand ) { /* Do Interviewers bidding here */ }
I have to write if upon if upon if upon if to do for all operators. Moreover, some operators are not even binary! Take example the abs() or say the negate()!
- NoOne October 14, 2016 in India
Bigger problem persists. With the if mode, we can not even add operators as we wish to without changing code!
But that is a sin. So, what do we do? That is question 1.
In question 2, as a software tester, how do you propose to test and automate the above? Writing more if than the developer is not allowed.| Report Duplicate | Flag | PURGE
SDET Algorithm Data Structures Object Oriented Design Programming Skills Software Design - 0of 0 votes
AnswersGiven a sorted (increasing order) array, write a program to create a binary tree with minimal height
- D PRAVEEN KUMAR September 26, 2016 in India| Report Duplicate | Flag | PURGE
Skill Subsist Impulse Ltd Software Developer Data Structures - 0of 2 votes
AnswersProblem statement: You are given a maze with N cells. Each cell may have multiple entry points but not more than one exit (ie. entry/exit points are unidirectional doors like valves). The cells are named with an integer value from 0 to N-1. You need to find the following :
- sarthakbansal19 September 23, 2016 in India
Nearest meeting cell: Given any two cells - C1,C2, find the closest cell Cm that can be reached from both C1 and C2.
Note: Aim for O(Log(N)) solution.
INPUT FORMAT - First line has the number of cells N
Second line has list of N values of the edge[] array. edge[i] contains the cell number that can be reached from of cell ‘i’ in one step. edge[i] is -1 if the ‘i’th cell doesn’t have an exit.
Third line contains two cell numbers whose nearest meeting cell needs to be found. (return -1 if there is no meeting cell from the two given cells) .
OUTPUT FORMAT - Find nearest meeting cell (NMC).| Report Duplicate | Flag | PURGE
Juspay Software Developer Data Structures - 1of 1 vote
AnswersProblem statement: You are given a maze with N cells. Each cell may have multiple entry points but not more than one exit (ie. entry/exit points are unidirectional doors like valves). The cells are named with an integer value from 0 to N-1. You need to find the following :
- sarthakbansal19 September 23, 2016 in India
find Maximum number of entry points (incoming edges) for any cell in the maze
Note: Aim for O(N) solution.
INPUT FORMAT - First line has the number of cells N
Second line has list of N values of the edge[] array. edge[i] contains the cell number that can be reached from of cell ‘i’ in one step. edge[i] is -1 if the ‘i’th cell doesn’t have an exit.
OUTPUT FORMAT - Find max entry points in any cell.| Report Duplicate | Flag | PURGE
Juspay Software Developer Data Structures - 0of 2 votes
AnswersProblem statement: You are given a maze with N cells. Each cell may have multiple entry points but not more than one exit (ie. entry/exit points are unidirectional doors like valves). The cells are named with an integer value from 0 to N-1. You need to find the following :
- sarthakbansal19 September 23, 2016 in India
The length of the largest cycle in the maze. Return -1 if there are no cycles.
Note: Aim for O(N) solution.
INPUT FORMAT - First line has the number of cells N
Second line has list of N values of the edge[] array. edge[i] contains the cell number that can be reached from of cell ‘i’ in one step. edge[i] is -1 if the ‘i’th cell doesn’t have an exit.
OUTPUT FORMAT - length of the largest cycle.| Report Duplicate | Flag | PURGE
Juspay Software Developer Data Structures