## Linkedin Interview Questions

- 0of 0 votes
/**

* A tournament tree is a binary tree

* where the parent is the minimum of the two children.

* Given a tournament tree find the second minimum value in the tree.

* A node in the tree will always have 2 or 0 children.

* Also all leaves will have distinct and unique values.

* 2

* / \

* 2 3

* / \ | \

* 4 2 5 3

*

* In this given tree the answer is 3.

*/`class Node { Integer value; Node left, right; Node(Integer value, Node left, Node right) { this.value = value; this.left = left; this.right = right; } } class Solution { /** * This should return the second minimum * int value in the given tournament tree */ public static Integer secondMin(Node root) { } }`

- 0of 0 votes
Given a number n that represents n lockers and n students. All lockers start closed. First student goes and opens all the lockers. Second goes and toggles 2nd, 4th, 6th.. lockers. Third student toggles 3rd, 6th, 9th.. lockers. Print the lockers that remain open after all students pass.

`public void lockers(int n) { // Implementation here }`

- 0of 2 votes
How to randomly select a number in an array?

array: [15, 2, 4, 5, 1, -2, 0]

Follow-up:

Given a second array freq where freq[i] represents the occurrence of the ith number in array, how to randomly select a number in array based on the frequency.

Extra requirement:

Could you complete the selection in a single-pass(go through each array only once)?

