## 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 States`public 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

**CareerCup**is the world's biggest and best source for software engineering interview preparation. See all our resources.

Open Chat in New Window