## Google Interview Questions

- 0of 0 votes
Give N socks, there is no guarantee that each can be paired, socks two colors, black and white, you need to pair them

- 0of 0 votes
css color format # abcdef, another abbreviated color format # rgb

(Converted to the previous format, ie, #rrggbb.) Now give your #abcdef, the first color format, to find the two least different colors, #rgb.

- 0of 0 votes
Google Fucked up question.

Given a random list of appointments (Start Date , End Date). Find all the appointments that are colliding.

This pretty easy looking question screwed me up today.There are tons of edge cases, I couldn't complete em all and 45 minutes pass like 15 minutes while explaining and coding same time.

- 0of 0 votes
Given list of edge in the graph, find the number of reversed pairs,(1,2)

and (2,1) are such pair. Follow up: How to implement the distributed version.

- 0of 0 votes
Implement a function that takes two strings, s and x, as arguments and finds the first occurrence of the string x in s. The function should return an integer indicating the index in s of the first occurrence of x. If there are no occurrences of x in s, return -1.

Example:

For s = "AGoogleInterviewIsAwesome" and x = "IA", the output should be

strstr(s, x) = -1;

For s = "AGoogleIsAwesome" and x = "IsA", the output should be

strstr(s, x) = 10.

Apparently, my solution was not efficient enough with string lengths that are 2000+:`int findFirstSubstringOccurrence(String s, String x) { int sLen = s.length(); int xLen = x.length(); int tracker = 0; if (sLen == xLen) { if (s.equals(x)) { return 0; } else { return -1; } } else { if (xLen >= 1) { for (int index = 0; index < sLen; index++) { if (s.charAt(index) == x.charAt(tracker)) { tracker++; if (tracker == xLen) { return index - (xLen - 1); } } else { index -= tracker; tracker = 0; } } } } return -1; }`

- 0of 0 votes
An n * m matrix represents an array of computers, giving you a List <int []> that represents the coordinates of the broken computer.

Now we start from (0,0) repair computer requirements:

1. You must finish all the broken computers in the current line to get to the next line

2. To go to the next line, the mechanic must first return to the far left or right of this line

And then find repair each computer order that has the minimum access distance,

- 0of 0 votes
A robot can only be moved one step to the right (x + 1) at a time while moving upward or downward or horizontally (y-1, y + 1, y) , given the starting and ending positions, and a series of points must pass, ask how many kinds of ways from start to end.

- 0of 0 votes
Find if the shorter string is a subsequence of the longer string

Output the second index corresponding to the first one, requiring output only If there is only one match, and false if there is more than one pair

a b c d e f g, a b -> [0,1]

a b b c, ab c -> False

- 0of 0 votes
To several bus lines, each line is a two-way line, such as:

0: A <-> B <-> D

1: C <-> D

give you a start and end, find the path through the least station. followup

Asked the least transfer case

- 0of 0 votes
Determine whether the inorder of n binary trees is the same

- 0of 0 votes
Give you a csv file There are three columns are id, parent, weight Then give you a class Node which has these three fields

But you also have the option of adding more fields for you to print out all the node's subwebs.

The definition of subweight is the sum of the node's weight plus the subweight of his children.

- 0of 0 votes
Give a chessboard, check if a group of white chesses are surrounded by all black chesses.

- 0of 0 votes
Given a list of relationship of report

A reported to D, D reported to Z, who are reported to Z

- 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?

- 2of 2 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"

- 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.

- 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
/**

*

* 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
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 -> ""

- 2of 2 votes
Minimum number of swaps of chars in only one string to make two strings the same

- 0of 0 votes
`Matrix conversion problem. For example, give a matrix a: 1, b: 2. b: 2, c: 3 Then converted into a, b, c 1, 2, . ., 2,3`

- 0of 0 votes
Implement a grep-like function. For example

[A1 + A2, B1 + B2, C1], grep (A = A1), is to return the result that contains A1,

For example, [A1, B1, C1], [A1, B2, C1].

More tricky can be grep (A = A1, A2, B = B1), so that is included (A1 || A2) & B1.