Google Interview Questions
 0of 0 votes
Define a function that can detect whether the characters of a string can be shuffled without repeating same characters as one other's neighbors. E.g. :
apple >> alpep, so valid
a >> a, valid
aa >> aa, invalid/impossible
aab >> aba, valid
aaaabbcc >> acabacab, valid
etc.
You do not have to find one representation, just have to detect if it is possible or not!
 0of 0 votes

 0of 0 votes
find consecutive integers in a list that give you the biggest sum
Like for 2 5 1 7 3 it would be 5 1 7
 0of 0 votes
Write the function READ, which is passed two double pointers pointing to the head pointers of two linked lists.
One list will hold even integers, the other one will hold odd integers. READ reads a series of integers. It separates adds odd integers to the first list, and even ones to the second, all in sorted order.
 0of 0 votes
How do you design a system for very large graphs(does not fit in a single machine)?
 0of 0 votes
Implement a Qsort similar to the build in one in C, but use an insertion sort instead
void GoogleSort(void *ptr, int number, int SIZE, int (*functionp)(const void *, const void *)) {
}
 4of 4 votes
You are given a function bool rand_bit_p() that returns true with some unknown probability p and false with probability 1  p.
Write function rand_bit() using rand_bit_p that will return true and false with equal probability (that is, implement a fair coin, given unfair coin)
 1of 1 vote
How would you design Google Analytics (there are huge number of users and we need realtime analysis report)?
How would you detect trends?
 0of 0 votes
You have 10^9 user, 10^3 websites that users are subscribed to and 2000 servers. Some users will unsubscribe from certain websites. How would you architect this system to be scalable and performant?
 4of 4 votes
Given a sorted array of size N of int32, find an element that repeats > ceil(N / 2) times. Your algo may assume that there will be always such element. Space/time O(1).
Follow up question: Now element repeats > ceil(N / 4) times. Space/time O(1)
 6of 6 votes

 0of 2 votes
How many Fibonacci numbers exists less than a given number n.Can you find a function in terms of n , to get the number of fibonacci number less than n.
Example : n = 6
Answer: 6 as (0, 1, 1, 2, 3, 5)
 3of 3 votes
find the no of possible patterns in android lock screen. write a program to count them.
 1of 1 vote
Find if a given binary tree has duplicate sub trees or not.
(Two leaf nodes of a parent do not count as subtree)
 1of 1 vote
Have you ever faced a time when you felt a particlar code base or product was not ready to be released, if so what did you do and how did you work with the development team or stakeholder to make sure your views were heard
 0of 0 votes
What do you feel is the most important thing in keeping good relations within a developer community.
 0of 0 votes
How would you scale a developer community from 10 to 1000.
I asked a followup "In what capacity" the interviewer responded with "just how would you scale it"
 0of 0 votes
Given an array of words (i.e. ["ABCW", "BAZ", "FOO", "BAR", "XTFN", "ABCDEF"]), find the max value of length(s) * length(t), where s and t are words from the array. The catch here is that the two words cannot share any characters.
Assume that there are many words in the array (N words) and average length of word is M.
Answer for the example above is "ABCW" and "XTFN" as the result is 4 * 4 = 12.
"ABCW" and "ABCDEF" do not work since they share similar characters.
 1of 3 votes
Find the nth smallest multiple given a set of numbers. For example, set = {4, 6}, n = 6:
The sequence is:
4, 6, 8, 12, 16, 18, etc...
Answer is 18
 2of 4 votes
We have a long string. We label some substrings with tags.
 A tag entry is [startIndex, endIndex, tag].
 Query: 1 or more tags
 Output: all blocks/ranges with all queried tags.
