25 Dec 2011

Right now I'm preparing for a phone interview from Facebook.

I have done all questions from XORSwap

They are not that difficult. I code on average 10 mins for each question.

I'll practice more questions from Glassdoor.

Here are the questions:

Coding Problems

“3SUM problem”

“Write a class providing an LRU cache”

“FInd the maximum sum of a sub-sequence from an positive integer array where any two numbers of sub-sequence are not adjacent to each other in the original sequence. E.g 1 2 3 4 5 6 –> 2 4 6”

“Compute the square root of a number down to a certain precision. ie sqrt(num, precision) returns a number that is in-between sqrt(num) - precision and sqrt(num) + precision.”

“Find the min and max in an array. Now do it in less than 2n comparisons. (they were looking for the solution that finds both max and min in about 3/2 n comparisons).”

“Given a tree, print the values contained at each level on the same line. So if you had the tree with root A, and children B and C, you would print: A B C”

“Given an array of integers, now we want to erase all 0's (can be other value), and we want the result array condensed, meaning no empty cell in the array.”

“Find a needle in the haystack: given two c-strings (null terminated), return a pointer to the location of where the needle occurs in the haystack, NULL otherwise.”

“given a list of words with a same size and a big string that contains one of the permutation of all the words combined(say p), find the startindex of the string p in the big string”

“given a set of words, return a set of anagrams . example : abc , cba , def, fed answer : (abc , cba) , (def , fed)”

“given a string, print every pair of consecutive characters example : abcd –> ab, bc, cd”

“Write the actual code to parse a regular expression including “*“, which stands for 0 or more characters, “+“, which stands for 1 or more characters, and “.“, which stands for 1 exact character.”

“print out all prime numbers in a given string. abc2134kd31 -> 2, 13, 3, 3”

“Implement division without using multiplication or division. It should work most efficient and fast.”

“Implement a suggestion function that generates alternative strings for given password strings like “facebook” => “F@ceß00k” and “fæc€Bo0K” or sth.”

“Implement a function string balanceParanthesis(string s); which given a string s consisting of some parenthesis returns a string s1 in which parenthesis are balanced and differences between s and s1 are minimum. Eg - “(ab(xy)u)2)” -> “(ab(xy)u)2” “)))(((” -> ““”

“Implement a function rotateArray(vector<int> arr, int r) which rotates the array by r places. Eg 1 2 3 4 5 on being rotated by 2 gives 4 5 1 2 3.”

“Given a Binary Search Tree, iterate over the elements without using recursion.”

“Given a set of non-overlapping integer ranges (1,3) (5,8), etc., and an input integer, what is the best way to organize the data and allow for quick search based on the input, etc.”

“Given a telephone number, find all the permutations of the letters assuming 1=abc, 2=def, etc.”

“Given a string, remove all the duplicate characters (not necessarily consecutive)”

“Given a set of words, group them into sets of anagrams.”

“Convert a binary search tree to a sorted, circular, doubly-linked list, in place (using the tree nodes as the new list nodes).”

“Print a singly-linked list backwards, in constant space and linear time.”

“Given a list of n objects, write a function that outputs the minimum set of numbers that sum to at least K. FOLLOW UP: can you beat O(n ln n)?”

“Write a function to prettify Json objects”

“Given sorted arrays of length n and 2n with n elements each, merge first array into second array.”

“Explain in detail what a hash table is, how would you implement it, what would be a good hash function, and when is it good to use a hash table.”

“Write a function that finds the minimum and maximum values within an unsorted array using divide-and-conquer.”

“Given a String containing java-script assets, write a parser which will output the String with proper indentation.”

“Print a binary tree in infix order. Recursive and iterative.”

“Fibonacci Numbers - Iteratively and Recursively”

“How would you implement a method to tell whether or not a string matches a regex that consists of lower case letters and *s.”

“You are trying to rob houses on a street. Each house has some +ve amount of cash. Your goal is to rob houses such that you maximize the total robbed amount. The constraint is once you rob a house you cannot rob a house adjascent to that house.”

“Given a matrix print it clockwise from the first element to the very inner element.”

“You are going to take some numbers as an input from a file. You need to write a program to find longest increasing sequence. You should process it as soon as you are taking an input. After finishing the last input immediately you should be able to tell the sequence. Input: 1 5 3 4 6 4 Output: 3 4 6”

“Given a set of integers, print out all its subsets. Write C/C++ code to solve it.”

“First question: for a random-ordered bucket of numbers 1 through 3000 with one number missing, how would you detect which number is missing?”

“Please write a program to merge 2 sorted arrays”

“Given a string, remove all chars from the string that are present in say another string called filter.”

“Given two binary trees, return true if they have same elements (irrespective of tree structure)”

“Implement stack using a queue”

“Print out all combinations of k numbers out of 1…N e.g. when k = 2, n = 4 Print out 12, 13, 14, 23, 24, 34”

“25 racehorses, no stopwatch. 5 tracks. Figure out the top three fastest horses in the fewest number of races.”

“Write a list class where the only data structure available is a stack”

“Given a function for a fair coin, write a function for a biased coin that returns heads 1/n times (n is a param).”

“Given a score S, and individual points p1,p2,…,pn. give all combinations of p that add up to s.”

“How do you find sequences of consecutive integers in a list that add to a particular number.”

“Write a function that takes in an integer and returns the number of ones set in the binary representation.”

“Find the first letter in a string that does not have a pair.”

“Given a binary tree, print out the elements in order. Without recursion.”

Conceptual Questions

“Open-ended systems/design question on storing and searching zillions of status updates”

“What do you see as fb's biggest challenge in the next 5 years?”

“Design a system to detect typos and provide suggestions to users.”

“Design and implement an algorithm that would correct typos: for example, if an extra letter is added, what would you do?”

“Design the Facebook Credit system which is a application where users can buy/trade virtual currency and can use the virtual currency to purchase Facebook services, like paid apps.”

“Given a 1TB file of serialized 4 byte integers, and 2GB of ram, sort the integers into a resulting 1TB file. My interviewer was very collaborative in entertaining various solution ideas until we came up with a combo that would work performantly and reduce the number of passes over the 1TB file and intermediate files.”

“A file contains 10 billions of Strings and need to find duplicate Strings. You have N number of systems available. How will you find duplicates?”

“Suppose you have a matrix of numbers. How can you easily compute the sum of any rectangle (i.e. a range [row_start, row_end, col_start, col_end]) of those numbers? How would you code this?”

“Given the numbers 1 to 1000, what is the minimum numbers guesses needed to find a specific number if you are given the hint “higher” or “lower” for each guess you make.”

“You have two lightbulbs and a 100-storey building. You want to find the floor at which the bulbs will break when dropped. Find the floor using the least number of drops.”

“Explain the difference between a LEFT and RIGHT SQL JOIN”

“How can you possibly do technical management if you're a very strong senior engineer?”

“You have a database with n normalized tables (the schema for which are shown on the board). The CEO complains that a particular daily report generated from it “is slow”; how would you deal with this issue?”