## SDE1 Interview Questions

- -2of 2 votes
three sum with duplicate, pirnt all indexes, for example:

0 2 -2 -2

(0)(1)(2)(3)

print (0, 1, 2) (0, 1, 3)

can you do it use n^2 (or less) time complexity with as less space as possible?

public List<List<Integer>> threeSum(int[] nums) {}

- 0of 2 votes
Given an array of task and k wait time for which a repeated task

needs to wait k time to execute again. please rearrange the task

sequences to minimize the total time to finish all the tasks.

Example

Tasks = 111222, k = 2,

One possible task sequence is

12_12_12,

another possible task sequence is 21_21_21

thus you shoud return 8

public int getMiniTime(int[] nums, int k){

}

follow up, output one of the sequence 12_12_12, or 21_21_21

- 0of 0 votes
Given a number of tasks (T) and servers (S), find out if the tasks can be accommodated on the servers. Each Task has a number of Units and each server has a number of Slots on which Units can run.

The only condition is that two Units of the same Task "cannot" run on the same Server.

Servers

S[0] = "SS1", "SS2", "SS3", SS4 //Slots // 4 -> 3 -> 2 -> 1

S[1] = "SS1", "SS2" // 2 -> 1 -> 0 -> false

S[2] = "SS1", "SS2", SS3, SS4, SS5 // 5 -> 4 -> 3 -> 2

S[3] = "SS1", "SS2", SS3, SS4, SS5 // 5 -> 4 -> 3 -> 2

Example:

S[0] = 4

S[1] = 3

S[2] = 5

S[3] = 5

...

Tasks

T[0] = U0, U1, U2, U3 //Tasks

T[1] = U0, U1

T[2] = U0, U1, U2

...

Example:

T[0] = 4

T[1] = 2

T[2] = 3

implement

boolean boolean CanRunTasks(S[], T[]){

}

- -1of 1 vote
deleted

- 0of 0 votes
`class UndirectedGraphNode { int label; List<UndirectedGraphNode> neighbors; UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<>(); } } public boolean isBipartite(List<UndirectedGraphNode> nodes){ }`

use DFS algorithm to check the bipartite-ness of a graph

- 0of 0 votes
Delhi Route Traffic Optimizer

Traffic congestion is an annoying issue in Delhi, the capital of India. Every morning thousands of people drivea residential area to the International Technology Park (ITPL). There are various routes one can take to reach ITPL and each route takes its own time making some routes faster than the others. People obviously take faster routes which causes congestion on those roads too. Congestion results into increased travel time, air pollution and wastage of fuel. As a Traffic commissioner of Delhi, you are asked to optimize the traffic by putting toll to various roads so that resultant cost of every route (driving time cost and toll cost) ends up the same. This has to be done in such a way that any driver pays toll only once no matter which route he/she takes.roads have one-way traffic and there is no cycle in any of the routes. You need to create a toll plan for a given road layout.

The toll plan must adhere to following rules:

1. Toll should be levied in such a way that perceived cost (base road cost and toll cost) remains same forroads.

2. The tolls should be levied such that the total cost for each route is minimized.

3. A route cannot have more than one toll.

4. In case of multiple solutions for a route, add toll to a road that is closer to destination.

In some use cases, it might be impossible to impose tolls that satisfy the above conditions.

http://qa.geeksforgeeks.org/11340/delhi-route-traffic-optimizer

- 0of 0 votes
Give a Runable interface, and then give a scheduler post method. This post is parallel, for example:

Method header:

public void post (Runable r) {};

Call 5 times:

Scheduler.post (r1);

Scheduler.post (r2);

Scheduler.post (r3);

Scheduler.post (r4);

Scheduler.post (r5);

The five runables are allocated to five threads and run at the same time. And then asked: how to achieve these five tasks one by one run,

- 0of 0 votes
There are two integer array arrayA and arrayB in the same size and two integer countA and countB. If arrayA[i] > arrayB[i], then we increase countA by 1, if arrayB[i]>arrayA[i], then we increase countB by 1. We will do nothing otherwise. Now you are given arrayA and arrayB, write a function to shuffle arrayA and so you can get countA > countB. Assume the input array are always valid, not empty and the input is guaranteed to have answer.

For example:

arrayA = [12, 24, 8, 32]

arrayB = [13, 25, 32, 11]

After shuffle:

arrayA = [24, 32, 8, 12]

arrayB = [13, 25, 32, 11]

- 4of 4 votes
there is a bunch of tasks, each have different time to complete, task is independent, and then there are some workers,

How to allocate tasks to these workers to minimize the total time to complete all the task. The tasks can be randomly picked from the task list.

Example

Task: 2,2,3,7, 1

Worker: 2.

Return 8, because the first worker can work on the first three tasks : 2 + 2 + 3 = 7, and the second worker can work on the last two tasks : 7 + 1 = 8, so the total time to finish all the task is 8.

public int getMini(int[] tasks, int k)

- 4of 4 votes
Given an non-negative int array and target number, check if the target can be equal to the sum of non-negative multiples of the numbers in the array.

For example, I have three numbers 6,9,20. Ex: n = 47 then it can be determined that 47 = 9*3 + 20

n=23 then there are no combinations.

public boolean combinationSum(int[] nums, int target) {

}

- 0of 0 votes
We have a List of FlightRoute

`public static class FlightRoute { String from; String to; int time; .... }`

