I was flying home from San Francisco and had 2 hours to spare. I solved problems A and B which were enough to pass the qualification round.
Difficulty: Easy. This was a basic set theory check
Difficulty: Easy/Medium. This solution works for both small and large inputs.
My submitted solution was wrong, but here's the correct (hopefully) solution I came up with after my submission.
Problem: Facebook Hacker Cup 2013 Qualification Round: (45) Find the Min
Solution: Time complexity - O(k) O(k^2)
Problem: Facebook Hacker Cup 2013 Qualification Round: (35) Balanced Smileys
I participated in Facebook Hacker Cup again this year. I am currently ranked 160th out of 10,000 participants. I will go way down the list when the official results come out because I messed up the third question.
Problem: Facebook Hacker Cup 2013 Qualification Round: (20) Beautiful string
I had to write this by hand at an interview with a local company. Pretty sure I aced it.
Given a string, write a method to return all possible substrings of the string.
Solution: Complexity O(n^2).
Book: Cracking the Coding Interview
Question: 9.3 (page 109)
A magic index in array A[0...n-1] is defined to be an index such that A[i] = i. Given a sorted array, write a method to find a magic index, if one exists, in array A.
FOLLOW UP
What if values are not distinct?
Solution: Complexity - O(log(n))
Book: Cracking the Coding Interview
Question: 17.1 (page 163)
Write a function to swap [two numbers] in place (that is, without temporary variables)
Solution: Simple arithmetic trick. Also could be done using XOR (not sure if works with negative values, though.).
Book: Cracking the Coding Interview
Question: 11.7 (page 122)
A circus is designing a tower routine consisting of people standing top one another's shoulders. For practical and aesthetic reasons, each person must be both shorter and lighter than the person below him or her. Given the heights and weights of each person in the circus, write a method to compute the largest possible number of people in such a tower.
Input (ht, wt): (65, 100) (70, 150) (56, 90) (75, 190) (60, 95) (68, 110)
Output: The longest tower is length 6 and includes from top to bottom:
(56, 90) (60, 95) (65, 100) (68, 110) (70, 150) (75, 190)
Solution: Complexity - O(n^2)
Book: Cracking the Coding Interview
Question: 11.5 (page 121)
Given a sorted array of strings which is interspersed with empty strings, write a method to find the location of a given string.
EXAMPLE:
Input: find "ball" in {"at", "", "", "", "ball", "", "car", "", "", "dad", "", ""}
Output: 4
Solution: Average case: O(log(n)), Worst case: O(n/2) => O(n)
Book: Cracking the Coding Interview
Question: 11.2 (page 121)
Write a method to sort an array of strings so that all the anagrams are next to each other.
Solution: Complexity - O(nlogn) [because of TreeMap]
Book: Cracking the Coding Interview
Question: 11.1 (page 121)
You are given two sorted arrays, A and B, where A has a large enough buffer at the end to hold B. Write a method to merge B into A in sorted order.
Solution: Complexity - O(n)
Book: Cracking the Coding Interview
Question: 4.6 (page 86)
Write an algorithm to find the 'next' node (i.e, in-order successor) of a given node in a binary search tree. You may assume that each node has a link to its parent.
Solution: Complexity - O(n) in the worst case. Did not test the below code; it makes sense and it should work fine.
Book: Cracking the Coding Interview
Question: 4.3 (page 86)
Given a sorted (increasing order) array, write an algorithm to create a binary search tree with minimal height.
Solution: Complexity - O(n)
