Preview

01 - The GF aptitude test

 1. You're given a cube of cheese and a knife. How many straight cuts of the knife do you need to divide the cheese into twenty-seven little cubes?
cheeseandknife_cert_AF_smartenough.jpg

  6

  10

  8

  12

 2. When there's a wind blowing, does a round-trip by plane take more time, less time, the same time, or would your answer be 'it depends on the plane!'?

  exactly the same time

  less time

  depends on the plane

  more time

 3. Read the problem and statement below. True or False? 
There are three boxes, and one contains a valuable prize;
the other two are empty. You're given your choice of a box,
but you aren't told whether it contains the prize. Instead,
one of the boxes you didn't pick is opened and is shown to 
be empty. 

You should definitely switch/swap it for the other 
unopened box if you wish to get the prize.

  TRUE

  FALSE

 4. At 3:15, what is the angle between the minute and hour hands on an analog clock?
clock_AF_smartenough1.jpg

  6 degrees

  0 degrees

  7.5 degrees

  5.5 degrees

 5. Read the "celebrity problem" below and select the most appropriate statement from the options given. 
In a party of N people, only one person is known to everyone.
Such a person may be present in the party, if yes, (s)he doesn?t
know anyone in the party. We can only ask questions like ?does A 
know B? ?. Find the stranger (celebrity) in the minimum number of
questions.

We can describe the problem input as an array of numbers/characters
representing persons in the party. We also have a hypothetical 
function HaveAcquaintance(A, B) which returns true if A knows B,
false otherwise. 

How can we solve the problem? (select the option that is valid in general - i.e starting out to solve the problem)

  All of the listed options are valid.

  We can model the solution using graphs. Initialize indegree and outdegree of every vertex as 0.

  We can push all the celebrities onto a stack and use this data structure to solve it (using push, pop and checking the return status of HaveAcquaintance(A, B).

  The solution is to use two pointers, one from start and one from the end. Assume the start person is A, and the end person is B.

 6. This was a genuine "phone screen" question from facebook. "Hey, so do you know about sets and arrays?"

 7. The "phone screen" interview continues: "Okay, so we want to use a set implementation to store a million names. Some of them are duplicates. By the way, what is a set?"(2 marks) 
Note: To get two marks use key words associated with set and comment on the duplicates. Get this wrong and your "phone screen" ends!

 8. Here's another "phone screen" question: Suppose I wanted a function that took in an input of "ivicc" and returned True. "civic" also returned True. What do you think I am asking you to do? 
Note: Here, the interviewer is honing in on your precision
 of thought and how well you understand and can comprehend
 any given problem or question.

  You are asking me to check whether any permutation of an input string is a palindrome.

  You are asking me to do the impossible,as the first input is not a real word.

  You are asking me to write a function that checks to see if any given input is a valid palindrome.

  You are asking me to write a function that returns true if a word has the characters 'c' and 'I' in it.

 9. Do you know what the Fibonacci sequence is? This program should output 0,1,1,2,3,5,8,13 etc, but doesn't. What is wrong? 
# Program to display the Fibonacci sequence up to n-th term
nterms = int(input("How many terms? "))
# first two terms
n1, n2 = 0, 1
count = 0
# check if the number of terms is valid
if nterms <= 0:
   print("Please enter a positive integer")
elif nterms == 1:
   print("Fibonacci sequence upto",nterms,":")
   print(n1)
else:
   print("Fibonacci sequence:")
   while count < nterms:
       print(n1)
       nth = n1 + n2
       # update values
       n2 = n1
       n2 = nth
       count += 1

  Line 19 has been coded incorrectly

  Line 16 has been coded incorrectly

  Line 18 has been coded incorrectly

  Line 4 has been coded incorrectly

 10. What is the following code doing? Given a 2D binary matrix filled with 0's and 1's, find the __________________________________. 
public int maximalRectangle(char[][] matrix) {
	int m = matrix.length;
	int n = m == 0 ? 0 : matrix[0].length;
	int[][] height = new int[m][n + 1];
 
	int maxArea = 0;
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			if (matrix[i][j] == '0') {
				height[i][j] = 0;
			} else {
				height[i][j] = i == 0 ? 1 : height[i - 1][j] + 1;
			}
		}
	}
 
	for (int i = 0; i < m; i++) {
		int area = maxAreaInHist(height[i]);
		if (area > maxArea) {
			maxArea = area;
		}
	}
 
	return maxArea;
}
 
private int maxAreaInHist(int[] height) {
	Stack stack = new Stack();
 
	int i = 0;
	int max = 0;
 
	while (i < height.length) {
		if (stack.isEmpty() || height[stack.peek()] <= height[i]) {
			stack.push(i++);
		} else {
			int t = stack.pop();
			max = Math.max(max, height[t]
					* (stack.isEmpty() ? i : i - stack.peek() - 1));
		}
	}
 
	return max;
}

  smallest rectangle containing all 0s and return its area.

   largest rectangle containing all ones and return its area.

  return the maxArea for any square or matrix containing 0s

  largest area of 0s and 1s and return the area


Report an error