Google Interview Questions
- 6of 8 votes
AnswersGiven a NxN matrix which contains all distinct 1 to n^2 numbers, write code to print sequence of increasing adjacent sequential numbers.
- talktomenow July 14, 2014 in United States
ex:
1 5 9
2 3 8
4 6 7
should print
6 7 8 9| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 6of 8 votes
AnswersGiven an unsorted array of natural numbers. Where numbers repeat in array. Out put numbers in the order of frequency. Where number of out put is passed as parameter.
- dreamchaser1984 March 25, 2015 in United States
For Ex:
Array -> [0, 0, 100, 3, 5, 4, 6, 4, 2, 100, 2, 100]
n -> 2
Out put -> [100, 0] or [100, 2]
Since 100 is repeated 3 times and 0, 2 is repeated 2 times, out put up to 2 most frequent elements, program should out put either 100, 0 or 100, 2| Report Duplicate | Flag | PURGE
Google Principal Software Engineer Algorithm - 6of 6 votes
AnswersThe input is a sequence x1,x2,...,xn of integers in an arbitrary order, and another sequence
- Coder April 17, 2014 in United States
a1,a2,..,an of distinct integers from 1 to n (namely a1,a2,...,an is a permutation of
1, 2,..., n). Both sequences are given as arrays. Design an 0(n logn) algorithm to order
the first sequence according to the order imposed by the permutation. In other words, for
each i, Xi should appear in the position given in ai. For example, if x = 17, 5, 1,9, and a =
3, 2, 4, 1, then the outcome should be x = 9, 5, 17, 1. The algorithm should be in-place, so
you cannot use an additional array.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Arrays - 6of 6 votes
AnswersIn a certain language which has same alphabets as in english language (ie. a-z), but the order of the alphabets is different (for eg 's' is the first character, 'g' is second, and likewise). Given a dictionary of this new language (which has words arranged according to new alphabetical order), FInd out the order of alphabets in this language.
- sgarg June 09, 2013 in India| Report Duplicate | Flag | PURGE
Amazon Google SDE1 Software Engineer / Developer SDE-2 Algorithm - 6of 6 votes
AnswersYou are given a matrix with N rows and N columns. Elements in matrix can be either 1 or 0. Each row and column of matrix is sorted in ascending order.
Find number of 0-s in the given matrix.
Example:0 0 1 0 1 1 1 1 1 Answer: 3 0 0 0 0 Answer: 4
Update: Expected complexity is O(log(N)). The best I've seen in comments is still O(N).
- emb June 26, 2016 in United States
Update2: Alright, guys, sorry for a bit of trolling. Obviously this is not possible to do faster than O(N). Here is why: take a diagonal (N, 1), (N-1, 2), ... (1, N). Suppose input matrix has all 0's above this diagonal and all 1's under this diagonal. So only diagonal elements vary. Clearly, diagonal elements do not depend on each other. So we have to analyze each diagonal element which is O(N).
Nice job, @gen-y-s :)| Report Duplicate | Flag | PURGE
Google Software Developer Algorithm - 6of 6 votes
AnswersGiven an array of elements, return an array of values pertaining to how many elements are greater than that element remaining in the array.
- PradeepN October 27, 2015 in United States
Brute force is obvious, but must be done faster than O(n^2)
Ex. [3,4,5,9,2,1, 3]
Return [3, 2, 1, 0, 1, 1, 0]
First element is 3 because 3<4,5,9. Second element is 2 because 4< 5,9 etc| Report Duplicate | Flag | PURGE
Google Algorithm - 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 6 votes
AnswersGiven 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).
- emb January 18, 2016 in United States
Follow up question: Now element repeats > ceil(N / 4) times. Space/time O(1)| Report Duplicate | Flag | PURGE
Google Intern - 6of 6 votes
AnswersPost order traversal for an N-ary tree iterative way.
- hm September 14, 2015 in United States
Given,
struct Node {
int val;
vector<Node*> children;
};
Without modifying original structure.| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm C++ Trees and Graphs - 6of 6 votes
AnswersPaper Cut into Minimum Number of Squares
- ajay.raj March 02, 2017 in United States
Given a paper of size A x B. Task is to cut the paper into squares of any size. Find the minimum number of squares that can be cut from the paper.
Examples:
Input : 13 x 29
Output : 9
Explanation :
2 (squares of size 13x13) +
4 (squares of size 3x3) +
3 (squares of size 1x1)=9
Input : 4 x 5
Output : 5
Explanation :
1 (squares of size 4x4) +
4 (squares of size 1x1)
geeksforgeeks provides a solution, but it is not right
http://www.geeksforgeeks.org/paper-cut-minimum-number-squares/| Report Duplicate | Flag | PURGE
Google - 6of 6 votes
Answers5th Round
- aonecoding April 13, 2017 in United States
Open-ended question What happens when you type a url in the browser and hit enter?
Second question Given an array of integers, print all the numbers that meet the following requirement - when the number is greater than every number on its left and smaller than every number on the right.| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 6of 6 votes
AnswersGiven an array of integers, find out how many unique BST can be generated from the array.
- kieth October 07, 2018 in United States| Report Duplicate | Flag | PURGE
Google SDE1 Trees and Graphs - 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 - 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 - 5of 7 votes
AnswersGiven the English alphabet, 'a' through 'z' (lowercase), and an imaginary onscreen keyboard with the letters laid out in 6 rows and 5 columns:
a b c d e f g h i j k l m n o p q r s t u v w x y z
Using a remote control - (up - 'u', down 'd', left 'l', right 'r' and enter '!'), write a function that given a word will produce the sequence of key presses required to type out the word on the onscreen keyboard. The function should return the sequence string.
- superduper March 01, 2013 in United States
NOTE: This was an actual question. I didn't pull this from TopCoder.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 5of 7 votes
AnswersInput - array of integers size N, integer Threshold. Output - the number of pairs (x, y) of distinct elements with condition x + y <= Threshold. Is that possible to implement it with O(n) ?
- anonymous October 04, 2013 in United States| Report Duplicate | Flag | PURGE
Google Java Developer - 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 - 5of 5 votes
AnswersGiven a N*N Matrix.
- 646 November 23, 2010
All rows are sorted, and all columns are sorted.
Find the Kth Largest element of the matrix.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 5of 5 votes
AnswersThree strings say A,B,C are given to you. Check weather 3rd string is interleaved from string A and B.
- learn August 27, 2012 in United States
Ex: A="abcd" B="xyz" C="axybczd". answer is yes. o(n)| Report Duplicate | Flag | PURGE
Google - 5of 5 votes
AnswersGiven two sorted array in ascending order with same length N, calculate the first K min a[i]+b[j]. time complexty O(N).
- mario87 December 18, 2013 in United States
some misunderstood first K, to put it straight, to find the Kth min, not the first min| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 5of 5 votes
AnswersGiven a source string and a destination string write a program to display sequence of strings to travel from source to destination. Rules for traversing:
- Dee November 06, 2012 in United States
1. You can only change one character at a time
2. Any resulting word has to be a valid word from dictionary
Example: Given source word CAT and destination word DOG , one of the valid sequence would be
CAT -> COT -> DOT -> DOG
Another valid sequence can be
CAT -> COT - > COG -> DOG
One character can change at one time and every resulting word has be a valid word from dictionary| Report Duplicate | Flag | PURGE
Google Site Reliability Engineer - 5of 5 votes
AnswersGiven a number "n", find the least number of perfect square numbers sum needed to get "n"
- tazo March 12, 2015 in United States
Example:
n=12, return 3 (4 + 4 + 4) = (2^2 + 2^2 + 2^2) NOT (3^2 + 1 + 1 + 1)
n = 6, return 3 (4 + 1 + 1) = (2^2 + 1^2 + 1^2)| Report Duplicate | Flag | PURGE
Google Dynamic Programming - 5of 5 votes
AnswersGiven a array of integers , find 3 indexes i,j,k such that, i<j<k and a[i] < a[j] < a[k]. Best possible is a O(n) algorithm.
- kingKode October 26, 2012 in India| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 5of 5 votes
AnswersFind whether string S is periodic.
- aonecoding4 March 01, 2019 in United States
Periodic indicates S = nP.
e.g.
S = "ababab", then n = 3, and P = "ab"
S = "xxxxxx", then n = 1, and P = "x"
S = "aabbaaabba", then n = 2, and P = "aabba"
Given string S, find out the P (repetitive pattern) of S.| Report Duplicate | Flag | PURGE
Google Software Engineer - 5of 5 votes
AnswersGiven a set of numbers, find the longest subset with consecutive numbers be it any order.
- anonymous June 14, 2013 in India
Input:
S = { 5, 1, 9, 3, 8, 20, 4, 10, 2, 11, 3}
we have 2 consecutive sets
s1 = {1, 2, 3, 4, 5}
s2 = { 8, 9, 10, 11}
Ans.
s1 = {1, 2, 3, 4, 5}| Report Duplicate | Flag | PURGE
Google Applications Developer Algorithm - 5of 5 votes
AnswersGiven two strings .Print all the interleavings of the two strings.
- grave July 10, 2012 in India
Interleaving means that the if B comes after A .It should also come after A in the interleaved string.
ex-
AB and CD
ABCD
ACBD
ACDB
CABD
CADB
CDAB| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm String Manipulation - 5of 5 votes
AnswersYou are given a function bool rand_bit_p() that returns true with some unknown probability p and false with probability 1 - p.
- emb January 24, 2016 in United States
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)| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 5of 5 votes
AnswersGiven a prime set, we call "prime expressible" if a number can be factorized only using given prime numbers. Find n-th big expressible number.
- pandacoder October 30, 2015 in United States
E.g., prime set = {2, 3}
expressible number = {1,2,3,4,6,8, 9, 12...}
non-expressible number = {5, 10... }
The primes in the prime set are ordered in an increasing order, and can include a prime < 10^4 (don't remember the exact range), and n can also be as large as 1-10^6.| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 5of 5 votes
AnswersGiven an integer array, adjust each integers so that the difference of every adjcent integers are not greater than a given number target.
- rjrush December 06, 2014 in United States
If the array before adjustment is A, the array after adjustment is B, you should minimize the sum of |A[i]-B[i]|
You can assume each number in the array is a positive integer and not greater than 100
Given [1,4,2,3] and target=1, one of the solutions is [2,3,2,3], the adjustment cost is 2 and it's minimal. Return 2.| Report Duplicate | Flag | PURGE
Google SDE1 Algorithm