## Data Structures Interview Questions

- 0of 0 votes
Design a phone book such that fields are searchable with name , with number. Later enhanced teh question asking searchable with address as well.

- 1of 1 vote
How to design a multi key hash map ( key count can be dynamic. if there are two keys , initiallly which can be used to find the value , keys can be increased to three as well ex: consider school structure. Intially , consider , student id is key , later , should be searchable even with key name , later with grade.

- 1of 1 vote
Design a telephone directory for large ppl (he gave example like design for India). fields will be , first name , last name , number . this should be searchable with first name , last name , number as welll.

later added more complexity like do the same for organisation where even it contains designations. so this should be searchable with designations.

- 0of 0 votes
Can anyone provide implementation of Suffix tree and trie?

- 2of 2 votes
Given a complete binary tree, print the outline of the tree in anti-clockwise direction, starting from the root. I.e. first print all the nodes on the left

edge of the tree going downwards, then print all the leaves going left to right (including leaves on both the last and the 2nd last level if necessary), then

print the nodes on the right edge of the tree going upwards.

Example tree:

A

/ \

/ \

B C

/ \ / \

D E F G

/ \ /

H I J

Expected Output: ABDHIJFGC

- -2of 2 votes
How do I prepare for Flipkart's Data Structuring round ? I have so far cleared the problem solving round. What kind of questions should I expect ?

- 0of 0 votes
Write a java program to find out 5000th number in the fibonacci series.?

For example:

5th number is 5.

6th number is 8.

10th number is 55.

5000th number is ????.

- -1of 1 vote
Write code to read from a file and build datastructure that helps you query products based on their category, title, author etc.

ItemNo , Product No (unique), Title, Author, Category

1 , 00000001, Cracking Coding Interview, Gayle Laakmann McDowell , Books > Business, Finance & Law > Careers > Job Hunting

2 , 000002, The Art of Captaincy, Robert James, Books > Biography > Sport > Cricket

- 1of 1 vote
Write a program to return minimum number of swaps required to convert this binary tree into a BST.

- -1of 1 vote
Draw a graph as a graph. Assume there is graphics library to draw lines and all. Just tell how will you order the vertices such that the edges don't intersect and they seem ordered.

- -1of 1 vote
struct st{

int a;

char *ptr;

}obj;

assign : a=10;

ptr="Hello world";

- 1of 1 vote
Create the data structure for a component that will receive a series of numbers over the time and, when asked, returns the median of all received elements.

(Median: the numerical value separating the higher half of a data sample from the lower half. Example: if the series is

2, 7, 4, 9, 1, 5, 8, 3, 6

then the median is 5.)

Model the data structure for a component that would have these two methods:`@interface SampleHandler { - (void)addNumber:(NSNumber*)number; - (NSNumber*)median; }`

Justify your decisions. Calculate the complexity of each method.

- 0of 0 votes
Design an LRU Cache with constant lookup, i.e, searching and updating should all happen in O(1) time. Assume a method of calculating the least recently used page is already given. Just implement the searching and updating logic which takes constant time.

- 0of 0 votes
Implement LRU cache of size 10 which can store Key, Value pair. (get(key) & put(key,value) methods)

- If we try to add 11th element, the least recently used element should get removed.

- If key already present, overwrite it and mark it as most recently used.

- 0of 0 votes
For a given binary search tree, replace each node with sum of all node which are greater then of equal to current node.

- 0of 0 votes
Machine Coding 1 hour

------------------------------

U have an organizational structure, which shows hierarchy of the organization. This hierarchy contains employees E or managers M who has some Employees or Managers reporting to M.

Employee has ( id, name, JobDesc, salary etc).

Design the data structure you would be using to store this hierarchy

problem 1: Given an ID of an employee , print all the employee ID's who are directly reporting or indirectly reporting to the manager.

problem 2: prefix search of employees by String. If employees have nishant and nikhil. If searched by "ni" we need to print all details of both nishant and nikhil.

problem 3(bonus): search should print all emloyee's and their details if a given string is subString of the name of an employee.(Like a phonebook contacts search)

P.S- This was asked to one of my friend in Flipkart.

- 0of 0 votes
give me the code for :

Given a string say "I am a human being" the output should reverse all letters of each word but not the whole string as such.

Eg: O/p should be "I ma a namuh gnieb"

I somewhat wrote the code, but i was asked what if there are extra spaces etc.

(i am able to write the code sitting at my desktop at one short but there front of interviewer i am struggling. Need to build up my confidence)

let me know the best and optimised way of writing this code.

Also i suggest people to aviod using inbuilt functions as much as possible

My Answer is as below in perl`#i want the reverse of the letters of all words in a string #eg Input is "I am a human being" then o/p shud be "I ma a namuh gnieb" $str="I am a human being"; @arr=split(' ',$str); print @arr; for($i=@arr-1;$i>=0;$i--) { $_=@arr[$i]; ####intead of above for loop if we use foreach(@arr) then it will reverse the whole string @word=split('',$_); { foreach $n (@word) { unshift(@final,$n); } } } print "\n @final \n";`

- 1of 1 vote
Given an array say [0,1,2,3,5,6,7,11,12,14,20]

given a number say 5.

Now find the sum of elements which sum to 5

eg:2+3=5, 0+5=5 etc.

I guess the interviewer wanted all possible combinations eg 0+2+3=5, etc

- 0of 0 votes
How to find starting of loop in a link list in case looping somewhere.

For ex: 1->2->3->4->5->3

- 0of 0 votes
Given a list with duplicate values find the first unique elements in it.

for eg: BH BH F AL HJ AL HJ PK

so answer is F

- 1of 7 votes
Given an excel column number convert it to excel column alphabet and reverse.

Example : If column number(starts from 0) = 26 : Column alpha = AA.

- 3of 3 votes
Print all paths of a binary tree from root to leaf.

Later, extend the solution to work with graphs, careful attention to cycles which you should print as paths as well (without printing visited nodes twice).

- 0of 0 votes
Compare time complexity of insert and search functions in HashMap, Array, Linked List and Queue

- 2of 2 votes
You are given a large set of integers, which are not sorted. Figure out a method to retrieve the largest 1000 elements, in O(n) run time

- -1of 3 votes
how to print this pattern

input N=4

output :

4444444

4333334

4322234

4321234

4322234

4333334

4444444

input N=3

output :

33333

32223

32123

32223

33333

- -1of 1 vote
Print the Pattern

input N=4

output :

4444444

4333334

4322234

4321234

4322234

4333334

4444444

input n=3

output :

N=3

33333

32223

32123

32223

33333

- 0of 0 votes
There is a file which contains N words. There may be M anagrams in that file, K words on each anagrams. K>=1, M>=1, N>=1. You need to write an algorithm which will create one list for each anagram with k words and group all M lists with one data structure

- 1of 1 vote
Find your own method to balance an unbalanced binary tree.(you must not use existing methods like AVL, red black or b trees)

- 0of 0 votes
Convert a sorted integer Array to balanced binary search tree. This is very simple one and I could do it in O(n) time and O(1)extra space

- 0of 0 votes
Given 2 sorted linked list , merge them into single sorted list. Change the pointers, don't copy data