Data Structures Interview Questions
- 0of 0 votes
AnswerGiven a 2-d integer array, find the size of the largest connected area (number of elements connected), where two elements are connected if they are side-adjacent in matrix(up,down,left,right operations). Also there can be maximum of two different integers present in this set.
- vs9968405834 June 08, 2018 in United States| Report Duplicate | Flag | PURGE
Data Structures - 0of 0 votes
AnswerWe have an array if 0's and 1's like
- johnsvakel April 16, 2018 in India for NA
00010000010001001
Assume that all 1's are a person and if a new person comes and if we want to add to the array in such a way that the gap between individuals are maximum as possible.
if we add a new person, then the new array should be
000100100010001001| Report Duplicate | Flag | PURGE
Microsoft Staff Engineer Data Structures - 1of 1 vote
AnswersGiven a string as input, return the list of all the patterns possible:
'1' : ['A', 'B', 'C'], '2' : ['D', 'E'], '12' : ['X'] '3' : ['P', 'Q']
Example if input is '123', then output should be [ADP, ADQ, AEP, AEQ, BDP, BDQ, BEP, BEQ, CDP, CDQ, CEP, CEQ, XP, XQ]
- ngupta32@hawk.iit.edu March 30, 2018 in United States| Report Duplicate | Flag | PURGE
Facebook Software Engineer Algorithm Coding Data Structures - 0of 0 votes
Answers/*Coding question: The customers for a particular business, required to use a webpage to select a Browse Node.
- pragramticProgrammer February 22, 2018 in United States
A Browse Node, is an element in the classification structure used to classify products in the Amazon webpage.
The products are classified in 8 categories. Each category has its own sub-classification that looks like a tree with many
children per node and many levels. The UI developer has a tool to paint such tree. He requires from you (You are the backend developer)
to implement 2 interfaces for him:
Node getRoot();
List<Node> getChildren(Node node);
The data is available for you in a text file with this format:
//nodeid, parent_node_id, nodename
Example:
//nodeid, parent_node_id, nodename
10, 1, Comedy Books
20, 2, Tablets
1, -1, Books
11, 1, Novels
12, 11, Terror novels
2, -1, Electronics
-1, 0, GlobalRoot
*/| Report Duplicate | Flag | PURGE
Amazon SDE1 Data Structures - 0of 0 votes
AnswersGiven n line segments, find if any two segments intersect
- anonymous December 10, 2017 in India for Office365
http://www.geeksforgeeks.org/given-a-set-of-line-segments-find-if-any-two-segments-intersect/| Report Duplicate | Flag | PURGE
Microsoft SDE1 Data Structures - 0of 0 votes
AnswersN different couple go to cinema with 2N different seats. They take their place randomly. You could make swap operations. Write a code for given input what is the minimum number of swap operations for sitting all couples with their partners? Additionally, be sure that no one swaps more than 2 times.
- new December 07, 2017 in United States| Report Duplicate | Flag | PURGE
Google SDE1 Algorithm Arrays Coding Data Structures - 1of 1 vote
AnswersGiven an array of sorted integers and find the closest value to the given number. Array may contain duplicate values and negative numbers.
- Vijay November 17, 2017 in India
Example : Array : 2,5,6,7,8,8,9
Target number : 5
Output : 5
Target number : 11
Output : 9
Target Number : 4
Output : 5| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm Arrays Coding Data Structures - 0of 0 votes
AnswersWrite a merger and separator for Linked List.
- Shilpi_Roy November 02, 2017 in United States
eg: 1->2->3->4->5
separator()
1->3->5 and 2->4
merger()
1->2->3->4->5| Report Duplicate | Flag | PURGE
Yahoo Software Engineer / Developer Data Structures - 0of 0 votes
AnswersYou are given a stream of numbers which represent the stock prices of a company with timestamp. You need to perform some set of operations on the stream of data efficiently as below: 1. findStockPriceAtGivenTimeStamp(Timestamp) 2. deleteAndGetMinimumStockPriceForToday() Timstamp: 1 2 3 . 4 . 5 Prices: 12 34 4 . 1 . 18
- bholeNath September 18, 2017 in India| Report Duplicate | Flag | PURGE
Amazon Software Developer Data Structures - 1of 1 vote
AnswerExplain the Data Structure which is well suited to implement UNIX commands like PWD, LS, MKDIR, CD in an imaginary OS. No code required.
- neer.1304 September 04, 2017 in United States| Report Duplicate | Flag | PURGE
Cisco Systems Software Developer Data Structures - 0of 0 votes
AnswersDesign a text based rpg.
- tnutty2k8 August 30, 2017 in United States
- Player can enter room.
- Room has 4 walls and items
- a wall can have door
- user can enter a different room if they chose a wall which has door.
- There is also a Enemy, which walks around different rooms. If present in the same room, takes away all your items
- A player has an inventory which has list of items
- a item can be food or weapon
User should be able to start a game and be given set options(in text) of what command to execute, like pick up item in current room, walk north, east, south, or west, or undo action to return to previous state.| Report Duplicate | Flag | PURGE
Data Structures - 0of 0 votes
AnswersYou are given a set of N horizontal lines which are connected by equal number of vertical lines to form squares of size 1x1. Now some segments are removed. You need to count the number of squares of all sizes (1x1, 2x2, ..., NxN) with all sides present.
- imunique August 30, 2017 in India
Image : https://he-s3.s3.amazonaws.com/media/uploads/1ce3516.png
In the above example you see four horizontal and vertical lines and few missing segments. Now you need to count the number of squares of all sizes with all sides.
Input :
First line is a positive integer N, number of horizontal and vertical lines.
Second line is positive integer M, number of segments removed.
Then there are m lines, each containing V,i,j or H,i,j where i and j are positive integers. H,i,j indicates a horizontal missing segment in the ith horizontal line between the jth and (j+1)th point on the line. V,i,j represents a gap in ith vertical line between the jth and (j+1)th point on the line.
Output :
Is the total number of squares in the figure with all sides along the remaining lines in the figure.
Sample Input :
4
4
H,2,1
H,3,1
V,2,2
V,2,3
Output :
5
Explanation : Here in this figure we have 4 squares of size 1x1 and 1 square of size 3x3, hence total is 5.| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm Data Structures Dynamic Programming Online Test Problem Solving - 0of 0 votes
Answers// Create a numeric binary tree structure/classes that have left and right children and an integer numeric value.
- deepmh August 14, 2017 in United States for Amazon Fresh
// Write a function 'isBalanced' for a node that returns true if the sum of all the children on the left is equal
// to the sum of all the children on the right.
//Example:
// [12] [12].isBalanced() -> True. [3, 3]
// / \
// [3] [1] [1].isBalanced() -> True. [2, 2]
// / \
// [2] [0]
// / \
// [2] [0]
// - Part I: setup and isBalanced() function
// - Part II: implement “allBalancedNodes()” <— given a node, finds all balanced children
// allBalancedNodes(12) -> returns a list of balanced nodes: { [1], ... }| Report Duplicate | Flag | PURGE
Amazon SDE-3 Data Structures - -1of 1 vote
AnswersGiven a fully connected graph with n nodes and corresponding values. One node can interact with other node at a time, to replace/ignore/add its value to other node’s value. Assuming this operation takes 1 unit of time, how much time would it take for all the nodes to have value equal to sum of all the nodes.
- koustav.adorable August 14, 2017 in United States
Examples : Given a graph with values {1,2,3,4}, find total time it takes, such that all nodes have value as 10.
I am assuming it can be done in O(N).It will take basically two traversals, one for calculating the sum of values of nodes(first traversal), other for replacing the value of the nodes(second traversal).
It will take 2*(no of nodes) time.
Are there any better ways possible ?| Report Duplicate | Flag | PURGE
Amazon SDE-2 Data Structures - 0of 0 votes
AnswersImplement a function that returns whether a string made of different bracket characters is well formed or not.
- JustYourAverageDev August 13, 2017 in United States
For example,
"{({})[]}" is a well formed bracket string
"{[](}" is not a well formed bracket string
Needless to say any single brackets are automatically counted as not well formed| Report Duplicate | Flag | PURGE
Eze Software Group Senior Software Development Engineer Data Structures - 0of 0 votes
AnswerDesign a system that supports updating table with options to discard the updates. It should have the following functions:
- create(String: rowName) #cannot be called until startTransaction has been called - delete(String: rowName) #cannot be called until startTransaction has been called - update(String: rowName) #cannot be called until startTransaction has been called - startTransaction() #start transaction operations( create/delete/update) - commitTransaction() #apply transaction to the actual Table( can be array-of-objects ) - discardTransaction() #discard any transaction applied thus far
Rough impl is acceptable as long as the design is displayed correctly.
- tnutty2k8 August 01, 2017 in United States| Report Duplicate | Flag | PURGE
Data Structures - 0of 0 votes
AnswersGiven a list of employees and their bosses as a CSV file , write a function that will print out a hierarchy tree of the employees.
- Trutgeek August 01, 2017 in United States for Phone Interview| Report Duplicate | Flag | PURGE
Amazon SDE-3 Data Structures - 0of 0 votes
AnswersI was asked this question for the above role:
Create a fixed size cache which is fully associative. The entries are evicted based on the rank. for any entry added, the function int getEntryRank(entry) will return its rank which will not change on lookup
db_read_entry() to get the entry from db
Part 2) The rank will change on lookup
- ali.kheam July 28, 2017 in United StatesMy solution was: a hashtable (unordered_set<entry>) and a priority queue <pair<int, entry> > lookup(entry) { hashtable lookup. if found, return the entry (O(1)) // otherwise (not found) if limit reached, then // evict the priority queue top, entry e = db_read_entry(); // expensive op //insert the entry into the hash set, //insert pair<int, entry>(get_entry_rank(entry), entry) into the priority queue. (O(logn)) return entry; } Part 2: The rank change on lookup Since the priority queue does not provide the key(hash key) value to be modified, and only provide access to top entry. I propose change in the associated ds for hashset, My proposal was: create an associated binary tree(std::set) with the hashmap (map of entry as key, and the iterator entry in the std::set of entries) . I used iterator to avoid look up for entry into the set during each entry lookup in the hashset. The set contains the [rank information + entry]. On look up, the entry into the set(of rank) is looked up (O(1)) and then erased, and then insert back after recaulated rank value.The iterator inrto the hash_set is also updated with this new iterator. On limit reached, the tree is searched for min value. from that min value item (the rank and the entry), the entry is looked up into the hash_set, and hence removed from there too. The rest of the process is the same as lookup as described below. I believed my slution was faor enough O(1) look up, if not found. the look up (with const rank) O(logn) + db access time. db access time dominate the O(logn) hence this logn (to insert into the priority queue,(or pop and insert into the priority) does not matter For changing rank: The binary tree lookup (O(1) since the hash_map has the iterator update of the rank, (lookup and removal of the rank entry in the binary tree O(1), and insert is O(logn). Hence each operator (lookup, evict and lookup, excluding the db access) will take O(logn) instead of O(1). I was rejected because of not optimize solution (performance is not good). I am wondering whether the solution was not good even though it was phone interview and I have to work within the time frame of 25 minutes. or the interview process is just unrealistic. Please share your solution so that I can see where I failed
| Report Duplicate | Flag | PURGE
Principal Software Engineer Data Structures - 0of 0 votes
AnswersRed black trees versus AVL trees. Which one is better ?
- vasu.verma8oct July 19, 2017 in United States| Report Duplicate | Flag | PURGE
Data Structures - 0of 0 votes
AnswersA new species has been discovered and we are trying to understand their form of communication. So, we start by identifying their alphabet. Tough Mr. Brown managed to steal a vocabulary that has words in it in ascending order and a team already identified the letters. So, we have now ordered words as sequences of numbers, print every letter once in ascending order.
- Chris July 07, 2017 in United States
[3,2]
[4,3,2]
[4,1,1]
[1, 2]
[1, 1]
alphabet: [3, 4, 2, 1]| Report Duplicate | Flag | PURGE
Software Engineer Data Structures - 0of 0 votes
AnswersHow would you store very large numbers that can't be store in a regular Integer or BigInteger, and make calculations
- UCJava July 04, 2017 in United States| Report Duplicate | Flag | PURGE
Amazon Software Developer Data Structures - 0of 0 votes
AnswersThere is a tree of nodes . each node is of type either place, area name, city, district , state, country
they are in tree like order like country contains multiple states ,states contain multiple cities ...so on
i want define the node structure and define the strategy to print the address of any node given from parent to all the child address of the node
- girishkumar518 June 21, 2017 in Indiapackage com.girish.sample; import java.util.ArrayList; import java.util.List; public class Node { private String name; private Node parent; private List<Node> childNodes; private String nodeType; public Node(String name,String nodeType){ this.name = name; this.nodeType = nodeType; } /** * @return the name */ public String getName() { return name; } /** * @param name * the name to set */ public void setName(String name) { this.name = name; } /** * @return the parent */ public Node getParent() { return parent; } /** * @param parent * the parent to set */ public void setParent(Node parent) { this.parent = parent; } /** * @return the childNodes */ public List<Node> getChildNodes() { return childNodes; } /** * @param childNodes * the childNodes to set */ public void setChildNodes(List<Node> childNodes) { this.childNodes = childNodes; } /** * @return the nodeType */ public String getNodeType() { return nodeType; } /** * @param nodeType * the nodeType to set */ public void setNodeType(String nodeType) { this.nodeType = nodeType; } public String getAddress() { return getparentAddress(); } public String getparentAddress() { if (parent == null) return ""; return parent.getparentAddress().concat("," + this.nodeType + ": " + this.name); } public List<String> getchildAddress() { List<String> childAddress = new ArrayList(); for (Node node : childNodes) { childAddress.add(node.getchildAddress()); } return null; } }
| Report Duplicate | Flag | PURGE
Ivycomptech Tech Lead Data Structures - 0of 0 votes
AnswersFirst asked how you can write a tree in a file?
- Ghosh June 17, 2017 in India
Next question was lets say value of one node is changed, how can you update that in that file without writing the whole tree in file again?d| Report Duplicate | Flag | PURGE
SDE-3 Algorithm Data Structures - 1of 1 vote
AnswersImplement circular buffer with read & write functions
- aonecoding June 06, 2017 in United States| Report Duplicate | Flag | PURGE
Facebook Software Engineer Data Structures - 0of 0 votes
AnswersDesigning a data-structure for following functions
- arnav251035 May 31, 2017 in India
Insert X : Insert an element X into the set.
Delete X : Delete an element X from the set. It is guaranteed that such X always exist in the data structure.
Mean : Report Mean of the elements present in the data set. It is guaranteed that data structure will not be empty at this query.
Mode : Report Mode of the elements present in the data set. It is guaranteed that data structure will not be empty at this query.
Median : Report Median of the elements present in the data set. It is guaranteed that data structure will not be empty at this query.| Report Duplicate | Flag | PURGE
Data Structures - 0of 0 votes
AnswersYou have a binary tree which consists of 0 or 1 in the way, that each node value is a LOGICAL AND between its children:
0 / \ 0 1 / \ / \ 0 1 1 1
You need to write a code, which will invert given LEAF and put tree in a correct state.
- vu-doo-cok May 22, 2017 in UK| Report Duplicate | Flag | PURGE
Facebook Software Engineer Data Structures - 0of 0 votes
AnswersProducts are identified by alphanumeric codes. Each code is stored as a string. We have three types of products:high priority, medium priority, and low priority. Given an array of product codes, sort the array so that the highest priority products come at the beginning of the array, the medium priority products come in the middle, and the low priority customers come at the end. Within a priority group, order does not matter. You are given a priority function which, given a product code, returns 1 for high, 2 for medium and 3 for low. This array may contain a large number of product codes, so do your best to minimize additional storage.
- job_seeker May 17, 2017 in United States| Report Duplicate | Flag | PURGE
SDE-2 Data Structures - 0of 0 votes
AnswersProducts are identified by alphanumeric codes. Each code is stored as a string. We have three types of products:high priority, medium priority, and low priority. Given an array of product codes, sort the array so that the highest priority products come at the beginning of the array, the medium priority products come in the middle, and the low priority customers come at the end. Within a priority group, order does not matter. You are given a priority function which, given a product code, returns 1 for high, 2 for medium and 3 for low. This array may contain a large number of product codes, so do your best to minimize additional storage.
- job_seeker May 17, 2017 in United States| Report Duplicate | Flag | PURGE
SDE-2 Data Structures - 0of 0 votes
AnswersGiven a Matrix A,
- GP700 May 15, 2017 in India
The rules for movement are as follows :
1. Can only move Right or Down from any element
2. Can only move within the row and column of element we start from intially.
3. You can only visit or cross an element if its value is lesser than the value of element you start from.
Find total number of elements one can visit, If one starts from an element A(i,j) where i-> row and j-> column.
Note : You have to print this output for each matrix element.
Input : Matrix
1 2 3
2 3 1
3 1 2
Output:
1 1 3
1 3 1
3 1 1| Report Duplicate | Flag | PURGE
Hackerrank Senior Software Development Engineer Data Structures Math & Computation Matrix - 0of 0 votes
AnswersGiven a binary tree of integers, write code to store the tree into a list of integers and recreate the original tree from a list of integers.
- Null0 May 13, 2017
Here's what your method signatures should look like (in Java):
List<Integer> store(Node root)
Node restore(List<Integer> list)
Example Tree:
5
/ \
3 2
/ / \
1 6 1| Report Duplicate | Flag | PURGE
Facebook Software Engineer Algorithm Data Structures Java Trees and Graphs