## Interview Questions

Sergey Kharagorgiev
What to expect at Google?

Be able to discuss the big-O complexity of your approaches. Don't forget to brush up on your data structures like lists, arrays, hash tables, hash maps, stacks, queues, graphs, trees, heaps. Also sorts, searches, and traversals(BFS, DFS). Also review recursion and iterative approaches.
Use the programming language you're best at. It's important to write your solution correctly and in time, so use the language you are most familiar with.
Find and fix the bugs by yourself: Don't wait for the interviewer to find them for you.
Use the hints you are given: Usually, the interviewer knows the question well enough to know which hints will help you next if you get stuck.

Gas Station

There are `N` gas stations along a circular route, where the amount of gas at station `i` is `gas[i]`.

You have a car with an unlimited gas tank and it costs `cost[i]` of gas to travel from station `i` to its next station `(i+1)`. You begin the journey with an empty tank at one of the gas stations.

Return the minimum starting gas station’s index if you can travel around the circuit once, otherwise return `-1`.

You can only travel in one direction. `i to i+1, i+2, ... n-1, 0, 1, 2..`
Completing the circuit means starting at `i` and ending up at `i` again.

Example :

``````Input :
Gas :   [1, 2]
Cost :  [2, 1]

Output : 1

If you start from index 0, you can fill in gas[0] = 1 amount of gas. Now your tank has 1 unit of gas. But you need cost[0] = 2 gas to travel to station 1.
If you start from index 1, you can fill in gas[1] = 2 amount of gas. Now your tank has 2 units of gas. You need cost[1] = 1 gas to get to station 0. So, you travel to station 0 and still have 1 unit of gas left over. You fill in gas[0] = 1 unit of additional gas, making your current gas = 2. It costs you cost[0] = 2 to get to station 1, which you do and complete the circuit.

``````

Majority Element

Given an array of size `n`, find the majority element. The majority element is the element that appears more than `floor(n/2)` times.

You may assume that the array is non-empty and the majority element always exist in the array.

Example :

``````Input : [2, 1, 2]
Return  : 2 which occurs 2 times which is greater than 3/2.
``````

Max Rectangle in Binary Matrix

Given a 2D binary matrix filled with `0`’s and `1`’s, find the largest rectangle containing all ones and return its area.

Bonus if you can solve it in O(n^2) or less.

Example :

``````A : [  1 1 1
0 1 1
1 0 0
]

Output : 4

As the max area rectangle is created by the 2x2 rectangle created by (0,1), (0,2), (1,1) and (1,2)

``````

Distinct Subsequences

Given two sequences S, T, count number of unique ways in sequence S, to form a subsequence that is identical to the sequence T.

Subsequence : A subsequence of a string is a new string which is formed from the original string by deleting some (can be none ) of the characters without disturbing the relative positions of the remaining characters. (ie, `"ACE"` is a subsequence of `"ABCDE"` while `"AEC"` is not).

Example :
``` S = "rabbbit" T = "rabbit" ```

Return `3`. And the formations as follows:

``````S1= "ra_bbit"
S2= "rab_bit"
S3="rabb_it"
``````

`"_"` marks the removed character.

Palindrome Partitioning II

Given a string s, partition s such that every substring of the partition is a palindrome.

Return the minimum cuts needed for a palindrome partitioning of s.

Example :
Given
`s = "aab"`,
Return `1` since the palindrome partitioning `["aa","b"]` could be produced using `1` cut.

Min Jumps Array

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Your goal is to reach the last index in the minimum number of jumps.

Example :
Given array `A = [2,3,1,1,4]`

The minimum number of jumps to reach the last index is `2`. (Jump 1 step from index 0 to 1, then 3 steps to the last index.)

If it is not possible to reach the end index, return `-1`.

Edit Distance

Given two words `A` and `B`, find the minimum number of steps required to convert `A` to `B`. (each operation is counted as 1 step.)

You have the following 3 operations permitted on a word:

• Insert a character
• Delete a character
• Replace a character

Example :
edit distance between
`"Anshuman"` and `"Antihuman"` is 2.

• Operation 1: Replace s with t.
• Operation 2: Insert i.

Word Break

Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

For example, given

``````s = "myinterviewtrainer",
dict = ["trainer", "my", "interview"].
``````

Return `1` ( corresponding to `true` ) because `"myinterviewtrainer"` can be segmented as `"my interview trainer"`.

Return `0 / 1` ( 0 for false, 1 for true ) for this problem

Regular Expression II

Implement regular expression matching with support for `'.'` and `'*'`.

`'.'` Matches any single character.
`'*'` Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

The function prototype should be:

``````int isMatch(const char *s, const char *p)
``````

Some examples:

``````isMatch("aa","a") → 0
isMatch("aa","aa") → 1
isMatch("aaa","aa") → 0
isMatch("aa", "a*") → 1
isMatch("aa", ".*") → 1
isMatch("ab", ".*") → 1
isMatch("aab", "c*a*b") → 1
``````

Return `0 / 1` ( 0 for false, 1 for true ) for this problem

Interleaving Strings

Given `s1`, `s2`, `s3`, find whether `s3` is formed by the interleaving of `s1` and `s2`.

Example,
Given:

``````s1 = "aabcc",
s2 = "dbbca",
``````

When `s3 = "aadbbcbcac"`, return `true`.
When `s3 = "aadbbbaccc"`, return `false`.

Return `0 / 1` ( 0 for false, 1 for true ) for this problem