Data Structures Interview Questions
- -2of 2 votes
AnswersGiven a sorted but rotated array. Search an element inside it without finding the pivot. Complexity of the solution should still remain O(Log n)
- Nitin Gupta October 05, 2012 in India| Report Duplicate | Flag | PURGE
Adobe MTS Algorithm Arrays Data Structures - -1of 1 vote
AnswersGiven a sorted but rotated array. Find the pivot.
- Nitin Gupta October 05, 2012 in India| Report Duplicate | Flag | PURGE
Adobe MTS Algorithm Arrays Data Structures - -1of 1 vote
AnswersHow will you implement a stack using a priority queue. Push and pop should be in O(1).
- Nitin Gupta October 05, 2012 in India| Report Duplicate | Flag | PURGE
Adobe MTS Algorithm Data Structures - -1of 3 votes
AnswersWhat data structures will you use to implement a text editor. Size of editor can be changed and you also need to save the styling information for all the text like italic, bold etc.
- Nitin Gupta October 05, 2012 in India| Report Duplicate | Flag | PURGE
Adobe MTS Algorithm Data Structures - 0of 0 votes
AnswersHow would you implement hash table on your own? Write the code for implementing your own hash table?
- Steve October 05, 2012 in United States| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Data Structures - 0of 0 votes
AnswersIf you wanted to make a highly concurrent cache with a least recently used replacement policy, what data structures would you use? How would this scale per number of threads?
- Steve October 05, 2012 in United States| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Data Structures - -1of 1 vote
AnswersThere 3 arrays A, B and C, all of equal length. C is the resultant array found using both A and B.
- abilash.s.90 October 02, 2012 in India for UI
Suppose the size of the array is 3, then we need to find out the following.
c[0] = a[0] * b[1] * b[2]
c[1] = a[1] * b[0] * b[3]
c[2] = a[2] * b[0] * b[2]
I know the answer is pretty easy when it comes to brute force. But the wanted to know the answer with time complexity O(2n) and O(log n)
Note: O(n^2) is not acceptable.| Report Duplicate | Flag | PURGE
Symphony Services Applications Developer Data Structures - 0of 0 votes
Answersgiven string is of the form "abcd1234defgh8965" then output should be "a1b2c3d4 d8e9f6g5" with O(n) time??
- rajeshanji8 October 02, 2012 in India| Report Duplicate | Flag | PURGE
Microsoft Student student Data Structures - 0of 0 votes
Answershow would you print the lever order of a tree (not a binary tree i.e. each node has more than two children)?
- MobileEdge September 27, 2012 in United States| Report Duplicate | Flag | PURGE
Algorithm C++ Coding Data Structures - 4of 4 votes
AnswersWhat is the data structure you will use to model Tennis tournament of size number of players n=8. Splitted into 2 groups? What is the complexity of finding the winner and the runner.
- hari@hbiz.in September 26, 2012 in India| Report Duplicate | Flag | PURGE
Synopsys R&D Software Engineer / Developer Data Structures - 0of 0 votes
AnswersWhich data structure would you use for optimum addition removal, querying and priority.
- scorpionking September 18, 2012 in United States
(Heap, Hash and BST were rejected )
ok after finishing the interview, he finally told me the answer: he said that with each node we must store the min and max child.
his opinion was: Hash has good insert query complexity, but bad priority wise retrieval.
BST has logn for all the operations
Heap just ensures that the top priority is at the top (not the next order)
no wonder i got a reject :P| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Data Structures - 0of 0 votes
AnswersFind the first occurance of a number in a sorted array.
- scorpionking September 18, 2012 in India| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Data Structures - 0of 0 votes
AnswersIf the head of a linked list is pointing to kth element, then how will you get the elements before kth element?
- veeru September 16, 2012 in India| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Data Structures - 1of 1 vote
AnswersImplement a thread-safe Blocking queue in C/C++(POSIX) or Java
- Steve September 14, 2012 in United States| Report Duplicate | Flag | PURGE
Linkedin Software Engineer / Developer Data Structures - 0of 0 votes
Answers\e
- Steve September 06, 2012 in United States| Report Duplicate | Flag | PURGE
Data Structures - 0of 0 votes
AnswerGoogle is going to provide an over-the-wire service that the phone companies can use. This over-the-wire protocol will support three operations:
- Steve September 06, 2012 in United States
(1) void I_GAVE_OUT(n) -- the phone company is telling us that it handed out phone number (n).
(2) bool IS_TAKEN_(n) -- we are telling the phone company whether (n) is taken.
(3) number GIVE_ME_ONE() - the phone company is letting us tell them what number to hand out next.| Report Duplicate | Flag | PURGE
Two Sigma Software Engineer / Developer Data Structures - 1of 1 vote
AnswersGenerate a grey code sequence given the number of digits as input.
- D3^!L September 04, 2012 in India
eg: input=2 output= 00 01 11 10
use minimum space and time complexity| Report Duplicate | Flag | PURGE
Microsoft Data Structures - 0of 0 votes
AnswersWrite a program to find the (n-3)rd element in a singly linked list of unknown length in a single pass...
- live September 04, 2012 in India| Report Duplicate | Flag | PURGE
Akamai Quality Assurance Engineer Data Structures - 0of 0 votes
AnswersWrite a program to find the middle element in a singly linked list of unknown length in a single pass...
- live September 04, 2012 in India| Report Duplicate | Flag | PURGE
Akamai Quality Assurance Engineer Data Structures - 0of 0 votes
AnswerDesign a system for the customer to review a product. It should be able to incorporate web-services. Describe the entire flow from the client to the database.
- Naveen Reddy Mandadi August 30, 2012 in India| Report Duplicate | Flag | PURGE
Amazon Applications Developer Computer Architecture & Low Level Data Structures Application / UI Design - 0of 0 votes
AnswersGiven two arrays A[6] and B[3], both the arrays have 3 elements each. Both of them are sorted, need to return the merged array A[] after merging with array B[]. Need to do this inplace.
- HardCode August 29, 2012 in India| Report Duplicate | Flag | PURGE
Expedia Software Engineer / Developer Data Structures - -1of 1 vote
AnswersGiven an N by M matrix with values of N and M, and co-ordinates of a particular dot. Need to return true if the dot lies inside the matrix, false otherwise. Just develop the condition for this.
- HardCode August 29, 2012 in India| Report Duplicate | Flag | PURGE
Expedia Software Engineer / Developer Data Structures - 1of 1 vote
AnswersWrite a C function to print all the elements less than the key element in binary search tree
- deepthirao345 August 29, 2012 in United States| Report Duplicate | Flag | PURGE
Oracle Software Engineer / Developer Data Structures - 0of 0 votes
AnswersGiven two trees, how do you find one of the tree is a subtree of other?
- hari@hbiz.in August 26, 2012 in India| Report Duplicate | Flag | PURGE
Amazon Software Development Manager Algorithm Data Structures Trees and Graphs - 0of 0 votes
AnswersGenerate a hashtable for storing the Phone book data having the tuples (Name, phone
- reso.ashish4u August 24, 2012 in India
number, mail id).
For the initial hash, you may use the hash function defined as (sum of ASCII values of all
the characters in the name field ) modulo m, where m is the size of your hashtable.
Compare the performance of the hashtable if
a) separate chaining is used,
b) open addressing with linear probing is used,
c) open addressing with quadratic probing is used.| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Data Structures - 0of 0 votes
Answershow do you create a duplicate of a DoublyLinkedList in which the .next is okay but .prev can point to any node in the link list
- jeetu.mfp August 23, 2012 in India| Report Duplicate | Flag | PURGE
Akamai Applications Developer Data Structures - 1of 1 vote
Answerswrite your own implementation of hashtable , write interface and implementation for same eg. get,put and delete function .
- chad August 21, 2012 in United States
follow up question : suppose you have hashtable of size 4 and its full . you then delete 2 elements from it. how will you reuse the space . implement linear probing collision resolution technique in this hash table .| Report Duplicate | Flag | PURGE
Live Nation Software Engineer / Developer Data Structures - 0of 0 votes
AnswersAlice is a kindergarden teacher. She wants to give some candies to the children in her class. All the children sit in a line and each of them has a rating score according to his or her usual performance. Alice wants to give at least 1 candy for each child.Children get jealous of their immediate neighbors, so if two children sit next to each other then the one with the higher rating must get more candies. Alice wants to save money, so she wants to minimize the total number of candies.
- Nitin Gupta August 14, 2012 in India| Report Duplicate | Flag | PURGE
Algorithm Data Structures - 0of 0 votes
AnswersGiven a doubly linked list which contains only 0 and 1(any number of 0 and 1). write a algorithm to sort them.
- suhas6ue August 13, 2012 in India| Report Duplicate | Flag | PURGE
Amazon Algorithm Data Structures - 0of 0 votes
Answershow to construct a balanced binary tree? it should be based on the value of level given by the user
- subramanianandhi August 05, 2012 in United States| Report Duplicate | Flag | PURGE
Data Structures