Data Structures Interview Questions
- 0of 0 votes
Answerslet there be a n x n matrix. two points say (a,b) and (c,d) are there in the matrix. find all the paths from point1 to point2 such that none of the path follows a diagonal path between the two points
- matrix September 25, 2009| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Data Structures - 0of 0 votes
AnswersPropose a tree based data structure
- nerdy September 17, 2009
to identify a node with nth rank with maximum efficiency| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Data Structures - 0of 0 votes
AnswersSuppose you want to implement an ADT on a set of integers S with the following operations:
- klpd September 15, 2009
• insert (k ) - Places k into S
• extract min(S ) - Removes the smallest element from S
• extract max(S ) - Removes the largest element from S
• min(S ) - Returns (but does not remove) the smallest element from S
• max(S ) - Returns (but does not remove) the largest element from S
Explain how to do this so min and max take O(1) time while insert, extractmin, and extractmax
take O(log n) time.| Report Duplicate | Flag | PURGE
Adobe Software Engineer / Developer Data Structures - 0of 0 votes
AnswersImplement a queue that is FIFO. Explain the classes and methods used.
- Anonymous September 08, 2009
I explained a queue program that has an array that contains elements. A function push to add elements and a function pop to remove elements. I mentioned that "pop" will check to see that the next position to popped has non-null value.
Interviewer asked "What if I want to add null values to my queue? what if I dont want size limitations enforced by an array?"
I understand that my solution is not optimal. I would appreciate your thoughts on an optimal solution.
Thanks to careercup and all its users who share their questions/thoughts.| Report Duplicate | Flag | PURGE
Zoosk Software Engineer / Developer Data Structures - 0of 0 votes
AnswersI have a stack which contains some integer data. I want to find out the min[or max] value from Stack in O(1) time. Any idea?
- LLOLer September 08, 2009| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Data Structures - 0of 0 votes
AnswersWhat should be the best way to invert a stack, without using any other EXTRA data structure, like a Stack2, or a temporary stack. Thus no stack1-stack2 or stack-queue-stack implementation in the answer. You just have access to push/pop feature of a standard stack.
- LLOLer September 08, 2009| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Data Structures - 0of 0 votes
AnswersHow a new node can be inserted at the middkle of a link list in one single step? (Without traversing it)
- Anonymous September 01, 2009| Report Duplicate | Flag | PURGE
Amazon Data Structures - 0of 0 votes
AnswersFirst phone screening: What's the difference between a array and link list in details.
- Roy August 18, 2009| Report Duplicate | Flag | PURGE
Amazon Software Engineer in Test Data Structures - 0of 0 votes
AnswersFirst phone screening: If you have implement a dictionary what possible data structures would you use?
- Roy August 18, 2009| Report Duplicate | Flag | PURGE
Amazon Software Engineer in Test Data Structures - 0of 0 votes
AnswersHow do u implement quicksort and mergesort algorithms without using recursion!!!
- Abhishek August 16, 2009
please explain the logic n write the code| Report Duplicate | Flag | PURGE
Data Structures - 0of 0 votes
AnswersDeninition about hash map.
- letitbe July 29, 2009
Space and time complexity.| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Data Structures Terminology & Trivia - 0of 0 votes
AnswersYou have more than 3 million entries of phone numbers. You have to create a phone book just like the one we have on the new phones these days. You type the name, and the numbers that match the letters you typed shows up on your phone.
- Tom July 17, 2009
For e.g: When you type 'K' all numbers under K appear,then you say "i"...all numbers under "Ki" appear..so on and so forth.
How will you design/architecture this type of search? Discuss data structures you would use whats the worst case for your design?| Report Duplicate | Flag | PURGE
Delve Networks Software Engineer / Developer Data Structures Ideas Object Oriented Design - 0of 0 votes
AnswersHas anyone tried this? http://www.facebook.com/careers/puzzles.php?puzzle_id=11
- tadbooch11 June 18, 2009
The brute force way is n! so definitely won't scale. I tried a little bit of pruning (where I keep track of expected time and as soon as I see that it's more than then current minimum expected time, I bail out). But other than that, can't think of any..
So here is I have uptill now:
for all permutations of possible paths:
find expected time for that shortest path
if (there is a path) and (expected time < min expected time)
minexpectedtime = expectedtime.
Can someone give me hints on pruning? I think I need a better way than going through all the permutations but am unable to think? Any help on algorithms/pruning/datastructure would be appreciated..| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Algorithm Data Structures - 0of 0 votes
AnswersHow do you implement a queue with stack data structure?
- Anonymous May 30, 2009| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Coding Data Structures - 0of 0 votes
AnswersSuppose there is a stream of numbers 1 to 9. It may contain duplecates.
- DPS Prog May 15, 2009
which data structure will u use.?
Which data structure will u use other than provided by STL?| Report Duplicate | Flag | PURGE
Bloomberg LP Software Engineer / Developer Data Structures - 0of 0 votes
Answers1. Suppose a dll allocates memory using malloc or new and user of dll releases that memory.Is this a good practice.If not then why?
- Cookie May 12, 2009
2.An application runs fine with a debug version of a dll but crashes with a release version of same dll.
What can be the possible causes of this.| Report Duplicate | Flag | PURGE
RSA Software Engineer / Developer Data Structures - 0of 0 votes
Answerswhat is the difference between a Skip list and a hash table ?
- Rajesh May 05, 2009| Report Duplicate | Flag | PURGE
Infinium Software Engineer / Developer Data Structures Hash Table - 0of 0 votes
AnswersConvert a binary search tree to a circular sorted linked list. The highest valued node should point to the lowest valued node at each step.
- prolificcoder April 27, 2009| Report Duplicate | Flag | PURGE
Microsoft Software Engineer in Test C++ Coding Data Structures Linked Lists - 0of 0 votes
AnswersTest a function that sorts a linked list. You have two pointers head which is the original unsorted list and head1 which is said to be the sorted linked list. Return true if head1 did the sorting correctly and return false if not.
bool testlinkedlistsort(Node *head,Node *head1)
I got the solution correct but messed it up while writing it over the white board :|
- prolificcoder April 27, 2009| Report Duplicate | Flag | PURGE
Microsoft Software Engineer in Test C++ Coding Data Structures Debugging Testing Linked Lists - 0of 0 votes
AnswersPick two data structures to use for implementing a Map.
- chad March 18, 2009
* Describe lookup, insert, & delete operations.
* Give time & space complexity for each.
* Give pros & cons for each.| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Data Structures Hash Table - 0of 0 votes
AnswersA binary tree contain integer values (both positive and negative) in its data field. Given a number N, find a path from root to leaf which sums to N.
- Daniel Johnson February 07, 2009
bool ContainsSum(btree *root, int N)
It was simple. By doing a iterative pre-order traversal, and keeping tab of sum of elements, we can easily determine if sum of elements from root to any of the leaves is equals to N.| Report Duplicate | Flag | PURGE
Microsoft Software Engineer in Test Data Structures - 0of 0 votes
AnswersConvert an integer into word. Example->1264 is One Thousand two hundred and sixty four. Corner cases are important. Integers are in the range 0-99999
- AMRITANSHU SHEKHAR February 02, 2009| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Data Structures - 0of 0 votes
AnswersGiven two int arrays A and B containing keys of binary tree. Is it possible for both the array elements to form identical binary tree in any combination or permutation .State the conditions .
- Prashi December 20, 2008| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Data Structures - 0of 0 votes
AnswersGiven a n-ary tree of resources arranged hierarchically. A process needs to lock a resource node in order to use it. But,
- Prashi December 20, 2008
A node cannot be locked if any of its descendant or ancestor is locked.
I was supposed to
-> write the structure of node
-> write codes for
-> islock()- returns true if a given node is locked and false if it is not
-> lock()- locks the given node if possible and updates lock information
-> unlock()- unlocks the node and updates information.
Codes should be :
Islock –O(1)
Lock()- O(log n)
unLock()- O(log n)| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Data Structures - 0of 0 votes
AnswersA string representation of a n-ary tree is given in the following format
- Prashi December 20, 2008
(a(b(v)(w))(c(k(d)))(e))
This string can be interpreted as root followed by all its children enclosed in (). Every children is then represented in the same way as root.
Eg: In above string a is root. b,c,e are its children, while v and w are b's children and k is c's child which in turn is parent of d.
I was supposed to write a code for converting the string into the corresponding n-ary tree.| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Data Structures - 1of 0 votes
AnswersWhat data structure do you prefer to use to implement a stack?
- neil turok December 17, 2008| Report Duplicate | Flag | PURGE
Bloomberg LP Financial Software Developer Data Structures - 0of 0 votes
AnswersImplement a priority queue with a Double Linked List.
- N December 10, 2008| Report Duplicate | Flag | PURGE
Microsoft Program Manager Data Structures