CareerCup

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]

Given:
a encoded to 1
b encoded to 2
....
z encoded to 26

You can translate a number to a string:

'123' can be translated to 'abc'
but also can be translated to 'aw','lc' which gives 3 total translations
'12' can be translated to 'ab' and 'l' -> 2 translations

Write a function to get the number of valid combinations from a number like '123123123'

how to find leaf node value from preorder sequence of BST without rebuilding the tree

deleted

for a binary tree, print the root to the leaf path, but add "_" to indicate the relative position.
example:

A 
       /   \  
      B     C 
     / \   / \
    D  E   F  G

output
_ _ A
_ B
D

_A
B
_E

A
_C
F

A
_ C
_ _ G

Q: Weighted meeting room
Given a series of meetings, how to schedule them. Cannot attend more than a meeting at the same time. Goal is to find maximum weight subset of mutually non-overlap meetings.

class Meeting:
def __init__(self):
	self.startTime
	self.endTime
	self.weight

@concernedCoder
When you claim the questions as fake, provide evidence. These are no doubt questions asked in the coding interviews of the best companies and they definitely help interviewees to prepare for the interview.
Why do you have a problem with this?

If a string is matched to any filter, it is in the black list, otherwise not.
Design a data structure and implement following two functions.

addFilter(filter)
isInBlackList(string)

filters are in the form of
“a*b”
“abc”
“aa*b”
having at most one star, which matches 0 or more chars.

You have L, a list containing some digits (0 to 9). Write a function answer(L) which finds the largest number that can be made from some or all of these digits and is divisible by 3. If it is not possible to make such a number, return 0 as the answer. L will contain anywhere from 1 to 9 digits. The same digit may appear multiple times in the list, but each element in the list may only be used once.

{{
Test cases
==========

Inputs:
(int list) l = [3, 1, 4, 1]
Output:
(int) 4311

Inputs:
(int list) l = [3, 1, 4, 1, 5, 9]
Output:
(int) 94311
}}

My Solution:
{{

package com.google.challenges;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;


public class Answer {
public static int answer(int[] l) {

// Your code goes here.
ArrayList<Integer> list0 = new ArrayList<>();
ArrayList<Integer> list1 = new ArrayList<>();
ArrayList<Integer> list2 = new ArrayList<>();
int sum =0;
Arrays.sort(l);
for(int i = 0; i<l.length; i++){
if(l[i] % 3 == 0){
list0.add(l[i]);
}else if(l[i] % 3 == 1){
list1.add(l[i]);
}else{
list2.add(l[i]);
}
sum += l[i];
}

if(sum%3==0){
StringBuilder strNum = new StringBuilder();
for(int i = l.length-1; i >= 0; i--)
{
strNum.append(l[i]);
}
return Integer.parseInt(strNum.toString());
}else if(sum%3 == 1){
if(list1.size()>0){
Collections.sort(list1);
list1.remove(0);
}else if(list2.size() >= 2){
Collections.sort(list2);
list2.remove(1);
list2.remove(0);
}else{
return -1;
}
}else if(sum%3 == 2){
if(list2.size()>0){
Collections.sort(list2);
list2.remove(0);
}else if(list1.size() >= 2){
Collections.sort(list1);
list1.remove(1);
list1.remove(0);

}else{
return -1;
}
}
list0.addAll(list1);
list0.addAll(list2);
StringBuilder strNum = new StringBuilder();
Collections.sort(list0);
for(int i = list0.size()-1; i >= 0; i--)
{
strNum.append(list0.get(i));
}
return strNum.length() > 0 ? Integer.parseInt(strNum.toString()) : -1;
}
}
}}

But here I am able to pass 4 test cases out of 5. Therefore I am looking for scenario which is left to check.
Can someone help me?

On google search, how to enable key word auto completion after a few letters typed.

Follow-up: How to rank the words if they are weighted by frequency?

Cross the street
ABC Company is involved in the logistics business.

The company has many outlets and stockyards in a city. The city is like an
N
×
M
N×M grid. We consider a single cell of the given grid to be a single block in the city. The stockyard is at the upper-left corner and the outlet is located in the lower right corner. Everyday, one of the employees has to travel from the upper left to the lower right corner for supplies. Each block in the city has a height, where the height of the block located at position (i,j) in the grid is equal to
A
[
i
]
[
j
]
A[i][j]. The company wants to change the heights of some of the blocks, so that the employee can enjoy a high-speed drive from the stockyard to the outlet. But this change comes at a certain cost.

Specifically, if they change a block height from x to y, then they must pay exactly
|
x
−
y
|
|x−y| dollars. Please help them find the minimum cost, such that by spending that specific amount, they can get a path from stockyard to the outlet with all blocks along the path having the same height.

In a single move, the employee can move from a block to any of its adjacent blocks. Note that during this journey, the employee is allowed to move in all four directions, fulfilling the condition that he never goes out of the grid at any point in time.

Input :

