## Data Structures Interview Questions

- 0of 0 votes

AnswersCreate a stack for bools. it will have these functions

- milota@mindgrip.com January 28, 2022 in United States

void push(bool input)

bool pop() // no one will ever try to pop if it is empty

bool empty() const // returns true if the stack is empty

void clear() // cleans out the data and recovers the memory

This stack should not be limited in size but grow as needed.

hard part

save space, it is ok if it is slow from time to time but should generally be fast

98% of the time we will push false and 2% of the time we will push true

edge conditions

the first push may be true or false

there may be long runs of just pushing true or long runs of just pushing true

second part

how would you change it to if it was 80 / 20 and there were long runs of an average length of 15 trues in a row?

third part

How would you change it if there were different ratios and different average length runs.| Report Duplicate | Flag | PURGE

Software Engineer / Developer Data Structures - 0of 0 votes

AnswersPrint the most near missing integer in the unsorted value.

- Manoj July 16, 2021 in India`public static void main(String args[]) { System.out.println(solution(new int[]{-4,-2})); } private static int solution(int[] ints) { //1,2,3,4 //2,3,4 = 1 //-2,-1,2,3,4 = 0,0,2,3,4 = 1 //-4,-3,-2 = 1 //-4,-2 = 1 //-3,-2,-1 , 1 = 2 Arrays.sort(ints); //O(log*n) for (int i = 0; i < ints.length; i++) { if (ints[i] > 0) { if (ints[i + 1] - ints[i] > 1) { return 1; } break; } ints[i] = 0; } //O(n-m) n- lenght array , m - negative interger //1,2,3,5,7,8,9,10 for (int i = 0; i < ints.length - 1; i++) { if (ints[i + 1] - ints[i] > 1) { return ints[i] + 1; } } //O(n-k) return ints[ints.length - 1] + 1; //O(log n * n2) }`

| Report Duplicate | Flag | PURGE

Walmart Labs Staff Engineer Data Structures - 2of 2 votes

AnswersWhen a person who knows it meets any other person, they immediately share the story with them.

- veeru June 25, 2021 in India

Initially, only person 1 knows the story. Given a list of meetings between people in a form of

(person_1_id, person_2_id, timestamp) construct a list of the persons who will know the story

at the very end.

Example: [(1, 2, 100), (3,4, 200), (1,3, 300), (2,5, 400)], 1 // The events could be out of order.

Person 2 will learn the story at the moment 100, person 3 — at the moment 300,

person 5 — in the moment 400. Person 4 will never learn the story. So the answer is [1, 2, 3, 5].

Eg2: [(1, 2, 100), (2, 3, 100), (4, 5, 100)], 2

where the first parameter is array of the Persons meet at particular timestamp, second parameter is the PersonId who knows the story first.

Output: [1, 2, 3]| Report Duplicate | Flag | PURGE

Google Software Engineer / Developer Data Structures - 1of 1 vote

AnswersGiven a string s consisting of items as "*" and closed compartments as an open and close "|", an array of starting indices startIndices, and an array of ending indices endIndices, determine the number of items in closed compartments within the substring between the two indices, inclusive.

- prashant1diwase May 24, 2021 in United States for Tax Systems

An item is represented as an asterisk ('*' = ascii decimal 42)

A compartment is represented as a pair of pipes that may or may not have items between them ('|' = ascii decimal 124).

Example

s = '|**|*|*'

startIndices = [1, 1]

endIndices = [5, 6]

The string has a total of 2 closed compartments, one with 2 items and one with 1 item. For the first pair of indices, (1, 5), the substring is '|**|*'. There are 2 items in a compartment.

For the second pair of indices, (1, 6), the substring is '|**|*|' and there are 2 + 1 = 3 items in compartments.

Both of the answers are returned in an array, [2, 3].

Function Description .

Complete the numberOfItems function in the editor below. The function must return an integer array that contains the results for each of the startIndices[i] and endIndices[i] pairs.

numberOfItems has three parameters:

- s: A string to evaluate

- startIndices: An integer array, the starting indices.

- endIndices: An integer array, the ending indices.

Constraints

1 ≤ m, n ≤ 105

1 ≤ startIndices[i] ≤ endIndices[i] ≤ n

Each character of s is either '*' or '|'

Input Format For Custom Testing

The first line contains a string, s.

The next line contains an integer, n, the number of elements in startIndices.

Each line i of the n subsequent lines (where 1 ≤ i ≤ n) contains an integer, startIndices[i].

The next line repeats the integer, n, the number of elements in endIndices.

Each line i of the n subsequent lines (where 1 ≤ i ≤ n) contains an integer, endIndices[i].

Sample Case 0

Sample Input For Custom Testing

STDIN Function

----- --------

*|*| → s = "*|*|"

1 → startIndices[] size n = 1

1 → startIndices = 1

1 → endIndices[] size n = 1

3 → endIndices = 3

Sample Output

0

Explanation

s = *|*|

n = 1

startIndices = [1]

n = 1

startIndices = [3]

The substring from index = 1 to index = 3 is '*|*'. There is no compartments in this string.

Sample Case 1

Sample Input For Custom Testing

STDIN Function

----- --------

*|*|*| → s = "*|*|*|"

1 → startIndices[] size n = 1

1 → startIndices = 1

1 → endIndices[] size n = 1

6 → endIndices = 6

Sample Output

2

Explanation

s = '*|*|*|'

n = 1

startIndices = [1]

n = 1

endIndices = [6]

The string from index = 1 to index = 6 is '*|*|*|'. There are two compartments in this string at (index = 2, index = 4) and (index = 4, index = 6). There are 2 items between these compartments.| Report Duplicate | Flag | PURGE

Amazon Software Engineer / Developer Data Structures - 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 - 9of 9 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

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