Google Interview Questions

Founded by Larry Page and Sergey Brin in 1998, Google LLC is an American multinational technology company which specializes in services and products related to the Internet, for instance, cloud computing, online advertising technologies, a search engine, software, and hardware. Google is one of the Big Five companies in the United States Information Technology industry, along with Amazon, Apple, Microsoft, and Facebook. Google was reorganized as a wholly owned subsidiary of Alphabet Inc. in 2015. Sundar Pichai is the CEO (Chief Executive Officer) of both Google and Alphabet.

There have been a lot of factors that have accelerated the company's rapid growth since the incorporation has included products, acquisitions, and partnerships beyond Google's core search engine, that is, the Google Search. On the list of the most valuable brands, Google is ranked second by Forbes and fourth by Interbrand.

As we know that Google has a plethora of products to offer, I am sure that you are tempted to interview at Google and take a job! Their hiring process is a crucial part of their culture as they care deeply about their teams and the people who make them up. Building a more representative and inclusive workplace is the motive of Google’s hiring team, and that begins with hiring highly skilled people from various backgrounds. According to the Googlers, in order to truly build for everyone, a diversity of perspectives and experiences, and a fair hiring process is the first step in getting there.

Interview Process

1. Recruiter Connect: Recruiter can contact the candidate based on his/her profiles on Linkedin etc or if any of his/her known has referred him/her to the company. However, it’s always best to message the recruiters via linkedin and apply for the roles in the Career page of Google. If the candidate is good in DS & Algo skills it is highly recommended that he/she participate in Google Kickstart, this is Google’s hiring contest which happens 6 times in a year. If the performance in those competitions is good the recruiters will contact you easily.
2. Interview Rounds: Google has a total of 7 rounds. First two are telephonic interviews where the interviewer mostly asks one medium or two easy Algo DS problems to the candidate and the candidate has 45 minutes to solve the problems. However if the performance in Kickstart is good, these rounds are skipped and you directly move to the next rounds. Next we have 5 onsite interviews out of which 4 are Algo DS interviews and 1 is Googliness interview, Googliness interview is mostly a behavioral interview.
3. After Interviews: Once the interviews are over, the recruiter will contact you with the feedback of the interviews, if the performance is good and the interviews are cleared your profile goes to the different teams in Google for the team matching round. In the team matching round the team understands your work style and your interests and you can understand their requirements and the work expectations of the team.
4. Hired: Once the team and you both are comfortable and ready to start, the offer letter is prepared and shared with you by the recruiters and you are HIRED!

Interview Rounds

1. Telephonic Interviews (Two Rounds) These are two 45 minute interviews on the phone where the interviewer shares a Google Doc with the candidate and asks either a medium problem or two easy problems of Algorithms and DS. It is expected that the candidate first explains the solution of the problem to the interviewer and then codes the problem on google doc within the time of the interview. (Suggestion: Practice writing the code on google doc if you have any interview coming up as it is a different experience compared to writing the code in any text editor).
2. Algo DS Interviews (Three or Four Rounds) These are 45 minute interviews where the interviewer shares a Google Doc with the candidate and asks Medium to Hard problems of Algorithms and DS. It is expected that the candidate first explains the solution of the problem to the interviewer and then codes the problem on google doc within the time of the interview.
3. Googliness Interviews (One Round) This is a new interview which Google started in 2020. It’s mostly the behavioral interview to check the cultural fitness of the candidate in the company.

Gas Station

Problem Description

Given two integer arrays A and B of size N. There are N gas stations along a circular route, where the amount of gas at station i is A[i].

