## SDE-2 Interview Questions

- 0of 0 votes
Given a dictionary of words and a string pattern. Output the count of words that match the string pattern in the dictionary.

Eg. Dictionary: [cat, rat, mat, apple, boy, bat]

String pattern: ?at

Output: 4 (because cat, rat, mat, bat matches the string pattern)

- 0of 0 votes
Given any two nodes in a binary tree, find the path from 1st node to another, and tell if the path is a straight line, or there are turns on the line, find number of turns.

- 0of 0 votes
Find the maximum difference between any combination of child and parent node in a given binary tree. Here child node can be any level below parent node, but should be in the same sub tree starting from parent node.

- 1of 1 vote
Design Truecaller. Both HLD and LLD.

- 0of 0 votes
Given a chessboard, find minimum number of moves for a knight to reach from source to destination.

- 0of 0 votes
Given 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.

Examples : Given a graph with values {1,2,3,4}, find total time it takes, such that all nodes have value as 10.

- 1of 1 vote
Given a Singly Linked list, Update the second half of the list such that n-th element becomes sum(1st + nth) element, (n-1)st element becomes sum(2nd + n-1st) element and so on. Eg: 2->3->4->5->6 => 2->3->(4+4)->(5+3)->(6+2)

- 0of 0 votes
Implement a queue using only one stack.

- 0of 0 votes
It’s a two player game. Both the players are equally intelligent to win the game. Give n no. of stones. A player can choose either 1 stone or k stones or l stone (1<k<l). Suppose player 'A' starts game then challenge was to identify the player who will win the game. Player who picks the last 1 stone or last k stone or last l stones win the game.

- 0of 0 votes
Design bus booking system:- Each row has x seat. If customer wants K seats if you have K consecutive seats available, reserve them. Otherwise give seats from any row.

- 0of 0 votes
There is a bridge and N no. people takes (a1,a2,—an) time to cross it and there are K torch and at any time x no of people can pass the bridge and it takes maximum of x people time to cross it. Minimum time required for N persons to cross the bridge.

- 0of 0 votes
There is a graph where each node represents a city and it contains specific no. of people. A tournament is going on and each match is playing in one city. All city’s people gather to watch match. Traffic department wants to manage how many people travel through city x if match is playing in city y for each x. City x and y can be any city.

- 0of 0 votes
Given an Infinite stream of strings as AAAAABBBCCDDDEEE… How will you arrange characters so that string become unique without duplicates .

Return true if it is possible to arrange else return -1.

Ex . AAABBCCDEF – O/p ABABCDCEF : Possible . AAAAAAAAAAAAAAAAAAAAAAB : Not possible

- 0of 0 votes
Given an array of integers, replace every number with the next higher number to its right. If a number can’t be replaced, we leave it as-it is.

For example, the list: 5, 2, 1, 4, 6, 7 needs to be changed to 6, 4, 4, 6, 7, 7.

- 0of 0 votes
Given two unsorted arrays A, B. They can contain duplicates. For each element in A count elements less than or equal to it in array B

Examples:

Input : A = [1, 2, 3, 4, 7, 9]

B = [0, 1, 2, 1, 1, 4]

Output : [4, 5, 5, 6, 6, 6]

- 0of 0 votes
How do I design a Payment Gateway system? What are the things to consider in this design ?

- 1of 1 vote
WAP to Convert Hex String to Equivalent decimal Integer.

- 0of 0 votes
Given a matrix. Convert it into a linked list matrix such that each node is connected to its next right and down node.

Ex:

1 2 3

4 5 6

7 8 9

Output:

1->2->3->NULL

| | |

v v v

4->5->6->NULL

| | |

v v v

7->8->9->NULL

| | |

v v v

--NULL-

This is my code.`class Ideone { public static void main(String args[]) throws Exception { int arr[][] = { { 1, 2, 3 }, { 4, 5, 6 } }; LList op = convert2DArrintoList(arr, 0, 0); System.out.println(op); } public static LList convert2DArrintoList(int arr[][], int col, int row) { if (col >= arr[0].length || row >= arr.length) return null; return new LList(arr[row][col], convert2DArrintoList(arr, col, row + 1), convert2DArrintoList(arr, col + 1, row)); } static class LList { LList(int data) { this.data = data; } LList(int data, LList down, LList next) { this.data = data; this.down = down; this.next = next; } LList() { this.data = Integer.MAX_VALUE; } @Override public String toString() { return " " + this.data + " "; } int data; LList next; LList prev; LList rand; LList down; } }`

Are there better ways of doing it?

- 0of 0 votes
Given 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.

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 ?

- 0of 0 votes
Design amazon's frequently viewed product page.

- 0of 0 votes
Design a ESPN like system. Ensure scaling and availability. Also one should get all details like score of a player, no. of mtches etc.

- 0of 0 votes
count number of combinations which are not possible.

There are 'n' empty slots.

A slot can be filled with 'O', 'E', or 'X'

A combination is possible if

1. 'O' s are placed in odd slot , 'E' a are placed in even slots.

2. 'O' and 'E' alternate among them,

i.e (OXOE) not allowed because between O s there is no 'E'; but (OEXXO) is allowed.

some allowed combinations

OEXXX, XXOEO, OXXEX

For 3 slots, not allowed combinations are

OXX

XXO

XEX

XXX

OXO

Only those combinations are considered in which O s and E s are in their respective odd and even slots.

i.e EEXXX will never be considered because a 'E' is in odd slot

A combination isn't allowed if 'O' is not followed by 'E' or vice versa

- 2of 2 votes
Design a FIDS(Flight Information Display System)

1. Consider most important classes & ignore Interfaces as of now

2. FIDS is not about reservation system but the dasboard to display

3. the information will look like:

DEPARTURES

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

Attributes:

STD Airline Flight Destination/Via CheckInCounter# Gate Status ETD

Values :

12:50 KingFisher 6E352 Hyderabad A-B 23 Check-In Open 13:15

ARRIVALS

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

Attributes:

STA Airline Flight# Destination/Via Gate Status ETA

Values :

12:50 KingFisher 6E352 UK/Mumbai Terminal2 Landed 13:15

- 0of 0 votes
Write a C code matrix multiplication in such a way that the matrix can be read in row major form only

- 1of 1 vote
Design a mall where there are 'm' entry gates and 'n' exit gates. There can be only 'x' number of people inside it. No more then 'x' people can be inside mall at any time.

- 0of 0 votes
How will you design a true collar?

- 0of 0 votes
Given an array of co ordinates (x,y). WAP to figure out if a square can be formed from any four points.

- 0of 0 votes
Given a 2d matrix and 4 points. WAP to figure out if they are row wise, column wise of diagonally wise consecutive.

- 0of 0 votes
The memmove() function copies n bytes from memory area src to memory area dest. The memory areas may overlap: copying takes place as though the bytes in src are first copied into a temporary array that does not overlap src or dest, and the bytes are then copied from the temporary array to dest.

- 0of 0 votes
Find distance between any two nodes of binary tree and binary search tree.