and write a function to find Shortest Path: findShorestPath(String start, String end, List<FlightRoute>routes)

- 2of 2 votes
Given an int array without repeated elements and a target, count the total number of subset that can be generated from the array such that min (subset) + max (subset) < target

public int countSubSet(int[] nums, int target){

}

- 0of 0 votes
Data structure design, N horse races, there are 10 checkpoints, whenever a horse through a check point will produce a (horse number, check point number) message, then design a data structure and algorithm to update the messages and then get the top 3 horse efficiently.

- 0of 0 votes
Input friend’s relation {{1,2}, {2,3}, {3,4}}, could you split all the users into two groups and for the user in each group, all the users do not know each other. So the expected output should be group1 {1,3}, group2 {2,4}. If it is cannot be spitted into two group, just return “impossible”

- 0of 0 votes
/**

* Definition for an interval.

* public class Interval {

* int start;

* int end;

* Interval() { start = 0; end = 0; }

* Interval(int s, int e) { start = s; end = e; }

* }

*/

Given a list of intervals, and a target interval

Our goal is to merge these intervals, so that the results of the merge can cover the target interval, return the minimum number of the original interval required for this merge

For example

IntervalList: [-1, 9] [1, 10] [0, 3] [9,10] [3, 14] [2, 9] [10, 16]

Target interval: [2, 15]

we find that there are several ways to cover [2,15], such as:

[-1, 9] + [9,10] + [10, 16] or [1, 10] + [10, 16].

We want to merge the least number of ways, so here should return 2

- 0of 0 votes
Given a decendents of nodes, write an algorithm to find whether it is a tree or a graph?

- 0of 0 votes
Caeser;s Cipher is a very famous encryptiontechnique used in crptography.It is a type of substitution cipher in which each letter in the plaintext is replaced by letter some fixed number of positions down the alphabet.For example,with a shift of 3 ,D would be replaced bt G,E would become H,X would become A and so on.

Encryption of a letter x by a shift k can bedescribed mathematically as Ek(X)=(X+K)%26.

Given a plain text and it's corresponding ciphertext,output the minimum no negative value of shift that was used to encrypt the plaintext or else output -1 if it is no possible to obtain the given ciphertext from the given plaintext using caeser's cipher technique.

Input

The first line of the input contains Q,denoting the number of queries.

The next Q lines contain two strings s and t consisting of only uppercase letters

output::

For each test case,output a single non negative integer denoting the minimum value of shift that was used to encrypt the the plaintext or else print -1 if the answer does not exist.

Sample Input OUTPUT

2 3

ABC -1

DEF

AAA

PQR

- 0of 0 votes
count Number of balanced Binary Tree given Preorder Sequence length

- 0of 0 votes
Given an array arr and a number n, you have to find whether there exist a subset in arr whose sum is n. You have to print length of the subset.

1. There exists only one subset like that

2. All number in arr are positive

- 1of 1 vote
Find largest sub-array?

- 0of 0 votes
I have a file which has a number of 10 digit numerals and 10 digit alphanumeric characters. Write a UNIX basic command to print distinct 10 digit alphanumeric charters

Sample Input

1234567890

1234567890

123456789X

0974385495

Expected O/P

123456789X

- 0of 0 votes
Delete files of size more than 100mb in a folder which are older than 90 days.

- 0of 0 votes
Given a comma separated file print the last but one column of every line.

e.g:

a,b,c,d,e,f

1,2,3,4

w,x,y,z

output should be

e

3

y

- 0of 0 votes
A binary tree and a number, say k are given. Print every path in the tree with sum of the nodes in the path as k.(A path can start from any node and end at any node, i.e. they need not be root node and leaf node; and negative numbers can also be there in the tree)

- 1of 1 vote
Given an integer target and binary tree (not a binary search tree!) each of whose nodes contains an integer (which may be positive or negative), find the set of all subtrees whose sum equals the given target. The sum of a subtree is just the sum of the integers contained in its nodes. Note that the subtree does not have to contain all child nodes - it can be any set of connected nodes.

- 1of 1 vote
You are given an array A[] with n elements. You are given S[], E[] and H[] array with each M elements.

Apply an operation such that all the elements from A[ S[i] ] and A[ E[i] ] will be less than H[i].

Example :

given array A[] = [2,4,8,6,7]

S[0] = 1

E[0] = 4

H[0] = 5

So, after doing an operation, the resulting array is A[] = [ 2,4,5,5,5]

Thus, u need to do the same thing for all i.

After doing this, find out the maximum element in the array.

- 0of 0 votes
Print elements of a matrix in spiral form.

- 0of 0 votes
It was an over email interview:

Write a program that takes as input a sufficiently large text document (several are available online for testing; e.g. via Project Gutenberg), and produces as output (via stdout) an alphabetical listing of each unique word in the document (case insensitive and space separated, though be careful to consider hyphenated words), along with the lines from the input document that the word appears on. Each unique word (and the list of lines that it appears on) should be on a separate line in the output.

For example, taking the following text as input:

This is

some kind OF text it

Is an example of text

The following would be the output:

an 3

example 3

is 1 3

it 2

kind 2

of 2 3

some 2

text 2 3

this 1

- -2of 2 votes
C++ Questions

- -1of 3 votes
Find sum of n elements after kth smallest element in BST. Tree is very large, you are not allowed to traverse the tree.