## Data Structures Interview Questions

- 0of 0 votes
None 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?

Solve this whole problem.

Time allocated was 1 hour. Face to face, panel with 2 interviewers.

- 0of 0 votes
As 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()!

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.

- 0of 0 votes
Given a sorted (increasing order) array, write a program to create a binary tree with minimal height

- 0of 0 votes
Problem 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 :

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

- 0of 0 votes
Problem 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 :

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.

- 0of 0 votes
Problem 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 :

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.

- -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].