## SDE1 Interview Questions

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

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

- 0of 0 votes
Design a stack using queue(s)

- 1of 1 vote
Design a valet parking system. Requirements of the valet parking system should be:

1. Customer are given a ticket that they can use to redeem to get their vehicle back

2. Parking spots come in three sizes, small, med, large

3. Thee types of vehicles, small, med, large

-a small vehicle can park in a small, medium, and large spot

-a medium vehicle can park in a medium and large spot

-a large vehicle can park in a large spot

- 0of 0 votes
Suppose you want improve the performance of search queries, using a cache. Each search queries is in form of a string and returns a list of ad id's in the form of longs.

Design a class with the appropriate data structure(s) that can manage a cache of search queries.

- 0of 0 votes
Say you have a string:

"Thisisasentence"

How would you separate the string into separate words, return either the sentence with spaces or as a list/array where each entry is a word

- 0of 0 votes
Write a program to find the smallest number that can be formed by 0 and 9 which is divisible by a given number.

For example, if given number is 3 output should be 9,

if given number is 2 output is 90,

if given number is 10 output is 90,

- -2of 2 votes
Write a program to find the smallest number that can be formed by 0 and 9 which is divisible by a given number.

For example, if given number is 3 output should be 9,

if given number is 2 output is 90,

if given number is 10 output is 90,

if given number is 7 output is 10^23.

- 0of 2 votes
Given ten million numbers, each having 11 bits, find the most time efficient way to sort the numbers.

- 0of 0 votes
Given an array and a number, find two integers that sums to the given number.

- 1of 1 vote
Given a graph where every two nodes are either friends or enemies with each other. Find a way to go from one node to the other.

Restrictions:

1) You can also travel from one node to next if they are friends with each other

2) You have some “magic potions”. You can convert an enemy path to a friend path with a magic potion.

I know this can be solved easily using dfs or bfs but i want to know the time complexity of each approach

- 0of 0 votes
Mice and holes are placed in a straight line. There are n holes on this line. Each hole can accomodate only 1 mouse. A mouse can stay at his position, move one step right from x to x+1, or move one step left from x to x−1. Any of these moves consumes 1 minute.

Assign mice to holes so that the time when the last mouse gets inside a hole is minimized.

for example if there are 3 mice positions of mice are:

4 -4 2

positions of holes are:

4 0 5

the answer should be 4

because:

Assign mouse at position x=4 to hole at position x=4 : Time taken is 0 minutes

Assign mouse at postion x=-4 to hole at position x=0 : Time taken is 4 minutes

Assign mouse at postion x=2 to hole at postion x=5 : Time taken is 3 minutes

After 4 minutes all of the mice are in the holes.

- 0of 6 votes
There are a large number of leaves eaten by caterpillars. There are 'K"' caterpillars which jump onto the leaves in a pre-determined sequence. All caterpillars start at position 0 and jump onto the leaves at positions 1,2,3...,N. Note that there is no leaf at position 0.

Each caterpillar has an associated 'jump-number'. Let the jump-number of the i-th caterpillar be A [i]. A caterpillar with jump number 7 keeps eating leaves in the order 1,241,3*1,... till it reaches the end of the leaves - i.e, it eats the leaves at the positions which are multiples of /'.

Given a set 'A' of 'IC elements. 'e<=15.,. 'N'<=109, we need to determine the number of uneaten leaves.

Input Format:

N -number of leaves

A - Given array of integers

Output Format:

An integer denoting the number of uneaten leaves.

Sample Input:

N = 10

A = [2,4,5]

Sample Output:

4

Explanation

1,3,7,9 are the leaves which are never eaten. All leaves which are multiples of 2, 4, and 5 have been eaten.

Java Code:`public class Solution { //need to complete the function below static int countUneatenLeave(int N, int[] A { } public static void main(String[] args) throws IOException { Scanner in = new Scanner(System.in); final String fileName = System.getenv("OUTPUT_PATH"); BufferedWriter bw = new BufferedWriter(new FileWriter(fileName)); int res; int _N; _N = Integer.parseInt(in.nextLine()); int _A_size = Integer.parseInt(in.nextLine()); int[] _A = new int(_A_size]; int _A_item; for(int _A_i = 0; _A_i < _A_size; _A_i++) { _A_item = Integer.parseInt(in.nextLine()); _A[_A_i] = _A_item; } res = countUneatenLeaves(_N,_A); bw.write(String.valueOf(res)); bw.newLine(); bw.close(); } }`

- 5of 5 votes
Given a Sorted integer array which is rotated N number of times. You have no idea what that N is. An element in the array can occur more for any number of time. Write a method to search the position of a given element. If there are more than one of the same element, return the position of the first element.

- 0of 0 votes
Recursively implement a function that returns boolean value by checking if a binary tree is binary search tree or not.

- -6of 6 votes
Traveling Salesman Problem

- 1of 1 vote
There is a compressed string eg. ”ab2c3”, the string has lowercase characters and numbers. We can uncompress the given string as follows: whenever we get a number “n” in the string, the portion of the string before the number will repeat “n” times. So in the above example, we get a 2, so string will become “ababc3”, now we get a 3, so final string will be “ababcababcababc”.

Given a compressed string and a number k, you have to output the k’th character in the uncompressed string.

1 <= length of string <= 1500

1 <= n <= 1000

1 <= k < 2^31

example:

input: ab2c3 10

output: c

- 0of 0 votes
On a very large rotated sorted array with one or more duplicates, find the index of a particular number: 20,30,30,45,60,60,5,17,17,19