Category: Google Interview

1

Print all sub sequences of a given array

Objec­tive:  Given an array write an algorithm to print all the possible sub subsequences. Example: int [] a = {1, 2, 3}; Output: Possible sub sequences – {Empty}, {1}, {2}, {3}, {1, 2} ,{1,3}, {2,...

1

Print all substrings of a given string

Objec­tive:  Given a string write an algorithm to print all the possible sub strings. Example: String input = “abcd”; Output: Possible sub strings – a          a b      a b c   a b c d b...

1

Dynamic programming – Printer Problem

Objective:  Given a printer which can perform only 2 operations- Printer can print consecutive identical characters in one go. It can replace consecutive characters by consecutive identical characters at any position. You are given a...

1

Dynamic programming – Minimum Jumps to reach to end

Objective:  Given an array of non negative integers, start from the first element and reach the last by jumping. The jump length can be at most the value at the current position in the array....

4

Find the local minima in a given array

Objec­tive:  Given an array of integer write an algorithm to find the local minima. Local Minima: An element is considered as local minima if it is less than both of its neighbors (if neighbors exist)....

3

Print All Diagonals of a given matrix

Objective: Given two dimensional matrix, write an algorithm to print all the diagonals of matrix. Example: Approach: We will solve this problem in two parts. first half of diagonals and second half of diagonals....

4

Dynamic Programming – Coin In a Line Game Problem

Objective: In this game, which we will call the coins-in-a-line game, an even number, n, of coins, of various denominations from various countries, are placed in a line. Two players, who we will call...

2

Dynamic Programming – Split the String into Minimum number of Palindromes.

Objective: You are given a large string. You need to cut the string into chunks such that each substring that you get is a palindrome. Remember that each 1 length string is always a...

1

Shortest Range in K-sorted Lists

Objective: You have k lists of sorted integers. Find the smallest range that includes at least one number from each of the k lists. This is very nice and tricky solution, This problem was asked...

1

Dynamic Programming – Minimum Numbers are Required Whose Square Sum is Equal To a Given Number

Objective: Given a number, Write an algorithm to find out minimum numbers required whose square is equal to the number. This question has been asked in the Google Interview for Software Developer position.This is...

16

Print All Possible Subsets with Sum equal to a given Number

Objective: Given a number N, Write an algorithm to print all possible subsets with Sum equal to N This question has been asked in the Google for software engineer position. Example: N=4 1111 112...

9

The Word Break Problem

Objective : Given an string and a dictionary of words, find out if the input string can be broken into a space-separated sequence of one or more dictionary words. Example: dictionary = [“I” ,...

3

Backtracking – Knight’s Tour Problem

Objective : A knight’s tour is a sequence of moves of a knight on a chessboard such that the knight visits every square only once. If the knight ends on a square that is...

3

Backtracking – N Queens Problem – Better Solution

Objective : In chess, a queen can move as far as she pleases, horizontally, vertically, or diagonally. A chess board has 8 rows and 8 columns. The standard 8 by 8 Queen’s problem asks...

%d bloggers like this: