## SDE1 Interview Questions

- 0of 2 votes
You have given a mathematical expression in string format.

Example: "3+12*3-4/7"

You need to write function which will return final result of the given expression. Don't use Expression Tree and start scanning from left to write.

It should be bug free.

- 0of 0 votes
A 2D matrix is given to you. Now user will give 2 positions (x1,y1) and (x2,y2),

which is basically the upper left and lower right coordinate of a rectangle formed within the matrix.

You have to print sum of all the elements within the area of rectangle in O(1) running time.

Now you can do any pre computation with the matrix.

But when it is done you should answer all your queries in constant time.

Example : consider this 2D matrix

1 3 5 1 8

8 3 5 3 7

6 3 9 6 0

Now consider 2 points given by user (0, 2) and (2, 4).

Your solution should print: 44.

i.e., the enclosed area is

5 1 8

5 3 7

9 6 0

- 1of 1 vote
You have a chess board of size NxN. You have a horse at a given starting position. You also have a function that gives you all the positions that the horse can reach from it's current position.

Given an ending position, find the path to it that uses the minimum number of moves.

- 5of 5 votes
Given an integer array, adjust each integers so that the difference of every adjcent integers are not greater than a given number target.

If the array before adjustment is A, the array after adjustment is B, you should minimize the sum of |A[i]-B[i]|

You can assume each number in the array is a positive integer and not greater than 100

Given [1,4,2,3] and target=1, one of the solutions is [2,3,2,3], the adjustment cost is 2 and it's minimal. Return 2.

- 0of 0 votes
Array of size (n-m) with numbers from 1..n with m of them missing. Find one all of the missing numbers in O(log). Array is sorted.

Example:

n = 8

arr = [1,2,4,5,6,8]

m=2

Result has to be a set {3, 7}.

- 1of 1 vote
Give you a list of Modules of Dependencies,

A --> B,C

B --> D,E,F

D --> F

And please return back a correct build order of Module (input)

- -4of 4 votes
Shorten a List of Strings.

- 0of 2 votes
Design a Black-Jack poker game

- 4of 4 votes
Give an 2d-characters Grid, char[][] A, and a dictionary, List<String> dict. Search all possible words in the 2d-Grid.

- 0of 0 votes
finds a domino pattern for a "double-N" domino set that forms a loop / a ring using all available tiles.

for example,In a double-two domino set, with six tiles, (0 , 0) (0 , 1) (1 , 1) (1 , 2) (2 , 2) (2 , 0). So if parameter is 2, the function should return true. if no loop found, should return false.

Dominoes are small rectangular game tiles divided into two squares and embossed with dots on the top surface of the tile. You can think of dots as integers. A double-N domino set consists of (N+1)(N+2)/2 tiles, e.g. a standard double-six domino set has 28 tiles (T): one for each possible pair of values from (0.0) to (6.6) - no pair of numbers occurs more than once.

- 0of 0 votes
We have a class as follows:

`public class People{ String name; String position; String sex; ... ... public String getAttribute(String attrName){ /** * This is a generic getter method that will give you * any attribute value based on the passed attribute * Name; * for eg: getAttribute("name") => will return the * attriute(Name) value of the current object. */ } }`

I now give you two List:

list1<People> friends;

list2<String> attributes;

Using the generic getter method, we have to group "friends" on "attributes". Think of this as an implementation of GROUP BY function to be implemented on objects in list1 and to be grouped on entries in list2.

eg: list2 = {sex, occupation}

So objects in list1 will be grouped such that all Male-doctors together, Female-cops together, male-cops together, etc.

- 1of 1 vote
Given a array of positive integers, find all possible triangle triplets that can be formed from this array.

eg: 9 8 10 7

ans: 9 8 10, 9 8 7, 9 10 7, 7 8 10

Note : array not sorted, there is no limit on the array length

- 2of 2 votes
Given a large array of unsigned ints, quickly find two who's sum is 10

Then the interviewer asked me to write test cases.

Followed by how to implement this on a distributed system, where multiple systems can read/write simultaneously on a shared cache (HINT: It is ok if you do not return the first instance)

- 1of 1 vote
Minesweeper question: Given an n x m grid holding individual mine co-ordinates, identify all of the mine clusters. A mine cluster is the largest collection of neighboring mines.

Example input:

0 1 2 3

---------

0|0|1|0|1

1|0|0|1|1

2|0|0|0|0

3|1|1|0|0

Expected output:

[cluster 1] (0,1),(1,2),(1,3),(0,3)

[cluster 2] (3,0),(3,1)

- 1of 1 vote
given a range of number 1 through N, where N >=3. you have to take an array of length 2N and place each number ( from the range 1 to N) twice. such a that the distance between two indexes of a number is equal to the number. example

N=3

( 3, 1, 2, 1, 3, 2 )

I know we can Use Backtracking but is there any other solution.

- 0of 0 votes
Write an algorithm to convert the given input string to the expected output string. The input string shall be the length of few million characters. So the output has to be updated in the same string...

Input String = "ABBCDEFGGGGGGGGHHXX..<20 more X>..XYY..."

Expected output = "A1B2C1D1E1F1G8H2X23Y2..."

Note: The count of each character has to be appended with the same character in the output string

- 1of 1 vote
Given a stream of characters (stream is increasing char by char), check if newly

formed 10character word is present in already parsed/scanned stream. Print such

repeating streams lexicographically at the end.

- 0of 0 votes
reverse nodes in k interval in single linked list

eg. k = 3

