CareerCup

Minimum number of swaps of chars in only one string to make two strings the same

Matrix conversion problem. For example, give a matrix
a: 1, b: 2.
b: 2, c: 3
Then converted into
a, b, c
1, 2, .
., 2,3

Implement a grep-like function. For example
[A1 + A2, B1 + B2, C1], grep (A = A1), is to return the result that contains A1,
For example, [A1, B1, C1], [A1, B2, C1].
More tricky can be grep (A = A1, A2, B = B1), so that is included (A1 || A2) & B1.

Given an array {a0, a1, a2, ... an, b0, b1, b2 ... bn},
Rearrange this array into {a0, b0, a1, b1, a2, b2, ... an, bn}
inplace, O (1) space

Suppose there is a map with N bikes on it and now we have N individuals,
Design an algorithm so that everyone can get the bike in the shortest distance

Given a string, at each time, you can move any one of the char to the front,
ask you to find the minimum such move to get the target string
example
source abc, target cba :
abc -> bac -> cba
return 2

Give you a bunch of light bulbs. Can flip a range of open change off, turn off open, and then asked to do so k times later, just ask you a light bulb is turned on or turned off, how to do

*e*er -> peter
**eue -> queue
**o
ma*
*p*a*e*
*erso*
***k*am*on
*ouse
*a*
*ur*
***igent

where there are 26 *, and we can fill all the stars in to form valid english words while using each letter once. Given this array and a dictionary how would you fill all the words in?

public string stringWrap (String text, int characters)

text is an input string, characters on behalf of the output of
each line up to the number of bytes
input

"Thank you for shopping at the XYZ store.\n Your order has been processed successfully.\n", 20
output：
        "Thank you for\n
        shopping at the XYZ\n
        store.\n
        Your order has been\n
        processed\n
        Successfully.\n"

example 2:"Hello! How are you?"，6
output
“Hello!\n
How\n
are\n
you?\n"

Modify the following code:

def GenerateGraph(data):
    d = {}
    g = Graph()
    for word in data:
        for i in range(len(word)):
            bucket = word[:i] + '_' + word[i+1:]
            if bucket in d:
                d[bucket].append(word)
            else:
                d[bucket] = [word]

    for v in d.keys():
        for word1 in d[v]:
            for word2 in d[v]:
                if word1 != word2:
                     g.addEdge(word1,word2)
    return g

The objective is to find all combination of words by changing one letter at a time and adding to the graph if word exists in the dictionary.

We need to rewrite a different logic for the above code.

Give a string [] words,
Find the shortest string [] containing the keyword inside.
example:
words: sky cloud google search sky work blue
keywords: sky blue
return: sky work blue

Given an array, find the number of tuple such that A [i] + A [j] + A [k] = A [l] in an array, where i <j <k <l.

Given a n-nary tree, check whether it is a mirror of itself (ie, symmetric around its center).

class TreeNode {
int val;
List<TreeNode> children;
TreeNode(int val) {
this.val = val;
children = new ArrayList<>();
}
}

Imagine a scenario where there are N cars on an infinitely long single-lane road. Each car has a unique, permanent integer speed ranging between 1 and N, inclusive (units are irrelevant). The cars can be placed in any order along the road and then told to start driving indefinitely. Let's assume that the cars are traveling from right-to-left. So the leftmost car is at the front. Given an ordering of N cars, construct an algorithm to return an array of cluster sizes

N=4

[2, 4, 1, 3] -> [2, 2]

[2, 5, 4, 3, 1] -> [4, 1]

followup：
New car speed = N+1. Given an ordering of N cars, construct an algorithm to return an array of arrays of cluster sizes that will arise when the N+1 car is inserted. The ith row in the outer array corresponds to the cluster sizes that exist when the N+1 car is inserted into the ith index

new car speed = 5

[2, 4, 1, 3] -> [[1, 2, 2], [3, 2], [3, 2], [2, 3], [2, 3]]

Given one string s1, and then insert one char into this string at any place, to get s2, find the inserted char
Could you do it in logn time