First line contains two positive integers N and M - number of rows and columns in the city. Then, N lines follow, each containing M integers, where the
j
t
h
jth integer on the
i
t
h
ith line denotes
A
[
i
]
[
j
]
A[i][j].

Output :

The first and only line of output should contain minimum cost.

Constraints :

1<= N, M <=100

1<= height of blocks <=100

Sample Input
5 5
1 1 1 1 1
9 9 9 9 1
1 3 3 3 1
1 9 9 9 9
1 1 1 1 1
Sample Output
6
Explanation
Optimal path taken by the employee will be : (1,1) -> (1,2) -> (1,3) -> (1,4) -> (1,5) -> (2,5) -> (3,5) -> (3,4) -> (3,3) -> (3,2) -> (3,1) -> (4,1) -> (5,1) -> (5,2) -> (5,3) -> (5,4) -> (5,5) The height of each block along this path can be changed to
1
1, at a total cost of
6
6. There is no way to get a cost less than this.

Alex has recently decided to learn about how to design compilers. As a first step he needs to find the number of different variables that are present in the given code.


So Alex will be provided N statements each of which will be terminated by a semicolon(;). Now Alex needs to find the number of different variable names that are being present in the given statement. Any string which is present before the assignment operator denotes to a variable name.

Input Format: :

The first line contains a single integer N


Each of the next N lines contains a single statement.

It is guaranteed that all the given statements shall be provided in a valid manner according to the format specified.

Output Format: :

Print the number of different variable name that are present in the given statements.


Sample Input
2
foo = 3;
bar = 4;
Sample Output
2
Explanation
Foo and Bar are only two variables used inside the statements so answer is 2.

Design classes to represent the following problem and solve the questions 1,2,3
A user might have some outstanding auto loan amount and you have 3 types of offers: personal loan, credit card and auto loan offers. You need to provide the user
with the following details:
1. Send user all the offers to the user
2. Send user all eligible offers (where minCreditScore < userCreditScore < maxCreditScore)
3. Send user all offers which satisfied 2) and where the (userOutStandingLoanAmount < maxOfferedAutoLoanAmount)



personal-loan = [{
"personal-loan": {
"id": 1,
"provider": "Avant",
"term": 36,
"minimumCreditScore": 300,
"maximumCreditScore": 700,
"maximumAmount": 10000
}
}, {
"personal-loan": {
"id": 2,
"provider": "Prosper",
"term": 24,
"minimumCreditScore": 600,
"maximumCreditScore": 700,
"maximumAmount": 5000
}
}]

credit-card=[{
"credit-card": {
"id": 2,
"provider": "CapitalOne",
"minimumCreditScore": 600,
"maximumCreditScore": 700
}
}, {
"credit-card": {
"id": 3,
"provider": "Chase",
"minimumCreditScore": 300,
"maximumCreditScore": 900
}
}]

autoloan = [{
"auto-loan": {
"id": 1,
"provider": "CapitalOne",
"term": 36,
"minimumCreditScore": 300,
"maximumCreditScore": 700,
"maximumAmount": 10000
}
}, {
"auto-loan": {
"id": 2,
"provider": "Blue Harbor",
"term": 24,
"minimumCreditScore": 600,
"maximumCreditScore": 700,
"maximumAmount": 5000
}
}]

Consider that the driver with one trip want to pick up some peoples in different locations like this:
String[] locations ={
"person1, person2, person3, person4, person5",
" person6, person7, person8, person9",
"person10, person11, person12",
"person13, person14, person15",}
in each location there are different choice, so write a code present all possible way to pick up people in the different locations. you can use every data structure needs.

given preorder traversal [5,3,2,4,8,7,9] of a BST, how do we identify the leaf nodes without building the tree ?

@Anonymous Thanks for the reply!
Please try other use cases like, only single leaf node

There is dedicated Samsung software for coding test the question is given below:
There is one spaceship. X and Y co-odinate of source of spaceship and destination spaceship is given. There are N number of warmholes each warmhole has 5 values.
First 2 values are starting co-ordinate of warmhole and after that value no. 3 and 4 represents ending co-ordinate of warmhole and last 5th value is represents cost to pass through this warmhole. Now these warmholes are bi-direction.
Now the to go from (x1,y1) to (x2,y2) is abs(x1-x2)+abs(y1-y2).
The main problem here is to find minimum distance to reach spaceship from source to destination co-ordinate using any number of warm-hole. It is ok if you wont use any warmhole.

list1 -->aaa,bbb,ddd,xyxz,...
list2-->bbb,ccc,ccc,hkp,..
list3> ddd,eee,,ffff,lmn,..

Inside a list the words are sorted
I want to remove words which are repeated across the list and print in sorted order
If the words are repeated in same list its valid.
In the above case
it should print aaa-->ccc-->ccc-->eee--->fff-->glk-->hkp-->lmn-->xyxz

Some questions about how to write a immutable class.

Find top n cities which got most orders. For example, amazon got a list of orders, and these orders will be shipped to different cities.