i/p 1 2 3 4 5 6 7 8 9

o/p 3 2 1 6 5 4 9 8 7

- 0of 0 votes
find if two people are connected in social network.

- 0of 0 votes
you wrote a c++ program and your processor change (eg. from intel to ARM or anything ) then what are thing needs to be change in compiler to get the same behavior of program in different (eg. ARM ) architecture machine.

- 1of 1 vote
There is a rectangle with left bottom as (0, 0) and right up as (x, y). There are n circles such that their centers are inside the rectangle. Radius of each circle is r. Now we need to find out if it is possible that we can move from (0, 0) to (x, y) without touching the circle. We can move freely anywhere.

- 0of 0 votes
calculate the summary statistics for a fleet of hosts. Each host has a fixed number of slots in which virtual instances can run. Each host can only run instances of a particular type, e.g. M1, M2, or M3. You are provided with the file “FleetState.txt” that contains the state of the fleet. Each line in the file represents a single host in the following comma-separated format:

<HostID>,<InstanceType>,<N>,<Slot1State>,<Slot2State>,…,<SlotNState>

where

<HostID> is an integer

<InstanceType> can be M1, M2, or M3

<N> is the total number of slots on the machine

<SlotjState> is 0 if slot j is empty and 1 if it is occupied by an instance

Write a program that loads the state of the fleet from the input file “FleetState.txt” and then computes and writes out the following summary statistics to the output file “Statistics.txt”:

For each instance type, the count of empty hosts (all slots empty)

For each instance type, the count of full hosts (all slots filled)

For each instance type, the count of the most filled hosts (having the smallest number of empty slots > 0). Both the host count and number of empty slots must be written out in that order.

The output file must have the following format:

EMPTY: M1=<count>; M2=<count>; M3=<count>;

FULL: M1=<count>; M2=<count>; M3=<count>;

MOST FILLED: M1=<count>,<empty slots>; M2=<count>,<empty slots>; M3=<count>,<empty slots>;

What is the best way to solve this problem?

- 0of 0 votes
calculate the summary statistics for a fleet of hosts. Each host has a fixed number of slots in which virtual instances can run. Each host can only run instances of a particular type, e.g. M1, M2, or M3. You are provided with the file “FleetState.txt” that contains the state of the fleet. Each line in the file represents a single host in the following comma-separated format:

<HostID>,<InstanceType>,<N>,<Slot1State>,<Slot2State>,…,<SlotNState>

where

<HostID> is an integer

<InstanceType> can be M1, M2, or M3

<N> is the total number of slots on the machine

<SlotjState> is 0 if slot j is empty and 1 if it is occupied by an instance

Write a program that loads the state of the fleet from the input file “FleetState.txt” and then computes and writes out the following summary statistics to the output file “Statistics.txt”:

For each instance type, the count of empty hosts (all slots empty)

For each instance type, the count of full hosts (all slots filled)

For each instance type, the count of the most filled hosts (having the smallest number of empty slots > 0). Both the host count and number of empty slots must be written out in that order.

The output file must have the following format:

EMPTY: M1=<count>; M2=<count>; M3=<count>;

FULL: M1=<count>; M2=<count>; M3=<count>;

MOST FILLED: M1=<count>,<empty slots>; M2=<count>,<empty slots>; M3=<count>,<empty slots>;

what is the best way to solve it?

- 0of 0 votes
Given a set of equalities and inequalities like A=B,B=C,F=J and A!=C, etc in two separate arrays (equalities[] and inequalities[]) and a method, separate that returns the two objects, e.g. separate(A=B) will return A and B, write an algorithm to find whether the entire set is consistent in constant time.

- 0of 0 votes
Given a string and a regular expression pattern, give the number of times the pattern occurs in the string. RegEx example means as follows:

. – 2 occurrences of the previous character

+ – 4 occurrences of the previous character

* – more than 5 occurrences of the previous character

Sample Input:

5

aaaaaannndnnnnnnfffhfhhgjjjwkkkllclc

a.

n+

a*

an.

a.d.

Sample Output:

5

3

2

1

0

- 1of 1 vote
Find the 90th percentile of a stream of numbers between 1 and 10^6.

Followup: What if there is not enough memory to store all numbers and no upper bound.

- 1of 1 vote
`Given a String s and a hashmap containing certain decodings for all the characters of alphabet. Find all possible passwords that can be generated by replacing decodings in the string s. Note that decodings of a charachter can only be single charachters Eg: String s="abcde" decodings given a-{1,2,p,o,q} b-{2,y} c-{p} d-{4,a,m,n} e-{9,z,x} h-{1} ' ' ' x-{0} y-{4,k,l} z-{r,5} So possible set passwords will be abcde,1bcde,2bcde,pbcde,obcde,qbcde, //replace a with all possible decodings a2cde,12cde,22cde,p2cde,o2cde,q2cde,aycde,1ycde,2ycde,pycde,oycde,qycde //replace b will all possible decodings a2pde,12pde,22pde,p2pde,o2pde,q2pde,aypde,1ypde,2ypde,pypde,oypde,qypde.....//replace c will all possible decodings`

- 0of 0 votes
non recursive method to calculate height of the binary tree.

- 0of 0 votes
you have a dictionary which will return true if the word is present in it otherwise false. You have a string "ABC", check if anagram of "ABC" is present or not. the condition was not to generate the all the anagram of ABC. (Assumption: you can store the dictionary in trie or hashmap (any data structure) and no need to implement the dictionary)

- 0of 0 votes
Merge two sorted linked list