Data Structures Interview Questions
- -1of 5 votes
AnswersFollow-up to above question:
- / July 31, 2016 in United States
Can you augment a BST to return the number of elements with node values in a given range?
If not, what other data structure would work?| Report Duplicate | Flag | PURGE
Google Software Engineer Data Structures - 0of 0 votes
AnswersThe following is the design question I was asked.
- gopi.komanduri July 26, 2016 in India
Design a dash board.
Should be very realistic.
Should be scalabe .
Should have very less latency .
Can expect millions of updates per second.
Dash board should show :
for each day :
1. city name ,
2.total trips in that city for that day ,
3.total fare it could collect in that city on that day,
4. fare collected from old clients
5. fare collected from new clients (new client is the client who is having his first ride in Uber after registration)
Input : we get two strings s1 , s2.
the format of s1 : trip_id , client_id , city , datetime
the format of s2 : trip_id , fare.
Could you please suggest how to proceed for this kind of question?| Report Duplicate | Flag | PURGE
StartUp Analyst Algorithm Business Question Cache Computer Architecture & Low Level Data Structures Distributed Computing Hash Table Ideas System Design - 3of 3 votes
AnswersA program stores total order numbers arrived at different time. For example, at 1.15 pm the program got 15 order, at 1.30 pm, the program got 20 order and so on.Now we need to design the data structure so that we can query the total orders we got in a time range efficiently. For this example, we can query as How many orders we have got between 1 and 2 pm? Ans will be 15+ 20 = 35
- gadha July 21, 2016 in India| Report Duplicate | Flag | PURGE
Amazon SDE-2 Data Structures Java Object Oriented Design - 0of 0 votes
AnswersGiven input format, The first line has the number of employees of a company Z. The next two lines have employees to perform certain operations on. The first employee of the fourth line can be assumed to be the ceo of the company. Each line from then on has the format Employee X Employee Y where X manages Y. (and hence Y forms the child for X).
- thisandthat July 04, 2016 in India
input:
6
Rajesh
Ravi
//Tree Starts here
Ram Raj
Ram Goku
Raj Rajesh
Raj Richa
Richa Ravi
Its known that each person in the company can directly line manage a maximum of 2 other employees.
For the two employees in the first two lines, find the lowest common manager.
How to construct this tree in java to eventually do an lca?| Report Duplicate | Flag | PURGE
Amazon SDE-2 Data Structures - 0of 0 votes
AnswerIn a 2D(m*n) int array few cells are marked as 0(zero). Distance between each cell is 1(one). Hence diagonal from one cell to next cell in the diagonal is 2(two). For each cell find the distance from the closest 0(zero) value cell.
- priyam.saha87 July 02, 2016 in United States
Input would be: length of array. width of array. count of zero in the array. followed by list of x coordinates and list of y coordinates
Example:
3
5
1
0
0
Output:
0 1 2
1 2 3
2 3 4
3 4 5
4 5 6| Report Duplicate | Flag | PURGE
Algorithm Data Structures - 0of 0 votes
AnswerImplement a data structure to represent this
- Anonymous June 29, 2016 in United States
[1,[2],[[[5]]],6,7,8]. Multi level indirection with in a list| Report Duplicate | Flag | PURGE
Uber Software Engineer Data Structures - 0of 0 votes
AnswersWhat is a stack? What operations can be performed on it?
- Enigma8ic June 07, 2016 in United States
Implement a stack data structure.| Report Duplicate | Flag | PURGE
Amazon SDET Data Structures - 0of 0 votes
AnswersImplement a datastructure with the following APIs
- Enigma8ic June 07, 2016 in United States
void add(int) - 3,12,5,6,1
int getMin() - 1,3,5,6,12| Report Duplicate | Flag | PURGE
Amazon SDET Data Structures - 2of 2 votes
AnswersGiven two sorted linked lists of integers write an algorithm to merge the two linked lists such that the resulting linked list is in sorted order. You are expected to define the data structure for linked list as well. Analyze the time and space complexity of the merge algorithm.
- vkoolkatz April 28, 2016 in United States| Report Duplicate | Flag | PURGE
Facebook Software Engineer Data Structures - -1of 3 votes
AnswersConstruct a Binary tree from the preorder traversal and find the distance between two nodes.
- EsmailDini April 28, 2016 in canada for Alexa| Report Duplicate | Flag | PURGE
Amazon Developer Program Engineer Data Structures - 0of 0 votes
AnswersFind out if there is cycle in Directed graph
- pc April 09, 2016 in United States| Report Duplicate | Flag | PURGE
Microsoft Senior Software Development Engineer Algorithm Data Structures - -1of 1 vote
AnswersGiven billions of Rectangle, find rectangle with minimum area overlapping to a given point P(x,y)
- pc April 09, 2016 in United States
There is a simple way to achieve answer in O(n) by processing each rectangle sequentially, but optimize it further provided large number of Rectangle array.| Report Duplicate | Flag | PURGE
Microsoft Senior Software Development Engineer Algorithm Data Structures - 0of 0 votes
AnswersFind all the customers who spent >2 minutes on Page "XYZ" & purchased
- LoneStarTexxan March 22, 2016 in United States
>2 items of cofffee_X && gave a review of >3
Objects given:
class PageView {
private String URL;
private String customerID;
private Integer timeSpent;}
class Purchase {
private String productID;
private String customerID;
private Integer itemsPurchased;}
class Review {
private String productID;
private String customerID;
private Integer reviewPoints;}| Report Duplicate | Flag | PURGE
Software Developer Data Structures - 0of 0 votes
AnswersIf I am designing a media player and I want to store songs and play them in random order
- ash.taunk3 March 17, 2016 in India
a) what data structure will you use to store songs?
b) how will select the next song to play in a way which prevents the same song being played in consecutive turn| Report Duplicate | Flag | PURGE
Amazon Data Structures - 0of 0 votes
AnswersIf you have the chapter of a book and you're supposed to build an index such that given a word, you can tell which pages the word occurs on, what data structure can you use? Optimize for space utilization.
- NS March 03, 2016 in United States| Report Duplicate | Flag | PURGE
JP Morgan Software Engineer / Developer Data Structures - 0of 0 votes
AnswersBoard Game:
- NS March 03, 2016 in United States
1) Write a program that can take a board of N x N filled with alphabets and print/return all the words that can be constructed by connecting alphabets together. You're allowed to connect alphabets in any direction including diagonally, the only restriction is that you cannot cross over the same alphabet twice. So for eg:
A,B,C,D
E,K,L,A
C,A,M,N
D,I,N,G
So example words that can be made are: BEAD, CALM, CAN, DAMN, MAKE.
2) What's the run time for your algorithm? Does your algorithm scale for large sizes of the matrix? What optimizations can you make to improve the run time.| Report Duplicate | Flag | PURGE
JP Morgan Software Engineer / Developer Data Structures - 0of 0 votes
AnswersGiven login/logout time of all users for a particular website in below form.
- dggn February 26, 2016 in India
userId, login time, logout time.
Now store this data in some data structure, so that we can efficiently query total number of users who logedin and logedout in given time range.| Report Duplicate | Flag | PURGE
Flipkart SDE-2 Data Structures - 0of 0 votes
AnswersBinary search inorder traversal asked by Amazon
- Info.Dubey February 20, 2016 in India
struct Node
{
int data;
Node *right.*left,*random
}
Tree should be in-order traversal and random node should keep the in-order transversal path.| Report Duplicate | Flag | PURGE
Amazon Software Developer Data Structures - 0of 0 votes
AnswersYou have a stream of numbers coming in (lets say more than a million). The numbers are between [0-999). Implement a class which can
- ranganath.mr February 16, 2016 in United States
insert(int i);
getMean();
getMedian();
in constant time O(1).| Report Duplicate | Flag | PURGE
Thumbtack SDE-3 Algorithm Data Structures - 1of 1 vote
AnswersThis is was asked in Amazon SDE online test from Hacker rank.
- sandeepparekh9 January 20, 2016 in Hong Kong
Initech is a company which has CEO Bill and a hierarchy of employees. Employees can have a list of other employees reporting to them, which can themselves have reports, and so on. An employee with at least one report is called a manager.
Please implement the closestCommonManager method to find the closest manager (i.e. farthest from the CEO) to two employees. You may assume that all employees eventually report up to the CEO.
Tree structure:
Bill -> Dom, Samir, Michael
Dom -> Bob, Peter, Porter
Peter -> Milton, Nina
Sample Data:
CEO Bill has 3 employees reporting to him: {Dom, Samir, Michael}
Dom has three reports { Peter, Bob, Porter}
Samir has no reports {}
Michael has no reports {}
Peter has 2 reports {Milton, Nina}
Bob has no reports {}
Porter has no reports {}
Milton has no reports {}
Nina has no reports {}
Sample calls:
closestCommonManager(Milton, Nina) = Peter
closestCommonManager(Nina, Porter) = Dom
closestCommonManager(Nina, Samir) = Bill
closestCommonManager(Peter, Nina) = Peter| Report Duplicate | Flag | PURGE
Amazon SDE1 Data Structures - 0of 0 votes
AnswersMerge two sorted singly linked lists into one sorted singly linked list. Allocate no extra node.
- Saurabh Singhal January 16, 2016 in India| Report Duplicate | Flag | PURGE
Arista Networks Software Engineer Data Structures Linked Lists - 0of 0 votes
AnswerGiven a sorted integer array. Convert it to a balanced BST (Size of array is given)
- Saurabh Singhal January 16, 2016 in India| Report Duplicate | Flag | PURGE
Arista Networks Software Engineer Data Structures Trees and Graphs - 0of 0 votes
AnswersAllocate a 2-D array of size m*n using malloc(). The array should be accessible as a[i][j].
- Saurabh Singhal January 16, 2016 in India| Report Duplicate | Flag | PURGE
Arista Networks Software Engineer Arrays C Data Structures Matrix - 2of 2 votes
AnswersHow to find middle element in a linked list without knowing the length of the linked list
- D PRAVEEN KUMAR December 10, 2015 in India| Report Duplicate | Flag | PURGE
unknown Applications Developer Data Structures - -1of 3 votes
AnswersA frog has to cross the river from one end to another end. river has stones in between randomly where frog can jump. frog can't jump into the river. problem is that will frog ever reach other end with following conditions?
- anuprao85 December 01, 2015 in United States for Office
1. frog allow to do same jump as previous jump. or
2. frog allow to jump 1 more as previous jump. or
3. frog allow to jump 1 less as previous jump.
consider river as Boolean Array. Stone is a element in array where value is true .| Report Duplicate | Flag | PURGE
Microsoft Software Developer Data Structures - 1of 1 vote
AnswersDesign a data structure which could perform the following operations in O(1):
- Abhigyan Mehra November 25, 2015 in India
- Insert(), Delete(), Search(), getRandom()
getRandom() should pick a "random" element from your data structure, and should not be predictable (for instance always picking the "first" element from your DS)| Report Duplicate | Flag | PURGE
Amazon SDE-2 Data Structures - 0of 0 votes
AnswersGiven string a and b, with b containing all distinct characters, find the longest common subsequence's
- siva.sai.2020 November 17, 2015 in India
length. Expected complexity O(nlogn).| Report Duplicate | Flag | PURGE
Uber SDE1 Algorithm Data Structures - 1of 1 vote
AnswersGiven a 4*n block, find number of different ways of filling it with 1*2 smaller blocks. Rotation of smaller blocks is allowed.
- siva.sai.2020 November 17, 2015 in India| Report Duplicate | Flag | PURGE
Uber SDE1 Algorithm Data Structures