CareerCup

Given a string s, break s such that every substring of the partition can be found in the dictionary.
Return the minimum break needed.
Example
Given a String CatMat
Given a dictionary ["Cat", "Mat", "Ca", "tM", "at", "C", "Dog", "og", "Do"]
return 1
we can break the sentences in three ways, as follows:
CatMat = Cat Mat break 1
CatMat = Ca tM at break 2
CatMat = C at Mat break 2
but the first way has the minimum break, thus return 1
public int wordBreak(String s, Set<String> dict) {
// Write your code here
}

Given a 2d grid map of '1's (land) and '0's (water), find the perimeter of each island. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

To determine if two graphs have isomorphism or not

Give an array A, find the (i, j) pairs that satisfy the condition.
Condition 1: A [j] = A [i] + 1, Condition 2: j - i is as large as possible
Followup condition 1 is changed to A [j]> A [i]

find a shortest string to cover all of a list of string,
For example, [aab, aabb, bc], should return aabbc,
because aab, aabb, bc are all the substring of aabbc

Given a linked list with next and random pointer, deepcopy the linked list and return new head.

Node {
char val,
Node next,
Node random }

A {
val: ’a’
next: D
random: G}

D {
val: ’d’
next: G
random: A}

G {
val: ’g’
next: null
random: D}


-----------
| |
| V
A -> D -> G -> null

-------------
| |
| V
A' -> D' -> G' -> null

Explain in detail about your favourite android api.

given 2 list of interval representing users online offline timestamp e.g (already sorted), find all intervals that both of users are online.

e.g A= [(3, 5), (7, 11)] B=[(2, 4), (9, 10)] --> [(3, 4), (9, 10)].

Facebook
-Phone: LC304 & longest arithmetic sequence. Return the sequence.

Given an array of integers and k, find the difference between the number of the strictly increasing number of subarrays (of size more than one) and the number of the strictly decreasing subarray in the window of size k. your method should be time and space efficent
example
int[] nums = {188930, 194123, 201345, 154243, 154243};
int k = 3;
Output
3, 0, -1
Explanation
For the first window of [188930, 194123, 201345], there are 3 increasing subranges ([188930, 194123, 201345], [188930, 194123], and [194123, 201345]) and 0 decreasing, so the answer is 3. For the second window of [194123, 201345, 154243], there is 1 increasing subrange and 1 decreasing, so the answer is 0. For the third window of [201345, 154243, 154243], there is 1 decreasing subrange and 0 increasing, so the answer is -1.
public int[] getdiff(int[] nums, int l){
}

There is an unordered interval stream, write a method, returns the total length that all intervals cover by now
class Interval{
 	int start;
	int end;
}
public List<Integer> countCoverLength(Iterator<Interval> stream){

}

‘.’Matches any single character,' * 'Matches any sequence of characters (including the empty sequence).
There are two input, one is string pattern, and the other is dictionary like dict = ["cat", "cats", "and", "sand", "dog"].
return a boolean: whether to find a dictionary in the pattern match the word
eg: dict = ["cat", "cats", "and", "sand", "dog"].
pattern = "* t", -> true (can match cat)
pattern = ".a *" -> true (can match cat, cats, can also match sand, because * can also express empty sequence)

How would you store and retrieve values in Memcache if the values are larger than the individual value size allowed by Memcache?

node {
node * left, * right;
}
Given a list of node to determine whether the node in the list can form a valid binary tree. several points of judgment
1. need to ensure that all left, right pointer point to the node inside list
2. no cycle
3. All node must be connected
Boolean isValidTree(List<Node> list){}

Given a matrix of N * M, given the coordinates (x, y) present in a matrix,
Find the number of paths that can reach (0, 0) from the (x, y) points with k steps (requires exactly k, k> = 0)
From each point you can go up, down, left and right in four directions.

For example, the following matrix:
----------
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
(x, y) = (1, 1), k = 2, the output is 2

Find all words [A-Z] in a dictionary (about 1M words) that are made of a subset (in any order) of the chars in the input parameter [A-Z].
ex: input "ACRAT" (10 to 20 chars, up to 30 worst case)
matching words: "A", "CAR", "ACA", "ART", "RAC".
non-matching words: "BAR", "AAA"

follow up : the input is a list of words. Return a list of words that each
list is formed by exactly the characters in the input list.
For example: two lists {“DEBIT”, “CARD”} and{“BAD”, “CREDIT”}
are formed by the same exact group of characters.

Given a sorted list of integers, square the elements and give the output in sorted order.

Find the distance between the farthest two elements in a binary tree.

Given a string separated by a space like "123456 abc+efg" determine
the solution by mapping integers to letters like a:1, b:2, c:3, d:4, e:5, f:6.
The only operations allowed were + or -. So the calculated solution
that made the tests pass was 123+456 = 579.

How many subsets of a given array sum to zero?

Given numbers 1 through 52, take 5 unique numbers and determine
if the number 42 can be made using any combination of addition (+),
subtraction (-), multiplication (*), and division (/) on those 5 numbers

/* Intersection of two sorted interval lists, A=[(1,2), (5,7)..]
B=[(2,6)...] return [(5,6)..] */

import java.util.*;
class Interval{
    int start;
    int end;
    public Interval(int start, int end){
        this.start = start;
        this.end = end;
    }
}
class Solution {
    
    public List<Interval> Intersection(Interval[] i1, Interval[] i2) {}

* Given a string on length N. You can swap only the adjacent elements
and each element can be swapped atmost once.
Find the no of permutations of the string that can be generated after
performing the swaps as mentioned.
Ex –
string – “12345”
Ans = 8
Explanations- (All the permutations)
12345
21345
13245
12435
12354
21435
13254
21354

Given an array of n positive integers, find the number of subarrays
such that product of the elements of those subarrays are less than k.
For eg. Arr= {2, 3, 6} k=10
No of such subarrays= 4

Print the levels of a binary tree in reverse order using stack and recursion

Given a binary tree, return the bottom-up level order traversal of its nodes' values. (ie, from left to right, level by level from leaf to root).

For example:
Given binary tree
    3
   / \
  9  20
    /  \
   15   7
return its bottom-up level order traversal as:
[
  [15,7],
  [9,20],
  [3]
]

public List<List<Integer>> levelOrderBottom(TreeNode root) {
}

given an array, find whether there exists 3 elements a,b,c in it such that a+b=c using efficient method.

You are provided a BST, which is corrupted. One of the nodes in it has 2 parents.
Let’s say those are parent 1 and parent 2. It is ensured that none
of these parents will be the ancestor of the other. Identify the node,
and remove the link of the wrong parent.

given an array of strings and characters, make the largest string possible.
The resultant string should be a combination of the strings given in the array.
The given array
of characters may contain repeated elements.
Example – Given char array – {a,a,b,c,d,d,e,c} and given strings
– {abba, aabc, de, cde} the
ans is aabccde

Given an adjacency matrix of a directed graph, find the number of cycles in the graph

Given K sorted (ascending) arrays. Write an iterator class that iterate over the arrays and returns the next element. Duplicate are allowed. What is the complexity to iterate the entire arrays? what is the complexity for each iteration?

Example:

arr1 = {1,2,3,4,7,9}
arr2 = {3,5,6,8,10}

The iterator should return:

1,2,3,3,4,5,6,7,8,9,10

Extension:
Don't return duplicates, so the above iterator should return:

1,2,3,4,5,6,7,8,9,10