CareerCup

find the isomorphic pairs of string !!

a string is said to be isomorphic if its each alphabets can be replaced by another alphabet

for ex "abca" and "zxyz" are isomorphic but "abca" and "pqrs" is not isomorphic

conditions :
1 - A character can be replaced by itself. for ex "abcd" and "pbfg" are isomorphic .
2- No two characters can be replaced by same character . for ex "abcd" and "bbcd" are not isomorphic .

Find the subarray within an array (containing at least TWO number) which has the largest sum.
For example, given the array [-2,-1,-3,-4,-1],
the contiguous subarray [-2,-1] has the largest sum = -3.
try to do it in O(n) time
Followup, if input is stream, how to solve it
public int maxSubArray(int[] nums) {}

Sorry had to remove this question

Write code for the following: given a text file containing this information (Date the customer is logged in, tab, customer id)
04/11/2017 /t 0003
04/12/2017 /t 0003
04/13/2017 /t 0004
04/13/2017 /t 0003
How to get the list of those customers that log in on three consecutive days.

OOPS: How to design Amazon locker? Provide code using OOP

How to merge two binary trees in place? (without creating a new node)

A binary gap within a positive integer N is any maximal sequence of consecutive zeros that is surrounded by ones at both ends in the binary representation of N.

For example, number 9 has binary representation 1001 and contains a binary gap of length 2. The number 529 has binary representation 1000010001 and contains two binary gaps: one of length 4 and one of length 3. The number 20 has binary representation 10100 and contains one binary gap of length 1. The number 15 has binary representation 1111 and has no binary gaps.

Write a function:

int solution(int N);
that, given a positive integer N, returns the length of its longest binary gap. The function should return 0 if N doesn't contain a binary gap.

For example, given N = 1041 the function should return 5, because N has binary representation 10000010001 and so its longest binary gap is of length 5.

Assume that:

N is an integer within the range [1..2,147,483,647].
Complexity:

expected worst-case time complexity is O(log(N));
expected worst-case space complexity is O(1).

Find two strings are meta string or not
for eg:-
Converse
Conserve

are meta strings because if we swap s and v in the string both string will become equal. If swapping of more than one pair can be done then it is not a meta string

Find the median of a bst in O(n) time and O(1) space

VMWare Standard Online Screen

3rd Question Given an array of strings and a long description about the formatting of IPv6 and IPv4 (it took me more than 5 minutes to read the description). Write a function to find if a string is IPv4 or IPv6 address or neither.

4th Question Given an integer array, whenever a duplicate number is found, you may increment it (++). Find the minimum sum of the numbers in the array by keep incrementing the dups until all the numbers are unique.

VMWare Standard Online Screen

The Online Assessment was called something like Life Cycle Challenge-qpan.
There are 4 questions in total given 60 minutes. The problem description was unexpectedly long that it takes 5 minutes just to read a question.

1st Question Design a function to create BST. Given an integer array, insert the integers into the binary search tree and print all the steps taken.

2nd Question Given an integer, print the index of all the positions in which the binary bit is 1 in order.

Given a count and maxvalue, write a program to return count number of unique random integers between 0 and maxvalue.

Facebook Senior Engineer On-site 2017

1st Round
Question 1: Binary tree to doubly linked list.
Question 2: Read 4 (Given the read4 API, read an entire file)

2nd Round
Culture fit. No coding.

3rd Round
Question: System Design POI (Point of Interest. Given a point, find things within a radius).

Lunch
4th Round
Question 1: Decode way
Question 2: Random max index

5th Round
Question: System design + component-wise design on download manager

Find the Lexicographic next word of the input word from a list of words
Example
Words list
[Cat, dog, cow, donkey, zebra, monkey],
input
duck
output
monkey

Input
dog
output
donkey
Can you use trie to solve it?
public String findNextWord(List<String> words, String input){
}

Given a equation in the form of "3x+4y+2=-5y+2x+10", simplify the equation to be in form "y=Ax+B", and return A,B. Also allow parenthesis to be in the equation. Ex. "3y-4x+(3-(2x-3y))=10y", result is "y =0.75 - 1.5x"

5th Round
Open-ended question What happens when you type a url in the browser and hit enter?

Second question Given an array of integers, print all the numbers that meet the following requirement - when the number is greater than every number on its left and smaller than every number on the right.

interviewed by senior engineer
Question Given two strings s1 and s2, combine the characters in the strings and maintain the sequence of characters
Follow-up If s1 has a length of m and s2 has a length of n, how many ways the strings could be merged. Figure out the formula F(m, n) = ?

Given a list of files. Return all the unique lines from all files.

Find the coordinates of the rectangle which is parallel to axis and has minimum area.

Suppose you have a stream of (timestamp, tag) events. You need to filter this stream (online), leaving only events with tags that haven't been already encountered in the last X seconds.

People enter and leave a room over the course of a day. Each person has a badge with a unique integer id, which is logged by the security system on enter/exit. Each log entry is an enter record (“E <id>”) or and leave record (“L <id>”) for the given badge id.
The room is empty at the beginning and ending of the day, and there are no other ways into or out of the room.
E: Enters the room
L: Leaves the room

Well formed log:
E 111
E 222
L 111
E 111
L 222
L 111

Question: You have a log and write a function to check is it the well formed log or not.

Design a data structure to support following operation:
Insert, delete, search and min difference
Time complexity of finding min Difference should be less than O(log n).

Given some email ids, and a similarity function which says whether two email ids are similar, determine all the sets of email ids that are similar to each other.

You have a string consisting of open and closed parentheses, but parentheses may be imbalanced.
Make the parentheses balanced and return the new string.

Design a system which takes in latitude and longitude and returns back closest 5 locations.

Given a sorted array, find all the numbers that occur more than n/4 times.

How to randomly select a number in an array?
array: [15, 2, 4, 5, 1, -2, 0]

Follow-up:
Given a second array freq where freq[i] represents the occurrence of the ith number in array, how to randomly select a number in array based on the frequency.

Extra requirement:
Could you complete the selection in a single-pass(go through each array only once)?

In school a student gets rewarded if he has an attendance record without being absent for more than once or being late for 3 times continuously.
Given a student's attendance record represented by a string with 3 possible characters 'L'(Late), 'A'(Absent), 'O' (On time),
check whether the student qualifies for the reward.

e.g.
@INPUT (String) "OLLAOOOLLO"
@RETURN (Boolean) False
The student does not qualify for reward because "LLA" means he was late for 3 times in a row.

@INPUT (String) "OLLOAOLLO"
@RETURN (Boolean) True



Follow-up:
If known the length of the attendance string is n, how many possible ways there is to attend school and make sure you get the reward.

In school a student gets rewarded if he has an attendance record without being absent for more than once or being late for 3 times continuously.
Given a student's attendance record represented by a string with 3 possible characters 'L'(Late), 'A'(Absent), 'O' (On time), check whether the student qualifies for the reward.

e.g.
@INPUT (String) "OLLAOOOLLO"
@RETURN (Boolean) False
The student does not qualify for reward because "LLA" means he was late for 3 times in a row.

@INPUT (String) "OLLOAOLLO"
@RETURN (Boolean) True



Follow-up:
If known the length of the attendance string is n, how many possible ways there is to attend school and make sure the student gets the reward.

Find three non-overlap windows of size k in an int array, that together has a maximum sum
of the 3k entries.
example
int[] nums = [1,2,1,2,6,7,5,1]
k = 2
output
[1,2],[2,6],[7,5]