CareerCup

Write a simple RegEx parser function that handles only the
operators * (0 or more) and + (1 or more), and returns true if
the provided string is a match. Signature:
boolean isMatch(String regex, String input).
Example: regex = a*b+ce, input = bce, return true
Example: regex = a*b+ce, input = ace, return false
Example: regex = a*b+ce, input = abcee, return false

Given a tree and a number N,
construct another tree such that each node of the tree has either 0 or
N elements,except for one node which has between 0 to N elements.
Only other constraint is
that ancestry is preserved in the new tree.

given start and end of a given set of meetings, asking how to schedule
as many meetings as possible。

find a points that has same distance to given three points

input is an int [] number is the car number parked in the parking lot, 0 for empty spaces
Output is also an int [] requires a method to convert the input into target array.
Each car can only be exchanged with a 0.

Given a string s1, we may represent it as a binary tree by partitioning it to two non-empty substrings recursively.

Below is one possible representation of s1 = "great":

    great
   /    \
  gr    eat
 / \    /  \
g   r  e   at
           / \
          a   t
To scramble the string, we may choose any non-leaf node and swap its two children.

For example, if we choose the node "gr" and swap its two children, it produces a scrambled string "rgeat".

    rgeat
   /    \
  rg    eat
 / \    /  \
r   g  e   at
           / \
          a   t
We say that "rgeat" is a scrambled string of "great".

Similarly, if we continue to swap the children of nodes "eat" and "at", it produces a scrambled string "rgtae".

    rgtae
   /    \
  rg    tae
 / \    /  \
r   g  ta  e
       / \
      t   a
We say that "rgtae" is a scrambled string of "great".

give a string s, print all the scrambled string of it

class Solution {
    public List<String> ScrambleString(String s) {
        
    }
}

The problem is to count all the possible paths from any points to bottom right of a mXn matrix with the constraints that from each cell you can either move only to right or down

We have two sequences A and B consisting of integers, both of length N, and you would like them to be (strictly) increasing, i.e. for each K (0 ≤ K < N − 1), A[K] < A[K + 1] and B[K] < B[K + 1]. Thus, you need to modify the sequences, but the only manipulation you can perform is to swap an arbitrary element in sequence A with the corresponding element in sequence B. That is, both elements to be exchanged must occupy the same index position within each sequence.

For example, given A = [5, 3, 7, 7, 10] and B = [1, 6, 6, 9, 9], you can swap elements at positions 1 and 3, obtaining A = [5, 6, 7, 9, 10], B = [1, 3, 6, 7, 9].

Your goal is make both sequences increasing, using the smallest number of swaps.

Write a function:

public int minswaps(int[] A, int[] B);

that, given two zero-indexed arrays A, B of length N, containing integers, returns the minimum number of swapping operations required to make the given arrays increasing. If it is impossible to achieve the goal, return −1.

For example, given:

A[0] = 5 B[0] = 1
A[1] = 3 B[1] = 6
A[2] = 7 B[2] = 6
A[3] = 7 B[3] = 9
A[4] = 10 B[4] = 9
your function should return 2, as explained above.

Given:

A[0] = 5 B[0] = 2
A[1] = -3 B[1] = 6
A[2] = 6 B[2] = -5
A[3] = 4 B[3] = 1
A[4] = 8 B[4] = 0
your function should return −1, since you cannot perform operations that would make the sequences become increasing.

Given:

A[0] = 1 B[0] = -2
A[1] = 5 B[1] = 0
A[2] = 6 B[2] = 2
your function should return 0, since the sequences are already increasing.

Assume that:

N is an integer within the range [2..100,000];
each element of arrays A, B is an integer within the range [−1,000,000,000..1,000,000,000];
A and B have equal lengths.
Complexity O(N)

Find the final states of a n-nary tree
each node has three states, 0,1,2.
Require that if all child nodes are 2,
The parent node is also 2.

All child nodes are 0, the parent node is 0, and the rest are all 1s.

