CareerCup

You have to implement the following function:
int MinColoring(int k, char* str);int MinColoring(int k, char* str);static int MinColoring(int k, String str) {}static int MinColoring(int k, string str) {}
The function takes a string 'str' of size 'n' and an integer 'k' as its arguments and returns the minimum no. of paint operation required to achieve the final colored sequence as represented by 'str'.
A paint operation is defined as coloring exactly 'k' consecutive balls out of 'n' balls with a single color.
Assumptions:
n > 0
0 < k <= n
Note:
Paint operation always starts from the ball at index 0
Any ball can be repainted any no. of times
Each character in 'str', represented by small letter alphabets, denotes the final coloring of the ball at that index
If the colored sequence cannot be obtained by any no. of paint operations, return -1
Paint operation can not be performed for less than 'k' balls

Example:
Input:
k: 3
str: rrggg
Output:
2
Explanation:
Since we can color 3 balls at a time, we can first color the balls {0, 1, 2} with color "r". Next, we can color the balls {2, 3, 4} with color "g". As a result, color sequence of the ball will be rrggg. And this was achieved in 2 paint operations.

Generate a random MxN starting board. It cannot have 3 or more pieces in a
row (horizontally or vertically) of the same color. K colors.

Robot walked from the upper left to the lower right, can only go down and to the right, the number of each grid is height,
If the next cell height is higher than the current, we must pay the difference cost, otherwise no cost,
Find the minimum cost to reach the lower right corner,
Follow up 1, print the minimum cost path;

Gas station problem, give you a starting point A and End B. An array of oil prices at each gas station index represents the location of each gas station. MPG = V, find the minimum cost of gas from A to B

given a string, and integer k, check if this string contain all the binary string of length k
For example, k is 2, then 00,10,01,11.
Followup 1, find a string that can contain all binary string of length k.
Followup 2, find a shortest string that can contain all binary string of length k.

Expression evolution
expr :: = int | '(' op expr + ')'
op :: = '+' | '*'
Cite a few examples:
"3" -> 3
"(+ 1 2)" -> 3
"(+ 3 4 5)" -> 12
"(+7 (* 8 12) (* 2 (+ 9 4) 7) 3)" -> ...
Public int getValue(String s){
}

Insert a number into an array of sorted intervals.
For example, [1,4], [6,8], after insert 5, return [1,8].
class Interval{
	int start;
	int end;
	public Interval(int start, int end){
		this.start = start;
		this.end = end;
	}
}
class Solution{
	public List<Interval> insert(List<Interval> list, int val){
		 
	}
}

give a bunch of job dependency, such as A-> B, A -> C, B-> D, and so on, implement two interfaces.
The first one is get_next_stage, which returns jobs in parallel for the next phase. The second is job_done, which tells you which job completed.

determine whether a number is the sum of two squares, such as 17 = 16 +1

Give a matrix, for example
1 0 0 1 0
0 0 1 0 1
0 0 0 1 0
1 0 1 0 1
Find if there is a rectangle in the matrix, all four corners are 1
For the example,  there is only one rectangle, that is
1 0 1
0 1 0
1 0 1

class DirectedGraphNode {
int label;
List<DirectedGraphNode> neighbors;
DirectedGraphNode(int x) {
label = x;
neighbors = new ArrayList<>();
}
}

check if there is a cycle in a directed graph, if there is a cycle, remove all the cycles

Sachin wants to buy a laptop for programming. he plans on buying a laptop whose price is made of digits 4 and 7 only. The number of 4s and 7s in the price should be equal. You are given laptop brand names and their prices. Find and print the name of the laptop brand that satisfies the above criteria. If there are multiple brands that meet the criteria, print the name of the one with the minimum price. If none of the laptops meet the criteria print -1.

For example, if Sharon has a choice between laptops 'BestBook' priced at 444777 and 'LapBook' priced at 7744, the solution should indicate ideal choice to be 'LapBook'. Although both 'BestBook' and 'LapBook' have equal number of 4s and 7s in the price, 'LapBook' is priced lower which makes it the right choice for Sharon.

You are given a binary tree and a function shouldBeErased(node to check whether a node should be erased. Erase all nodes that should be erased in the binary tree and return the resulting forest in the form of an array of every root node.

Follow up:

What if this is a Binary Search Tree? (In this case you are given a list of nodes that should be erased instead of the function.) Does it make the problem simpler or more complicated or just the same?

given a string and a segmentation length k
For example:
"This is a good day" k = 10
Cut into:
"This (1/4)"
"is a (2/4)"
"good (3/4)"
"day (4/4)"
Each line followed by a suffix in the form of (i/n) has 10 chars including space (except for the last line), return the minimum cut required, for the example, just return 4.

trie search, Search Return all words that match the wildcard *
such as
add ("car")
add ("caw")
add ("cauw")
search ("c*w") returns "caw" and "cauw".

There are n bus lines, known bus stops by bus, the bus is bi-direction, ask from station A to station B at least a few transfers.

given a binary array, you can flip 0 -> 1 or 1 -> 0 to make all the 1  
are in the left part and all the 0 to the right part, return the minimun flip required
example 1
 1011000  -> 1111000 only need one flip 0 -> 1
 example 2
 00001 -> 10000 require 2 flips
 public int findMiniFlip(int[] nums) {
        
    }
}

the longest unique value path in a graph
/**
* Definition for undirected graph.
* class UndirectedGraphNode {
* int label;
* List<UndirectedGraphNode> neighbors;
* UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<UndirectedGraphNode>(); }
* };
*/
public class Solution {
public int findLongestUniqueValuePath(List<UndirectedGraphNode> node) {

}
}

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]

Given an array of length n + 1, containing elements 1 through n and a space,
Requires the use of a given swap (index i, index j) function to sort the array,
You can only swap the gap and a number, in the end, put the gap at the end

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 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)].

Design a SparseVector class that implements
Vector interface, which contains 4 methods: get(int index),
increment(int index, int delta), numNonZeros(), and dotProduct(Vector other)

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){
}

give an enum, where each element has a parent-children relationship, and children's expression is the value of parent append an index, such as
enum vehicle {
         car = 1
             toyota = 11
                  camry = 111
                  corolla = 112
             honda = 12
        truck = 2
             GMC = 21
}  

Ask a value, return to his parent, such as GMC = 21, return to the truck

Given a list points on a 2d plane, find
largest rectangular area that can be formed
for the rectangle only considers those parallel to x and y

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)