## Recent Interview Questions

- 0of 0 votes
Give the structure of a directed graph

START -> a -> b -> c -> END

If a word can start from start and end at END, then we think the word is in this diagram

For example, the string "abc" is consistent, but "ab" does not match,

Although "ab" is also inside the graph, b's next is "c" instead of END, so it's not legal word

(Note: each node can have more than one next)

1. According to the problem, design the data structure

Write a function, input is START and a string, to determine whether the string is a valid word

3. follow up, if the graph has cycle, how to do?

4. If the graph has repeated characters how to do?

- 0of 0 votes
Javascript solution for this question???

Given a list of characters, write a function to output a list of length of minimum non overlapping subsequences that can partition the input list.

For example:

Input : [a,b,c]

Output: [1,1,1]

Explanation: There are no repeated characters.

Input : [a,b,c,a]

Output: [4]

Explanation: The 'a' is repeated so one subsequence is between a to last a.

Input : [a,b,c,b,a,e,b,a,d,f,g,d,f,i,f,k,l,m,n,m,l]

Output: [8,7,6]

Explanation: max length from 1st 'a' to last 'a' is 8.

1st 'f' to last is 6 adding d to it = 7

so on

- 3of 3 votes
Decompress string - string (s) followed by {n} denotes s repeating n times

"a(b(c){2}){2}d" decompresses to "abccbccd"

"((x){3}(y){2}z){2}" decompresses to "xxxyyzxxxyyz"

- 0of 0 votes
Design a system that works like the you see on Amazon search - lets say you enter 'women's sandals'. What happens in the background? Explain all that you can think of.

- 0of 0 votes
Given a Binary string of 0s and 1s, and k, Find the number of different ways to get longest continuous streak of 1s. You can flip any k number of 0s to 1s.

Example:

1)Stirng is S=1010101, K=1

Result=3

1)Stirng is S=01010, K=3

Result=1

- 1of 1 vote
Write a function that takes two numbers as strings and returns the result as a string:

mul(l string, r string) : string

Assume the numbers might be too large to be parsed into a variable of any numeric type the language has.

- -2of 2 votes
How to bring back ex lost love back with in 24 hours

- 0of 0 votes
how to check is a small matrix appear in a big matrix

boolean isSubmatrix(int[][] small, int[][] big)

- 0of 0 votes
You have to cut a wood stick into pieces. The most affordable company, The Analog Cutting Machinery,

Inc. (ACM), charges money according to the length of the stick being cut. Their procedure of work

requires that they only make one cut at a time.

It is easy to notice that different selections in the order of cutting can led to different prices. For

example, consider a stick of length 10 meters that has to be cut at 2, 4 and 7 meters from one end.

There are several choices. One can be cutting first at 2, then at 4, then at 7. This leads to a price

of 10 + 8 + 6 = 24 because the first stick was of 10 meters, the resulting of 8 and the last one of 6.

Another choice could be cutting at 4, then at 2, then at 7. This would lead to a price of 10 + 4 + 6 =

20, which is a better price.

Your boss trusts your computer abilities to find out the minimum cost for cutting a given stick.

- 0of 0 votes
Given an aray with ['a1', 'a2', .....'aN', 'b1', 'b2', ....'bN', 'c1', 'c2', .....'cN'],

stagger the subarrays so it becomes ['a1', 'b1', 'c1', 'a2', 'b2', 'c2', ...'aN', 'bN', 'cN']. The optimal solution requires linear-time

sorting and a constant space complexity.

- 0of 0 votes
How to design a spreadsheet program? How do you know to update a field after another

field was changed that it depended on?

- 0of 0 votes
Given a set of points in the 2D coordinate system, find the radius of the

smallest circle which encompasses

all the given points

- 0of 0 votes
Try to come up with a combination of two data structures to implement a

data structure that supports search,

delete in O(1) time and insert in O(n) time.Try to come up with a combination of two data structures to implement a

data structure that supports search,

delete in O(1) time and insert in O(n) time.

- 0of 0 votes
You are given an integer N,print N+1 lines in a following manner

case 1: N=3 then the pattern would be

333

313

323

333

case 2: N=4 then the pattern would be

44444

44144

44244

44344

44444

- 0of 0 votes
What is the greatest common factor of all integers of the form p^4 + 1where is a prime number greater than 5?

- 0of 0 votes
A king gathers all the men in the kingdom who are to be put to death for their crimes, but because of his mercy, he will pardon one. He gathers the men into a circle and gives the sword to one man. The man kills the man to his left, and gives the sword to the man to the dead man's left. The last man alive is pardoned.

With 5 men, the 3rd is the last man alive.

Write a program that accepts a single parameter: a number N that represents the number of criminals to start with. The program should output the number of the last two men alive.

Example #1: myProgram 5

would output:

5, 3

Example #2: myProgram 7

would output:

3, 7

- 0of 0 votes
It was asked in Chargebee off campus interview. Needed solution for this problem in java

