Data Structures Interview Questions
- 3of 3 votes
AnswersCreate the data structure for a component that will receive a series of numbers over the time and, when asked, returns the median of all received elements.
(Median: the numerical value separating the higher half of a data sample from the lower half. Example: if the series is
2, 7, 4, 9, 1, 5, 8, 3, 6
then the median is 5.)
Model the data structure for a component that would have these two methods:@interface SampleHandler { - (void)addNumber:(NSNumber*)number; - (NSNumber*)median; }
Justify your decisions. Calculate the complexity of each method.
- Diego May 16, 2014 in United States| Report Duplicate | Flag | PURGE
Facebook iOS Developer Data Structures - 0of 0 votes
AnswersDesign an LRU Cache with constant lookup, i.e, searching and updating should all happen in O(1) time. Assume a method of calculating the least recently used page is already given. Just implement the searching and updating logic which takes constant time.
- Masterchief117 May 12, 2014 in United States| Report Duplicate | Flag | PURGE
Software Engineer in Test Data Structures - 1of 1 vote
AnswersImplement LRU cache of size 10 which can store Key, Value pair. (get(key) & put(key,value) methods)
- Miral Patel May 07, 2014 in United States
- If we try to add 11th element, the least recently used element should get removed.
- If key already present, overwrite it and mark it as most recently used.| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Data Structures - 1of 1 vote
AnswersFor a given binary search tree, replace each node with sum of all node which are greater then of equal to current node.
- Razz May 02, 2014 in United States| Report Duplicate | Flag | PURGE
Amazon SDE-2 Data Structures - 0of 0 votes
AnswersMachine Coding 1 hour
- hulk April 26, 2014 in India
------------------------------
U have an organizational structure, which shows hierarchy of the organization. This hierarchy contains employees E or managers M who has some Employees or Managers reporting to M.
Employee has ( id, name, JobDesc, salary etc).
Design the data structure you would be using to store this hierarchy
problem 1: Given an ID of an employee , print all the employee ID's who are directly reporting or indirectly reporting to the manager.
problem 2: prefix search of employees by String. If employees have nishant and nikhil. If searched by "ni" we need to print all details of both nishant and nikhil.
problem 3(bonus): search should print all emloyee's and their details if a given string is subString of the name of an employee.(Like a phonebook contacts search)
P.S- This was asked to one of my friend in Flipkart.| Report Duplicate | Flag | PURGE
Flipkart SDE1 Data Structures - 2of 2 votes
Answersgive me the code for :
Given a string say "I am a human being" the output should reverse all letters of each word but not the whole string as such.
Eg: O/p should be "I ma a namuh gnieb"
I somewhat wrote the code, but i was asked what if there are extra spaces etc.
(i am able to write the code sitting at my desktop at one short but there front of interviewer i am struggling. Need to build up my confidence)
let me know the best and optimised way of writing this code.
Also i suggest people to aviod using inbuilt functions as much as possible
My Answer is as below in perl
- i_learn April 11, 2014 in India#i want the reverse of the letters of all words in a string #eg Input is "I am a human being" then o/p shud be "I ma a namuh gnieb" $str="I am a human being"; @arr=split(' ',$str); print @arr; for($i=@arr-1;$i>=0;$i--) { $_=@arr[$i]; ####intead of above for loop if we use foreach(@arr) then it will reverse the whole string @word=split('',$_); { foreach $n (@word) { unshift(@final,$n); } } } print "\n @final \n";
| Report Duplicate | Flag | PURGE
Amazon Testing / Quality Assurance Algorithm Android Application / UI Design Arrays Automata Coding Data Structures Dynamic Programming Perl - 0of 2 votes
AnswersGiven an array say [0,1,2,3,5,6,7,11,12,14,20]
- i_learn April 11, 2014 in India
given a number say 5.
Now find the sum of elements which sum to 5
eg:2+3=5, 0+5=5 etc.
I guess the interviewer wanted all possible combinations eg 0+2+3=5, etc| Report Duplicate | Flag | PURGE
Amazon Testing / Quality Assurance Algorithm Android Application / UI Design Arrays Coding Data Structures Dynamic Programming Perl Sorting test Testing - 0of 0 votes
AnswersHow to find starting of loop in a link list in case looping somewhere.
- PKT April 06, 2014 in India
For ex: 1->2->3->4->5->3| Report Duplicate | Flag | PURGE
Citigroup Data Structures - 0of 0 votes
AnswersGiven a list with duplicate values find the first unique elements in it.
- Vaibhavs April 02, 2014 in United States
for eg: BH BH F AL HJ AL HJ PK
so answer is F| Report Duplicate | Flag | PURGE
Amazon SDE1 Data Structures - 1of 7 votes
AnswersGiven an excel column number convert it to excel column alphabet and reverse.
- codechamp March 30, 2014 in India for AWS
Example : If column number(starts from 0) = 26 : Column alpha = AA.| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm Brain Teasers Data Structures - 3of 3 votes
AnswersPrint all paths of a binary tree from root to leaf.
- meh March 23, 2014 in United States
Later, extend the solution to work with graphs, careful attention to cycles which you should print as paths as well (without printing visited nodes twice).| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Data Structures - 0of 0 votes
AnswersCompare time complexity of insert and search functions in HashMap, Array, Linked List and Queue
- naveenm.025 March 17, 2014 in United States| Report Duplicate | Flag | PURGE
Amazon Software Engineer Intern Data Structures - 4of 4 votes
AnswersYou are given a large set of integers, which are not sorted. Figure out a method to retrieve the largest 1000 elements, in O(n) run time
- varunumesh77 March 12, 2014 in United States| Report Duplicate | Flag | PURGE
Amazon Intern Algorithm Data Structures - -1of 3 votes
Answershow to print this pattern
- premnath.velmurugan March 08, 2014 in India
input N=4
output :
4444444
4333334
4322234
4321234
4322234
4333334
4444444
input N=3
output :
33333
32223
32123
32223
33333| Report Duplicate | Flag | PURGE
Software Trainee Algorithm C# Data Structures Applications Developer Java - 0of 0 votes
AnswersThere is a file which contains N words. There may be M anagrams in that file, K words on each anagrams. K>=1, M>=1, N>=1. You need to write an algorithm which will create one list for each anagram with k words and group all M lists with one data structure
- suresh March 05, 2014 in India| Report Duplicate | Flag | PURGE
Amazon SDE1 Data Structures - 1of 1 vote
AnswersFind your own method to balance an unbalanced binary tree.(you must not use existing methods like AVL, red black or b trees)
- suresh March 05, 2014 in India| Report Duplicate | Flag | PURGE
Amazon SDE1 Data Structures - 0of 0 votes
AnswersConvert a sorted integer Array to balanced binary search tree. This is very simple one and I could do it in O(n) time and O(1)extra space
- suresh March 05, 2014 in India| Report Duplicate | Flag | PURGE
Amazon SDE1 Data Structures - 0of 0 votes
AnswersGiven 2 sorted linked list , merge them into single sorted list. Change the pointers, don't copy data
- suresh March 05, 2014 in India| Report Duplicate | Flag | PURGE
Amazon SDE1 Data Structures - 0of 0 votes
AnswersGiven a read only linked list with next and random pointer , clone the list
- suresh March 05, 2014 in India| Report Duplicate | Flag | PURGE
Amazon SDE1 Data Structures - -1of 1 vote
Answersdelete all the nodes from a binary tree that lie on a path whose sum from root to leaf is less than a given value K. Twist was that the node values can be any integer. It may be a negative number.
- suresh March 05, 2014 in India| Report Duplicate | Flag | PURGE
Amazon SDE1 Data Structures - 0of 0 votes
AnswersData structure to push, pop and find min element in O(1) time.
- suresh March 05, 2014 in India| Report Duplicate | Flag | PURGE
Amazon SDE1 Data Structures - 0of 0 votes
AnswersGiven a linked list like a1-a2-a3-a4-b1-b2-b3-b4. Convert it into a1-b1-a2-b2-a3-b3-a4-b4
- suresh March 05, 2014 in India| Report Duplicate | Flag | PURGE
Amazon SDE1 Data Structures - 0of 0 votes
Answersprogram to pruning a binary tree
- pavan February 27, 2014 in India| Report Duplicate | Flag | PURGE
Amazon SDE1 Data Structures - 1of 3 votes
AnswersWrite a function in C to create a new BST which is the mirror image of a given tree.
- gjp February 24, 2014 in United States| Report Duplicate | Flag | PURGE
NVIDIA Software Engineer Intern Algorithm C Data Structures - -2of 2 votes
AnswerDesign a meeting scheduler. The solution I came up with was to create an array of intervals for each day, so if intervals is 15 mins, then array size would be 24*4. However, if interval is small, that will substantially increase the size of the array, and that might be considered as a waste of space, though it supports O(1) look up. I was wondering if there is any other way to do this. I think we might be able to keep a sorted array of meetings sorted by start time, so look up would be O(logn). But insertion in the middle of the array would take O(n) since it requires data shifting.
- Guy February 19, 2014 in United States| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Data Structures - -2of 2 votes
AnswersDesign a meeting scheduler. One way is to use an array to represent each interval, like every 15 mins. Although it provides O(1) look up, if interval is small, it seems like we are wasting a lot of space. Any alternative approach that can save space? If we keep a sorted array of meetings sorted by start time, look up will be O(logn), but inserting the new meeting in the middle of the array will require shifting elements, which is O(n).
- Guy February 19, 2014 in United States| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Data Structures - 0of 0 votes
AnswersWrite a function in C to create a new BST which is the mirror image of a given tree.
- gjp February 12, 2014 in United States for Driver Development| Report Duplicate | Flag | PURGE
NVIDIA Software Engineer Intern Data Structures - -6of 6 votes
AnswersIf you have data coming in rapid succession what is the best way of dealing with redundant data?
- Guy February 06, 2014 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Data Structures - 2of 2 votes
AnswersI was asked a question in an interview.
- Park February 06, 2014 in India
On an office floor , there are e entities - Walls , Cubicles , Coffee Rooms.
In what data structure we should store this design that when a new member joins the company , the cubicle number which is empty and next closest to any coffee room should be assigned to it.
Basically , data structure DS.pop() should return that cubicle number in the most efficient way.
A Person can walk through cubicles to reach a coffee room but not through walls.| Report Duplicate | Flag | PURGE
Motorola Software Engineer / Developer Data Structures - 0of 0 votes
AnswersHow you can find whether a link list contains a cycle or not?
- mpss.umbc January 29, 2014 in United States for Android| Report Duplicate | Flag | PURGE
Samsung Software Engineer Intern Data Structures