Google Interview Questions
- 1of 1 vote
AnswersEveryone knows that finding a loop in the single linked list is using runner and follower method. Could you provide mathematical proof of correctness for it and why it works. I said something like induction hypothesis. Someone help me with the correct answer.
- Madan November 27, 2013 in United States| Report Duplicate | Flag | PURGE
Google SDE-2 Algorithm - 0of 2 votes
AnswersHow will you find if a string is a substring of another string in O(n) complexity. For example, "tl" is substring of bottle.
- Madan November 26, 2013 in United States| Report Duplicate | Flag | PURGE
Google SDE-2 Algorithm - 3of 3 votes
Answerssuppose a string is consists of a, b, and c
- codingfunnyguy November 25, 2013 in United States
Now given a integer N, output the amount of all possible strings of length N that don't of have consecutive a,b,c.
e.g. given N=5, string bacca is invalid since the first 3 letters have consecutive a,b,c. and bbbbb is valid.| Report Duplicate | Flag | PURGE
Google Algorithm - 1of 1 vote
AnswersSuppose there were n numbers in an array S1, S2, S3, S4.......SN rearrange them in a such a way that they satisfy bellow property.
- Rahul Sharma November 24, 2013 in United States
S1<S2>S3<S4>......| Report Duplicate | Flag | PURGE
Google Intern - 8of 8 votes
AnswersQ: Design a component that will implement web browser history. the user goes to different site and once he press on history button you should display the last 5 (no duplicates allowed, and 5 can be any N later) if duplicates occur display the most recent one. so if user visit : G,A,B,C,A,Y and than press "history" we will display Y,A,C,B,G. and of course he can go later to two other websites and than press "history" we will show them than the previous 3.
- Dany November 21, 2013 in United States
A: I solved it with stack, list and hash table in O(n) but it was too complicated and I didn't like my solution. please suggest something simpler.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer - 3of 5 votes
Answersgiven a dictionary of wrods,find the pair of word with following property:
- haozyname November 19, 2013 in china
1,the two word don't have same letter.
2,the multiple of the two word's length is maximum.
i give a simple O(n*n*k)(k is the average length of word) method.but i think there will be better one .| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 4of 14 votes
AnswersGiven two aligned sequences `a` and `b`. Write a function "findCommon", that finds the longest substring of the longer sequence that align to the smaller sequence in such a way that the alignment length (matching length) can be maximized. Sequences initially were of different lengths but the smaller one is padded with hyphen ('-') after alignment to make it equal to the longer sequence. The length of longer sequence is known in advance (m, which is same for the smaller padded sequence). The output is always the subsequence of the longer string.
- mary.kindall November 19, 2013 in United States
The total number of such operations to be done is in billions.
findCommon(a, b, m)
Example 1:
a = ------bixg--
b = xxxxxxbi-gzz
m = 12
output: big
Example 2:
a = xxxxxxbxigxx
b = ------b-ig--
m = 12
output = bxig
Example 3:
a = bigxxxxxxxxx
b = bi-x--------
m = 12
output = bigx| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 4of 4 votes
AnswersGiven an array of pairs of the form <a, b>. We have to find a sub-array such that the 1st element in the pairs are in increasing order and the sum of 2nd element of the pairs in the sub-array is maximum possible
- geekofthegeeks November 15, 2013 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 5of 7 votes
AnswersGiven N strings, find the smallest string in lexicographic order which contains all the given strings as subsequences
- geekofthegeeks November 15, 2013 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 2of 4 votes
AnswersImplement HashTable in java , especially hash function that should take care of any type of keys. The key may be integer or String or Object. But based on that the hash function should find index in the hashArray
- sivaji8 November 15, 2013 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Data Structures - -4of 4 votes
AnswersImplement Array Class in java.
- sivaji8 November 15, 2013 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Data Structures - 2of 2 votes
AnswersSuppose I have some (lng, lat) coordinate. I also have a big list of ranges,
- Aasen November 12, 2013 in United States
[ { northeast: {lng, lat}, southwest: {lng, lat} } ... ]
How can I most efficiently determine which bucket the (lng, lat) point goes into?
Also, on a design perspective. Would it make more sense for the "list of ranges" to be on some database like mysql, monodb, or on something like memcached, redis?| Report Duplicate | Flag | PURGE
Google Software Engineer Intern - 6of 6 votes
AnswersYou visited a list of places recently, but you do not remember the
- UserOne November 05, 2013 in United States
order in which you visited them. You have with you the airplane
tickets that you used for travelling. Each ticket contains just the
start location and the end location. Can you reconstruct your journey?| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - -6of 8 votes
AnswersGiven two Btrees. these trees "may" have right and left branches swapped. Now compare it
- Bee November 03, 2013 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Trees and Graphs - 5of 7 votes
AnswersImplement below function.
int getRandom(int N, int K[])
Constraints:
->K is sorted and contains elements in range [0,N)
->Output should be a random number between [0,N) excuding elements from K
->probability of generated number should be 1/(N-K.length) and not 1/N
-->int uniform(int N) is given which returns random number [0,N) with 1/N probability for each number.
->No more than O(1) memory
->No more than O(N) time
Below is my solution but it uses O(N) space.
- G10 November 01, 2013 in United Statespublic int randomNumber(int N, int[] K) { // K is sorted //assumed size of K is less than N int remains[] = new int[N-K.length]; //i is index [0,N-1], j is an index of K, k is an index of remainings //Fill remaining array for (int i=0,j=0,k=0;i<N;i++){ if (i!=K[j]){ remainings[k++]=i; }else{ j++; } } int index = uniform(remainings.length); return remainings[index]; } Time complexity: O(N) Space Complexity: O(N)
| Report Duplicate | Flag | PURGE
Google SDE1 Algorithm - -3of 5 votes
AnswersTossing a coin ten times resulted in 8 heads and 2 tails. How would you analyze whether a coin is fair? What is the p-value?
- midtownguru November 01, 2013 in United States
In addition, more coins are added to this experiment. Now you have 10 coins. You toss each coin 10 times (100 tosses in total) and observe results. Would you modify your approach to the the way you test the fairness of coins?| Report Duplicate | Flag | PURGE
Google Research Scientist Probability - 1of 1 vote
AnswersFind numbers which are palindromic in both their decimal and octal representations
- geekofthegeeks November 01, 2013 in India| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 2of 2 votes
AnswersEngineers at Google have decided to call any integer (+ve, -ve or 0) that is divisible by at least one of the single digit primes (2, 3, 5, 7) as Walprimes. Thus -21, -30, 0, 5, 14 etc are Walprimes, while -121, 1, 143 etc. are not Walprimes.
- geekofthegeeks October 26, 2013 in India
Now, consider a n-digit integer d1d2d3..dn. Between any 2 consecutive digits you can place either a (+) sign, a (-) sign or nothing. So, there are 3n-1 different expressions that can be formed from it. Some of the expressions so formed may evaluate to a Walprime. For example, consider the 6 digit integer 123456: 1 + 234 - 5 + 6 = 236, which is a Walprime, but 123 + 4 - 56 = 71, which is not a Walprime.
Your task is to write a program to find the no. of expressions (out of the possible 3n-1 expressions) that evaluate to a Walprime, for a given input. Note that leading zeroes are valid. For example, if the input is 1202004, it can be split as 12 + 020 - 04 etc. Also, the input itself can contain leading zeroes.
Input format: (Read from stdin)
The first line of input contains a single integer 'T' denoting the no. of test cases.
Each of the following 'T' lines contain a single string 's' (of length 'n') denoting an input for which you need to find the no. of valid expressions evaluating to a Walprime.
Output format: (Write to stdout)
Output exactly 'T' integers (one per line), where the ith line denotes the no. of valid expressions that evaluate to a Walprime for the ith input string. Since the output can be large, print all the quantities modulo 1000000007.
Sample testcase:
Input:
2
011
12345
Output:
6
64
Explanation:
For the first test case, s = "011". There are 32 = 9 valid expressions that can be formed from this string, namely {0+11, 0-11, 0+1+1, 0+1-1, 0-1+1, 0-1-1, 01+1, 01-1, 011} . Out of these 9 expressions, only the following 6 of them evaluate to a Walprime: {0+1+1, 0+1-1, 0-1+1, 0-1-1, 01+1, 01-1}.
Constraints:
There are 3 data sets.
For the first data set (5 points) -
1
For the second data set (10 points) -
1
For the third data set (15 points) -
1| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 3of 11 votes
AnswersGiven a binary representation of an integer say 15 as 1111, find the maximum longest continous sequence of 0s. The twist is it needs to be done in log N. I could think of O(N) solution. but couldn't go for log(N).
- TapeRecordia October 24, 2013 in United States
For example. 10000101
the answer should be 4, because there are 4 continouos zeroes.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - -3of 3 votes
Answers4 individual numbers which could be permuted in 4 factorial ways. permutation of these 4 integers is an 0indexedarray consisting of 4 digits in some order when integers are different. the best permute of the 4 integers is by the following funciton func(summ) = abs(summ[0] - summ[1]) + abs(summ[1] - summ[2] + abs(summ[2] - summ[3])) that would give maximum value.
- TapeRecordia October 24, 2013 in United States
method signature
public int answer(int w, int x, int y, int z){
}
w = 5
x = 3
y = -1
z = 5
the sample permute wiht given numbers in the given function that would give maximum value is as follows.
for the
summ[0] = 5
summ[1] = -1
summ[2] = 5
summ[3] = 3
This should be done in O(1)time ans space complexity. My questions wordings may be confusing, but the function and sample data are perfectly correct.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 4of 6 votes
AnswersYou have two integer arrays. Treat these arrays as if they were big numbers, with one digit in each slot. Perform addition on these two arrays and store the results in a new array.
- Aasen October 24, 2013 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer Intern Algorithm - 3of 13 votes
AnswersIn a language, there are only 4 characters ‘h’, ‘i’,’r’, ‘e’. and we have to write a function which takes a string as input and returns whether the given input string is a “valid word” or not.
- hugakkahuga October 23, 2013 in India
Definition of valid word :
1. A given word is a valid word if it is of the form h^n i^n r^n e^n where n >=1. (eg: hhiirree)
2. Valid words has concatenation property i.e. if w1 and w2 are valid words w1w2 is also a valid word.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 0of 0 votes
AnswersSuppose the sub-requests can be queued at each server, and the servers are running all the time. Discuss feasible on-line algorithms that can achieve sub-optimal solutions with N ~ 10000.
- wayne October 23, 2013 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - -5of 5 votes
AnswersWhat is the in order successor of 6 in the given BST? (Ah! This is not an assignment. I am a working professional).
- Gaile October 22, 2013 in United States
4
2 6
1 3 5
4.5 5.5
2 is left child of 4 and 6 is right child of 4.
1 is left child of 2 and 3 is right child of 3.
5 is left child of 6.
4.5 is left child of 5 and 5.5 is right child of 5.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 2of 10 votes
AnswersHow many times “Hello World” is printed by following program?
- whatsmyname1993 October 22, 2013 in India
int main()
{
if(fork() && fork())
{
fork();
}
if(fork() || fork())
{
fork();
}
printf(“Hello world”);
return 0;
}
a. 16
b. 20
c. 24
d. 64| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Operating System - 0of 6 votes
AnswersHow to find if a number is power of 4 in O(loglogn).
- AVK October 21, 2013 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer - -1of 5 votes
AnswersFind if 2 lists of rectangle are exactly equal. How would you sort the lists?
- chandeepsingh85 October 21, 2013 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Graphics - 5of 9 votes
AnswersQ: Given a sorted 2D N x N array (where array[i][j] < array[i][j+1] and array[i][j] < array[i+1][j]), can you write a function that converts this to a sorted 1D array?
- pdoggeth October 18, 2013 in United States
The obvious and naive way that I thought of was to convert the entire array into a 1D and do a mergesort on it, but there must be a better way than that. I'm wondering what the better and more efficient way is.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - -9of 9 votes
AnswersAn arraylist containing datatype studentsScores are given where studentId, and results are twostates of this datatype. Each student takes more than 10 exams. We need to return the averages score of each student as a Map<student, average score> where the average score is calculated by taking the average of top 5 exams of a student.
- sivaji8 October 08, 2013 in United States
First we iterate the arraylist and create another Map<Integer, ArrayList<>> where the inner ArrayList has values of test scores. Iterating the arrayList to find avergae score and adding it to the another Map<student, averageScore>. What is the complexity of this?| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer - 8of 10 votes
AnswersComplete the below function which takes an arraylist and displays the list in the expected output
- AP October 07, 2013 in United States
public class TreePrinter {
public static void printTree(Iterable<Relation> rs) {
// your code
}
}
public static class Relation {
String parent;
String child;
public Relation(String parent, String child) { ... }
}
}
Example input:
List<Relation> input = newArrayList();
input.add(new Relation(“animal”, “mammal”));
input.add(new Relation(“animal”, “bird”));
input.add(new Relation(“lifeform”, “animal”));
input.add(new Relation(“cat”, “lion”));
input.add(new Relation(“mammal”, “cat”));
input.add(new Relation(“animal”, “fish”));
TreePrinter.printTree(input);
Expected output:
line 1: lifeform
line 2: animal
line 3: mammal
line 4: cat
line 5: lion
line 6: bird
line 7: fish| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Data Structures