LinkedIn Interview Questions

 Question: Binary Search Tree Iterator

Question: Binary Tree Level Order Traversal

Question: Find The Celebrity

Question: House Robber

Question: Insert Interval

Question: Lowest Common Ancestor Of A Binary Tree

Question: Maximum Depth Of A Binary Tree

Question: Maximum Product Subarray

Question: Maximum Subarray

Question: Merge Intervals

Question: Merge K Sorted Lists

Question: Minimum Window Substring

Question: Paint House

Question: Palindromic Substrings

Question: Permutations

Question: Power Of X To The N

Question: Product Of Array Except Self

Question: Search In Rotated Sorted Array

Question: Sparse Matrix Multiplication

Question: Symmetric Tree

Question: Two Sum

Question: How to find if nodes in graph are exactly 1/2/3 edges apart. how would you distribute graph across machines.

Question: Given set of characters and a string, find smallest substring which contains all characters.

Question: You have bunch of numbers coming in, and a given a window size, how would you save numbers so that you can return number if present in window and provide average for current window. 

Question:  Manager round: You are given bunch of machines with services running on them, how would you improve things. very vague design talk.

Question: Reverse words in a string.

- Implement decimal to roman and vice versa.

Question: Implement double pow(double a, int b) without using any already built-in functions (aka, don't use an already defined pow function).  

Question: Given two (dictionary) words as Strings, determine if they are isomorphic. Two words are called isomorphic if the letters in one word can be remapped to get the second word. Remapping a letter means replacing all occurrences of it with another letter while the ordering of the letters remains unchanged. No two letters may map to the same letter, but a letter may map to itself.

Example:

Given "foo", "app"; returns true

   we can map 'f' -> 'a' and 'o' -> 'p'

Given "bar", "foo"; returns false

   we can't map both 'a' and 'r' to 'o'

Given "turtle", "tletur"; returns true

   we can map 't' -> 't', 'u' -> 'l', 'r' -> 'e', 'l' -> 'u', 'e' -'r'

Given "ab", "ca"; returns true

   we can map 'a' -> 'c', 'b'  

Question: the deepest common ancestor of two nodes of a tree

Question: all permutations of a string.

Question: Print a tree like reading a book, left to right.

Question: Write a function that, given a list of integers (both positive and negative) returns the sum of the contiguous subsequence with maximum sum. Thus, given the sequence (1, 2, -4, 1, 3, -2, 3, -1) it should return 5. 

Question: Write a program that takes an integer and prints out all ways to multiply smaller integers that equal the original number, without repeating sets of factors. In other words, if your output contains 4 * 3, you should not print out 3 * 4 again as that would be a repeating set. Note that this is not asking for prime factorization only. Also, you can assume that the input integers are reasonable in size; correctness is more important than efficiency.

PrintFactors(12)

12 * 1

6 * 2

4 * 3

3 * 2 * 2  

==>void printFactors(multiset &set1, int number)

{

    for(int i = number/2; i>=2;i--)

    {

        int quotient = number % i;

        if(quotient == 0)

        {

            int result = number / i;

            set1.insert(result);

            set1.insert(i);

            if(!resultSet.count(set1))

                resultSet.insert(set1);

            set1.erase(set1.lower_bound(i));

            printFactors(set1,i);

            set1.erase(set1.lower_bound(result));

        }

    }

}

Question: find number in rotated sorted array, like: find 3 in "4,5,1,2,3".  

Question: Power of a number. Wrote a logn algorithm directly

Question: Level order traversal

Question: Permutations of an array of numbers. Wrote a recursive algorithm 

Question:  Print binary tree level by level

Question:  Find distance between words in a string

  eg: String = "I am a good girl" distance between "I" and "good" is 3  

Question: return n closest points on a plane

 Question: Check if a String contains a number or not  

Question: Program an iterator for a Linked List which may include  nodes which are nested within other nodes. i.e. (1)->(2)->(3(4))->((5)(6). Iterator returns 1->2->3->4->5->6

Question: Implement an algorithm to convert an integer into a roman numeral string and vice versa.  

Question: implementing hash table (using array and BST)

Question:  linked list reversal

Question:  LRU cache

Question:  find median of stream of integers in O(1) time

Question:  file iterator hasnext() and next() function  

Question:  implement BFS

Question:  Given a nested list of integers, returns the sum of all integers in the list weighted by their depth

 * For example, given the list {{1,1},2,{1,1}} the function should return 10 (four 1's at depth 2, one 2 at depth 1)

 * Given the list {1,{4,{6}}} the function should return 27 (one 1 at depth 1, one 4 at depth 2, and one 6 at depth 3)

 */

int depthSum (NestedInteger *input, int count)

{}

/**

 * This is the interface that represents nested lists.

 * You should not implement it, or speculate about its implementation.

 */

class NestedInteger

{

    /** @return true if this NestedInteger holds a single integer, rather than a nested list */

    boolean isInteger();

    /** @return the single integer that this NestedInteger holds, if it holds a single integer

     * Return null if this NestedInteger holds a nested list */

    Integer getInteger();

    /** @return the nested list that this NestedInteger holds, if it holds a nested list

     * Return null if this NestedInteger holds a single integer */

    NestedInteger *getList();

    int getCount();

}  

Question:  print factors for number 

Question: Merge two sorted lists

Question:  Three segments of lengths A, B, C form a triangle iff

     *

     * A + B > C

     * B + C > A

     * A + C > B

     *

     * e.g.

     * 6, 4, 5 can form a triangle

     * 10, 2, 7 can't

     *

     * Given a list of segments lengths algorithm should find at least one triplet of segments that form a triangle (if any).

     *

     * Method should return an array of either:

     * - 3 elements: segments that form a triangle (i.e. satisfy the condition above)

     * - empty array if there are no such segments

     */

    int[] getTriangleSides(int[] segments);

}  

Question: Write a function to determine if a string is a number without using any built-in function. Create an isNumber(string) function. Handle signed / unsigned, floating point, any number of digits, etc. Probably commas, and currency signs, or whatever. It was open ended and governed by whatever unit tests he wanted you to make it work against.

Question: Given a maximum line length, left right justify a long string. (make spaces evenly distributed between adjacent words)  

Question: Find maximum consecutive sum of array

Question: print a tree in level order.  

Question:  given a target and a sorted array, find the element that is strictly (just larger) larger than the target.

i.e. {a,c,d,e} b output: c

Question:  find the max sum of continuous sequence in the array.

{2,-1,3,-5,3} output: 4

Question:  given a DNA sequence find pattern (hardest problem that you probably won't be expected to finish)

Question:  given intervals find overlap and return the length. (it is surprising how easy to make mistakes in this one)

Question: Given an input string and a target string, find the minimum substring of the input string that contains all of the characters in the target string

Question: How to implement a non-blocking queue for multi-threading? How to implement a non-blocking task scheduler for multiple tasks?  

Question:  Stack with min

Question:  Stack with Max

Question: subarray with maximum sum  

Question: lowest common ancestor of tree if there is a parent pointer, what if without parent pointers

Question:  implement a hashtable and make it thread-safe  

Question: Implement a function which modifies a binary tree so that the output is a mirror of the input.

Question:  For a given array find the maximum size palindrome subset. The subset may be not continues.

    For input 1, 2, 4, 5, 1 the answer is 3, the subset is 1,2,1  

Question: Flowerbed problem  

Question: Given an array of numbers and a target value, return indices for numbers in the array which sum to this target value

Question: Given a string, return a boolean value for if it is a valid number  

Question: Find the number of possible permutations of paths given n number of stairs and 1, 2 or 3 stairs jump

Question: implement a HashMap with primitives 

Question:  find all the palindromic subsequence

Question: Given an array of integers, write a function that will produce a random permutation of the input array

Question: Given two linked lists that could potentially have a merge—i.e., at some point during one of the linked lists, the next node is a node in the other list—write an algorithm that determines if two lists merge or not. The lists could also potentially contain a cycle—i.e., an element can loop back around to the head.  

Question: Find if string is numeric

Question:  Edit distance using recursion and dp 

Question:  Binary search on a sorted array that has been shifted left

Question: design the blacklist. and implement hashmap

Question: longest common subsquence problem

Question:  Implement kmeans for a collection of 2d points.  

Question: Given an array of words and a length L, format the text such that each line has exactly L characters

Question: The system contains N points. Given a point and a value k, find the k closest points in the system.  

Question: Find element in rotated array (has duplicate) Find minimum in rotated array(has duplicate)  

Question: sorted character array return next largest character for given input character, e.g., {c,f,g,h,k} i/p c o/p f  

Question: Valid Perfect Square 

Question: Design and implement a data structure that can insert, remove, and randomly select an item all in constant time. 

Question: Serialize a binary tree 

Question: Find a triangle in a list of random numbers (a triangle is three numbers such that no one number is larger than the other two numbers added up)

Question: Find all the permutations of a string 

Question: How would you find the greatest depth in a binary search tree?  

Question: Print all level or binary tree line by line. Follow up: reverse every other line.

Question:  Write a method to justify a Paragraph

Question: merging intervals

Question:  serialize and deserialize a binary tree

Question:  Edit distance

Question:  co-linear points in a plane  

Question: Asked about determining if a given string is a number, and the second question was to find the max sum sub array given an integer array

Question: determine if a graph is bipartite 

Question:  implement LRU cache

Question: Check if an element is present in a completely sorted 2D array

Question: Reverse words in a sentence 

Question: given an article, output in a format that for each line, spaces between words are equal. (If impossible, how to deal with)  

Question: Find maximum successive sum in a array  

Question: given strings like +77288.100, a772sb, 2000.00.11. return if it's a number. you could either write a regular expression or simply go through the string.

1. it should start with "+/-" or "0-9".

2. there should only have one "." in the string.

3. all other character are "0-9"

that's it.  

Question: Implement Java Iterator interface in a question that requires a tree traversal-like algorithm.  

Question: Reverse a linked list 

Question: Find if a pattern can be found in a longer string (KMP, Boyer-Moore, or Rabin-Karp)

Question: Find the number of connected components

Question: Shuffle array

Question: reverse a binary tree

Question: Write an algorithm that determines whether or not two binary trees are equivalent

Question: Given initial and final positions, shortest path for a knight to move in a chess board. 

Question: Write a program that takes in a string and line length T as inputs and returns the string in justified form with each line of length T.  

Question: How to find if nodes in graph are exactly 1/2/3 edges apart. how would you distribute graph across machines.

Question: You have bunch of numbers coming in, and a given a window size, how would you save numbers so that you can return number if present in window and provide average for current window.

Question:  Implement decimal to roman and vice versa.

Question: What is the optimization problem for a SVM?  

Question: Seemed every interviewer asked a variant of an A/B test for the homepage. 

Question: Given a random generator that produces a number 1 to 5 uniformly, write a function that produces a number from 1 to 7 uniformly or something like that.  

Question: sampling question which is quite similar to Reservoir sampling

Question: A/B testing

Question: Segment a long string into a set of valid words using a dictionary. Return false if the string cannot be segmented. What is the complexity of your solution?

Question: find out k most frequent numbers from incoming stream of numbers one the fly. 

Question:  largest subsequence given an array that yields the largest sum. The second question was a modification of the first that required me to find the largest subsequence of the given array that yields the largest PRODUCT. 

Question: Code a non blocking thread safe queue

Question: Parse the IP in a file

Question: Implement a busy queue.

Question: find coverage of a bunch of intervals.... like given [1,4),[-2,3),[9,10) return 7

Question: given an array of integers A[1..n], make a new array B[1..n] where B[i] is the product of every thimg in A excluding A[i]. O(n) solution without division.