## Data Structures Interview Questions

- -1of 1 vote
JAVA:

Given an array say of length 1000; Pick up every value from every 20th index and store it in a separate array. Make sure to loop through all the elements in the array. Example: newArray1 = {0, 20, 40, 60, ..};

newArray2 = {1, 21,41, 61, ..};

- 0of 0 votes
Given an array say of length 1000; Pick up every value from every 20th index and store it in a separate array. Make sure to loop through all the elements in the array. Example: newArray1 = {0, 20, 40, 60, ..};

newArray2 = {1, 21,41, 61, ..};

- -1of 1 vote
package jp.co.worksap.global;

import java.util.NoSuchElementException;

/**

* The Queue class represents an immutable first-in-first-out (FIFO) queue of objects.

* @param <E>

*/

public class ImmutableQueue<E> {

/**

* requires default constructor.

*/

public ImmutableQueue() {

// modify this constructor if necessary, but do not remove default constructor

}

// add other constructors if necessary

/**

* Returns the queue that adds an item into the tail of this queue without modifying this queue.

* <pre>

* e.g.

* When this queue represents the queue (2, 1, 2, 2, 6) and we enqueue the value 4 into this queue,

* this method returns a new queue (2, 1, 2, 2, 6, 4)

* and this object still represents the queue (2, 1, 2, 2, 6) .

* </pre>

* If the element e is null, throws IllegalArgumentException.

* @param e

* @return

* @throws IllegalArgumentException

*/

public ImmutableQueue<E> enqueue(E e) {

return null;

}

/**

* Returns the queue that removes the object at the head of this queue without modifying this queue.

* <pre>

* e.g.

* When this queue represents the queue (7, 1, 3, 3, 5, 1) ,

* this method returns a new queue (1, 3, 3, 5, 1)

* and this object still represents the queue (7, 1, 3, 3, 5, 1) .

* </pre>

* If this queue is empty, throws java.util.NoSuchElementException.

* @return

* @throws java.util.NoSuchElementException

*/

public ImmutableQueue<E> dequeue() {

return null;

}

/**

* Looks at the object which is the head of this queue without removing it from the queue.

* <pre>

* e.g.

* When this queue represents the queue (7, 1, 3, 3, 5, 1),

* this method returns 7 and this object still represents the queue (7, 1, 3, 3, 5, 1)

* </pre>

* If the queue is empty, throws java.util.NoSuchElementException.

* @return

* @throws java.util.NoSuchElementException

*/

public E peek() {

return null;

}

/**

* Returns the number of objects in this queue.

* @return

*/

public int size() {

return -1;

}

}

- 0of 0 votes
How will you design, and what data structure will you use for a contact list in a cell Phone. It should support insert/modify/delete/search functionality like that provided in a cell phone.

Suppose some of the entries are

Aman

Amazon

Neha Aman

and we type 'ama'

then the result should show all the above three enteries.

Also it should be possible to search using phone numbers.

- 0of 0 votes
Given an array[0, n-1], each number of the array is positive int. Your task is adding the operators,"+","*", "(",")" (add, multiply, parenthesis) to maximize the result . The position in the array is Fixed.

For example, "2,1,1,2", you can get (2+1)*(2+1)=9.

Follow up, if the number may be negative , how to solve it ?

- 0of 0 votes
Design a system like friend's functionality in facebook. should have all features of facebook's friends functionality. like for each person , he can have any number of friends , he will get suggestions for new firends , showing common friends if we visits any other profile . algo should be scalable , robust .

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

- 3of 3 votes
Given a complete binary tree, Find a Max element

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

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