Data Structures Interview Questions
- 0of 0 votes
AnswersFind the(two) nodes which are at maximum distance in a binary tree?
- grave May 31, 2012 in India
This is not finding the distance but the nodes which are farthest.| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm Data Structures Trees and Graphs - 0of 0 votes
AnswersIn this problem, you have to implement a variation of Insertion Sort as described below.
- dev May 27, 2012 in United States
Suppose X is an array of N positive integers to be sorted. In this scheme, another array Y is used to store the
sorted integers. This array is to be viewed as a circular array, ie. index (N-1)+1 = index 0 and index 0-1 =
index N-1. The sorted integers get stored in a circular manner in Y, ie, it is possible that the index of the
smallest integer may be greater than the index of the largest integer.
Eg. 6 8 _ _ _ 1 2 4 5 is a view of the array Y sometime into the algorithm. ’_’ indicates unused locations of
the array. Smallest integer 1 is at index 5, largest integer 8 is at index 1. So the sorted array in Y is to be
generated by printing the contents from index 5 to 1, assuming the array wraps around at the end, ie. after
index 8, the next index is 0.
Assume that h holds the index of the smallest integer in Y and t holds the index of the largest integer in Y.
Initially,
1. h = t = 0
2. Y[0] = X[0] ie. the first integer in X[] is copied as the first integer in Y[].
3. All other elements in Y[] are initialised to a dummy value -1.
The rest of the integers in X[] are now inserted one by one into Y[] such that Y[] always contains a sorted
list of integers, with the smallest integer at index h and the largest at index t. This is done in the following
manner:
Let I be the next integer from X[] to be inserted into Y[]. Scan the array Y downwards from index h (with
wrap-around at the end) till index t and find out the place in Y[] where I has to fit in. If I fits in at either end
of the list, then insert it at the appropriate place in Y[]. Modify either t or h as appropriate to indicate the new
array structure; ie. either t is incremented or h is decremented (with wrap-around).
If I fits in somewhere in the middle of the list, then I should be inserted by shifting all the S smaller integers
one place to the left or by shifting all the L larger integers one place to the right, depending on the number of
integers to be shifted. That is, if S < L, the smaller integers should be shifted one place to the left and if S >=
L, the larger integers should be shifted one place to the right. Again either h or t should be modified
appropriately.
Example
Integers to be sorted X[]: 25 57 37 48 12 92 86 33
Contents of Y[] after inserting each integer from X[]:
Initially (t=0, h=0)
25 –1 –1 –1 –1 –1 –1 –1
57 fits in at end (t=1)
25 57 –1 –1 –1 –1 –1 –1
37 fits in middle, S=1, L=1, so shift 57 right. (t=2)
25 37 57 –1 –1 –1 –1 –1
48 fist in middle, S=2, L=1, So shift 57 right. (t=3)
25 37 48 57 –1 –1 –1 –1
12 fits in at beginning, circular property, (h=8, t=3)
25 37 48 57 –1 –1 –1 12
92 fits in at end (t=4).
25 37 48 57 92 –1 –1 12
86 fits in middle, S=5, L=1, so shift 92 right, (t=5).
25 37 48 57 86 92 –1 12
33 fits in middle, S=2, L=5, so shift 12, 25 left (h=7, t=5).
33 37 48 57 86 92 12 25
Input Specification
The input will consist of a single line containing an integer N followed by the N integers to be sorted. All
integers are positive and are separated by a single space. There will be no duplicates among the N integers.
Output Specification
The output should consist of N lines, each line containing N integers. The N integers are the contents of Y[]
(ie. Y[0] to Y[N-1]) after the insertion of each integer from X[]. All integers on a line should be separated by
a single space. N will be less than 50.
Sample Input/Output
Input
8 25 57 37 48 12 92 86 33
Output
25 -1 -1 -1 -1 -1 -1 -1
25 57 -1 -1 -1 -1 -1 -1
25 37 57 -1 -1 -1 -1 -1
25 37 48 57 -1 -1 -1 -1
25 37 48 57 -1 -1 -1 12
25 37 48 57 92 -1 -1 12
25 37 48 57 86 92 -1 12
33 37 48 57 86 92 12 25| Report Duplicate | Flag | PURGE
Lunatic Server Solutions Java Developer Data Structures Sorting - 0of 0 votes
AnswersRain strikes and the roads are flooded, Mr X has to get home from work. Your task is to make sure he
- dev May 27, 2012 in United States
returns home in the shortest time.
Consider the roads as a graph with crossings as nodes, and the path between two nodes as an edge. Assume
the graph is undirected and the nodes are numbered, 1 to V (V <= 50).
The input consists of :
1. An integer H on a line, this is the height of Mr X.
2. Two integers N and M on the next line, where, N is the number of edges in the graph. M is the
number of nodes in the graph.
3. A sequence of N lines each having 4 integers : C1 C2 T D where, C1, C2 are the nodes (or
crossings), T is the time it takes to go from C1 to C2. D is the water depth along the edge(or road)
from C1 to C2.
Note: The depth D has to be less than the height of Mr X for him to be able to take the road.
4. Two integers S and E indicating the node at which Mr X starts and where he is expected to go to,
respectively.
As output you have to give the shortest path starting at S, listing each vertex in the order and ending with E
that Mr X can take. Assume that there will be at least one way to reach the destination and that the shortest
path is unique.
Sample Input/Output
Input
5
10 7
1 2 10 4
1 4 6 3
1 5 8 2
2 3 2 1
3 7 1 2
2 6 1 3
4 6 4 4
6 7 2 5
5 4 2 6
5 7 6 1
1 7
Output
1 2 3 7| Report Duplicate | Flag | PURGE
Lunatic Server Solutions Java Developer Data Structures - 0of 0 votes
Answershi to all tech brains.
- dev May 25, 2012 in United States
we made an interview round and ask this problem.
problem needs complete solution in java.
Any one of you who can solve it may appreciate and will get some benefits.
In this problem, you have to implement a sorting algorithm called Tournament sort, which uses a complete
binary tree.
The depth D of the tree will be given as input. Also, N positive integers will be given, where N is the Dth
power of 2 (ie, 2 ** D).
Construct a complete binary tree of depth D and fill in the leaf nodes with the N given integers in the order
given ie. the first integer should be at the leftmost leaf and the last integer should be at the rightmost leaf.
Next, update all the non-leaf nodes in the tree such that each nonleaf node contains the maximum of the
values in its children. Thus, the root will contain the maximum of all the N integers.
Implement a procedure ’maxdelete’ which essentially removes the maximum value from the tree and updates
the tree as follows:
1. traverse the tree from the root
2. find the leaf with the maximum value ie. the value at the root. (note that in this tree, if the value at a
non-leaf node is T, either its left child or its right child will have value T).
3. replace the value at that leaf node with -1 and
4. update the rest of the non-leaf nodes such that each non-leaf node contains the maximum of the
values in its children.
Perform the ’maxdelete’ operation 3 times on the tree and print out the INORDER traversal of the tree after
each operation.
Example
Given depth = 2
Given integers: 25 57 37 48
Constructed and updated tree:
57
/ \
57 48
/ \ / \
25 57 37 48
after first 'maxdelete'
48
/ \
25 48
/ \ / \
25 -1 37 48
after second 'maxdelete'
37
/ \
25 37
/ \ / \
25 -1 37 -1
after third 'maxdelete'
25
/ \
25 -1
/ \ / \
25 -1 -1 -1
Input Specification
The input will consist of a positive integer D followed by a positive integer N (where N is the Dth power of
2) followed by N positive integers. All the integers are separated by a single space and will be on a single
line. There will be no duplicates among the N integers. D will be greater than 1 and less than 9.
Output Specification
The output should consist of 3 lines. Each line should contain the INORDER traversal of the tree after a
’maxdelete’ operation. All the integers on a line should be separated by a single space.
Sample Input/Output
Input
2 4 25 57 37 48
Output
25 25 -1 48 37 48 48
25 25 -1 37 37 37 -1
25 25 -1 25 -1 -1 -1| Report Duplicate | Flag | PURGE
Lunatic Server Solutions Java Developer Data Structures - 0of 0 votes
AnswersConsider a service counter. People waiting for service form a queue. At the start, the queue is empty and
- Anonymous May 23, 2012 in United States
time is 0. The service time per person is 3 minutes.
The input to the program consists of an integer N followed by a sequence of integers indicating the arrival
time (in minutes) of the customers. These times are given as offset from the start of the simulation, so that an
input of 44 means 44 minutes from the start of simulation. The sequence of input numbers is terminated by
the number -1.
Your program must simulate the queue and print out the following:
1. The number of customers waiting in the queue at time = N minutes from the start of simulation.
2. The arrival times of the customers in the queue at that time, in increasing order.
Each integer must be separated by a space. Terminate your output with a newline character.
For doing the computation, you can assume that if the counter is expected to be vacant at time t, the first
person in the queue will be scheduled for service, before the counting is done for time t.
You must use the queue data structure to solve this problem.
Sample Input/Output
Input
9 0 2 5 6 6 8 10 -1
Output
2 6 8
provide the solution using QUEUE.
This problem will tell you your coding power.| Report Duplicate | Flag | PURGE
Lunatic Server Solutions Developer Program Engineer Data Structures - 0of 0 votes
AnswersConsider a service counter. People waiting for service form a queue. At the start, the queue is empty and
- PriyaDarad May 22, 2012 in United States
time is 0. The service time per person is 3 minutes.
The input to the program consists of an integer N followed by a sequence of integers indicating the arrival
time (in minutes) of the customers. These times are given as offset from the start of the simulation, so that an
input of 44 means 44 minutes from the start of simulation. The sequence of input numbers is terminated by
the number -1.
Your program must simulate the queue and print out the following:
1. The number of customers waiting in the queue at time = N minutes from the start of simulation.
2. The arrival times of the customers in the queue at that time, in increasing order.
Each integer must be separated by a space. Terminate your output with a newline character.
For doing the computation, you can assume that if the counter is expected to be vacant at time t, the first
person in the queue will be scheduled for service, before the counting is done for time t.
You must use the queue data structure to solve this problem.
Sample Input/Output
Input
9 0 2 5 6 6 8 10 -1
Output
2 6 8| Report Duplicate | Flag | PURGE
Lunatic Server Solutions Developer Program Engineer Data Structures - 0of 0 votes
Answera tree is either:
- a branch with a list of child trees
- or a leaf with a value@ / | \ / | \ @ D @ / | \ | | | | | A B C E
1) write a struct to represent it.
2) write a function f() to print out leaf values in in-order travesal
- Itcecsa May 21, 2012 in United Statesclass InvalidTree { }; template <class T> struct tree { vector<tree> child; T* value; // no empty tree is allowed tree(vector<tree>& _tree, T* _t) { if( !_t && _tree.empty() ) throw InvalidTree(); } bool IsLeaf() const { return branch.empty(); } T* GetValue() const { return value; } const vector<tree>& GetChild() const { return child; } }; template <class T> void f(tree<T>* root) { if(root->IsLeaf() ) { cout << root->GetValue(); return; } vector<tree> childs = root->GetChild(); for(vector<tree>::const_iterator iter = childs.begin(); iter != childs.end(); ++iter) { f(iter); } }
| Report Duplicate | Flag | PURGE
Jane Street Software Engineer / Developer Data Structures - 0of 0 votes
AnswersAmazon telliphonic 17 May, 2012
- adarsh May 17, 2012 in India
1.) There is a sequence where aphabets are written like this..
a,b,c,d,.......,x,y,z,aa,ab,ac........,az,ba,bb,bc,bd......bz,ca,cb.........cz........,aaa,aab,aac.....aaz,............zzz,aaaa...........zzzz..... and so on..
WAP to find out the string value at kth position.
like if k= 28 the string on 28 will be "ab".| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Data Structures - 0of 0 votes
AnswersIn given array of elements like [a1,a2,a3,..an,b1,b2,b3,..bn,c1,c2,c3,...cn] Write a program to merge them like [a1,b1,c1,a2,b2,c2,...an,bn,cn].
- masoom May 13, 2012 in India
PS: Do it without using extra memory
Sample Testcases:
Input #00:
{1,2,3,4,5,6,7,8,9,10,11,12}
Output #00:
{1,5,9,2,6,10,3,7,11,4,8,12}
Explanation:
Here as you can notice, the array is of the form
{a1,a2,a3,a4,b1,b2,b3,b4,c1,c2,c3,c4}| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Data Structures - 3of 3 votes
AnswersQ1.- Written exam (Amazon, Bangalore)
- Nitin Gupta May 12, 2012 in India
Given a singly link list and a number 'K', swap the Kth node from the start with the Kth node from the last. Check all the edge cases.
Sample Input: 1->2->3->4->5->6->7->8 and K = 3
Sample Output : 1->2->6->4->5->3->7->8
Sample Input: 1->2->3->4->5->6->7->8 and K = 10
Sample Output: print error "LIST IS OF LESSER SIZE".| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm C C# C++ Coding Data Structures Java Linked Lists - 0of 0 votes
AnswersQ2. F2F Round-1, Amazon(Bangalore)
- Nitin Gupta May 12, 2012 in India
Given an array of integers having the property that first that array is strictly increasing then it is strictly decreasing, You have to search for a given number.
Constraint: Minimize the complexity| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm Arrays C C# C++ Coding Data Structures Java - 0of 0 votes
AnswersQ1. F2F Round 1 Amazon(Bangalore)
- Nitin Gupta May 12, 2012 in India
Given a character array as input. Array contains only three types of characters 'R', 'G' and 'B'. Sort the array such that all 'R's comes before 'G's and all 'G's comes before 'B's.
Constraint :- No extra space allowed(except O(1) space like variables) and minimize the time complexity.
You can only traverse the array once.| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm Arrays C C# C++ Coding Data Structures Java Sorting - 0of 0 votes
AnswersQ4. Written Exam Amazon(Bangalore)
- Nitin Gupta May 12, 2012 in India
Given an array of integers A[1....n-1] where 'N' is the length of array A[ ]. Construct an array B such that B[i] = min(A[i], A[i+1], ......., A[i-K+1]), where K will be given.
Array B will have N-K+1 elements.
Constraint: Extra space allowed O(K) and time complexity allowed O(N.K) or lower.| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm Arrays C C# C++ Coding Data Structures Java Sorting - 1of 1 vote
AnswersQ3. Written Exam Amazon(Bangalore)
- Nitin Gupta May 12, 2012 in India
Given a singly linked list which may or may not contain loop and loop may or may not start from the head node. Count the number of elements in the linked list.| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm C C# C++ Coding Data Structures Java Linked Lists - 0of 0 votes
AnswersGiven an array of integers, return the first integer which occurs only once in O(n).
- Evan May 01, 2012 in United States| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Data Structures - 0of 0 votes
AnswersWrite a program to:- Finding the “Nth node from the end” of a linked list
- rasmiranjanbabu April 27, 2012 in India| Report Duplicate | Flag | PURGE
Dover Organization Developer Program Engineer Data Structures - 0of 0 votes
AnswersWrite an algorithm to split a circular linked list two linked list with equal no of nodes
- brijithb April 25, 2012 in India| Report Duplicate | Flag | PURGE
Adobe Software Engineer / Developer Data Structures - 1of 1 vote
AnswersGiven a dictionary of strings [ strings are in sorted order] you have to find the precedence of characters according to the dictionary..
- Anton April 21, 2012 in India
eat
bxy
e is ranked above b according to the dictionary.| Report Duplicate | Flag | PURGE
Google Amazon Software Engineer / Developer Algorithm Data Structures Trees and Graphs Brain Teasers - 0of 0 votes
AnswersN players played in a tournament and the results are out. Each player has played all other players. To print out a combination 1,2,3, .. , i-1, i, i+1,....n such that i-1 has lost to player i and player i has lost to i+1.
- anuj78 April 21, 2012 in India
What would be the complexity for the same?| Report Duplicate | Flag | PURGE
Amazon Algorithm Data Structures - 0of 0 votes
Answersinterviewer, do you know what is an expression tree?.I said No.Than he explained.
- pga April 16, 2012 in United States
He asked me to computer the value of the expression tree.
%
1 +
5 8
How to solve this. It took me 30 minutes to get the answer?.| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Data Structures - 0of 0 votes
AnswersWrite a program for binary tree (not BST) where left is connected to right and the whole structure is connected.
- ps April 16, 2012 in United States| Report Duplicate | Flag | PURGE
Microsoft Software Engineer in Test Data Structures - 0of 0 votes
AnswersA node of a binary tree has two pointers left and right and two data fields- left count and right count. left count specifies the number of nodes in left of the node and right specifies the number of nodes in right of the node. Write an algorithm to populate the data fields of all the nodes of the tree.
- rising April 14, 2012 in India| Report Duplicate | Flag | PURGE
Oracle Software Engineer / Developer Data Structures - 0of 0 votes
AnswersWrite a function for reversing a doubly linked list.
- Parbays April 14, 2012 in India| Report Duplicate | Flag | PURGE
Adobe Software Engineer / Developer Data Structures - 0of 0 votes
AnswersReturn true if two trees are same
- RohitDumbre86 April 10, 2012 in United States| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Data Structures - 0of 0 votes
AnswersAn array has duplicate elements each elements occurs even number of time except one occurs odd number of times. Print that number. Provide the complexites of the solution
- RohitDumbre86 April 10, 2012 in United States| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Data Structures - 0of 0 votes
AnswersDifference between LinkedList and arraylist as to what are the advantages of LinkedList
- RohitDumbre86 April 10, 2012 in United States| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Data Structures - -1of 1 vote
AnswerImplement a stack-based linked lists for generic objects in c++?
- apple-maybe? April 08, 2012 in United States for QA| Report Duplicate | Flag | PURGE
Apple Data Structures - 0of 0 votes
AnswersAll the Insert,delete and search complexities for Arrays,HashMaps,Binary trees.
- An April 04, 2012 in United States| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Data Structures