You have a car with an unlimited gas tank and it costs B[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.

Problem Constraints

1 <= |A| <= 5 * 105
|A| == |B|
0 <= Ai <= 5 * 103
0 <= Bi <= 5 * 103

Input Format

The first argument given is the integer array A. The second argument given is the integer array B.

Output Format

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

Example Input

A = [1, 2]
B = [2, 1]

Example Output

1

Example Explanation

If you start from index 0, you can fill in A[0] = 1 amount of gas.
Now your tank has 1 unit of gas. But you need B[0] = 2 gas to travel to station 1.

If you start from index 1, you can fill in A[1] = 2 amount of gas.
Now your tank has 2 units of gas. You need B[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 A[0] = 1 unit of additional gas, making your current gas = 2. It costs you B[0] = 2 to get to station 1, which you do and complete the circuit.

Majority Element

Problem Description

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.

Problem Constraints

1 <= |A| <= 106
1 <= Ai <= 109

Input Format

The first argument is an integer array A.

Output Format

Return the majority element.

Example Input

A = [2, 1, 2]

Example Output

2

Example Explanation

2 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 A, B, count number of unique ways in sequence A, to form a subsequence that is identical to the sequence B.

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

Input Format:

The first argument of input contains a string, A.
The second argument of input contains a string, B.

Output Format:

Return an integer representing the answer as described in the problem statement.

Constraints:

1 <= length(A), length(B) <= 700

Example :

Input 1:
    A = "abc"
    B = "abc"
    
Output 1:
    1

Explanation 1:
    Both the strings are equal.

Input 2:
    A = "rabbbit" 
    B = "rabbit"

Output 2:
    3

Explanation 2:
    These are the possible removals of characters:
        => A = "ra_bbit" 
        => A = "rab_bit" 
        => A = "rabb_it"
        
    Note: "_" marks the removed character.

Distinct Subsequences
Given two sequences A, B, count number of unique ways in sequence A, to form a subsequence that is identical to the sequence B.
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).
Input Format:
The first argument of input contains a string, A.
The second argument of input contains a string, B.
Output Format:
Return an integer representing the answer as described in the problem statement.
Constraints:
1 <= length(A), length(B) <= 700
Example :
Input 1:
    A = "abc"
    B = "abc"
    
Output 1:
    1

Explanation 1:
    Both the strings are equal.

Input 2:
    A = "rabbbit" 
    B = "rabbit"

Output 2:
    3

Explanation 2:
    These are the possible removals of characters:
        => A = "ra_bbit" 
        => A = "rab_bit" 
        => A = "rabb_it"
        
    Note: "_" marks the removed character.
Palindrome Partitioning II
Given a string A, partition A such that every substring of the partition is a palindrome.
Return the minimum cuts needed for a palindrome partitioning of A.

Input Format:
The first and the only argument contains the string A.
Output Format:
Return an integer, representing the answer as described in the problem statement.
Constraints:
1 <= length(A) <= 501
Examples:
Input 1:
    A = "aba"

Output 1:
    0

Explanation 1:
    "aba" is already a palindrome, so no cuts are needed.

Input 2:
    A = "aab"
    
Output 2:
    1

Explanation 2:
    Return 1 since the palindrome partitioning ["aa","b"] could be produced using 1 cut.
Min Jumps Array
Problem Description
 
 
Given an array of non-negative integers, A, of length N, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Return the minimum number of jumps required to reach the last index.
If it is not possible to reach the last index, return -1.

Problem Constraints
1 <= N <= 106
0 <= A[i] <= 50000

Input Format
The first and the only argument contains an integer array, A.

Output Format
Return an integer, representing the answer as described in the problem statement.

Example Input
Input 1:
A = [2, 1, 1]
Input 2:
A = [2, 3, 1, 1, 4]


Example Output
Output 1:
1
Output 1:
2


Example Explanation
Explanation 1:
The shortest way to reach index 2 is
    Index 0 -> Index 2
that requires only 1 jump.
Explanation 2:
The shortest way to reach index 4 is
    Index 0 -> Index 1 -> Index 4
that requires 2 jumps.
Edit Distance

Given two strings 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

Input Format:
The first argument of input contains a string, A.
The second argument of input contains a string, B.
Output Format:
Return an integer, representing the minimum number of steps required.
Constraints:
1 <= length(A), length(B) <= 450
Examples:
Input 1:
    A = "abad"
    B = "abac"

Output 1:
    1

Explanation 1:
    Operation 1: Replace d with c.

Input 2:
    A = "Anshuman"
    B = "Antihuman"

Output 2:
    2

Explanation 2:
    => Operation 1: Replace s with t.
    => Operation 2: Insert i.
Word Break
Problem Description
 
 
Given a string A and a dictionary of words B, determine if A can be segmented into a space-separated sequence of one or more dictionary words.

Problem Constraints
1 <= len(A) <= 6500
1 <= len(B) <= 10000
1 <= len(B[i]) <= 20

Input Format
The first argument is a string, A.
The second argument is an array of strings, B.

Output Format
Return 0 / 1 ( 0 for false, 1 for true ) for this problem.

Example Input
Input 1:
 A = "myinterviewtrainer",
B = ["trainer", "my", "interview"]
Input 2:
A = "a"
B = ["aaa"]

Example Output
Output 1:
1
Output 2:
0

Example Explanation
Explanation 1:
Return 1 ( corresponding to true ) because "myinterviewtrainer" can be segmented as "my interview trainer".
Explanation 2:
Return 0 ( corresponding to false ) because "a" cannot be segmented as "aaa".
Regular Expression II
Problem Description
 
 
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).

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

