CareerCup

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.

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.

Design a task execution service, which accepts tasks from clients and runs them and returns result. Following is how the

Client Registration (client name, callback method)
Submit Job to service
Once executed service will return the result to client

Lets assume that 20k jobs are getting submitted per second, you need to scale it in such a way that we are able to process as much jobs per second as possible.

Further questions:

So the components are going to be a load balancer, workstations, cache, task runner and DB. How will you make sure that data is consistent among them, mimimal duplication of data and every job is ran only once.

If any machine is down, say DB, workstation etc. how that is going to be handled.

Developing Java game
creating a RESTful service using which players can play a simple game described
below.
The game should have the following rules:
• The player has an infinite amount of coins.
• The player bets 10 coins to play a normal game round.
• In any round (free or normal), the player has a 30% chance of winning back 20 coins.
• In any round (free or normal), the player also has a 10% chance of triggering a free round where
the player does not have to pay for bet. The free round works in the same way as a normal round except
it costs 0 coins. The free round should follow immediately after the normal round.
• The player can both win coins and free round at the same time.

I participated interview event with Amazon and receive email from Amazon recruiter that the team was happy with my performance and would be giving me offer at Amazon Vancouver Office, Canada. However,17 days later i still not get an official offer. I did several follow up with the recruiter within the period, just to get some "they are finding team for me" response. What could go wrong? Why is it in my case that the offer is being process so slow?