Arrays-String interview question solution

Cracking the coding interview

Arrays and String question solutions

Hey guys i am providing the solutions for the question given in the Chapter one Arrays and String of the very famous book Cracking the coding interview. All these solutions are written by myself and checked for all the possible cases. Please take a look at them and help your self to solve your problems. If you have any query regarding the solutions or you want to ask something leave your comment and i will get back to you as soon as possible. Happy coding

Question 1

Implement an algorithm to determine if a string has all unique characters.Think what you can do if you cannot use additional data structures? means that all the characters in the string must be for one time only.

Solution
You can find the solution for this problem here.

Question 2

Given two strings, write a method to decide if one is a permutation of the other. that means that they same number of characters in it but arrangement will be different or we can say that order is different.

Solution
You can find the solution for this problem here.

Very simple problem just sort the strings and then compare them.

Solution 1 using java.

Question 3 from the Cracking the coding interview.

Write a method to replace all spaces in a string with '%20. Assume that the string has sufficient space at the end to hold the additional characters, and that you are given the true length of the string. ( If implementing in Java, you can use a character array so that you can perform this operation in place.) or you can use string builder.

EXAMPLE
Input: "Mr John Smith "J 13
Output: "Mr%20John%20Smith"

Solution
You can find the solution for this problem here.
Solution 1 using java click the following link to get the solution for this problem.

Question 4

Palindrome Permutation: Given a string, write a function to check if it is a permutation of a palindrome. A palindrome is a word or phrase that is the same forwards and backwards. A permutation is a rearrangement of letters. The palindrome does not need to be limited to just dictionary words.

EXAMPLE
Input: Tact Coa
Output: True (permutations: "taco cat". "atco cta". etc.)

Solution

You can find the solution for this problem here.

Solution 1 using java .

Question 5

One Away: There are three types of edits that can be performed on strings: insert a character, remove a character, or replace a character. Given two strings, write a function to check if they are one edit (or zero edits) away.

EXAMPLE pale, ple -> true
pales. pale -> true
pale. bale -> true
pale. bake -> false

Solution
You can find the solution for this problem here.
Solution 1 using java separate functions.
Solution 2 using java combined functions.

Question 6

String Compression: Implement a method to perform basic string compression using the counts of repeated characters. For example, the string aabcccccaaa would become a2b1c5a3. If the "compressed" string would not become smaller than the original string, your method should return the original string. You can assume the string has only uppercase and lowercase letters (a - z).

Solution
You can find the solution for this problem here.
Solution 1 using java.

Question 7

Rotate Matrix: Given an image represented by an NxN matrix, where each pixel in the image is 4 bytes, write a method to rotate the image by 90 degrees. (an you do this in place?)

Solution
You can find the solution for this problem here.
Solution 1 using java.

Question 8

Zero Matrix: Write an algorithm such that if an element in an MxN matrix is 0, its entire row and column are set to O.

Solution
You can find the solution for this problem here.
Solution 1 using java.

Question 9

String Rotation: Assume you have a method isSubstring which checks if one word is a sub string of another. Given two strings, S1 and S2, write code to check if S2 is a rotation of S1 using only one call to isSubstring (e.g., "waterbottle" is a rotation of"erbottlewat").

Solution
You can find the solution for this problem here.
Concatinate s1 with s1 and then use isSubstring function for the result.