Problem Constraints
1 <= |A| <= 5 * 103
1 <= |B| <= 5 * 103

Input Format
The first argument is a string A.
The second argument is a string A.

Output Format
Return an integer, 0 / 1 ( 0 for false, 1 for true ) for this problem

Example Input
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
Interleaving Strings
Given A, B, C, find whether C is formed by the interleaving of A and B.
Input Format:*
The first argument of input contains a string, A.
The second argument of input contains a string, B.
The third argument of input contains a string, C.
Output Format:
Return an integer, 0 or 1:
    => 0 : False
    => 1 : True
Constraints:
1 <= length(A), length(B), length(C) <= 150
Examples:
Input 1:
    A = "aabcc"
    B = "dbbca"
    C = "aadbbcbcac"

Output 1:
    1
    
Explanation 1:
    "aa" (from A) + "dbbc" (from B) + "bc" (from A) + "a" (from B) + "c" (from A)

Input 2:
    A = "aabcc"
    B = "dbbca"
    C = "aadbbbaccc"

Output 2:
    0

Explanation 2:
    It is not possible to get C by interleaving A and B.
Puzzles
Daughters' Ages
Two MIT math grads bump into each other at Fairway on the upper west side. They haven’t seen each other in over 20 years.
The first grad says to the second: “how have you been?”
Second: “great! i got married and i have three daughters now”
First: “really? how old are they?”
Second: “well, the product of their ages is 72, and the sum of their ages is the same as the number on that building over there..”
First: “right, ok.. oh wait.. hmm, i still don’t know”
Second: “oh sorry, the oldest one just started to play the piano”
First: “wonderful! my oldest is the same age!”
How old are the daughters?

Respond with daughter ages sorted in ascending order and concatenated together. No spaces.
Divide the Cake

Consider a rectangular cake with a rectangular section (of any size or orientation) removed from it. Is it possible to divide the cake exactly in half with only one cut?
Only when the rectangular section passes through the centre
Only if the centre of both rectangles match
Only when rectangular section has axis parallel to the actual rectangle
Always possible

Eggs and Building
There is a building of 100 floors
If an egg drops from the Nth floor or above it will break. If it’s dropped from any floor below, it will not break. You’re given 2 eggs. Find N, while minimizing the number of drops for the worst case.
These are very strong eggs, because they can be dropped multiple times without breaking as long as they are dropped from floors below their “threshold” floor, floor N. But once an egg is dropped from a floor above it’s threshold floor, it will break.
Output the minimum number of drops required to figure out N.
Answer is a integer.  Just put the number without any decimal places if its an integer. If the answer is Infinity, output Infinity.
Feel free to get in touch with us if you have any questions
Storage Scalability
Design a distributed key value caching system, like Memcached or Redis.
Largest Distance between node
Problem Description
Given an arbitrary unweighted rooted tree which consists of N nodes.
The goal of the problem is to find largest distance between two nodes in a tree.
Distance between two nodes is a number of edges on a path between the nodes (there will be a unique path between any pair of nodes since it is a tree).
The nodes will be numbered 0 through N - 1.
The tree is given as an array A, there is an edge between nodes A[i] and i (0 <= i < N). Exactly one of the i's will have A[i] equal to -1, it will be root node.


