CareerCup

Given two string check if they can be made equivalent by performing some operations on one or both string.

swapEven:swap a character at an even-numbered index with a character at another even-numbered index

swapOdd:swap a character at an odd-numbered index with a character at another odd-numbered index

Given : s="cdab" , x="abcd"
s -> cdab ->swap a and c ->adcb (swapEven)-> swap b and d (swapOdd) -> s="abcd" = x="abcd"

Given: s="dcba" , x="abcd"
no amount of operation will move character from an odd index to even index, so the two string will never be equals

Given: s="abcd" ,x="abcdcd"
x length to big so will never be equals

Given an array of lower case strings, the task is to find the number of strings that are special equivalent.
Two strings are special equivalent if they can be made equivalent by performing some operations on one or both string

swapEven : swap a character at an even-numbered index with a character at another even-numbered index

swapOdd : swap a character at an odd-numbered index with a character at another odd-numbered index


Input : arr = {"abcd", "cbad", "bacd"}
Output : 2
The 2nd string can be converted to the 1st by swapping
the first and third characters. So there are 2 distinct
strings as the third string cannot be converted to the
first.


string input[] = {"abcd", "acbd", "adcb", "cdba",
"bcda", "badc"};
ans =4

Given an array of lower case strings, the task is to find the number of strings that are distinct.
Two strings are distinct if they can be made equivalent by performing some operations on one or both string

swapEven : swap a character at an even-numbered index with a character at another even-numbered index

swapOdd : swap a character at an odd-numbered index with a character at another odd-numbered index


Input : arr = {"abcd", "cbad", "bacd"}
Output : 2
The 2nd string can be converted to the 1st by swapping
the first and third characters. So there are 2 distinct
strings as the third string cannot be converted to the
first.


string input[] = {"abcd", "acbd", "adcb", "cdba",
"bcda", "badc"};
ans =4

design an email job that would deliver high number of emails and will work on a really old and slow hardware.

how to design a system to fast lookup cars on the market according to the user's geo position.

Given two two integer arrays. Find the longest common subsequence.
eg: a =[1 5 2 6 3 7], b = [5 6 7 1 2 3]. return [1 2 3] or [5 6 7]

Question : Given a set of N numbers [1,N], partition them into 2 disjoint subsets based on a set of K queries.
Each query is of the type (n1, n2) where n1 and n2 are distinct numbers from the set and n1 and n2
belong to opposite subsets.

Example:

Input:

Input:
N = 4
K = [(1, 2), (1, 3), (2, 4)]

Output:
Set 1 : (1,4)
Set 2 : (2,3)

Give a binary tree, find if it's possible to cut the tree into two halves of equal sum. You can only cut one edge.

Find all triplet that sum to a given value in an array of integers, given that the array is too big to fit into memory

Design and implement a interest matching algo, to match people according to their interests in a particular area.
Suggest a score based on their interests. And rank matchings accordingly.

You are standing in the top-left corner of n*m grid. At each step you can only move up, down, right or left. Count the number of unique paths to the bottom-right corner of the grid (paths cannot cross themselves). The interviewer suggested that a backtracking solution is not the most performant one.

Collect tree leafs. Give a binary tree, remove and collect the leaves layer by layer.

eg.

 1
/ \
2  3
   / \
   4  5

first layer: 2, 4, 5
second layer: 3
last layer: 1
return [[2, 4, 5], [3], [1]]

Given an undirected graph represented as a list of edges, find out the number of connected component.

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