Facebook Interview Question
Software DevelopersTeam: Infrastructure
Country: United States
Interview Type: In-Person
with the described DS string concatenation will require O(n+m) for every concatenation operation, where n is the length of one and m the length of the other string. It creates a new array and copies the existing twos in there. If appending many strings to one string that keeps growing, then m << n. Now it's worth implementing some kind of smart buffering, where the concatenated string allocates more memory than needed for a single append operation so a some concatenation or append operations can be done without reallocation. Of course that needs some balance (wasting memory vs. reallocation and copying). Having an immutable string object and a mutable string builder seems to make sense. With the right memory allocation strategy one can get a O(m) where m << n, runtime compensated.
An other alternative might be to have a concatenated string class, which is a list that holds only pointers to the original, immutable string objects...
public static String compressed(int[] nums){
int len=nums[0];
int cons=0;
StringBuilder rst=new StringBuilder(""); // Create a compressed String
StringBuilder s=new StringBuilder(""); // To store the original string
for(int i=1;i<nums.length;++i){
cons++;
if(i+1 >= nums.length ||
(nums[i]!=nums[i+1])){
rst.append((char)nums[i]).append(cons);
cons=0;
}
s.append((char)nums[i]);
}
rst = s.length() > rst.length() ? rst : s; // If the compressed string is shorter
// return compressed string, else there
// is no use of compression(shortcoming)
return rst.toString();
}
public static String compressed(int[] nums){
int len=nums[0];
int cons=0;
StringBuilder rst=new StringBuilder(""); // Create a compressed String
StringBuilder s=new StringBuilder(""); // To store the original string
for(int i=1;i<nums.length;++i){
cons++;
if(i+1 >= nums.length ||
(nums[i]!=nums[i+1])){
rst.append((char)nums[i]).append(cons);
cons=0;
}
s.append((char)nums[i]);
}
rst = s.length() > rst.length() ? rst : s; // If the compressed string is shorter
// return compressed string, else there
// is no use of compression(shortcoming)
return rst.toString();
}
public static String compressed(int[] nums){
int len=nums[0];
int cons=0;
StringBuilder rst=new StringBuilder(""); // Create a compressed String
StringBuilder s=new StringBuilder(""); // To store the original string
for(int i=1;i<nums.length;++i){
cons++;
if(i+1 >= nums.length ||
(nums[i]!=nums[i+1])){
rst.append((char)nums[i]).append(cons);
cons=0;
}
s.append((char)nums[i]);
}
rst = s.length() > rst.length() ? rst : s; // If the compressed string is shorter
// return compressed string, else there
// is no use of compression(shortcoming)
return rst.toString();
}
public String myString(char [] charInput){
StringBuilder sb = new StringBuilder();
sb.setLength(charInput.length +1);
sb.insert(0, charInput.length); //first element of the string is the length of the array.
int j=1;
for (int i=0; i<charInput.length; i++){
sb.insert(j, charInput[i]); //add all elements of array to string after length
j++;
}
System.out.println("final string -" +sb);
return sb.toString();
}
Don't quiet understand the implementation by @Anwar.
- deep.kulshreshtha July 06, 2017Concatenation should require adding the new string ASCII values to the existing array. If the array length is short. It will have to be re-sized.
Shortcomings:
a. Finding a consecutive block of memory to store array of a bigger size might be challenging when memory utilization is high.
b. Resizing takes O(n) time since each input is copied to the new array.
c. High number of abandoned arrays might need Garbage collection regularly. This might take CPU bandwidth and might slow the machine.