Problem Constraints
1 <= N <= 40000

Input Format
First and only argument is an integer array A of size N.

Output Format
Return a single integer denoting the largest distance between two nodes in a tree.

Example Input
Input 1:
 A = [-1, 0, 0, 0, 3]


Example Output
Output 1:
 3


Example Explanation
Explanation 1:
 node 0 is the root and the whole tree looks like this: 
          0
       /  |  \
      1   2   3
               \
                4

 One of the longest path is 1 -> 0 -> 3 -> 4 and its length is 3, thus the answer is 3.
Word Search Board
Given a 2D board and a word, find if the word exists in the grid.
The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The cell itself does not count as an adjacent cell. 

The same letter cell may be used more than once.
Example :
Given board =
[
  ["ABCE"],
  ["SFCS"],
  ["ADEE"]
]
word = "ABCCED", -> returns 1,
word = "SEE", -> returns 1,
word = "ABCB", -> returns 1,
word = "ABFSAB" -> returns 1
word = "ABCD" -> returns 0
Note that 1 corresponds to true, and 0 corresponds to false.

Convert Sorted List To Binary Search Tree

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

A height balanced BST : a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

Example :

Given A : 1 -> 2 -> 3
A height balanced BST  :

      2
    /   \
   1     3

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 * 
 * typedef struct TreeNode treenode;
 * 
 * treenode* treenode_new(int val) {
 *     treenode* node = (treenode *) malloc(sizeof(treenode));
 *     node->val = val;
 *     node->left = NULL;
 *     node->right = NULL;
 *     return node;
 * }
 */
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 * 
 * typedef struct ListNode listnode;
 * 
 * listnode* listnode_new(int val) {
 *     listnode* node = (listnode *) malloc(sizeof(listnode));
 *     node->val = val;
 *     node->next = NULL;
 *     return node;
 * }
 */
/**
 * @input A : Head pointer of linked list 
 * 
 * @Output root pointer of tree.
 */
treenode* sortedListToBST(listnode* A) {
}

Edit Distance

Given two strings 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

Input Format:

The first argument of input contains a string, A.
The second argument of input contains a string, B.

Output Format:

Return an integer, representing the minimum number of steps required.

Constraints:

1 <= length(A), length(B) <= 450

Examples:

Input 1:
    A = "abad"
    B = "abac"

Output 1:
    1

Explanation 1:
    Operation 1: Replace d with c.

Input 2:
    A = "Anshuman"
    B = "Antihuman"

Output 2:
    2

Explanation 2:
    => Operation 1: Replace s with t.
    => Operation 2: Insert i.

Least Common Ancestor

Problem Description

Find the lowest common ancestor in an unordered binary tree given two values in the tree.

Lowest common ancestor: the lowest common ancestor (LCA) of two nodes v and w in a tree or directed acyclic graph (DAG) is the lowest (i.e. deepest) node that has both v and w as descendants.

Note:

• You are given 2 values. Find the lowest common ancestor of the two nodes represented by val1 and val2
• No guarantee that val1 and val2 exist in the tree. If one value doesn't exist in the tree then return -1.
• There are no duplicate values.
• You can use extra memory, and helper functions, and can modify the node struct but, you can't add a parent pointer.

Input Format

The first argument is a TreeNode A, pointing to the root of the binary tree.
The second argument is an integer B.
The third argument is an integer C.

Output Format

Return an integer, equal to the value of the LCA of B and C.

Example Input

        _______3______
       /              \
    ___5__          ___1__
   /      \        /      \
   6      _2_     0        8
         /   \
         7    4


B = 5
C = 1

Example Output

3

Example Explanation

        _______3______
       /              \
    ___5__          ___1__
   /      \        /      \
   6      _2_     0        8
         /   \
         7    4

