Facebook Interview Question for Software Engineer / Developers


Country: United States
Interview Type: In-Person




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

1. binary-search (O(log(n)). If citations[i] >= i then h >= i (if array's in descending order).
2. Here's a O(n) time & space solution in ruby. The trick is you can ignore citation-counts larger than n.

# citations: array of integers. citations[i] = num citations on paper i.
# O(n) time & space
def h_count_unsorted(citations)
  
  # h_count <= max citations on a paper, number of papers
  max_h_count = [citations.size, citations.max].min
  
  # tally the number of papers w/ each number of citations
  # note: if we use max_h_count instead of (max_h_count + 1), we need
  # to add a little more (ugly) logic to ignore papers w/ zero citations
  tallies = Array.new(max_h_count + 1, 0)
  citations.each do |num_citations|
    # round num_citations down to the max allowed value, if necessary
    tallies[[num_citations, max_h_count].min] += 1
  end
  
  # compute h_count
  sum = 0
  max_h_count.downto(1) do |i|
    # num papers w/ at least i citations = the sum of tallies for >= i citations
    sum += tallies[i]
    if sum >= i
      return i
    end
  end
end

- Cole September 07, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
2
of 4 vote

If there are 'n' papers in total, this problem can be solved in O(n) with space complexity of O(n). Note that, h-index can be between 0 to n. Say if the h-index is 10, this means, there has to be 10 papers with citation count >= 10. So if we can find out the number of papers with citations >=X for every X (and store it in an array C) where X ranges between 0 to n, then by scanning the count array C from the right to left, we can find the h-index at index i where i == C[i].

Pseudocode:
input array A of length n.

- init array C[0] to C[n] with 0
- foreach p in A, if p >= n, c[n]++; else c[p] +=1
- for i=n-1 to 0, c[i]=c[i]+c[i+1]
- for i=n to 0, if c[i] == i return i

- sachin September 07, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

@sachin: your solution is correct but not O(n) as asked in the question.

- Abhishek September 07, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Abhishek, why is it not o(n)?

- Anonymous September 07, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Sorry..My bad...The solution is indeed O(n)

- Abhishek September 07, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

In the last line,
'for i=n to 0, if c[i] == i return i"
should be ".. if c[i]>=i..".
Nice solution!

- AR November 04, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Binary search for the first part as mentioned by @gnahzy:

public static void main(String[ ] args) {
int [ ] sortedCitation = {21, 17, 12, 2, 2, 1};
System.out.println("The h-index value is: " + getHindexFromSorted(sortedCitation));

}

private static int getHindexFromSorted(int[ ] citation) {
int low = 0; int high = citation.length - 1;
int idx = (low+high)/2;
while(low <= high) {
if(citation[idx] >= idx + 1) {
low = idx + 1;
}
else {
high = idx - 1;
}
idx = (low+high)/2;
}
return idx + 1;
}

- Abhishek September 07, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Cole's idea in Java:
private static int getHindexFromUnsorted(int[] citation) {
int[] hindex = new int[citation.length + 1];
for (int i = 0; i < citation.length; i++) {
if (citation[i] >= citation.length) {
hindex[citation.length]++;
} else {
hindex[citation[i]]++;
}
}
int count = 0;
for (int i = hindex.length - 1; i > 0; i--) {
if (i >= count) {
count += hindex[i];
}
}
return count;
}

- Abhishek September 07, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

1. we can solve this use binary search, which is O(logN).
2. implement @Cole 's idea in python, which is O(n)

def get_hindex_unsorted2(array):
	# the trick is the h index can not be greater than either the size of the array
	# or the max citation in the paper list.
	max_hindex = min(len(array), max(array))

	# citations[i] = the number of paper with citation being i
	# for citation > max_hindex, we will put it into citations[max_hindex]
	citations = [0] * (max_hindex + 1)
	for x in array:
		citations[min(x, max_hindex)] += 1
	
	# paper count = the number of papers with citations greater than i
	paper_count = 0
	for i in range(max_hindex, -1, -1):
		paper_count += citations[i]
		if paper_count >= i:
			# we find more than i papers with citations greater than i
			return i

def get_hindex_sorted(array):
	return get_hindex_helper(array, 0, len(array) - 1)
	
def get_hindex_helper(array, left, right):
	assert left <= right
	
	if left == right:
		return min(len(array) - left, array[left])
	
	mid = (left + right)//2
	n = len(array) - mid 
	m = array[mid]
	#there are n papers whose citations are at least m.
	if n == m:
		return n
	elif m > n:
		return get_hindex_helper(array, left, mid)
	else: # n > m
		return get_hindex_helper(array, mid + 1, right)

- gnahzy September 06, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

For 2, can we use an adapted quick selection algorithm? Instead of searching k-th element, search the largest element a satisfying citation(a) >= num of elements with larger of equal citation.

- Anonymous September 07, 2012 | 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