## Data Structures Interview Questions

- -2of 4 votes
Follow-up to above question:

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?

- 0of 0 votes
The following is the design question I was asked.

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?

- 1of 1 vote
A 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

- 0of 0 votes
Given 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).

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?

- 0of 0 votes
In 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.

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

- 0of 0 votes
Implement a data structure to represent this

[1,[2],[[[5]]],6,7,8]. Multi level indirection with in a list

- 0of 0 votes
What is a stack? What operations can be performed on it?

Implement a stack data structure.

- 0of 0 votes
Implement a datastructure with the following APIs

void add(int) - 3,12,5,6,1

int getMin() - 1,3,5,6,12

- 2of 2 votes
Given 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.

- 0of 2 votes
Construct a Binary tree from the preorder traversal and find the distance between two nodes.

- 0of 0 votes
Find out if there is cycle in Directed graph

- -1of 1 vote
Given billions of Rectangle, find rectangle with minimum area overlapping to a given point P(x,y)

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.

- 0of 0 votes
Find all the customers who spent >2 minutes on Page "XYZ" & purchased

>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;}

- 0of 0 votes
If I am designing a media player and I want to store songs and play them in random order

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

- 0of 0 votes
What data str should we use to store restaurants(having location info), So that we can easily find the list of restaurants near my current location ?

- 0of 0 votes
If 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.

- 0of 0 votes
Board Game:

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.

- 0of 0 votes
Given login/logout time of all users for a particular website in below form.

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.

- 0of 0 votes
Binary search inorder traversal asked by Amazon

struct Node

{

int data;

Node *right.*left,*random

}

Tree should be in-order traversal and random node should keep the in-order transversal path.

- 0of 0 votes
You have a stream of numbers coming in (lets say more than a million). The numbers are between [0-999). Implement a class which can

insert(int i);

getMean();

getMedian();

in constant time O(1).

- 1of 1 vote
This is was asked in Amazon SDE online test from Hacker rank.

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

- 0of 0 votes
Merge two sorted singly linked lists into one sorted singly linked list. Allocate no extra node.

- 0of 0 votes
Given a sorted integer array. Convert it to a balanced BST (Size of array is given)

- 0of 0 votes
Allocate a 2-D array of size m*n using malloc(). The array should be accessible as a[i][j].

- 2of 2 votes
How to find middle element in a linked list without knowing the length of the linked list

- -1of 3 votes
A 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?

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 .

- 1of 1 vote
Design a data structure which could perform the following operations in O(1):

- 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)

- 1of 1 vote
You are given a stream of incoming strings. Design a data structure, which at any instant, could tell the 100 most repeated words in constant time.

- 0of 0 votes
Given string a and b, with b containing all distinct characters, find the longest common subsequence's

length. Expected complexity O(nlogn).

- 1of 1 vote
Given a 4*n block, find number of different ways of filling it with 1*2 smaller blocks. Rotation of smaller blocks is allowed.