- 1of 1 vote
/**

* Given a nested list of integers, returns the sum of all integers in the list weighted by their REVERSED depth.

* For example, given the list {{1,1},2,{1,1}} the deepest level is 2. Thus the function should return 8 (four 1's with weight 1, one 2 with weight 2)

* Given the list {1,{4,{6}}} the function should return 17 (one 1 with weight 3, one 4 with weight 2, and one 6 with weight 1)`*/ public int reverseDepthSum (List<NestedInteger> input) { // implementation here }`

- 0of 0 votes
Print an NxM matrix with nw-se diagonals starting at bottom left corner. Ex:

`1 2 3 4 5 6 7 8 9 10 11 12`

The output should be:

`9 5 10 1 6 11 2 7 12 3 8 4`

- 0of 0 votes
If you can hop 1, 2, or 3 steps at a time, calculate the total number of possible combinations for `n` steps.

- 0of 0 votes
public interface FirstCommonAncestor {

/**

* Given two nodes of a tree,

* method should return the deepest common ancestor of those nodes.

*

* A

* / \

* B C

* / \ \

* D E H

* / \

* G F

*

* commonAncestor(D, F) = B

* commonAncestor(C, G) = A

* commonAncestor(E, B) = B

*/

Node commonAncestor(Node one, Node two);

}`class Node { final Node parent; final Node left; final Node right; public Node(Node parent, Node left, Node right) { this.parent = parent; this.left = left; this.right = right; } boolean isRoot() { return parent == null; } }`

- 0of 0 votes
Find unique integers from list of integers

`# Question # Write a function that will return an array of integers that occur exactly once in a given array of integers. # e.g. For a list [1,2,3,5,2,2,3,4], return [1,5,4] since they appear once (order does not matter). def once_integers(integers):`

Follow up:

Optimize the code if input is sorted.`# What if the input is sorted, such as [1,2,2,2,3,3,4,5], could the algorithm be further optimized # (e.g. space complexity)? def once_integers_sorted(integers):`

- 0of 0 votes
String Rotation. Given two string check if String1 is rotating match for String2

`# Given two strings. Write a function that will return true if one string is a rotation of the other string. # e.g. 'bca' and 'cab' are rotations of 'abc' and the function should return true # 'barbazfoo', 'oobarbazf' and 'rbazfooba' are rotations of 'foobarbaz' def is_rotation(string1, string2):`

- 0of 0 votes
You are designing the client side of a Survey website. Provide the list of classes and methods you will use to break the problem down. Also, provide the API interaction with server.

- 0of 0 votes
Given an array of numbers find the duplicates

- 1of 1 vote
Suppose you have a list of Dishes, where each dish is associated with a list of ingredients. Group together dishes with common ingredients.

E.g:

Input:

"Pasta" -> ["Tomato Sauce", "Onions", "Garlic"]

"Chicken Curry" --> ["Chicken", "Curry Sauce"]

"Fried Rice" --> ["Rice", "Onions", "Nuts"]

"Salad" --> ["Spinach", "Nuts"]

"Sandwich" --> ["Cheese", "Bread"]

"Quesadilla" --> ["Chicken", "Cheese"]

Output: ("Pasta", "Fried Rice") ("Fried Rice, "Salad") , ("Chicken Curry", "Quesadilla") ("Sandwich", "Quesadilla")

Follow up: What is the time and space complexity?

- 0of 0 votes
Basic background questions, describe a situation where you proposed a design and it was opposed. What did you do to convince people that your design was sound. Describe a situation where something you suggested resulted in improved process or caused a big positive impact on the company, etc.

- 0of 0 votes
Implement a TwoSum interface that has 2 methods: Store and Test. Store adds an integer to an internal data store and Test checks if an integer passed to Test is the sum of any two integers in the internal data store. Once you provide an answer interviewer will ask the O complexity of the solution and ask you to optimize it.

I provided 2 solutions, one with O(n-square) and another O(n). However the O(n) solution used 2 internal data stores. I was asked to preserve O(n) but not use the second internal store`public interface TwoSum { /* * Stores input in an internal data structure. */ public void Store(int input); /* * Returns true if there is any pair of numbers in the internal data structure which * have sum val, and false otherwise. * For example, if the numbers 1, -2, 3, and 6 had been stored, * the method should return true for 4, -1, and 9, but false for 10, 5, and 0 */ public bool Test(int val); } public class TwoSumImpl : TwoSum { private List<int> _store = new List<int>(); private List<int> _sums = new List<int>(); public void TwoSumImp() { } //-3,-2,3,5,7 //-5,0,1,-2,-3,8, public void Store(int input) { if(!_store.Contains(input)) { _store.Add(input); } } public bool Test(int val) { for(int i=0; i<_store.Count;i++) { if(_store[i] < 0) //store[i] is negative { diff = val + Math.Abs(_store[i]); if(_store.Contains(diff)) { return true; } } else //store[i] is positive { diff = val - _store[i]; if(_store.Contains(diff)) { return true; } return false; } } }`

- 0of 0 votes
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.

Eg: PrintFactors(12) 12 * 1 6 * 2 4 * 3 3 * 2 * 2

- 0of 0 votes
Write a function that takes a string representing as value in roman numbers and returns it as an integer.

`Implement the following /** * * romanNumber("III") = 3 * romanNumber("IV") = 4 */ int romanNumber(String roman) { // ... }`

- 0of 0 votes
Write a function that takes a number and returns the square root

`Implement the following double sqrt(double d) { // ... }`

- 0of 0 votes
Given a stream of numbers write a program that computes sum of pair of numbers. There should be two methods store and IsNumberPresent. The store should store the numbers and IsNumberPresent should check if the number is present in the computed sums.

- 0of 0 votes
Implement following interface so that multi-put is atomic. Expect multiple producers and consumers inserting to and extracting from this queue implementation.

/**

* threadSafe bounded blocking queue implementation. Expected to be used in a

* Producer->Consumer pattern

*/

public interface MultiPutBlockingBoundedQueue<E> {

/**

* Sets the capacity of the buffer. Can be called only once. If called more

* than once or if the passed capacity is <= 0, throw an exception.

*/

public void init(int capacity) throws Exception;

/**

* Get the next item from the queue throws Exception if not initialized

*/

public E get() throws Exception;

/**

* Put the item to the tail of the queue. throws Exception if not

* initialized

*/

public void put(E obj) throws Exception;

/**

* Put the list of items in an atomic manner. The list can be more than the

* capacity throws Exception if not initialized

*/

public void multiput(List<E> objs) throws Exception;

}

- 0of 0 votes
Find the length of a maximum palindrome subset in an array. For example: in 1, 2, 4, 1 the maximum palindrome subset is 1, 2, 1 and the answer is 3

- 0of 0 votes
Implement a function which modifies a binary tree so that the output is the tree that is a mirror of an input tree

- 0of 0 votes
1) What is transaction

- 0of 0 votes
Given string say ABCGRETCABCG and substring length let us take length as 3, find the count of possible substrings, for example in above string ABC => 2 and BCG => 2 , where CGR and other 3 word length substrings has a count of 1.

- 0of 0 votes
Given a set of numbers find if a triplet can form a triangle a+b > c , b+c > a and c+a > b. The result to display all possible combinations of triplets. [ 10 5 3 4 7 1] [5,3,4 ] is one possible triplet and there can be many more.

- 0of 0 votes
For typical word ladder problem to get the shortest path, BFS has complexity exponential to the word string length. How to optimize?

- 2of 2 votes
Evaluate the value of an expression given in Reverse Polish notation

- 4of 4 votes
This question was asked in the Technical Design round.

How would you design a system to provide the top trending topcis in the last 5m/1hour/24hours

The most trending topic should appear first

A topic is said to be trending if it is shared the most. We are talking about a typical multi user environment (something like twitter, facebook).

- 1of 1 vote
This question was asked in the first coding round on-site.

Give two sorted lists List<Integer> a and List<Integer> b.

Find

the Union of these two lists -> the union list should also be sorted

the Intersection of these two lists -> Intersection list should also be sorted.

- 1of 1 vote
Those who've attended on-site interview with LinkedIn might know that there are 2 rounds of coding interviews. This question was asked in my 2nd round of coding interview,

Given two valid dictionary words of same length, write a function which returns the minimum number of steps to go from the first to the second word.

You can change only one character at a time. Also, the word formed at every step should be a valid dictionary word.

Eg: Provide minimum steps to go from 'cat' to 'dog'

cat -> bat -> bet -> bot -> bog -> dog

Ans: 5

- 0of 0 votes
Given a collection of pair representing intervals write a function which inserts new interval into collection and merges overlapping intervals.

Example:

[-10, -1], [0,2], [4,10]

insert [-5, 1]

output: [-10, 2], [4, 10]