For the above tree, the LCA of nodes 5 and 1 is 3.
Please note that LCA for nodes 5 and 4 is 5.

Rotate Matrix
Problem Description
 
 
You are given a N x N 2D matrix A representing an image.
Rotate the image by 90 degrees (clockwise).
You need to do this in place. Update the given matrix A.
Note: If you end up using an additional array, you will only receive a partial score.

Problem Constraints
1 <= N <= 1000

Input Format
First argument is a 2D matrix A of integers

Output Format
Rotate the given 2D matrix A.

Example Input
Input 1:
 [
    [1, 2],
    [3, 4]
 ]
Input 2:
 [
    [1]
 ]


Example Output
Output 1:
 [
    [3, 1],
    [4, 2]
 ]
Output 2:
 [
    [1]
 ]


Example Explanation
Explanation 1:
 After rotating the matrix by 90 degree:
 1 goes to 2, 2 goes to 4
 4 goes to 3, 3 goes to 1
Explanation 2:
 2D array remains the ssame as there is only element.

Longest Consecutive Sequence
Given an unsorted array of integers, find the length of the longest consecutive elements sequence.
Example: 

Given [100, 4, 200, 1, 3, 2],

The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.
Your algorithm should run in O(n) complexity.
Permutations
Given a collection of numbers, return all possible permutations.
Example:
[1,2,3] will have the following permutations:
[1,2,3]
[1,3,2]
[2,1,3] 
[2,3,1] 
[3,1,2] 
[3,2,1]
NOTE
No two entries in the permutation sequence should be the same.
For the purpose of this problem, assume that all the numbers in the collection are unique.
Warning : DO NOT USE LIBRARY FUNCTION FOR GENERATING PERMUTATIONS.

Example : next_permutations in C++ / itertools.permutations in python.

If you do, we will disqualify your submission retroactively and give you penalty points.
Largest Rectangle in Histogram
Problem Description
 
 
Given an array of integers A .
A represents a histogram i.e A[i] denotes height of the ith histogram's bar. Width of each bar is 1.
Find the area of the largest rectangle formed by the histogram.


Problem Constraints
1 <= |A| <= 100000
1 <= A[i] <= 1000000000


Input Format
The only argument given is the integer array A.

Output Format
Return the area of largest rectangle in the histogram.

Example Input
Input 1:
 A = [2, 1, 5, 6, 2, 3]
Input 2:
 A = [2]


Example Output
Output 1:
 10
Output 2:
 2


Example Explanation
Explanation 1:
The largest rectangle has area = 10 unit. Formed by A[3] to A[4].
Explanation 2:
Largest rectangle has area 2.
Insertion Sort List
Sort a linked list using insertion sort.
We have explained Insertion Sort at Slide 7 of Arrays
Insertion Sort Wiki has some details on Insertion Sort as well.
Example :
Input : 1 -> 3 -> 2

Return 1 -> 2 -> 3

Remove Duplicates From Sorted Array
Problem Description
 
 
Given a sorted array A consisting of duplicate elements.
Your task is to remove all the duplicates and return the length of the sorted array of distinct elements consisting of all distinct elements present in A.

Note: You need to update the elements of array A by removing all the duplicates
 

Problem Constraints
1 <= |A| <= 106
1 <= Ai <= 2 * 109

Input Format
First and only argurment containing the integer array A.


Output Format
Return a single integer, as per the problem given.

Example Input
Input 1:
A = [1, 1, 2]
Input 2:
A = [1, 2, 2, 3, 3]


Example Output
Output 1:
2
Output 2:
3


Example Explanation
Explanation 1:
Updated Array: [1, 2, X] after rearranging. Note that there could be any number in place of x since we dont need it.
We return 2 here.
Explanation 2:
Updated Array: [1, 2, 3, X, X] after rearranging duplicates of 2 and 3.
We return 3 from here.
Median of Array
There are two sorted arrays A and B of size m and n respectively.

Find the median of the two sorted arrays ( The median of the array formed by merging both arrays ).

