CareerCup

Given a map represented as a 2d array with only 0’s and 1’s. An island is a group of connected 1’s. Find out how many distinct islands(can be rotated).
eg:
1 1 0 0
1 0 0 0
0 0 0 1
0 0 1 1

return 2.

Design a concurrent hashmap.

Please point me to the link if this has been discussed before.
They wanted design with code snippet of the classes.

Give an positive integer n, find out the smallest integer m, such that all digits in m multiply equals to n. For example, n = 36, return 49. n = 72, return 89. You can assume there is no overflow.

Reverse a linked list

Given a random MxN matrix and a positive integer, recursively Your program should then find a continuous path thought the matrix starting at position 0,0 that will sum to n. Your program shouldomly move left (col -1), right(col +1), up (row -1) and down (row+1)and can only use a position once in the sum. if there is a such path in the matrix, create the path in a separate matrix with the same size, and replacing the indices used with 1 and the rest 0.

Yahoo Sunnyvale onsite
A string s3 consists of multiple repetitions of s1.
Given s1 and another string s2, find if s2 is a substring of s3.
s3 = s1 + s1 + … + s1 = n * s1, where n is a positive integer 0.
For example
s1 = “aabc”, s2 = “caa” => true
s1 = “aabc”, s2 = “cab” => false
s1 = “aabc”, s2 = “caabcaa” => true

A city represented by a rectangular matrix is divided into plot of lands, and the cost of each plot is known. Find the largest rectangular area of land we can buy, within a budget B.

4 6 7
3 5 2
2 4 5

B = 16

Amazon phone interview
A queue of people are waiting to buy ice cream from you.
Each person buys one ice cream, which sells for $5.
Each customer is holding a bill of $5, $10 or $20.
Your initial balance is 0.
Find whether you will be able to make change for every customer in the queue. You must serve customers in the order they come in.

For example
5, 5, 5, 10, 20 -> true,
5, 5, 10 -> true,
10, 10 -> false

Congrats on aonecode member A.P. for signing the offer with FB! Thanks for sharing the experience with us.
phone:
postorder tree traversal recursive -> iterative
add two binary number


on-site:
1 ring buffer
2 merge intervals
3 Leetcode alien dictionary
4.sort list of words

Airbnb: Design webbrowser back button

Your web browser supports will support three actions: back, forward and open. The init webpage is “about:blank”.
Given a sequence of commands. Return the result page.

find the sum of bit wise OR of minimum and Maximum element of all the subsets whose length is greater than 2 of the given of set.

for ex:-

{1,2,3} is set
then possible subsets of length is{ 1,2},{1,3},{2,3}{1,2,3} answer 1|2 +1|3 +2|3 +1|3=12

The wildcard regex can include the characters * and + .

‘+’ – matches any single character or empty character!

‘*’ – Matches any sequence of characters (including the empty sequence) For example,

Text = "baaabab":

regex = "ba*a++", output : true

regex = "ba*a+", output : true

regex = "a*ab", output : false

//empty string

Text=""

Regex= "+" , output : true

I was asked this question in a recent interview for a startup.

We have coffee vending machine with 3 buttons which can dispense 4oz, 7oz and 13oz of coffee.

Given a cup and the min and max amount(oz) of coffee it should fill. determine if the coffee vending machine can satisfy the condition.

The buttons can be pressed as many times as possible to fill the cup. Coffee shouldn't overflow..

AWS phone interview
Find the left view of binary tree
1
/ \
2 3
/\ \
4 5 6
/ /
7 8
/
9
return [1, 2, 4, 7, 9]

If b == “1”:
quit()

Write a method that can take in an unordered list of airport pairs visited during a trip, and return the list in order:

Unordered: ("ITO", "KOA"), ("ANC", "SEA"), ("LGA", "CDG"), ("KOA", "LGA"), ("PDX", "ITO"), ("SEA", "PDX")
Ordered: ("ANC", "SEA"), ("SEA", "PDX"), ("PDX", "ITO"), ("ITO", "KOA"), ("KOA", "LGA"), ("LGA", "CDG")

April Google Interview 1/4
A = a+b-c-a-b-c-a-b (Tree)
B = b+a+c+a+b-c+b (Tree)
is A equal to B

April Google Interview 4/4
Build HTML Reverser
Given
<A>(hello)(<P>ab</P>)(<S>hi</S>)</A>
Return
<A>(<S>ih</S>)(<P>ba</P>)(olleh)</A>

April Google Interview 3/4
Maze
N,M array
Level 1 0,0 to N-1,M-1 => Path exsits?
Level 2 if path exists then print path
Level 3 if path exists then print min cost path
Level 4 O(nm log mn) using Priority Queue.

April Google Interview 2/4
Count Number Given Array
Level1 Unsorted Array [1, 3, 2, 1, 2 ,3 , 4, 10]
Find occurrence of 1
Level 2 Sorted Array
Find occurrence of 1

/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/

Find the largest duplicate subtree in a binary tree


For example,

        1
       / \
      2   3
     /   / \
    4   2   4
       /
      4
The following are two duplicate subtrees:

      2
     /
    4
and

    4

but the former is the largest, thus return the root of the first subtree

Given a target string, an input request replaces the word after the given index a->b such as:
Target string: "Hello world!"
Input:{s:0, a:Hello b: Goodbye}
Output:"Goodbye world!".
The requirement is that input be given to several words that need to be changed at one time: {{s:0,a:Hello,b:Goodbye},{s:11,a:!,b:?},{s:6 a: World,b:friend}}
And each modified index is based on the original unmodified target string so the end result is
"Goodbye friend?"

given a n-ary tree, find the total distance from this node to any other nodes

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


public int findDistance(TreeNode root, TreeNode node) {

}

Design a Twitter-like topic system so that the most popular topics can be retrieved from the system. A post can have one or more topics and these topics can be shared by multiple posts. (hint: thinking of scalability)

Assume courses labeled by their index in an array. Given a list of pairs where the first element represents a prerequisite course required for the second course, derive an ordered list of courses.

For a given set of non-negative integers get the number of subsets that add up to a target value k.

For a given array of integers compute the maximum sum of any range in the array. Then modify the function to find maximum product (note the effect of negatives on max product).

Write a function to compute n^k. (don't forget negative exponents)

Print (or return) the longest movie title found by successively matching the last and first words in each title, joining to form new titles, given a file containing a list of movie titles.
For example: 'OF MICE AND MEN' and 'MEN IN BLACK' join to form 'OF MICE AND MEN IN BLACK'.
You could further join 'OF MICE AND MEN IN BLACK' wth 'BLACK MASS' to form 'OF MICE AND MEN IN BLACK MASS'.

The longest title I found (at 143 characters is): WENT TO CONEY ISLAND ON A MISSION FROM GOD BE BACK BY FIVE WIVES THREE SECRETARIES AND ME WITHOUT YOU CANT TAKE IT WITH YOU WERE NEVER LOVELIER

Given a bar chart which the heights of bars are notated as an array of positive integers. Rectangles can be formed in areas covered by one or more bars. Find the largest rectangle.