## SDE1 Interview Questions

- 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

- 0of 0 votes
How would you architect a client based recommendation feature(based on customer history) on product detail page?

- 0of 0 votes
Design Customers who viewed this also viewed that for an online shopping portal

- 0of 0 votes
. In an unsorted array of numbers that occurs an odd number of times except one that occurs an even number of times, find the number that occurs an even number of times

- -3of 3 votes
Solve Travelling salesman problem using Iterative Deepening Search Algorithm.

Edit:

You have been given distance between each pair of cities and the number of cities

- 0of 0 votes
Consider a regular polygon with N vertices labelled 1..N. In how many ways can you draw K diagonals such that no two diagonals intersect at a point strictly inside the polygon? A diagonal is a line segment joining two non adjacent vertices of the polygon.

Input:

The first line contains the number of test cases T. Each of the next T lines contain two integers N and K.

Output:

Output T lines, one corresponding to each test case. Since the answer can be really huge, output it modulo 1000003.

Constraints:

1 <= T <= 10000

4 <= N <= 10^9

1 <= K <= N

Sample Input:

3

4 1

5 2

5 3

Sample Output:

2

5

0

Explanation:

For the first case, there are clearly 2 ways to draw 1 diagonal - 1 to 3, or 2 to 4. (Assuming the vertices are labelled 1..N in cyclic order).

For the third case, at most 2 non-intersecting diagonals can be drawn in a 5-gon, and so the answer is 0.

- 0of 0 votes
There are 8 statues 0,1,2,3,4,5,6,7 . Each statue is pointing in one of the following four direction North, South, East or West.

John would like to arrange the statues so that they all point in same direction. However John is restricted to the following 8 moves which correspond to rotation each statue listed 90 degrees clockwise. (N to E, E to S, S to W, W to N)

Move A: 0,1

B: 0,1,2

C: 1,4,5,6

D: 2,5

E: 3,5

F: 3,7

G: 5,7

H: 6,7

Help John figure out fewest number of moves to help point all statues in one direction.

Input : A string initialpos consisting of 8 chars. Each char is either 'N,'S,'E,'W'

Output: An integer which represents fewest no. of moves needed to arrange statues in same direction. If no sequence possible then return -1.

Sample test cases:

input: SSSSSSSS

Output: 0

Explanation: All statues point in same direction. So it takes 0 moves

Test case 1:

Input : WWNNNNNN

Output: 1

Exp: John can use Move A which will make all statues point to North

Test Case 3:

input: NNSEWSWN

Output: 6

Exp: John uses Move A twice, B once, F twice, G once. This will result in all statues facing W.

Note: Read input from stdin and output from stdout

- 0of 0 votes
Given a set of restaurants (the number being quite large) and its geographical location(x,y) , you are allowed to do an significant amount of pre-processing on it. Now suppose there are x customers located at position (s,t), design an efficient algorithm to find the k nearest restaurants to these customers.

- 1of 1 vote
A ternary string consists of only a, b, c following the given 3 rules

1. a's cannot be consecutive.

2.b can appear only once.

Find the nuber of possible ternary string of length n.

- 1of 1 vote
how to do this round1 question 1:

http://www.geeksforgeeks.org/directi-interview-set-5-campus/

A string can contain only a, b or c. There cannot be 2 consecutive same character. First and last character cannot be same. Now given a string with ‘a’, ‘b’, ‘c’ or ‘?’. We need to find the string replacing ‘?’ that satisfy the above conditions. For multiple answer display lexicographically smallest string. For no answer possible display “Not Possible”.

- 0of 0 votes
How to remove file named "~" ?

- 2of 2 votes
Given a file containing a list of ip addresses that have lost their dots(.'s), write a program to find the ip addresses, assume ipv4. input: 11111 output. 1.1.1.11, 11.1.1.1, etc

- 2of 2 votes
You are given an array of both negative and positive integers. You need to rearrange the array such that positive and negative numbers alternate. Also, the order should be same as previous array and only O(1) auxiliary space can be used and time complexity boundation O(n).

eg. -2 3 4 5 -1 -6 7 9 1

result – 3 -2 4 -1 5 -6 7 9 1.

- 0of 0 votes
we have website having several web-pages. And also there are lot many user who are accessing the web-site.

say user 1 has access pattern : x->y->z->a->b->c->d->e->f

user 2 has access pattern : z->a->b->c->d

user 3 has access pattern : y->z->a->b->c->d

user 4 has access pattern : a->b->c->d

and list goes on for lot many users which are finite and numbered.

Now the question is we have to determine the top 3 most occurring k-Page-sequence.

for the above example result will be : (k=3) a->b->c , b->c->d , z->a->b.

- 5of 5 votes
Write a program to replace each element of an array with a number present on the right side of the element such that the number is least greater than the element. If there is no greater number replace it with -1

e.g : 8, 58, 71, 18, 31, 32, 63, 92, 43, 3, 91, 93, 25, 80, 28

ans : 18, 63, 80, 25, 32, 43, 80, 93, 80, 25, 93, -1, 28, -1, -1

I gave the obvious o(n^2) solution. He asked to optimize it.

- 0of 0 votes
Write a program to replace each element of an array with a number present on the right side of the element such that the number is least greater than the element. If there is no greater number replace it with -1

e.g : 8, 58, 71, 18, 31, 32, 63, 92, 43, 3, 91, 93, 25, 80, 28

ans : 18, 63, 80, 25, 32, 43, 80, 93, 80, 25, 93, -1, 28, -1, -1

- 4of 4 votes
Two ﬁnite, strictly increasing, integer sequences are given. Any common integer between the two sequences constitute an intersection point. Take for example the following two sequences where intersection points are

printed in bold:

First= 3 5 7 9 20 25 30 40 55 56 57 60 62

Second= 1 4 7 11 14 25 44 47 55 57 100

You can ‘walk” over these two sequences in the following way:

1. You may start at the beginning of any of the two sequences. Now start moving forward.

2. At each intersection point, you have the choice of either continuing with the same sequence you’re currently on, or switching to the other sequence.

The objective is ﬁnding a path that produces the maximum sum of data you walked over. In the above example, the largest possible sum is 450 which is the result of adding 3, 5, 7, 9, 20, 25, 44, 47, 55, 56, 57, 60, and 62

this is the same problem which I saw in SPOJ Problem Set

- 0of 0 votes
Write a java program to evaluate given arithmetic expression to get maximum possible answer. ( Expression will contain only 3 type of operations +,-,* ). it will not contain any brackets. so the order of operator precedence will not be there. any part of the expression can be executed in any order to get the maximum possible ans.

- 0of 0 votes
Reverse the alternate level nodes of the binary tree.

a

/ \

b c

/ \ / \

d e f g

/ \ / \ / \ / \

h i j k l m n o

Modified tree:

a

/ \

c b

/ \ / \

d e f g

/ \ / \ / \ / \

o n m l k j i h

- 2of 4 votes
Given a complete binary tree, Find a Max element

- 0of 0 votes
Base class is given you need to stop exposing the base class methods without touching the base class at all.