Data Structures Interview Questions
- 0of 0 votes
AnswersQ.1 Rather than separate T[1…m] into two half size arrays for the purpose of merge sorting, we
- ninjaaarashi May 23, 2020 in United States
might choose to separate it into three arrays of size x%3, (x+1)%3, and (x+2)%3, to sort each of
these recursively, and them to merge the three sorted arrays. Give a more formal description of
this algorithm and analyze its execution time. Justify your answer with example.| Report Duplicate | Flag | PURGE
Algorithm Arrays Data Structures Programming Skills - 0of 0 votes
Answersrain strikes and the roads are flooded .Mr x has to get home from work.your task is to make sure he returns home in the shortest time .consider the roads as a graph with crossing as nodes and the path between two nodes as an edge. SAssume the graph is unidirected and the numbers are numbered .1 to v(v<=50)
- swetankkanaujiamk March 21, 2020 in United States| Report Duplicate | Flag | PURGE
Data Structures - 0of 0 votes
AnswerGiven a square (n x n) matrix which only contains 0 and
- danishm026 September 29, 2019 in India
1. Find the minimum cost to reach from left most column to rightmost column.
Constraints/rules:
a. Starting point: You can start from any cell in the left most column i.e. (i, 0) where i can be between 0 and n( number of rows/ columns)
b. Destination: You can reach any cell in the rightmost column i. e ( k, n) where k can be anything between 0 and n.
c. You cannot visit a cell marked with 0.
d. Cost is defined as the sum of cells visited in path.
e. You can move up, down, left and right but not diagonally.
For example,
take 2x2 matrix
1 | 0
1 | 1
One possible path is 00 -- 10 -- 11 with cost 3
Other one is 10 -- 11 with cost 2
so minimum cost on this case is 2.| Report Duplicate | Flag | PURGE
unknown Random Algorithm Data Structures - 2of 2 votes
AnswerA dictionary is combination of characters from a-z. let's say a=1,b=2.. and so on z=26. you are given n and k. you have to find sum of length k from given combination.
- acharyashailendra1 August 21, 2019 in India
for example n=51 and k=3 then your answer should be =axz
as there can be many combination for given sum so it is suggested to print those string which comes first in dictonary| Report Duplicate | Flag | PURGE
LendingKart SDE-2 Data Structures - 1of 1 vote
Answersbeautiful numbers are those numbers which contains digit only 4 and 5 also they are palindrome.length of number can't be odd. for example
- acharyashailendra1 August 21, 2019 in India
44,55,4554 are beautiful numbers where as 38, 444 are not.
your task is to find nth number in this series. let's say if n=4 then output should be 4554. for n=1 output will be 44 always.| Report Duplicate | Flag | PURGE
LendingKart SDE-2 Data Structures - 0of 0 votes
AnswersYou are required to collect N numbers from a bag. Initially, the bag is empty. Whenever you put a number X in the bag, then the owner of the bag asks the question.
- Sameer June 21, 2019 in United States
The questions are as follows:
. What is the greatest integer that is smaller than X and present inside the bag?
. What is the smallest number that is greater than X and present inside the bag?
If you answer both the questions correctly, then you can put X inside the bag. Your task is to answers the questions that are asked by the owner of the bag. If no such numbers exist in the bag print -1.
Example:
5 (Number of elements in the bag)
1
4
2
3
7
output:
-1 -1
1 -1
1 4
2 4
4 -1| Report Duplicate | Flag | PURGE
Amazon Java Developer Data Structures - 1of 1 vote
AnswersGiven an integer 'n', create an array such that each value is repeated twice. For example
- robb.krakow May 09, 2019 in United States
n = 3 --> [1,1,2,2,3,3]
n = 4 --> [1,1,2,2,3,3,4,4]
After creating it, find a permutation such that each number is spaced in such a way, they are at a "their value" distance from the second occurrence of the same number.
For example: n = 3 --> This is the array - [1,1,2,2,3,3]
Your output should be [3,1,2,1,3,2]
The second 3 is 3 digits away from the first 3.
The second 2 is 2 digits away from the first 2.
The second 1 is 1 digit away from the first 1.
Return any 1 permutation if it exists. Empty array if no permutation exists.
Follow up: Return all possible permutations.| Report Duplicate | Flag | PURGE
Facebook Software Engineer Data Structures - 1of 1 vote
AnswersWrite a program to find the given new program can be scheduled or not?
- veeru April 23, 2019 in United States
Already scheduled Programs: P1(10,5), P2(25,15)
New Programs: P3(18,7), P4(12, 10).
In P1(10, 5), where 10 is the starting time, 5 is the execution time.
As The P3(18, 7) starts at time 18 and executes for 7 mins i.e., the end time is 18+7 = 25. So this time slot is free and there is no overlap with already scheduled programs. Hence P3 can be scheduled.
As the P4 overlaps with P1, So P4 cannot be scheduled.| Report Duplicate | Flag | PURGE
Google Software Engineer Data Structures - 0of 0 votes
AnswersGiven two strings, A and B, of equal length, find whether it is possible to cut both strings at a common point such that the first part of A and the second part of B form a palindrome.
- nemishsangani96 March 23, 2019 in India
Extension1. How would you change your solution if the strings could be cut at any point (not just a common point)?
Extension2. Multiple cuts in the strings (substrings to form a palindrome)? Form a palindrome using a substring from both strings. What is its time complexity?| Report Duplicate | Flag | PURGE
Algorithm Coding Computer Science Data Structures Dynamic Programming String Manipulation - 2of 2 votes
AnswersWrite a new data structure, "Dictionary with Last"
- Coder January 15, 2019 in United States
Methods:
set(key, value) - adds an element to the dictionary
get(key) - returns the element
delete(key) - removes the element
last() - returns the last key that was added or read.
In case a key was removed, last will return the previous key in order.| Report Duplicate | Flag | PURGE
Facebook Software Engineer Data Structures - 1of 1 vote
AnswersPrroblem: write an algorithm to calculate the minimum cost to add new roads between the cities such that all the cities are accessible from each other
int numTotalAvailableCities = 6;
int numTotalAvailableRoads = 3;
int[,] roadsAvailable = { { 1, 4 }, { 4, 5 }, { 2, 3 } };
int[,] costNewRoadsToConstruct = { { 1, 2,5 }, { 1,3,10 }, {1,6,2} ,{ 5, 6, 5 } };
int numNewRoadsConstruct = 4;
- sunil.sebastian January 05, 2019 in United Statespublic class MinimumCostToConstructNewRoad { public static int getMinimumCostToConstruct(int numTotalAvailableCities, int numTotalAvailableRoads, int[,] roadsAvailable, int numNewRoadsConstruct, int[,] costNewRoadsConstruct) { int totalCost = 0; bool[] Visited = new bool[numTotalAvailableCities]; int[] Keys = new int[numTotalAvailableCities]; int[] Parent = new int[numTotalAvailableCities]; int[,] AdjMatrix = GetAdjecencyMatrix(roadsAvailable, costNewRoadsConstruct, numTotalAvailableCities); for (int i=0;i< numTotalAvailableCities;i++) { Keys[i] = Int32.MaxValue; } Keys[0] = 0; Parent[0] = -1; for(int i=0;i< numTotalAvailableCities-1;i++) { var u = FindMin(Visited, Keys); Visited[u] = true; for(int v=0;v< numTotalAvailableCities;v++) { if(Visited[v]==false && AdjMatrix[u, v]!=Int32.MaxValue && AdjMatrix[u,v]<Keys[v]) { Parent[v] = u; Keys[v] = AdjMatrix[u, v]; } } } for(int i=1;i< numTotalAvailableCities;i++) { totalCost = totalCost + AdjMatrix[Parent[i], i]; } return totalCost; } private static int FindMin(bool[] Visited, int[] Keys) { int min = Int32.MaxValue; int index = -1; for (int i = 0; i < Keys.Length; i++) { if (Visited[i] == false && Keys[i] < min) { min = Keys[i]; index = i; } } return index; } private static int[,] GetAdjecencyMatrix(int[,] roadsAvailable, int[,] costNewRoadsConstruct,int numTotalAvailableCities) { int[,] AdjMatrix = new int[numTotalAvailableCities, numTotalAvailableCities]; for (int i = 0; i < numTotalAvailableCities; i++) { for (int j = 0; j < numTotalAvailableCities; j++) { AdjMatrix[i, j] = Int32.MaxValue; } } int count = 0; for (int i = 0; i < roadsAvailable.GetLength(0); i++) { int start = roadsAvailable[i, count]-1; int end = roadsAvailable[i,count+1]-1; AdjMatrix[start, end] = 0; } for (int i = 0; i < costNewRoadsConstruct.GetLength(0); i++) { int start = costNewRoadsConstruct[i, count]-1; int end = costNewRoadsConstruct[i, count+1]-1; int cost= costNewRoadsConstruct[i, count + 2]; AdjMatrix[start, end] = cost; } return AdjMatrix; } }
| Report Duplicate | Flag | PURGE
Amazon SDE-2 Data Structures - 2of 2 votes
AnswersGiven a string s contains lowercase alphabet, find the length of the Longest common Prefix of all substrings in O(n)
- Prateek Agrawal December 02, 2018 in United States
For example
s = 'ababac'
Then substrings are as follow:
1: s(1, 6) = ababac
2: s(2, 6) = babac
3: s(3, 6) = abac
4: s(4, 6) = bac
5: s(5, 6) = ac
6: s(6, 6) = c
Now, The lengths of LCP of all substrings are as follow
1: len(LCP(s(1, 6), s)) = 6
2: len(LCP(s(2, 6), s)) = 0
3: len(LCP(s(3, 6), s)) = 3
4: len(LCP(s(4, 6), s)) = 0
5: len(LCP(s(5, 6), s)) = 1
6: len(LCP(s(6, 6), s)) = 0
String contains only lowercase alphabates.| Report Duplicate | Flag | PURGE
Google SDE1 Data Structures - 0of 0 votes
AnswersImplement phone book <unique name, number>
- reshma.dhotre November 30, 2018 in India
1.Sorted phone book
2.searching based on name
3Searching based on number. What are the data strutures required| Report Duplicate | Flag | PURGE
Bloomberg LP Senior Software Development Engineer Data Structures - -2of 4 votes
AnswersHow should I prepare for the interview with Alexa team at Amazon?
- ihsihs005 October 17, 2018 in United States for Alexa| Report Duplicate | Flag | PURGE
Amazon SDE1 Data Structures - 0of 0 votes
AnswersIf you had n racers and m checkpoints, how would you list out the racers in the order in which they are in the race given that each checkpoint gets a notification when a specific racer crosses it?
- AnonyMous October 11, 2018 in United States
Your code should run in O(1).
Note: Players cannot cheat, i.e. they cannot miss a checkpoint
Example:
Assume 5 checkpoints(C1, C2, C3, C4, C5) and 10 racers(P1, P2,...P10).
Now once the race begins, lets say P2 first crosses C1. So the current race order is P2.
Now P1, P3, P4 cross C1; so the race order is P2, P1, P3, P4.
Now P1, crosses C2; so the race order becomes P1, P2, P3, P4
Now P3, crosses C2; so the race order becomes P1, P3, P2, P4
Now P5, crosses C1; so the race order becomes P1, P3, P2, P4, P5
Now P1 crosses C3; so the race order remains P1, P3, P2, P4, P5
and so on.
Assume that you get notified of players crossing a checkpoint by a function update(player name, checkpoint). Your task is to show the players in order in O(1) i.e return a vector of players in-order in O(1)| Report Duplicate | Flag | PURGE
Bloomberg LP SDE1 Data Structures - 0of 0 votes
AnswersGiven multiple input streams of sorted numbers of infinite size, produce a single sorted output stream.
- sanjos October 01, 2018 in United States
(The size of all the input streams are unknown)
For eg.
Input Stream 1: 2,4,5,6,7,8...........
Input Stream 2: 1,3,9,12..............
Input Stream 3: 10,11,13,14........
Output Stream:
1,2,3,4,5,6,7,8,9,10,11,12,13...............| Report Duplicate | Flag | PURGE
Amazon SDE-3 Data Structures - 0of 0 votes
Answersprint hockey stick number in pascal triangle where row of triangle can be upto 30000 and length of stick can be upto 100.
- Randhir September 09, 2018 in India| Report Duplicate | Flag | PURGE
Wissen Technology Software Developer Coding Data Structures Dynamic Programming Java - 2of 2 votes
AnswersQuestion : Given a set of N numbers [1,N], partition them into 2 disjoint subsets based on a set of K queries.
- robb.krakow July 25, 2018 in United States
Each query is of the type (n1, n2) where n1 and n2 are distinct numbers from the set and n1 and n2
belong to opposite subsets.
Example:
Input:
Input:
N = 4
K = [(1, 2), (1, 3), (2, 4)]
Output:
Set 1 : (1,4)
Set 2 : (2,3)| Report Duplicate | Flag | PURGE
Microsoft Software Engineer Data Structures - -4of 6 votes
Answerword look up
- bryan July 06, 2018 in United States| Report Duplicate | Flag | PURGE
Facebook Data Structures - -1of 1 vote
AnswerYou have been given a map which holds book name and book author. One author might have several different books. But books are unique. Now, write a function which will return you a Map which will have the author name as unique and all the books he has written as values.
Book Map=["Java"-->"John", "C#"-->"Rob", "Ruby"-->"John", "Rails"-->"Rob"]
This should return a Map which has the following:
- TurboMap June 22, 2018 in United States["John"-->{"Java","Ruby"} "Rob"--{"C#","Rails"}]
| Report Duplicate | Flag | PURGE
PayPal Quality Assurance Engineer Data Structures - 0of 0 votes
Answershttps://codejamanalysis.wordpress.com/2017/03/18/crossover-problem-super-stack/
- akshaysjk June 13, 2018 in United States
Any Optimized Solution to avoid TLE for 4 test cases. I have tried by implementing Stack using Doubly Linked List.
Still not able to pass test cases!!!| Report Duplicate | Flag | PURGE
Java Developer Data Structures Java Stacks - 0of 0 votes
AnswersGiven a BST of memory sizes. Find best fit for a memory block of size M.
- akisonlyforu June 11, 2018 in India| Report Duplicate | Flag | PURGE
Amazon SDE1 Data Structures - 0of 0 votes
AnswersGiven a wall, which is made up of two types of bricks (Porus / opaque ). Porus bricks allow water pass through them. Opaque won't. Find whether water reaches to ground, if there is any rainfall.
- gopi.komanduri June 11, 2018 in India for Office
Water can flow from top to bottom, diagonally, horizontally as well. Only flowing from bottom to top is not possible.| Report Duplicate | Flag | PURGE
Microsoft SDE-3 Algorithm Arrays Brain Storming Coding Data Structures Dynamic Programming Problem Solving Programming Skills - 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
Open Chat in New Window