## Recent Interview Questions

- 0of 0 votes
`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) { } }`

- 0of 0 votes
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

- 0of 0 votes
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)

- 0of 0 votes
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.

- 0of 0 votes
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).

- 0of 0 votes
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.

- 0of 0 votes
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

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

ab : ba true

ac : ab false

- 0of 0 votes
`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) {

}

}

- 0of 0 votes
check if there are two subarrays in an array are identical

- 0of 0 votes
comparison of two strings if they are the same, use o(1) space

abc \ b is equal to ab

abc \ ca equals abcA

\ b = backspace

\ c = CapsLock

- 0of 0 votes
convert Prefix to Postfix using recursion

+ * A B / C D -> A B * C D / +

- 0of 0 votes
Design a dictionary with historical records

t0: hdict = HistoricalDict ()

t2: hdict.set ('foo', 1)

t4: hdict.set ('foo', 2)

t5: hdict.get ('foo', t5) -> 2

t6: hdict.get ('foo', t3) -> 1

t7: hdict.get ('foo', t0) -> None

- 0of 0 votes
CSS colors can be defined in the hexadecimal notation "#rgb", a shorthand for "#rrggbb". For example, "#03f" is equivalent to "#0033ff". Suppose the similarity between two colors "#abcdef" and "#ghijkl" is defined as (-(ab-gh)^2 - (cd-ij)^2 - (ef-kl)^2), write a function that accepts a color in the "#abcdef" format and returns a "#rgb" color that is most similar to the input. For example, given "#09f166", "#1e6" should be returned.

- 0of 0 votes
`Given a binary tree, output the maximum EVEN sum along any path 10 / \ 2 5 / \ \ 1 101 13 Maximum even sum = 101 +2 +10 + 5 = 118`

- 0of 0 votes
Given two input arrays, return true if the words array is sorted according to the ordering array

Input:

words = ['cc', 'cb', 'bb', 'ac']

ordering = ['c', 'b', 'a']

Output: True

Input:

words = ['cc', 'cb', 'bb', 'ac']

ordering = ['b', 'c', 'a']

Output: False

- 2of 2 votes
Give the following input, output if the array is sorted according to the ordering array given. Return true or false.

Input:

words = ['cc', 'cb', 'bb', 'ac']

ordering = ['c', 'b', 'a']

Output: True

Input:

words = ['cc', 'cb', 'bb', 'ac']

[bb cb cc ac]

ordering = ['b', 'c', 'a']

Output: False

- -1of 1 vote
Define a class 'Space' which has a member string variable that indicates if the space is a "tree", a "house" or an empty space and another member variable that will store the 'space neighbors' (left, right, up and down only)

Given a 'Grid' (list) of Spaces write the code for the findAll(start) method to find all the trees and houses given a 'Space' as start point

Example, Grid of 'Spaces':

T 0 0 H 0

0 0 0 0 0

H H T H 0

Where Ts are trees and Hs are houses

- 0of 0 votes
Given a singly linked list, Your task is to remove every Kth node. The task is to complete a method deleteK that takes two argument, head of linked list and an integer k.The method returns the head of the new linked list. There are multiple test cases. For each test case, this method will be called individually.

- 0of 0 votes
Given a binary tree (not only BST) return the length of the longest consecutive sequence. The sequence can be between ANY TWO nodes and not only from root to leaves.

For example:`- 2 / \ 1 3 / / \ 0 4 7 / 10`

Should return 5: 0->1->2->3->4

- 0of 0 votes
A and B are playing a perfect 8-9 game. The rules are pretty simple. At each point, you can either insert an 8 at the end of the previous number or a 9. one 8 and one 9 forms a pair. a 9 can only be inserted if there is an 8 which does not form a pair. Perfect solution is the one which has all its numbers in pair. Find out all the possible perfect outcomes of the game in lexicographic order.

Input-

Input 1: Max length of number

Output-

Your array must return an array of string s containing all possible outcomes.

Example 1:

Input: 4

Output: {"8899", "8989"}

Explanation: There can be only 2 possible outcomes out of 4 as nine must follow eight.

Example 2:

Input: 6

Output:{"888999","889899","889989","898899","898989"}

Explanation: The possible outcomes are 5.

- 0of 0 votes
Given a 3x3 tic-tac-toe board with players 1 and 2. Find all the possible ways player 1 can lose given a particular configuration of the board.

For example (0 denotes empty spot):

input:

0, 1, 0

2, 2, 1

1, 1, 2

Output: 1 (because the only move for player 2 to win would be to play board[0,0])

The input board can have any configuration (player 1 and 2 can be in all possible spots with any number).

- 0of 0 votes
convert a Sorted linkedList to complete BST

- -1of 1 vote
I am surprised by this GS question.I thought this is one of the classic number theory partition problem which is so hard that the best algorithm is approximation one.

Given value, find all possible combination of ways which equals to that sum.

- 0of 0 votes
Give N socks, there is no guarantee that each can be paired, socks two colors, black and white, you need to pair them

- 0of 0 votes
css color format # abcdef, another abbreviated color format # rgb

(Converted to the previous format, ie, #rrggbb.) Now give your #abcdef, the first color format, to find the two least different colors, #rgb.

- 0of 0 votes
/*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

*/

- 0of 0 votes
Given the below input and output and asked to write in Java.

Example 1)

input : {1,2,3,4, &, 12,13,14,15}

output : {15,14,13,12,1,2,3,4}

Example 2 )

input : {33,34,&,55,63}

output : {63,55,33,34}

Assumption : '&' will always be in the middle.

- 0of 0 votes
Google Fucked up question.

Given a random list of appointments (Start Date , End Date). Find all the appointments that are colliding.

This pretty easy looking question screwed me up today.There are tons of edge cases, I couldn't complete em all and 45 minutes pass like 15 minutes while explaining and coding same time.

- 0of 0 votes
Given list of edge in the graph, find the number of reversed pairs,(1,2)

and (2,1) are such pair. Follow up: How to implement the distributed version.