## Data Structures Interview Questions

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

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

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

- 1of 1 vote
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);

}

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

- 0of 0 votes
Round 2

Question 3 : You have to implement an external iterator which iterate the binary tree InOrder. You have to figure out what kind of iterator one should use, and implement each of those function. required complexity is O(N) time + O(log(N)) space

- -3of 3 votes
Round 1(taken by DATA SCIENTIST 2)

Question 1 : You are given a street map of a city, Every day you travel from your home to work. some day you take bus or someday your our car. Bus fare is also not constant, it may change in future, may increase or decrease ?

you have to find shortest path from your home to your work ?.

Note that : you have to expose this as library, so no custom assumptions. need to find out how you incorporate variable bus fare ?, also it is up-to the user to choose between bus and his car ?, in case of bus, you have to minimise the total money, and in case of care, you have to minimise the distance.

- 0of 0 votes
Given huge database of songs design search data structure and algorithm to search all songs with words starting with the letters entered and words matching the sequence of words entered.

Suppose the songs are:

1. Every night in my dreams

2. Listen to my heart

3. Show me the meaning

4. Night in London

5. Night changes

Entering "m" should list 1,2 and 3. "my" should list 1 and 2. "Night" should list 1,4 and 5. "Night in" should list 1 and 4.

- 0of 0 votes
Input Parser and Processor

Problem

Implement a java program for querying data from a java object. Java object need to be constructed based on text data provided to program.

The parser should be generic to parse any input confirming to the hierarchical format similar to the one mentioned in sample

The Content of the file

[employee]

name=john

age=30

salary=100

[address]

houseno=221b

street=bakerstreet

[location]

place=xyz

state=abc

country=123

[/location]

[/address]

designation = srDeveloper

[/employee]

Sample Input and Output

employee.name Output John

employee.address.houseno Output 221b

employee.address.location.state Output abc

employee.manager Output NOT_FOUND

The program should work any object data specified as input file.

- 1of 1 vote
Tech Screening

Question 1 : You will be given a stream of integers, and a integer k for window size, you will only receive the streams integers one by one. whenever you receive an integer, you have to return the maximum number among last k integers inclusive of current entry.

Interviewer was expecting O(N) solution for N asks.

Edits: Interviewer was expecting O(N) Time + O(1) avg case space complexity solution for N asks.

and integers are not given in a array, every time only one integer will be passed as input to your method.

- 0of 0 votes
Round 3

Question 1, you are given a puzzle, You can check the image here`https://drive.google.com/file/d/0B6-TjTC-KfTqQThBamxPa0NwNGM/view?usp=sharing`

You have to write a program to provide a solution for this.