Given two functions, start (id, start_time), stop (id, time),
Respectively, to the id assignment start and end time, gave a bunch of such operations (to ensure that the operation start small id first appeared,
And each id last have start_time and stop_time), press the start order to print the corresponding id, start_time, stop_time,
Requirements of space complexity as small as possible,
e.g., start (1, 1), start (2, 2), stop (2, 3), start (3, 4), stop
The print order is (1,1,6), (2,3,2), (3,4,5) # (id, start_time, end_time).

To several bus lines, each line is a two-way line, such as:
0: A <-> B <-> D
1: C <-> D

After writing the map, give you a start and end, let me find the path through the least station.

Output the second index corresponding to the first one, requiring output only if there is only one match, and false if there is more than one pair
a b c d e f g a b -> [0,1]

a b b c, a b c -> False

Check if characters of a given string can be swaped to form target string

ab : ba true
ac : ab false

1
   \
2 - 3
 \ /
  4
  |
  5 - 8
  |  /
   7
For the undirected graph, the LCS is 2,3,4,5, so how can we find it?
 For a undirected graph, find the Longest Consecutive Sequence

/**
* Definition for undirected graph.
* class UndirectedGraphNode {
* int label;
* List<UndirectedGraphNode> neighbors;
* UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<UndirectedGraphNode>(); }
* };
*/
public class Solution {
public List<Integer> longestGraph(List<UndirectedGraphNode> nodes) {

}
}

/*Coding question: The customers for a particular business, required to use a webpage to select a Browse Node.
A Browse Node, is an element in the classification structure used to classify products in the Amazon webpage.
The products are classified in 8 categories. Each category has its own sub-classification that looks like a tree with many
children per node and many levels. The UI developer has a tool to paint such tree. He requires from you (You are the backend developer)
to implement 2 interfaces for him:

Node getRoot();
List<Node> getChildren(Node node);
The data is available for you in a text file with this format:
//nodeid, parent_node_id, nodename

Example:
//nodeid, parent_node_id, nodename
10, 1, Comedy Books
20, 2, Tablets
1, -1, Books
11, 1, Novels
12, 11, Terror novels
2, -1, Electronics
-1, 0, GlobalRoot
*/

Remove '_' and print with 1 space separated string from "Amazon_w_e_b_services are___widely__used_acc__ro___ss_the_worl_d", output should be : Amazon web services are widely used accross the world.

Design a system that works like the you see on Amazon search - lets say you enter 'women's sandals'. What happens in the background? Explain all that you can think of.

Partition given string in such manner that i'th substring is sum of (i-1)'th and (i-2)'nd substring. If such partition not possible then return empty arrayList.
eg.
1) given "1111223" then return ["1", "11", "12", "23"]
2) given "1111213" then return ["11", "1", "12", "13"]
3) given "11121114" then return []

Minimum Continuous Subsequence: targetList & availabletTagsList are two lists of string.

Input:

targetList = {"cat", "dog"};
availableTagsList = { "cat", "test", "dog", "get", "spain", "south" };

Output: [0, 2] //'cat' in position 0; 'dog' in position 2

Input:

targetList = {"east", "in", "south"};
availableTagsList = { "east", "test", "east", "in", "east", "get", "spain", "south" };

Output: [2, 6] //'east' in position 2; 'in' in position 3; 'south' in position 6 (east in position 4 is not outputted as it is coming after 'in')

Input:

targetList = {"east", "in", "south"};
availableTagsList = { "east", "test", "south" };

Output: [0] //'in' not present in availableTagsList

Note: targetList will contain Distinct string objects.

Given a list of characters, write a function to output a list of length of minimum non overlapping subsequences that can partition the input list.

For example:
Input : [a,b,c]
Output: [1,1,1]
Explanation: There are no repeated characters.

Input : [a,b,c,a]
Output: [4]
Explanation: The 'a' is repeated so one subsequence is between a to last a.