Give you a 2xN board and two kinds of tiles: 1x2 (two squares across), 2x1 (two squares up) Ask how many ways you can fill the board.

**       **       *      *                                      
*         *        **   **

Follow up is the new four kinds of tiles: L shape in different angle, , ask you how many kinds of tiles are now six

give a binary matrix, 0 on behalf of the sea, 1 on behalf of the land, the val also represents the height of the altitude, if a cell is originally on land and is also surrounded by eight neighbor are on land, that cell become 2, each cell and its eight neighbor elevation cannot differ by more than 1. Return to the highest altitude can take altitude (special case is if the entire matrix is 1, then it is unlimited)

In the range of 0-n, return all the numbers that in the reverse can be mistaken for another number. E.g. 18 -> 81. The corner case is not counting the same number, such as 101 and not 0 at the end of the figure such as 60 (because 09 is not 9)
Public List<Integer> getNum(int n)

Given a function that reads 4096 bytes from a file. write a new function which takes in a buffer and the number of bytes to be read from the user and uses the given function to write values into the buffer.

//given
//returns the number of bytes read
private int read4k(int[] buffer, int offset)


//TODO:
// it should return the bytes read
public int readIntoBuffer(int[] buffer, int byteCount);

Give a binary tree, each node has an extra information, that is, how many children he has,
Find the kth node val in the inorder transversal ,
Followup how to insert a node, such that this newly added node become the Nth node of the inorder binary tree's traversal

class TreeNode{
    int val;
    int NumberOfchildren;
    TreeNode left;
    TreeNode right;
    public TreeNode(int val){
        this.val = val;
    }
}
public static int findKthOfInorder(TreeNode root, int k) {

Give a weighted n-nary tree and find the longest path from the root node to the leaf node
    class Node {
        int id;
        // connected node id, edge weight
        Map <Integer, Integer> edges;
    }

Google
1st round
Given a box with N balls in it, each ball having a weight, randomly choose pick one out base on the weight.
Input ball1-> 5kg, ball2 -> 10kg and ball3 -> 35kg,
then Prob(ball1 chosen) = 10%, Prob(ball2) = 20%,
Prob(ball3) = 70% ;

Follow-up:
Select a ball randomly based on weights. Once a ball is chosen, remove it. Next time select from the remaining balls. Go on until there is nothing left in the box.

Given a binary matrix, count the number of square that can be formed by all 0s

given a string p, called order, such as abc, means a in front of b, and so on
given a second string s, to determine whether it is follow the order of p, return boolean,
example If aaa return true,
If cba is false
If aaxyc is true, the letters that have not been seen in the order are skipped

Find whether string S is periodic.
Periodic indicates S = nP.
e.g.
S = "ababab", then n = 3, and P = "ab"
S = "xxxxxx", then n = 1, and P = "x"
S = "aabbaaabba", then n = 2, and P = "aabba"

follow up:
Given string S, find out the P (repetitive pattern) of S.

Given a string as a datastream Iterator<Character>, find the length of the longest substring without repeating characters

public String longestUniqueChars(Iterator<Character> chars)

Giving start string and end string, determine if start string can finally reach to the same as end string with below rules.
For example:
"R L _ _ L R L"
"_": the space is empty
"L": this can only swap with the empty letter _ on its left side
"R": this can only swap with the empty letter _ on its right side
So, "R L _ _ L R L" can change to "R L _ L _ R L" , and can continue change to (if you want) "R L L _ _ R L". from: 1point3acres.com/bbs
The question is given these rules and the start string and end string, could we change the start string to end string (unlimited # moves as long as it is valid).
For example:
"R _ _ L R _ R _L"
can be changed to
"_ R L _ _ R R L _"

Round3 Google
For N light bulbs , implement two methods
I. isOn(int i) - find if the ith bulb is on or off.
II. toggle(int i, int j) - i <= j. Switch state (switch on if it's off, turn off if it's on) of every bulb in range i to j.
All bulbs are off initially.

given a list of points in a rectangular coordinate system, seeking any two points, such that all the remaining points will be in only one side of the line.

Give a string, finds all duplicate substrings of length k