Example tag entries:
[23, 72, 0] // label [23, 72) with tag 0
[34, 53, 1] // label [34, 53) with tag 1
[100, 128, 0]
Query and Output:
0 => [23, 72], [100, 128]
0,1 => [34,53] // [34, 53) matches both tag 0 and 1
Give an efficient algorithm. Please describe your algorithm before posting code.
**Edit**: To add some difficulties, partial overlap is treated the same as full overlap, ONLY the overlapped part matches both tags. E.g. if we have entries:
[23, 72, 0] // label [23, 72) with tag 0
[10, 53, 1] // label [34, 53) with tag 1
Query and Output:
0,1 => [23,53] // [23, 53) matches both tag 0 and 1
Minor detials: Note in the comments we used open range on the right, i.e. if the string named "str", [23, 72, 0] includes str[23] but NOT str[72]; and there's no overlap between the following entries:
[23, 72, 0]
[10, 23, 0]
 1of 1 vote
Write 2 functions to serialize and deserialize an array of strings. strings can contain any unicode character. Do not worry about string overflow.
 2of 2 votes
Given a long string s and short strings t1, t2, t3 (which can have different length) find the shortest substring of s which contains t1, t2 and t3.
 0of 0 votes
Implement an algorithm that takes a adjacency list and produces a topological sort of the vertices.
INPUT:
1 2
1 3
1 4
3 5
2 5
4 5
Returns:
1 2 3 4 5
 1of 1 vote
Validate whether given string is valid JSON fromat string or not.
I/P: {a:b}
O/P: Yes Valid JSON
I/P: {a:b, c:d}
O/P: Yes Valid JSON
I/P: {a:b,c:{e:f}}
O/P Yes Valid JSON
I/P: {a}
O/p: not a valid json
I/P: {{a}}
O/P: not valid JSON
 0of 0 votes
write a method that takes in 2 int arrays of any size and returns an array that calculates the sum of both.
for example, [1,2,3] and [2,3,4] will return [3,5,7]
Or [1,2,3] and [2,3,5,5] will return [2,4,7,8]
however, if it's like [9,9,2] and [0,1,3] you need to carry the sum so it returns as [1,0,0,5]
** SINGLE DIGIT ONLY
 0of 0 votes
Imagine you have a row of numbers like below(a traiangle) .By starting at the top of the triangle find the maximum number in each line and sum them up example below
5
9 6
4 6 8
8 7 15
Answer I.e. 5+9+8+7 = 29
writw a code to find the maximum total from top to bottom. Assume triangle can have at most 100000 rows.
Input Output specifications
Input Specification
A string of n numbers (where 0<=n<=10^10)
eg.5#9#6#4#6#8#0#7#1#5
Output Specification
A sum of the max numbers in each line (as string ) or Output invalid in case of invalid input/triangle
Examples
eg1.
Input :5#9#6#4#6#8#0#7#1#5
Output:29
eg 2 .
Input :5#9#6#4#6#8#0#7#1
Output:invalid
eg 2 .
Input :5#9##4#6#8#0#7#1
Output:invalid
 0of 0 votes
Given N balloons, if you burst ith balloon you get Ai−1∗Ai∗Ai+1 coins and then (i1)th and (i+1)th balloons become adjacent. Find maximum number of coins you can gather.
Assume that we have extra 1 at left most and right most positions. (don't take in answer just for boundary positions)
Hence if we have left or right boundary positions we multiply 1.
 2of 2 votes
We have an iterator class as below:
class CIterator { int Next(); //Returns the value of the next element in the iteration by advancing the iterator bool HasNext() const; //check whether any next element for the current iterator };
We need a CPeekIterator class which is having below functionalities
Class CPeekIterator { int Next (); //Same as CIterator does bool HasNext() const; //same as CIterator does int Peek(); // Returns the next element in the iteration without advancing the iterator };
Write the CPeekIterator class
 0of 0 votes
Write a bitmap class where we don’t have fixed size for the bitmap. Calculate the changed bits from previous instance to new instance in least iteration.
Realtime usage : In file systems we will scan only those parts changed from last save to new edit. At that time this bitmap should be used to scan the changed/added/removed parts.
 1of 1 vote
Google is conducting a contest where they display a special doodle to the user
submitting the billionth query of the day. Design a system to achieve this. (NOTE:
Google has thousands of servers and each query can hit a different server).
Optimise it. How will you handle server failures?