Input : [a,b,c,b,a,e,b,a,d,f,g,d,f,i,f,k,l,m,n,m,l]
Output: [8,7,6]
Explanation: max length from 1st 'a' to last 'a' is 8.
1st 'f' to last is 6 adding d to it = 7
so on

You are given with a large paragraph and N words.
You have to find a min length subparagraph of the paragraph which contain all those N words in any order. Here length of a paragraph is the count of words in the paragraph.

Amazon

Given an ArrayList of Nodes, with each Node having an ID and a parent ID, determine whether the List is given in preorder.

Write a program to return nearest elements from a binary search tree for input element.

There is a dictionary already implemented. Write a method , which takes input String without space, to replace the characters from the strings which are not present in dictionary with –

Example: Dictionary – a*
………….Input- aaabaa
………….Output- aaa_aa

There is a dictionary already implemented. Write a method, which takes input String without space, to prints all subsets of the input string which is present in dictionary.
Example: Dictionary – a*
………….Input- aaabaa
………….Output- a,a,a,aa,aa,aaa,a,a,aa

There is a door to enter a restroom. Once you enter the restroom there are N toilets starting from 1, 2,... to N. The toilet which is near to entry door starts from 1 and then it serially goes till N. You can use toilet based on below conditions:
1. If none of the toilets are occupied then choose one which is nearest to the entry door(which is toilet#1).
2. If at least one toilet is occupied then choose that unoccupied toilet which is farthest from the occupied ones.
3. If there are more than one unoccupied toilets whose farthest distance from the occupied ones are same then choose one which is near to the door.

For example:
Let's say there are 5 toilets.
-> First person comes and occupies toilet#1(Based on rule#1).
-> 2nd person comes and occupies toilet#5(Based on rule#2).
-> 3rd person comes and occupies toilet#3(Based on rule#2). Note that the farthest distance would have been formed when the new person would have occupied toilet#2(or toilet#4) but with that, the distance between toilet#2(unoccupied) and toilet#1(occupied) would be just 1.
-> 4th person comes in. Now from toilet#1 to toilet#5, only toilet#2 & toilet#4 are unoccupied. Now there are 2 toilets(#2 & #4) whose farthest distance from unoccupied ones are equal(=1). So rule#3 will apply and toilet#2 will be occupied.

You have to find the sum of those toilet numbers which are occupied.

So in above example after 4th person, toilet numbers which are occupied are #1, #5, #3 & #2.
So answer would be 1+5+3+2 = 11.

Print words in order which are occurring once in huge document. The RAM size 100MB and file size 10 GB.
Example: I am good. You are good.
Answer : I am You are
Note : It's not datastructure problem where we can simply make use of LinkedHashMap. The file size is going to be huge.

given a set of digit from 1 to 9 {1,2,3,4,5,6,7,8,9}, write code to find k elements whose sum is equal to n.

e.g.
k=3, n= 9
{1, 2, 6}, {1, 3, 5}, {2, 3, 4}

vector<vector<int>> findKElementsSum(int k, int n)
{

}

How would you like to efficently find the total number of possible ways with which given string may be converted to whole dictionary words.

Example :
String = “Dogeatscare”

possible combinations – “Dog, eat, scare ” and “Dog, eats, care”

output is 2.

class QueryVector
{
QueryVector(vector values)
{
// Implement
}
vector GetIndices(list filters)
{
// Implement
}
}

Say for example vector is like

{“an”, “apple”, “day”, “keeps”, “doctor”, “away”, “apple”, “iphones”, “cool”, “doctor”, “recommends”}.

GetIndices(“apple”) should return (1, 6)
GetIndices(“doctor”,”cool”) should return (4,8,9)
GetIndices(“random”) should return empty vector ()
GetIndices(“random”,”keeps”,”day”,”doctor”) should return empty vector (2,3,4,9)

Important:

1. There can be millions of values in the input vector of string
2. GetIndices can be called repeatedly and it should be optimized
3. How storage optimization is considered and bitmaps etc are used.