The overall run time complexity should be O(log (m+n)).

NOTE: If the number of elements in the merged array is even, then the median is the average of n / 2 th and n/2 + 1th element. For example, if the array is [1 2 3 4], the median is (2 + 3) / 2.0 = 2.5 


Problem Constraints
0 <= |A| <= 106
0 <= |B| <= 106
1 <= |A| + |B| <= 2 * 106

Input Format
The first argument is an integer array A.
The second argument is an integer array B.

Output Format
Return a double value equal to the median.

Example Input
A : [1 4 5]
B : [2 3]

Example Output
3

Example Explanation
Merged A and B will be : [1, 2, 3, 4, 5]
Its median will be 3
Justified Text

Problem Description
 
 
Given an array of words and a length of L, format the text such that each line has exactly L characters and is fully (left and right) justified. You should pack your words in a greedy approach; that is, pack as many words as you can in each line.
 
Pad extra spaces ' ' when necessary so that each line has exactly L characters. Extra spaces between words should be distributed as evenly as possible. If the number of spaces on a line does not divide evenly between words, the empty slots on the left will be assigned more spaces than the slots on the right. For the last line of text, it should be left justified and no extra space is inserted between words.
Your program should return a list of strings, where each string represents a single line. 
Note: Each word is guaranteed not to exceed L in length.

Problem Constraints
0 <= |A| <= 1000
0 <= B <= 5 * 104

Input Format
The first argument is an array of strings A representing words.
The second argument is an integer B representing L.

Output Format
Return a list of strings, where each string represents a single line.

Example Input
A: ["This", "is", "an", "example", "of", "text", "justification."]
B: 16.

Example Output
[
   "This    is    an",
   "example  of text",
   "justification.  "
]

Example Explanation
Given words: ["This", "is", "an", "example", "of", "text", "justification."]
L: 16.


Return the formatted lines as:
[
   "This    is    an",
   "example  of text",
   "justification.  "
]
Remove Duplicates From Sorted Array
Given a sorted array A consisting of duplicate elements.
Your task is to remove all the duplicates and return the length of the sorted array of distinct elements consisting of all distinct elements present in A.

Note: You need to update the elements of array A by removing all the duplicates
 

Problem Constraints
1 <= |A| <= 106
1 <= Ai <= 2 * 109

Input Format
First and only argurment containing the integer array A.


Output Format
Return a single integer, as per the problem given.

Example Input
Input 1:
A = [1, 1, 2]
Input 2:
A = [1, 2, 2, 3, 3]


Example Output
Output 1:
2
Output 2:
3


Example Explanation
Explanation 1:
Updated Array: [1, 2, X] after rearranging. Note that there could be any number in place of x since we dont need it.
We return 2 here.
Explanation 2:
Updated Array: [1, 2, 3, X, X] after rearranging duplicates of 2 and 3.
We return 3 from here.
Merge Overlapping Intervals
Given a collection of intervals, merge all overlapping intervals.
For example:
Given [1,3],[2,6],[8,10],[15,18],
return [1,6],[8,10],[15,18].
Make sure the returned intervals are sorted.
Grid Unique Paths
A robot is located at the top-left corner of an A x B grid (marked ‘Start’ in the diagram below).
The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Finish’ in the diagram below).
How many possible unique paths are there?
Note: A and B will be such that the resulting answer fits in a 32 bit signed integer.
Example :
Input : A = 2, B = 2
Output : 2

2 possible routes : (0, 0) -> (0, 1) -> (1, 1) 
              OR  : (0, 0) -> (1, 0) -> (1, 1)
Merge Overlapping Intervals
Given a collection of intervals, merge all overlapping intervals.
For example:
Given [1,3],[2,6],[8,10],[15,18],
return [1,6],[8,10],[15,18].
Make sure the returned intervals are sorted.
Merge Overlapping Intervals
Given a collection of intervals, merge all overlapping intervals.
For example:
Given [1,3],[2,6],[8,10],[15,18],
return [1,6],[8,10],[15,18].
Make sure the returned intervals are sorted.