Given a string say s and k denotes the number of commas and the output should be like when you insert the comma in the string at different places and find the maximum number.

Test case 1

say s = 999 and k = 1 so the choice would be 9,99 or 99,9 in either case the maximum number is 99

Test case 2

say s=999 and k =2 so the choice will be like 9,9,9 so output will be 9

Test case 3

say s = 857 and k = 1 the choice would be 85,7 or 8,57 so the output will be like 85

- 0of 0 votes
If you are able to find the bug in production but not in the test build, how will you test it so the bug is found in the test build?

- 0of 0 votes
/**

*

* Google OnSite Round 3

*

* Data structure for Task Dependency

* A task can start only after all its pre-requisites are done

*

* Code the methods addTask(preRequisiteTask, dependentTask)

* and

* getExecutionSequence()

*

*/

- 0of 0 votes
/**

*

* Google OnSite Round 2

*

* Input is an integer array A

* Return an array B such that B[i] = product of all elements of A except A[i]

*

*/

- 0of 0 votes
/**

*

* Google Telephonic Round 2

*

* Given any uppercase string. Report the starting index at which any valid permutation of

* ABCDEF starts. If not found, then report -1.

* Possible permutations of ABCDEF are ABCDFE, BCDAFE, FEDCAB etc (a total of 6! = 720 permutations)

*

*/

- 0of 0 votes
/**

*

* Google Telephonic Round 3

* Find the sum of all nodes stored in a tree

*

*/

- 0of 0 votes
/**

*

* Google Telephonic Round 3

*

* Convert an integer to base-3 equivalent

*

*/

- 0of 0 votes
/**

*

* Google Telephonic Round 1

*

* Given two strings - S1 and S2.

* Arrange the characters of S1 in same alphabetical order as the characters of S2.

* If a character of S1 is not present in S2 - such characters should come at the end of

* the result string, but make sure to retain the order of such characters

* Case sensitivity is irrelevant

* e.g. S1 = "Google", S2 = "dog"

* Output = "ooggle"

*

* e.g. S1 = "abcdedadf", S2 = "cae"

* Output = "caaebdddf"

*

*/

- 0of 0 votes
Company S has developed an industrial endoscope available to explore inner part of the decrepit water pipes. It is possible to explore the inner part of the pipes putting the endoscope in a certain part of the pipe. The endoscope can be moved in the pipe only. Meanwhile, when the pipes are connected to each other, if the length of the endoscope is long enough to explore ,then it is able to inspect the connected pipes. However, we cannot observe every pipe because the length of endoscope is limited.

When the map of the ground water pipe, the location where the endoscope to out in, and the length of the endoscope is given, calculate the number of pipe which are available to explore. Length of endoscope means the range upto which endoscope can explore. There are seven kind of pipes, and description for each pipe are shown below:

S.No Pipe Connected to

1 Up, Down, Left, Right

2 Up, Down

3 Left, Right

4 Up, Right

5 Down, Right

6 Down, Left

7 Up, Left

When the map of the ground water pipe, the location where the endoscope to out in, and the length of the endoscope is given, calculate the number of pipe which are available to explore. Length of endoscope means the range upto which endoscope can explore.

Input

In the first line, T, the number of total test cases is given. From the second line, T test cases are given. In the first line of each test case, N, the height of the map of the ground water pipes, M, the width, R, the vertical location of the water pipe where to put in the endoscope, C, the horizontal location of it, and the length of the endoscope L are given. In the following N lines information of the map of ground water pipe is given. Each line has M numbers. Each number (from 1 to 7) means the type of water pipe for that point. 0 means there is no water pipe buried in that place.

Output

Print the respective answer for T test cases in total for T lines. The answer is the number of water pipes which is available to observe using the endoscope.

Constraints

1≤ T ≤100

1≤ N, M ≤50

0≤ X < N

0≤ Y < M

1≤ L ≤ 20

- 0of 0 votes
Write a program to print all the columns of a binary tree from left to right and top down.

- 0of 0 votes
A sequence of strings, printed first by column, on a screen of width K,

Requires the first column of the same column by column alignment,

At least one character interval between columns and columns,

Ask how many lines at least?

such as:

The string sequence is {"abc", "de", "fghij", "k", "lmno", "p"}

The screen width is 10

The answer is at least 3 lines

abc k

de lmno

fghij p

- 0of 0 votes
Give a decimal number, such as 123. Asking a total of smaller num than 123 made up by 1 and 0 composed of decimal numbers.

111, 110, 101, 100, 11, 10, 1, 0.

- 0of 0 votes
To a word, and a map, map which is a word, ask this if a word is smash able? That is, you can smash one letter each time, and the rest of the letters can form a single word (the new word is still in the map) until it is completely hit.

For example: sprint -> print -> pint -> pit -> it -> i -> ""

- 0of 0 votes
Given list of strings like “ crane, drain, refrain” and a pattern such as *an*

where * can match any number of chracters.

Return the matching word in an efficient manner.

Answer to above question : crane