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” , “have”, “Jain”, “Sumit”, “am”, “this”, “dog”] String = “IamSumit” Output: “I am Sumit” String =”thisisadog” Output : String can’t be broken … Read more The Word Break Problem

Sort Names by their Last Names.

Objective: Given a list of names ( first name and last name), sort the list by their last names. Example: List [] = {“Daenerys Targaryen”, “Jon Snow”, ” Tyrion Lannister”, ” Joffrey Baratheon”} Output: [Joffrey Baratheon, Tyrion Lannister, Jon Show, Daenerys Targaryen] Approach: We have sort() and Collections.sort() but we cannot do the normal sorting … Read more Sort Names by their Last Names.

Find All the Well Ordered Permutations of a Given String.

Objective: Write an algorithm to Print All the Well Ordered Permutations of a Given String.

What is Well Ordered String: When all the alphabets in a string occur in the increasing order irrespective of Lower Case or Upper case.

http://www.careercup.com/question?id=6206517812396032

Example :

"Sumit" - Not Well Ordered . 'u' occurred after 'S'.

"Now" - Well Ordered. N<o<W.

Input: Interview
Output: 
[e, e, I, i, n, r, t, v, w]
[e, e, i, I, n, r, t, v, w]
[e, e, i, I, n, r, t, v, w]
[e, e, I, i, n, r, t, v, w]

Read moreFind All the Well Ordered Permutations of a Given String.

Print All Possible Valid Combinations Of Parenthesis of Given ‘N’

Objec­tive: Given “n”, generate all valid parenthesis strings of length “2n”.
Example:

Given n=2

Output:
(())
()()

Approach:

Read morePrint All Possible Valid Combinations Of Parenthesis of Given ‘N’

Check if one string is Rotation of another string

Objective: Write an algorithm to check if one string is Rotation of another string. This question has been asked in the Amazon interview.

Example:

Input Strings : 'sumitjain' and 'tjainsumi'
Output : true

Input String : 'Jaain' and 'ainJ'
Output: false

Input: Two Strings

Output: True or false based on whether strings are rotation of each other.

Approach:

Read moreCheck if one string is Rotation of another string

String Compression using count of repeated characters – Run Length Encoding

Objective: Write an algorithm to compress the given string by using the count of repeated characters and if new compressed string length is not smaller than the original string then return the original string.

Example:

Input String : ssssuuuummmmmmiiiittttttttttttt
Compressed String : s4u4m6i4t13

Input String : Jaain
Compressed String : Jaain (Since compressed string is length is greater than original string)

Input: A String

Output: either A compressed string or original string whichever us smaller.

Approach:

Read moreString Compression using count of repeated characters – Run Length Encoding

Replace all spaces in a String with ‘%20’

Objective: Write an algorithm to replace all spaces in a given string with ‘%20’. You can consider that string has enough space at the end of the string to hold the extra characters.

Input: A String and true length of a string

Output: Updated string in which each space is replaced by the ‘%20’

Example: 

Input String : I am Sumit Jain    

Output String : I%20am%20Sumit%20Jain

Approach:

Read moreReplace all spaces in a String with ‘%20’

Find Whether Two Strings are Permutation of each other

Objective: Given Two Strings, check whether one string is permutation of other

Input: Two Strings

Output: True or false based on whether strings are permutation of other or not.

Example:

"sumit" and "tiums" are permutations of each other.

"abcd" and bdea" are not permutations of each other.

Approach:

Read moreFind Whether Two Strings are Permutation of each other

Find The Longest Sequence Of Prefix Shared By All The Words In A String

Objective: Write an algorithm to find The Longest Sequence Of Prefix Shared By All The Words In A String. This interesting problem was asked in the Google interview for software engineer. This problem is bit tricky, it looks difficult but actually it is simple problem.

Input: A String

Output: The longest sequence of prefix common in all the words in a string

Example:

“Bedroom BedClock BedTable BedWall” => “Bed”

Approach:

Read moreFind The Longest Sequence Of Prefix Shared By All The Words In A String

Check If String has All Unique Characters

Objective: Write an algorithm to find out whether in a given string contains all the unique characters. This question has been asked in the Amazon and Microsoft interviews.

Input:  A String

Output: True or false based upon whether string contains all the unique characters or not.

Approach:

Method 1.

Read moreCheck If String has All Unique Characters

Valid or Well Formed Parentheses | Part – 1

Objective: You have been asked to Write an algorithm to find Whether Given the Sequence of parentheses are well formed. This question was asked in the Amazon Interview.

Input: A String contains a sequence of parentheses

Output: true or false on whether parentheses are well formed or not

Approach:

  • Idea is to have two counters, one for open parentheses ‘{‘ and one for close ‘}’
  • Read one character at a time and increment one of the counters
  • If any given point of time count of close parentheses is greater than the open one, return false
  • If at the end both counters are equal, return true

Example: { { } { } } – Well formed

{ { } { = Not well formed

Read moreValid or Well Formed Parentheses | Part – 1