## Google Interview Questions

- 0of 0 votes
Given 2 set of arrays of size N(sorted +ve integers ) find the median of the resultant array of size 2N.

(dont even think of sorting the two arrays in a third array , though u can sort them. Try something better than order NLogN

- -3of 3 votes
Write a method to return first five 10 digit prime numbers

- 1of 1 vote
Write a method to return first five 10 digit prime numbers.

- 10of 10 votes
Output 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:

1, 10, 100, 1000, 101, 102, ... 109, 11, 110, ...

- 2of 2 votes
Find the longest sequence of prefix shared by all the words in a string.

"abcdef abcdxxx abcdabcdef abcyy" => "abc"

- 4of 4 votes
Given a NxN matrix which contains all distinct 1 to n^2 numbers, write code to print sequence of increasing adjacent sequential numbers.

ex:

1 5 9

2 3 8

4 6 7

should print

6 7 8 9

- 2of 2 votes
Give efficient implementation of the following problem.

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.

- -2of 2 votes
Swap 2 nodes in a Binary tree.(May or Maynot be a BST)

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

- -5of 5 votes
You 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.

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

- 4of 4 votes
Given 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.

Sample input : [1, 2, 3, 4] -- output : 2

Sample input : [900, 2, 901, 3, 1000] -- output: 3

- 1of 1 vote
Traveler 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:`class Step { String start; String finish; }; class Node { String value; Node next; } List<String> findPath(List<Step> steps) { }`

- 4of 4 votes
Given 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 !!).

- 1of 1 vote
You 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.

- 2of 2 votes
Given a complete binary tree, print the outline of the tree in anti-clockwise direction, starting from the root. I.e. first print all the nodes on the left

edge of the tree going downwards, then print all the leaves going left to right (including leaves on both the last and the 2nd last level if necessary), then

print the nodes on the right edge of the tree going upwards.

Example tree:

A

/ \

/ \

B C

/ \ / \

D E F G

/ \ /

H I J

Expected Output: ABDHIJFGC

- 2of 2 votes
Design a two player battleship game to be played over internet

- 0of 0 votes
Suppose you have a million integer numbers.

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.

- 0of 0 votes
Given a string with multiple spaces write a function to in-place trim all spaces leaving a single space between words

e.g.

_ _ _ Hello _ _ _ World _ _ _

Hello _ World _ _ _ _ _ _ _ _ _

- 2of 2 votes
How 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?

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.

- -1of 1 vote
Quest: create a Random number generator without using the java in build Random class?

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

- 1of 1 vote
Given a string (for example: "a?bc?def?g"), write a program to generate all the possible strings by replacing ? with 0 and 1.

Example:

Input : a?b?c?

Output: a0b0c0, a0b0c1, a0b1c0, a0b1c1, a1b0c0, a1b0c1, a1b1c0, a1b1c1.

- -1of 1 vote
Table 1: Parents -> (int id, int age)

Table 2: Children -> (int id, int age, int parent_id)

Get the parent id, his/her oldest and youngest children ids.

- -1of 1 vote
Table 1: Parents -> (int id, int age, int Child_id)

Table 2: Children -> (int id, int age, int parent_id)

Get the parent id, his/her oldest and youngest children ids.

- 0of 0 votes
given 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"

- -2of 8 votes
Find minimum number of steps to reach the end of array from start (array value shows how much you can move).

- -1of 1 vote
Draw 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.

- 1of 1 vote
Need 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.

Various problems, features and design of this architecture were discussed.

- 0of 0 votes
There 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().

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.

- 2of 2 votes
Write an algorithm to find the ‘next’ node (e.g., post-order successor) of a given node in a binary tree and binary search tree

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

- 0of 4 votes
Given 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.

Apologies for the formatting.

- -5of 5 votes
How to delete two rows from the table in database ?

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>