Some interview questions about array and string
文章目录
Hash Table
In C++, the namespacestd::tr1
contains lots of hash tables. We can play
with it.
{% include_code careeruparray/careeruphash.cpp %}
Questions
1.1. Implement an algorithm to determine if a string has all unique characters. What if you can not use additional data structures?
I have come up with 2 methods.

Iterate the string and compare each character to other character. This is the common way to solve this problem. It will cost (O ^ 2) time.

Use the
std::tr1::unordered_set
data structure so that we can only iterate the string once.
Here is the code.
{% include_code careeruparray/careerup1.1.cpp %}
However, there are two more effecient methods.

If the string contains only ASCII(Ask the interviewer!), we can use an array of size 256 to mark every character. The time complexity is O(n). But this is to sacrifice space for time, just as the unordered_set method.

If the string contains only letters, we can use a 4bytes integer to mark the characters in the string.
Here is the code.
{% include_code careeruparray/careerup1.1answer.cpp %}
1.2. Write code to reverse a CStyle String(CString means that “abcd” is represented as five characters, including the null character)
The approach I come up with is described as follows.

Get the length of the string, which needs iterate the whole string.

According to the property of continuing, we can manipulate the string from the end. So we can swap the first character with the last character, and swap the second character with the last but not least character, … This needs iterate half of the string.
In sumary, this will need O(1.5n) > O(n) time complexity. Here is the code.
{% include_code careeruparray/careerup1.2.cpp %}
However, the answer is using pointer instead of index. But the algorithm and the time complexity are the same. Here is the code.
{% include_code careeruparray/careerup1.2answer.cpp %}
This code has several problems. First, the variable end
and tmp
should
be defined in the if
block. Otherwise, if str
is NULL
, the
definition of the two variables will be wasteful. Second, using the pointer with
the ++
and 
is errorprone.
1.3 Design an algorithm and write code to remove the duplicate characters in a string without using any additional buffer. NOTE: One or two additional variables are fine. An extra copy of the array is not.
FOLLOW UP
Write the test cases for this method.
I am not so smart that I can only come up with the straightforward method. Just iterate the whole string and check from the former characters to find duplicate character. If there is duplicate, remove it by moving the rest characters front. Here is the code.
{% include_code careeruparray/careerup1.3.cpp %}
The algorithm is ok but the program is too slow. In fact, the last for
loop
is not necessary. Here is the improved version according to the answer.
{% include_code careeruparray/careerup1.3answer.cpp %}
1.4 Write a method to decide if two strings are anagrams or not.
From Wikipedia, An anagram is a type of word play, the result of rearranging the letters of a word or phrase to produce a new word or phrase, using all the original letters exactly once.
For example, "abc"
, "acb"
, "bac"
, "bca"
, "cab"
and "cba"
are all anagrams.
I come up with two approaches.

Sort them and compare them. This will require at least O(nlogn) * 2 + O(n) time complexity.

Use an extra array to record the occurrence of each character when compare the two string.
I implemented the last method here.
{% include_code careeruparray/careerup1.4.cpp %}
1.5 Write a method to replace all spaces in a string with ‘%20’.
There is a replace
method in class std::string
, so I can use it
directly. But it’s too slow(O(n^2)). There is another method with the time
complexity O(n). Count the number of the spaces and resize the string and
copy the string from tail to head. If encounter the space, replace it with
%20
. Here is the code of the two methods.
{% include_code careeruparray/careerup1.5.cpp %}
1.6 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 Can you do this in place?
The first time I looked at this problem, I think it’s very simple and write
down an equation a[i][j] = a[n  j  1][i]
. When I implemented the program
using this equation, I found that I was totally wrong!
Since you can’t request another space to store the matrix that was unmodified,
the modified value will affect the value to be changed. So we should think about
other solutions. One effective solution is to divide the whole matrix into
N / 2
parts and rotate each parts by swapping the values four times.
Here is the code.
{% include_code careeruparray/careerup1.6.cpp %}
1.7 Write an algorithm such that if an element in an MxN matrix is 0, its entire row and column is set to 0.
I made the same mistake as problem 1.6. I think we should just iterate the whole matrix and set its entire row and row to 0 when we met an element that is 0. But this is wrong! It will also affect the elements that haven’t been iterated.
One solution is to use another matrix to record the original matrix. But this will need too much space.
Actually, we just need two array of length M
and N
respectively and
record whether there are an 0
in that row or column. If there are, set the
entire row or column to 0.
Here is the code.
{% include_code careeruparray/careerup1.7.cpp %}
1.8 Assume you have a method isSubstring which checks if one word is a substring 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 (i.e., “waterbottle” is a rotation of “erbottlewat”).
I am not so smart that I can’t come up with the method to solve this problem after a long time. The answer amazed me.
Just concatenate s1
and check if s2
is a substring of it. For example,
waterbottle
is a substring of erbottlewaterbottlewat
, so it’s a rotation
of erbottlewat
.
Here is the code.
{% include_code careeruparray/careerup1.8.cpp %}