Facebook Interview Question for Software Developers


Team: Infrastructure
Country: United States
Interview Type: In-Person




Comment hidden because of low score. Click to expand.
2
of 2 vote

Don't quiet understand the implementation by @Anwar.

Concatenation 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.

- deep.kulshreshtha July 06, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
2
of 2 vote

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...

- Chris July 07, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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();
  }

- Anwar July 05, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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();

}

- Anwar July 05, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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();
  }

- Anwar July 05, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@Anwar, the resulting String has to be in the same representation: int[]

also the interviewer asked: what could happen for the concatenation of very long strings.

- funk July 05, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote
{{{ {{{ public static String StringConcat(int[] A){ int len=A[0]; if(A.length!=len+1){ return null; } String str=""; for (int i =1;i<A.length;i++){ str+=(char)A[i]+""; } System.out.println(str); return str; - Holly July 06, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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();
	}

- java082864 July 07, 2017 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More