Oops!! It seems some javascript files did not load. Please hard reload(SHIFT + reload) your page.

Israel Tsadok

Sergey Kharagorgiev

What to expect at Google?

**2 Telephonic interviews**which focus on basic problem solving and data structures**2-4 Coding Onsite interviews**which involve whiteboarding solutions to slightly harder data structures / algorithmic problems. The lesser experienced you are, the more number of coding onsite interview rounds for you.**0-2 System Design Onsite interviews**which involve coming up with high level design architectures for real life products. The more experienced you are, the more number of these interviews you might face.

**Coding rounds :**Material in the programming section of InterviewBit is pretty comprehensive. For your reference, the section below has some of the questions which are frequently asked in Google's Interview. Make sure to try and solve most of them.**Design rounds :**InterviewBit System Design prep has you covered here. Make sure to go through some frequently asked interview problems listed on the page.**Cultural fit rounds :**In most cases, this should not be an issue. However, we have guidelines around how not to screw this up. Send us a mail at hello@interviewbit.com to get access to the guideline doc.

Solve Interview Problems asked at Google

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

Solve Now

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

Solve Now

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)
```

Solve Now

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.

Solve Now

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.

Solve Now

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`

.

Solve Now

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.

Solve Now

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

Solve Now

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

Solve Now

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

Solve Now