Google Interview Questions
- 2of 4 votes
AnswersWrite a method to return first five 10 digit prime numbers.
- saudip100 July 22, 2014 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer - 16of 18 votes
AnswersOutput top N positive integer in string comparison order. For example, let's say N=1000, then you need to output in string comparison order as below:
- John July 15, 2014 in United States
1, 10, 100, 1000, 101, 102, ... 109, 11, 110, ...| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Coding - 2of 2 votes
AnswersFind the longest sequence of prefix shared by all the words in a string.
- employee11 July 15, 2014 in Israel
"abcdef abcdxxx abcdabcdef abcyy" => "abc"| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 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 - 1of 3 votes
AnswersGive efficient implementation of the following problem.
- sigkill July 08, 2014 in India
An item consist of different keys say k1, k2, k3. User can insert any number of items in database, search for item using any key, delete it using any key and iterate through all the items in sorted order using any key. Give the most efficient way such that it supports insertion, search based on a key, iteration and deletion.| Report Duplicate | Flag | PURGE
Google Intern Algorithm - -4of 4 votes
AnswersSwap 2 nodes in a Binary tree.(May or Maynot be a BST)
- l33t June 21, 2014 in United States for ChromeCast
Swap the nodes NOT just their values.
(preferably in Java please..(My requirement not theirs :p))
ex:
5
/ \
3 7
/ \ /
2 4 6
swap 7 and 3
5
/ \
7 3
/ / \
6 2 4| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - -4of 6 votes
AnswersYou have an array of integers(size N), such that each integer is present an odd number of time, except 3 of them(which are present even number of times). Find the three numbers.
- gdg June 21, 2014 in United States for Bing
Only XOR based solution was permitted.
Time Complexity: O(N)
Space Complexity: O(1)
Sample Input:
{1,6,4,1,4,5,8,8,4,6,8,8,9,7,9,5,9}
Sample Output:
1 6 8| Report Duplicate | Flag | PURGE
Google Developer Program Engineer Arrays - 11of 11 votes
AnswersGiven an unsorted array of integers, you need to return maximum possible n such that the array consists at least n values greater than or equals to n. Array can contain duplicate values.
- abc June 20, 2014 in India
Sample input : [1, 2, 3, 4] -- output : 2
Sample input : [900, 2, 901, 3, 1000] -- output: 3| Report Duplicate | Flag | PURGE
Google Applications Developer - 1of 1 vote
AnswersTraveler wants to travel from city “A” to city “D”.
There is a path from city “A” to city “D”.
Path consists of steps, i.e. travel from city “A” to city “B”.
Path is encoded as sequence of steps.
Sequence is in incorrect order.
Your task is to restore order of steps in the path.
Input (unordered sequence):
C -> D
A -> B
B -> C
Output (Correctly ordered list which represents path):
A, B, C, D
Implement following API:
- abc June 20, 2014 in Indiaclass Step { String start; String finish; }; class Node { String value; Node next; } List<String> findPath(List<Step> steps) { }
| Report Duplicate | Flag | PURGE
Google Applications Developer Algorithm - 10of 10 votes
AnswersGiven a Binary Search tree of integers, you need to return the number of nodes having values between two given integers. You can assume that you already have some extra information at each node (number of children in left and right subtrees !!).
- abc June 19, 2014 in India| Report Duplicate | Flag | PURGE
Google Applications Developer Algorithm - 2of 2 votes
AnswersYou are given information about hotels in a country/city. X and Y coordinates of each hotel are known. You need to suggest the list of nearest hotels to a user who is querying from a particular point (X and Y coordinates of the user are given). Distance is calculated as the straight line distance between the user and the hotel coordinates.
- abc June 19, 2014 in India| Report Duplicate | Flag | PURGE
Google Applications Developer Algorithm - 2of 4 votes
AnswersGiven a complete binary tree, Find a Max element
- sLion June 18, 2014 in United States| Report Duplicate | Flag | PURGE
Google SDE1 Data Structures - 1of 3 votes
AnswersDesign a two player battleship game to be played over internet
- ravik June 16, 2014 in United States| Report Duplicate | Flag | PURGE
Google - 0of 0 votes
AnswersSuppose you have a million integer numbers.
- l33t June 14, 2014 in United States for Hangouts
Return all possible values of a,b and c such that
a+b+c<=d.
d will be provided to you.
ex: if the numbers are 1,2,3,4,5,6,7
and d=7
[1,2,3]
[1,2,4]
[1,2,3] will be same as [1,3,2] and [3,2,1]...
follow up:
Return all such parts that satisfy the above condition if d is not provided.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 1of 1 vote
AnswersGiven a string with multiple spaces write a function to in-place trim all spaces leaving a single space between words
- employee11 June 09, 2014 in Israel
e.g.
_ _ _ Hello _ _ _ World _ _ _
Hello _ World _ _ _ _ _ _ _ _ _| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 3of 3 votes
AnswersHow many occurrences of a given search word can you find in a two-dimensional array of characters given that the word can go up, down, left, right, and around 90 degree bends?
- lueikhong June 07, 2014 in Australia
Ex:
Count of occurrences of SNAKES
S N B S N
B A K E A
B K B B K
S E B S E
The answer is 3.
Write a program for that question.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - -1of 3 votes
AnswersQuest: create a Random number generator without using the java in build Random class?
- vrajendra.singh.mandloi May 31, 2014 in India
public class GenerateRandomNumbers {
public static int seed = 10;
public void generateInt(int num){
seed = num;
for(int i=1;i<num;i++){
seed = ((int)System.nanoTime()%(i));
if(seed<=0)
seed = ((int)System.currentTimeMillis()%i);
System.out.println(seed);
}
}
public static void main(String[] args) {
new GenerateRandomNumbers().generateInt(20);
}
}
its a class to generate random numbers but the problem is It always starts with 0...!
Can someone add some more to this code.??| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 7of 7 votes
AnswersGiven a string (for example: "a?bc?def?g"), write a program to generate all the possible strings by replacing ? with 0 and 1.
- pennepalli May 30, 2014 in United States
Example:
Input : a?b?c?
Output: a0b0c0, a0b0c1, a0b1c0, a0b1c1, a1b0c0, a1b0c1, a1b1c0, a1b1c1.| Report Duplicate | Flag | PURGE
Google Developer Program Engineer Algorithm C# C++ Java - -2of 2 votes
AnswersTable 1: Parents -> (int id, int age)
- pennepalli May 30, 2014 in United States
Table 2: Children -> (int id, int age, int parent_id)
Get the parent id, his/her oldest and youngest children ids.| Report Duplicate | Flag | PURGE
Google Developer Program Engineer SQL - -1of 3 votes
AnswersTable 1: Parents -> (int id, int age, int Child_id)
- pennepalli May 30, 2014 in United States
Table 2: Children -> (int id, int age, int parent_id)
Get the parent id, his/her oldest and youngest children ids.| Report Duplicate | Flag | PURGE
Google Developer Program Engineer SQL - -1of 1 vote
Answersgiven 10 files (text files) each of size of 900 Mb. givena another file named "hello". match the contents of this file with other 10 file and return the file whose contents closely match with the contents of file "hello"
- mad May 30, 2014 in India| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - -1of 9 votes
AnswersFind minimum number of steps to reach the end of array from start (array value shows how much you can move).
- byteattack May 19, 2014 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Dynamic Programming - -3of 3 votes
AnswersDraw a graph as a graph. Assume there is graphics library to draw lines and all. Just tell how will you order the vertices such that the edges don't intersect and they seem ordered.
- kenadams.awesome May 18, 2014 in India| Report Duplicate | Flag | PURGE
Google SDE1 Data Structures - 0of 2 votes
AnswersNeed to implement something like pastebin wherein you paste some text, you are given an url. The url can be used anywhere to access the text.
- kenadams.awesome May 18, 2014 in India
Various problems, features and design of this architecture were discussed.| Report Duplicate | Flag | PURGE
Google SDE1 System Design - 0of 0 votes
AnswersThere are N lanes, and the speed of each lane is given. There are many cars in all the lanes and the start position and the length of each car and its corresponding lane is given. There is a frog which an do 2 functions: wait() or jump().
- kenadams.awesome May 18, 2014 in India
Find if there is a path for the frog to go from lane 1 to lane N without getting hit by any of the moving cars.| Report Duplicate | Flag | PURGE
Google SDE1 Algorithm - 3of 3 votes
AnswersWrite an algorithm to find the ‘next’ node (e.g., post-order successor) of a given node in a binary tree and binary search tree
- Jeff May 18, 2014 in United States
a.) where each node has a link to its parent.
b.) without parent pointer
implement 2 versions of the algorithm: 1.) binary tree 2.) BST| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer - 0of 4 votes
AnswersGiven a matrix of size N*N and a starting point "s" in the matrix which represents a color.
Find the area of the shape represented by the color of the starting point "s".
Note 1: A shape can be anything as long as it is connected, e.g. a square, a circle, a doughnut or a line.
Note 2: It is only a shape if they are connected from the starting point.
Note 3: Connected means, adjacent and the same color.
E.g.zero based index. Starting point = top left "R" [3][2], color = R, area = 10 000000000 000000000 000000000 00RRRR000 00R00R000 00RRRR000 000000000 000000000 000000000
Update: OK as requested further clarifications, a cell is only a single color, it is a matrix and contains
a single value stating the color of the cell. Think of each cell as a pixel and each pixel represents a length of 1.
The shape above has an area of 10, because that it is not a regular square but has two holes in the middle, if you do it mathematically:
(3*4) - (1*2) = 10 or simply by visually counting the R squares.
You are not trying to create shapes, you are using the starting point "s" to find the complete shape (traverse the matrix until you have found all connected pixels) and calculate the area.
If you need more clarification I can try but I think that should clarify.
State your Time and Space complexity of your algorithm.
Consider also this:0000000000000 0000000000000 0000000000000 0000000000000 0000000000000 00RRRR0000000 00R00R000RR00 00RRRR000RR00 0000000000000 0000000000000 0000000000000 0000000000000 0000000000000 zero based index. Starting point s = top-left "R" [5][2], area = 10.
In the above case, the other shape, same color is not connected to the shape specified by the starting point, hence is not part of the area calculation.
- DotQ May 09, 2014 in United States
Apologies for the formatting.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - -6of 6 votes
AnswersHow to delete two rows from the table in database ?
- ajaybhardwaj789 May 07, 2014 in India
Note: Delete only first two rows from the Database.
<table style="width:300px" border="2px">
<tr>
<th>USERNAME</th>
<th>LOCATION</th>
</tr>
<tr>
<td>zac</td>
<td>california</td>
</tr>
<tr>
<td>zac</td>
<td>california</td>
</tr>
<tr>
<td>zac</td>
<td>california</td>
</tr>
<tr>
<td>zac</td>
<td>california</td>
</tr>
</table>| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Database - 3of 3 votes
Answerspublic class LogEntry {
- Invhelper May 05, 2014 in United States
public final long startTime; // start time of a job in millisec granularity
public final long endTime; // end time of a job in millisec granularity.
public final long ram; // the amount of ram the job occupies.
public final long jobId;
... constructor ...
}
running total of RAM
|
| 3GB
| -----
| 2GB
| ------
| 1GB -----------
|----- -----------
|
|____________________________________________________time
Find the peakRAM when the input is a collection of LogEntry objects| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Coding - 4of 4 votes
AnswersWhat happens when you type in shell
list=$(ls)
Interviewer expected the list of system-calls made, file-descriptors involved etc.
- Moony April 29, 2014 in United States| Report Duplicate | Flag | PURGE
Google Site Reliability Engineer Unix