## Data Structures Interview Questions

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

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

- 0of 0 votes
Given an array of numbers, for every index i, find nearest index j such that a[j] > a[i].If such an index doesn’t exist for i, 1 should be printed.

- 1of 1 vote
Data structure which supports both map operations and array operations without time complexity penalty.

- 0of 0 votes
Write func repeat(e, n).

Args:

e: any object

n: a number of times

Returns:

an iterator producing the element e n times

- 0of 0 votes
How is the per-process file/socket descriptor table is implemented in Linux? Specifically, which data structure(s) and algorithms are used to implement it and keep it efficient.

- 0of 0 votes
Given an array of integers. Modify the array by moving all the zeros to the end (right side). The order of the other elements doesn't matter.

- 1of 1 vote
How to find if a given expression is a valid arithmetic expression?

Eg:(())()) - Invalid expression, (()()) - Valid expression

- 3of 3 votes
Given a linkedlist, write an algorithm to divide the linkedlist into two linkedlists, the first contains the Fibonacci numbers in the list and the second contains the non-Fibonacci numbers.

Test the algorithm after developing the code

- 3of 3 votes
Suppose you have a incoming stream of numbers and a method like T* readNextNumber() to read them, and each time there is only limited amont of them coming in and readNextNumber would return null if no more available. implement a method to calculate the median of all numbers you have read.

The key point to the question is figure out the data structure to store those numbers you have read and I stopped at a balance tree, the interviewer told me it should be 2 heaps, one ascending and one descending, plus a median value between them. The final algorithm I figure out based on it is each time compare the new number with median, if bigger than it insert to the descending heap at the right side of the median else to the left, recalculate the median by checking heap sizes, the new median would be either current median, max of the left heap or min of the right heap.

- 1of 1 vote
Design a data structure which should have following operation. Insert, Delete, Random access

- 0of 0 votes
Design a system java same as relational database.

For example,

You Have employee table as bellow:`ID | Name | Manager | Salary`

Now you can execute queries like :

`select * from Employee where ID= ' something' select * from Employee where Name= ' something' select * from Employee where salary = ' something'`

In same way you have a class Emplyee as bellow:

`class Employee { String ID; String Name; String Salary; String Manager; }`

Now I want to query on this class as same as the sql queries above,

How can I do it efficiently?

The code should be optimized on time complexity and space complexity.

- 0of 0 votes
Implement a class to provide in real-time the list of the top 100 most viewed

properties in the last hour. For the purposes of this exercise, you should think of

"the last hour" as the 3600 seconds ending now. Properties are represented by a

"zpid" or Zillow property ID, which we will treat as a unique string.

Example, if the current time is 2:20:

| 1 | 2 | 3 | 4 |

|-------| <- we want this time range

One possible interface:

interface MostViewed

{

// Every user view of a property calls this:

void propertyViewed(String zpid);

//Anytime we want the top 'count' properties, we can call this:

//which returns a list of zpids

List<String> getCurrentMostPopular(int count);

}

- 1of 1 vote
Design a data structure in which we can do all CRUD operations in O(1) ?

CRUD- Create, Retrieve, Update, Delete

- 0of 0 votes
Write a function which will sort a linked list efficiently. I explain merge sort, However interviewer was not agree with my answer.

Interviewer was expecting answer bubble sort along with backtracking. Not convinced or agreed with his opinion though.

- 2of 2 votes
A single-elimination tournament with 64 teams. Before the tournament, fans construct fantasy brackets for their tournament predications. Design a data structure for storing fan brackets and algorithm to score their brackets against a winning bracket. Assume we will then need to quickly score a player’s predictions (1 point per successful round prediction) and your solution should be optimal enough to handle millions of fan brackets with minimal data.

- 3of 3 votes
Design a data structure that supports kind of full text search but in numbers.

We are given file with lot of 10-digits numbers, for example:

1234 567 890

4124 123 123

3123 123 322

On a given number X we should return all numbers that contain X.

For example, if the number 123 was given, we should return all numbers (from the list above) because 123 is in all of them.

If the number 41 was given we should return only the middle number - because the number 41 is only in it.

- 0of 0 votes
A client wants to build a software phone book that contains everyone in the world (7 billion people). Every person has only the first name and the name is unique. What data structure would you use to store the data?

- 0of 0 votes
Given a BST write a function that looks for a value.

- -1of 1 vote
Round 5

Question 4 : Now lets say you have 1 PB(1000 TB) of numbers, what kind of system you would prefer, not that you can't store this data in one box. How will you sort these many numbers, what is the time complexity in seconds ?. does increasing core per machine help here ?

- -1of 1 vote
Round 4

Question 3 : this question was similar to Round 2 Question No 3, which is basically convert row type of data to column type of data

- -1of 1 vote
Round 3

Question 2 : You are given a array of integers, array may have duplicates, you have to find out the rank k number, and then print out the k highest numbers ?

Required complexity is O(N) + O(1) space, duplicates may be an issue, on which she wanted me to put more focus.