Data Structures Interview Questions
- 5of 5 votes
AnswersYou have a link list with the following structure:
- francisco.gutierrez.91 January 24, 2013 in United States for Office
struct Node{ Node*next; Node*other; }
next pointer points to next node, but "other" pointer points to any node in the list, it can be itself or null.
you receive the header of a list with this structure.
you have to copy it(allocate new memory) , you cannot modify the structure, you can not modify the list you are given.| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Linked Lists Algorithm Data Structures - 0of 0 votes
AnswersImplement a shared int pointer in C++ (SharedIntPtr).. the use would be like this:
SharedIntPtr a(new int); // reference count 1; SharedIntPtr b(a); // reference count 2; *a = 2; cout << *b; // "2"; a.reset(); // reference count -> 1 *a // <- NULL b.reset(); // reference count ->0 , object is deleted.
There is also this reference count which tells how many references do you have.
- rodrigoreis22 January 22, 2013 in United States
And the question was: Implement SharedIntPtr, constructors and reset().| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Data Structures - 0of 0 votes
AnswersHow does a site like Facebook store "Likes" ?
- bertrandreddy January 19, 2013 in United States
Whats the best approach for Space complexity and Time complexity ? Can we do it in O(1) space or at least O(n) space ?| Report Duplicate | Flag | PURGE
Google Member Technical Staff Algorithm Data Mining Data Structures Large Scale Computing - 0of 0 votes
Answers1.You are given a function calcDifference which takes in the root pointer of a
- kumar.prince6 January 13, 2013 in India
binary tree as it's input. Complete the function to return the sum of values of nodes at
odd height - sum of values of node at even height. Consider the root node is at height 1
/* Write your own custom functions here */
int calcDiff(node * root){
/*
struct node {
struct node *left,*right;
int val;
node(int x){
val = x;
}
};
typedef struct node node;
The structure is already declared, you can just start initializing nodes
*/
}| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Data Structures - 0of 0 votes
AnswersWhat is the difference between heap and priority queue?
- vigneshselvakumar January 10, 2013 in United States
What is its time complexity?| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Data Structures - 0of 0 votes
AnswersTime Complexity of array(both sorted and unsorted) and doubly linked list(both sorted and unsorted)?
- vigneshselvakumar January 10, 2013 in United States| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Data Structures - 0of 0 votes
AnswersHow would you define a data structure that stores a set of values (i.e., a value cannot appear more than one time), and implements the following functions:
- skeptical.scientist January 05, 2013 in United States
add(p)--adds the value p to the set
delete(p)--removes the value p from the set
getrandom()--returns a random value from the set (all items should be equally likely). (Assume you have access to some nice random() function.)
Need not write actual code, just sketch a structure to implement this efficiently.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Data Structures - 0of 2 votes
AnswersRound 3 :
- sonesh January 03, 2013 in India
Q 6 : You are given a ternary tree (a tree with 3 children at max with left, middle, right pointer at each node), create a singly linked list from it without using extra space ?| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Algorithm Data Structures Linked Lists Trees and Graphs - 3of 3 votes
AnswersRound 3 :
- sonesh January 03, 2013 in India
Q 5 : You are given a binary search tree, and a value(data item), you need to tell the left most right cousin in as minimum time and as minimum space ?(need to minimize actual time complexity, he need minimum order of complexity as well as number of node access should be minimum)| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Algorithm Data Structures Trees and Graphs - 0of 0 votes
AnswersRound 2 :
- sonesh January 03, 2013 in India
Q 2 : You are given finitely many intervals in 1D, you have to design a data structure an efficient data structure which can answer queries of the form “In how many intervals the point P belong ?”, P is an input point, and all intervals are closed. I answer B tree(think why) which is most efficient.| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Algorithm Data Structures Dynamic Programming Probability Trees and Graphs - -1of 1 vote
AnswersRound 2 :
- sonesh January 03, 2013 in India
Q 1 : You are the supervisor of an airport. What happens is that visitors are not visit your airport, instead they go to another one, which means your airport become unpopular nowadays, Now as a supervisor you need to find out what has happens ?, What went wrong ?,How do you find out ?, What is correct ?, How do you find correct one and at what cost ?| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Algorithm Behavioral Data Mining Data Structures Experience Ideas Probability Application / UI Design - 0of 0 votes
AnswersRound 1 :
- sonesh January 03, 2013 in India
Q 3 : What do you think, how the posts in Facebook are shown, to your page, as there are thousands of posts, likes, videos, images, links etc. shared by your friends, but not all are shown to you ? (Data mining question, have to tell appropriate solution which can work ?)| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Algorithm Data Mining Data Structures - 0of 0 votes
AnswersRound 1 :
- sonesh January 03, 2013 in India
Q 1 : When you visit on your friend’s Facebook profile, there is a mutual friend section where common friends are listed, now let’s assume that your friend do the same thing, he/she visit his/her friend other then you, now the people other than common are connected to you by distance of two. Similarly think you are given two people on Facebook, how do you find this connectivity?. (Please give appropriate solution),
Now let’s think that some important people are given some weight(any), now do the same thing ?
Now calculate the most influential person? (Not an easy question, because of weights) ?| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Algorithm Data Mining Data Structures Trees and Graphs - 0of 0 votes
Answersc = ‘a’
- zyfo2 December 26, 2012 in United States
w = “apple”
c covers w, iff w contains c.
c_set = {‘a’, ‘b’, ‘c’, ‘g’}
w_set = {‘apple’, ‘ibm’, ‘cisco’, ‘google’}
c_set covers w_set, iff every w in w_set is covered by some c in c_set.
Given c_set and w_set, Whether w_set is covered by c_set?
Follow up: if w_set is fixed say a book, how to determine whether a c_set covers this w_set?| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Data Structures - 3of 3 votes
AnswersA soccer league has n matches with A,B,C teams with number of goals scored by each team in each match.If a team wins against another team ,It gets 3 points and lost team gets 0 point.If a tie ,both team gets 1 point.Now how do you frame the ranking of teams.
- sriramMS December 20, 2012 in United States
1) All teams played n matches.
2) A team 1 match,B Team 2 matches, 3 team 3 matches.Like wise it goes.
They looked for coding and data structure techniques.| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm Data Structures - 0of 2 votes
AnswersA log file which has user details(user ID,timestamp) and pages visited in a particular day by that user.The next day -the same kind of log file gets generated.How do you find the probability of users who logged in consecutive days out of the second day - logged in users? The question is simple,but they look for the efficient data structure and time complexity.
- sriramMS December 20, 2012 in United States| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm Application / UI Design Arrays Assembly Automata Behavioral Bit Manipulation Brain Teasers C C# C++ Cache Coding Data Mining Data Structures - 0of 0 votes
Answersrepresent a n-ary tree with a data structure.
- jayeshr007 December 13, 2012 in India for wafl
and also check whether tree has a cycle or not?| Report Duplicate | Flag | PURGE
NetApp Software Engineer / Developer Data Structures - 0of 0 votes
AnswersHow to find length of a singly linked list with loops??
- AJ December 13, 2012 in India| Report Duplicate | Flag | PURGE
Amazon Developer Program Engineer Data Structures - 1of 3 votes
AnswersHow can you efficiently implement three stacks in a single array, such that no stack overflows until there is no space left in the entire array space.
- alex December 13, 2012 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Data Structures - 0of 0 votes
AnswersThe dynamic-set operation UNION takes two disjoint sets S1 and S2 as input, and
- Rahul December 10, 2012 in India for Kindle
it returns a set S = S1 U S2 consisting of all the elements of S1 and S2. The
sets S1 and S2 are usually destroyed by the operation. Show how to support UNION
in O(1) time using a suitable list data structure.| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Data Structures - 0of 2 votes
AnswersImplement a bus reservation system asume bus' seats are as follows
- rachitrocks2k December 10, 2012 in India for Bing
HHHHHH
HHHHHH
HHHHHH
. . . . . . . .
you can assume 10 rows in bus.
Now if user enters 4 as required seat no then the prefrence order would be
4
3,1
2,2
2,1,1
1,1,1,1
and the function should return the seat number.| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Data Structures - 1of 1 vote
AnswersPrint a binary tree in vertical order using singly linked list...complexity should be O(n)
- Nueman December 02, 2012 in India| Report Duplicate | Flag | PURGE
Groupon Software Engineer in Test Data Structures - 1of 1 vote
AnswersGiven a seria of points (Xi, Yi), find the line containing the highest number of points from the list.
- Grr1967 November 29, 2012
Per my question he mentioned that I can assume that there is a given function that receives two points and returns the a and b of the line euqation (aX+b)| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm Data Structures - 0of 0 votes
AnswersImplement queue using stack
- Survivor November 20, 2012 in United States| Report Duplicate | Flag | PURGE
Overstock.com Software Engineer / Developer Data Structures - 0of 0 votes
AnswersStream has 2 methods
- king Zidane November 15, 2012 in India for Aggregation
char getNextChar()
bool hasNextChar()
Stream is expected to have 1 M characters. Your application cant store them.
Want to find the 1st unique character in the stream| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Data Structures - 0of 0 votes
AnswersGiven List of some servers, if a server has some problem and if we want to load balance the servers how would you perform add, delete or pick a server at random most efficiently.
- annonymous November 12, 2012 in United States for YouTube Engineering| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Data Structures - 0of 0 votes
AnswersYou have a large number of data maybe millions. Which is the best data structure to use?
- SPB November 10, 2012 in India
Following operation needs to be performed :
Insert, Delete and Searching.| Report Duplicate | Flag | PURGE
Data Structures - 0of 0 votes
AnswersYou have a matrix of size (m x n). find submatrix of size (k x k) with maximum possible sum. 0<k<m and 0 <k <n
- ratn November 10, 2012 in India
[HINT] use DP| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm Data Structures - 0of 0 votes
AnswersYou are given a binary search tree T of finite (means can fit in memory) size n in which each node N contains
- mag November 09, 2012 in India
- integer data element
- pointer to left child
- pointer to right child
- pointer to in order successor (which is set null for each node)
Set all in order successor pointers of the given binary search tree.| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm Coding Data Structures - 0of 0 votes
AnswersGive a BST and a number. we need to find next bigger number in BST.
- Harsh123 November 04, 2012 in India for Kindle| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm Data Structures Trees and Graphs