Data Structures Interview Questions
- 0of 0 votes
AnswersYou have a binary tree (not BST), serialize it in a stream and reconstruct the tree maintaining the format of the tree.
- amzngoogaapl August 03, 2012 in United States
sending 2 streams InOrder+PreOrder or InOrder+PostOrder is not an option.| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Data Structures - 0of 0 votes
AnswersWhich data structure will you use for creating a real world dictionary?
- kavitha July 31, 2012 in United States| Report Duplicate | Flag | PURGE
Adobe Software Engineer in Test Data Structures Java - 0of 0 votes
AnswersYou have a sorted circular linked list and a sorted linear linked list. Write a program to merge these two arrays and create a new sorted circular linked list
- kavitha July 31, 2012 in United States| Report Duplicate | Flag | PURGE
Adobe Software Engineer in Test Data Structures Java - 0of 0 votes
AnswersDelete the nth node in a linked list by passing only "n" as a parameter to the function. i.e the function does not have the address of the first node of the Linked list.
- jaiswal.amarnath July 29, 2012 in India| Report Duplicate | Flag | PURGE
HCL Software Engineer / Developer Data Structures - 0of 0 votes
AnswersWhat's the difference between a Hash Table & Hash Map? How would you handle a collision where key/hash are different, and visa-versa?
- Yev July 26, 2012 in United States for Risk Metrics| Report Duplicate | Flag | PURGE
Highbridge Capital Java Developer Data Structures - 0of 0 votes
Answershow map is implemented? how insert and delete works?
- Sach July 24, 2012 in India| Report Duplicate | Flag | PURGE
Igate Technical Architect C++ Data Structures - 1of 1 vote
AnswersHow to stop recursion stack as soon as we find a result.
- Ashupriya July 22, 2012 in United States
e.g. in a Tree recurion where the Order of the algo is O(n) and suppose we find the result just after 4 calls, can we empty the recursion stack and stop the ececution right away...| Report Duplicate | Flag | PURGE
Software Engineer / Developer Algorithm Data Structures General Questions and Comments Ideas Java - 0of 0 votes
AnswersCreate the n-ary tree from the ancestor matrix.
- grave July 19, 2012 in India
matrix[i][j]=1 if i is the ancestor of j.
My answer-
find the root (row with all zeroes).
Set the column with a[i][root] =0
find all the rows with all zeroes.insert into the tree all the children.and push all into the queue.
pop and find the children ,insert into the tree with popped node as parent and push into the queue.
Can not implement properly as it needed some modifications.
This is asked from my friend at amazon bangalore.| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm Arrays Data Structures Trees and Graphs - 0of 0 votes
AnswersGiven a pointer to the root of a binary tree , check whether the tree is
- cobra July 19, 2012 in India
balanced or not.| Report Duplicate | Flag | PURGE
Microsoft Data Structures - 0of 0 votes
AnswersCan we access the node of a tree using pointer ?
- niraj.nijju July 17, 2012 in India
if yes then give an example to traverse tree using pointer?| Report Duplicate | Flag | PURGE
Data Structures - 0of 0 votes
Answersdevise an algorithm to color the graph in such a way that no two adjacent vertices have same color.You have to color them with any of the two colors say red or green?what will the time and space complexity of the solution.
- softy July 15, 2012 in India| Report Duplicate | Flag | PURGE
Mentor Graphics MTS Algorithm Data Structures - 0of 0 votes
Answersfind the balance index of an array where balanced index i is defined as the one whose left sum is equal to the right sum of the index .
- softy July 15, 2012 in India for bing
i.e
summation (1 to i-1) = summation (i+1 to length of an array) firdt I gave o(n2) solution , but then before i could give O(n) solution it was time up for me,
O(n) solution will be we have to loop through i = 1 to N and find if ( sum of array - sum of array (1 to i-1 ) = ( sum of array - sum of array (1 to i+1 ) the return i.
Your thoughts?| Report Duplicate | Flag | PURGE
Microsoft Algorithm Arrays Coding Data Structures - 2of 2 votes
AnswersUser inputs a sequence of digits. Every digit is a keystroke, that is equivalent to some character out of a sequence of characters. Digit zero and five mean NULL. The table is given below
- ranechabria July 14, 2012 in United States
0 - NULL
1 - v, t, f, r, q
2 - f, t, k
3 - w, z, b, g
4 - r, s
5 - NULL
6 - f, i, r
7 - p
8 - l, o
9 - p
Generate all possible character sequence for a given sequence of digits.
Ex - If the user input 9801, your program should generate
{plv, plt, plf, plr, plq, pov, pot, pof, por, poq} (not necessarily in this order).
This problem is somewhat similar to the SMS problem. It basically boils down to generating a cartesian product of the character sets corresponding to keys.| Report Duplicate | Flag | PURGE
Epic Systems Software Engineer / Developer Algorithm Coding Data Structures - 0of 0 votes
AnswersImplement insert and delete in a tri-nary tree. Much like a binary-tree but with 3 child nodes for each parent instead of two -- with the left node being values < parent, the right node values > parent, and the middle node values == parent. For example, if I added the following nodes to the tree in this
- chad July 12, 2012 in United States| Report Duplicate | Flag | PURGE
Zillow Software Engineer / Developer Data Structures - 1of 1 vote
AnswersImplement the plusplus operator when we are getting the input as integer array = { 9,9,9,9 }.output will be {1,0,0,0,0}
- JobHunter July 11, 2012 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm Arrays C Coding Data Structures - 1of 1 vote
AnswersGiven an array which contains the parent of the ith element in the n-ary tree.Parent[i] = -1 for root.
- grave July 07, 2012 in India
Find the height of the tree.
Gave O(n2) ,space O(1).
Expected Complexity- Linear
You can use extra space if you want.
Example-
{-1 0 1 6 6 0 0 2 7}
0 1 2 3 4 5 6 7 8
0 is the root here.
0 is the parent of 1 5 6
1 is parnt of 2
6 is parent of 3 4
2 is of 7 which is parent of 8.| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm Data Structures Hash Table Trees and Graphs - 0of 0 votes
AnswersWrite a function to count the number of numbers between two 64 bit numbers a, b that have the sum of their bits equal to a fibonacci number. E.g Between 15 and 17 there are two numbers that have sum of bits equal to a fibonacci number.
- 14.ashish July 05, 2012 in India
15: 1111 sum=4
16: 10000 sum=1 (fibonacci)
17:10001 sum=2 (fibonacci)
I can do it with 0(n) where n being the no of elements between range but i want a better solution where i donot need to go through all the numbers. I want to know the pattern. Like if i take the complete range of 64 bit numbers then a simple pattern to identify all these numbers is (64c1+ 64c2+ 64c3+ 64c5+ 64c8.... 64c53). Similarly a pattern for given range.| Report Duplicate | Flag | PURGE
Amazon Data Structures - 0of 0 votes
AnswersGiven a binary tree whose node structures have an extra member to hold an integer value. Fill these with values that is equal to the total number of Left nodes in the left sub-tree minus total number of nodes in right sub tree.
- raj.kamal.nitj July 05, 2012 in India| Report Duplicate | Flag | PURGE
Software Engineer / Developer Data Structures - 0of 0 votes
AnswersYou have yesterday's and today's log files that contains ids of users who logged in on amazon's website (there could be million entries). Design and implement way to find out user ids who logged in on both days.
- bobbysanders007 July 01, 2012 in United States| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm Data Structures - 0of 0 votes
AnswersGiven two integer unsorted arrays, your task is to compare the BST formed by both the arrays.
- shivi116 June 30, 2012 in India
any o(n) solution???| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Data Structures - 0of 0 votes
AnswersDesign any datastructure with three methods insert, delete and getRandom in a highly optimized way. The interviewer asked me to think of a combination of datastructures to design a new one. Insert can be designed anyway but for random and delete i need to get the position of specific element. He gave me a hint to think about the datastructure which takes minimum time for sorting.
- Vikram June 27, 2012 in India| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Data Structures - 0of 0 votes
AnswersIf i type some numbers in my cell, all phone numbers which have these typed nos in any order should appear, tell data structure for this.
- Aashish June 25, 2012 in United States
eg:if i type 926 then
932678....
92678...
9777726....
should appear.
[EDIT]: It seems you have lot of confusion.
Let me clear it through another example
eg: i enter 321, then
o/p(if they r in book)
9344241..
972153....| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Data Structures - 0of 0 votes
AnswersHow to check a whether a very big number n^n = k
- banerjees36 June 22, 2012 in India| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Systems Design Engineer Algorithm Data Structures - 0of 0 votes
AnswersDesign LRU cache data structure
- kamoliddin June 21, 2012 in United States| Report Duplicate | Flag | PURGE
Amazon Data Structures - 0of 0 votes
AnswersWrite code to compute number of structural different binary trees for given 'n' number of nodes. (with and without Catalan number)
- Ram June 10, 2012 in United States| Report Duplicate | Flag | PURGE
Algorithm Data Structures Math & Computation - 0of 0 votes
AnswersGiven an n-ary tree (i.e. it can have max n children). One need to roll up the tree from leaves back to root such that the data of root will be the sum of root's data and sum of all its children data.
- Vyshnavi June 10, 2012 in India| Report Duplicate | Flag | PURGE
Amazon Data Structures - 0of 0 votes
AnswersConstruct a BST and do its zigzag traversal.
- souptikpro June 03, 2012 in India| Report Duplicate | Flag | PURGE
Directi Software Engineer / Developer Data Structures