CareerCup

Multiply two numbers without using * and only be using bitwise operations

Display nodes of a tree in level order using DFS

Implement a deque using stacks

Given the entire dictionary of English words, what data structure will you use to efficiently store and match the custom regex string like "D*sk", where * represents any single alphabet, and return the list of matched words?

Given a skewed tree, an insect is sitting at the root of the tree at t = 0min, every minute insect steps down in the tree, find the probability of the insect being at any node at t = infinity. Once I came up with a solution various other complexities has been added to the problem such as: What if the tree is binary tree (written code for this) What if three is n-ary What if it is now a directed acyclic graph Handle cases that there can be more than one entry point There can be more that one way to reach a node

Given a binary tree of numbers and a search number has given, find out first occurence of that number and smallest distance from root node. if you have given k search numbers find their occurence and nearest from root node in a single walk.

Given a string of numbers put commas so that it become readable like million trillion thousands. eg 1010503 ===> 1,010,503

Given an array of 0s and 1s. find maximum no of consecutive 1s. If you have given chance to flip a bit to 1 such that it maximises the consecutive 1s. find out that flipped bit and after flipping that bit maximum no of consecutive 1s. Above question but you have options to flip k bits.

Design a system which will keep track of product and its inventory count. The service will expose two api incrCnt(int prodId, int cnt) and decrCnt(int prodId, int cnt). Which db would you use ? How will you handle hot products ?

/**
Given a nested list of integers, return the sum of all integers in the list weighted by their depth.

Each element is either an integer, or a list -- whose elements may also be integers or other lists.

Example 1:

Input: [[1,1],2,[1,1]]. - 1 at depth 2, 1 at depth 2, 2 is at depth 1, 1 at depth2, 1 at depth 2

// [1] - at depth 1, [[1]] - at depth 2, [[[[1]]]] at depth 4

Output: 10
Explanation: Four 1's at depth 2, one 2 at depth 1.

1*2 + 1*2 + 2*1 + 1*2 + 1*2 = 10

Example 2:

Input: [1,[4,[6]]]
Output: 27
Explanation: One 1 at depth 1, one 4 at depth 2, and one 6 at depth 3; 1*1 + 4*2 + 6*3 = 27.

[[[1]]] - at depth 3
*/


/**
* // This is the interface that allows for creating nested lists.
* // You should not implement it, or speculate about its implementation
* public interface NestedInteger {
* // Constructor initializes an empty nested list.
* public NestedInteger();
*
* // Constructor initializes a single integer.
* public NestedInteger(int value);
*
* // @return true if this NestedInteger holds a single integer, rather than a nested list.
* public boolean isInteger();
*
* // @return the single integer that this NestedInteger holds, if it holds a single integer
* // Return null if this NestedInteger holds a nested list
* public Integer getInteger();
*
* // Set this NestedInteger to hold a single integer.
* public void setInteger(int value);
*
* // Set this NestedInteger to hold a nested list and adds a nested integer to it.
* public void add(NestedInteger ni);
*
* // @return the nested list that this NestedInteger holds, if it holds a nested list
* // Return null if this NestedInteger holds a single integer
* public List<NestedInteger> getList();
* }
*/
public int depthSum(List<NestedInteger> nestedList) {

}

Design a system in which read a file which has data and operation to be performed give a line by line. Ex a=5, next line b= 10, next line a*b. This design extended to support float, doubles, boolean, vector and complex numbers. Like if the file has a=5+i8, then how you handle such scenarios. How you will store and process data.

Design content ingestion system

Find min number of jumps it will take to reach to the top in snake and ladder game using recursive function

Design database schema with entity and relations to store the family tree of a person.

Given array of ball size we need to return the sum of shadow balls

For example

7 3 2 8 1

shadow ball of 7 ---> 3, 2, 1
shadow ball of 3 ---> 2, 1
shadow ball of 2 ---> 1
shadow ball of 8 ---> 1

Output ---> 3+2+1+1 --> 7

Complexity should be better than 0(n^2)

Given an integer array and an integer K, find the number of sub arrays in which all elements are less than K.

Follow up -
Given an integer array and an integer K, find the number of non overlapping unordered pairs of sub arrays in which all elements are less than K.

Design a low level design and db schema for railway reservation system for supporting following 2 features -

1) User would give source city, destination city and date as input and would get the list of trains matching the criteria.

2) On selection of a train from the list user should be able to see the schedule of the train including the arrival time, departure time and station name.

How to Cancel a Cash App Payment

Design a distributed key-value store that can perform the following
Store a set of attributes (value) against a particular key (k)
Fetch the value stored against a particular key (k)
Delete a key (k)
- Perform a secondary index scan to fetch all key along with their attributes where one of the attribute values is v.
Key can have a value consisting of multiple attributes.
Each attribute will have name, type associated (primitive types - boolean, double, integer, string) & type has to be identified at run time.

Ex -
1) Key = delhi has 2 attributes ( pollution_level & population)
2) Key = jakarta has 3 attributes (latitude, longitude, pollution_level)
3) Key = bangalore has 4 attributes (extra - free_food)
4) Key = india has 2 attributes (capital & population)
5) Key = crocin has 2 attributes (category & manufacturer)

Example of Secondary index:
Get all keys (cities) where pollution_level is high. Get all medicines by manufacturer (GSK)
So, in a nutshell, value must be strongly typed when defined.

Attribute
1. Attribute is uniquely identified by its name (latitude, longitude etc.
2. Data type of the attribute is defined at the first insert. (i.e. data type of pollution_level is set when key = delhi is inserted)
3. Once data type is associated with a particular attribute, it cannot be changed.
(i.e. free_food when defined takes type = boolean, hence, any key when using the attribute - free_food must allow only boolean values on subsequent inserts/updates)

Non-functional requirements

Highly scalable - Support for high throughput with very low latency
Highly available
Shared nothing architecture i.e. Support for Multiple nodes and each node is independent & self-sufficient.
Stretch - Smart client i.e. clients being aware of available servers & makes smart routing based on that available information.

TPM interview question. In this tech company, backend engineers quickly develop/ prototype and test new features with live data on the server by some framework, how do you extend a similar framework to mobile app developers as well to use such prototype features and validate with live data. It was a very abstract question. To me it sounded more like sandbox testing. The key requirement was to on the fly develop new features and test with live data. I spoke about prototyping engines, sdk for the backend service to be integrated to the mobile apps, and these apps could use the same canary rollout data or a backup of live data. There wasn't a definitive answer more of a thought process question. I mentioned nuances in mobile app context like less resources, pagination requirement etc. Appreciate if some one has been asked or familiar with a similar question and any responses are appreciated.

You are given a series of arithmetic equations as a string, such as:

y = x + 1
5 = x + 3
10 = z + y + 2
The equations use addition only and are separated by newlines. Return a mapping of all variables to their values. If it's not possible, then return null. In this example, you should return:

{
x: 2,
y: 3,
z: 5
}

Question: TPM interview question. In this big tech company, backend engineers quickly develop/ prototype and test new features with live data on the server by some framework, how do you extend a similar framework to mobile app developers as well to use such prototype features and validate with live data. It was a very abstract question. To me it sounded more like sandbox testing. The key requirement was to on the fly develop new features and test with live data. I spoke about prototyping engines, sdk for the backend service to be integrated to the mobile apps, and these apps could use the same canary rollout data or a backup of live data. There wasn't a definitive answer more of a thought process question. I mentioned nuances in mobile app context like less resources, pagination requirement etc. Appreciate if some one has been asked or familiar with a similar question and any responses are appreciated.

Design twitter trending topics feature to show trending topics in past 24 hours.

Q.1 Rather than separate T[1…m] into two half size arrays for the purpose of merge sorting, we
might choose to separate it into three arrays of size x%3, (x+1)%3, and (x+2)%3, to sort each of
these recursively, and them to merge the three sorted arrays. Give a more formal description of
this algorithm and analyze its execution time. Justify your answer with example.

Given two very large files – first contains Id and name, another one contains Id and address – you need to create 3rd file which will contain id, name, and address. -First, ask the clarifying questions and then tell the approach.

Two tables employee (contains name and Id) and employee details having work experience history (contains Id, fromYear, toYear) – find out all the employees who worked w/o career break.
Java implementation for the same.
From the same table list the name, fromYear, toYear for all employee.
Dependency Injection.
Design patterns which can be used.

VERY IMPORTANT C PROGRAMMING QUESTION. PLEASE HELP. DUE DATE: 19.05.2020 21:00 (I HAVE 7 HOURS TO SUBMIT QUESTION)
Your task is to find the given list of words inside a given character grid. The dimensions of the character grid will be 8 x 8. Each cell of the character grid will contain one of the capital letters in the English alphabet.

The inputs of the program will be as follows:

1) First, a 8 x 8 character grid will be given as input where each row will be given in separate lines. Each row of the character grid will be separated from other rows with a newline character ('\n') including the last row.

2) Next, the number of list of words to be found will be given as input in a separate line ending with a newline character.

3) Finally, the list of words to be found inside the character grid will be given as input in separate lines. Each word in the list will be separated from other words with a newline character ('\n') including the last word.



The properties of the character grid and the rules for finding the words are given as follows:

1) The number of list of words may be at least 1 and at most 15.

2) The length of each word in the list of words will be at least 3 and at most 8 characters.

3) Each word in the list of words may be located inside the character grid in any of:

a) horizontal which is left to right,

b) vertical which is up to down,

c) diagonal which either

i) starts at an upper-row-left-column and ends with a lower-row-right-column (e.g. a 3 characters length word "PIE "which starts at (1,2) and ends at (3,4) ),

ii) starts at an upper-row-right-column and ends with a lower-row-left-column (e.g. a 4 characters length word "FEEL" which starts at (2,6) and ends at (5,3) )

directions where each letter that compose that word should be located in the neighboring cells. The directions other than the given above will not be considered while searching any word inside the character grid.

4) When your program finds a word inside the character grid, the letters that compose that word should be substituted with the "#" character.

5) While searching words inside the character grid, you should consider that a character inside the character grid may be reused to find more than 1 word. Check the sample run for a concrete example.

6) All the words in the list of words will be available on the character grid.

7) All the words inside the list of words will be distinct.

8) A word inside the character grid will appear only once in the character grid: It is not possible to find any word more than one location inside the character grid.

9) When the list of words is input by the user, the order of the words IS NOT necessarily an alphabetical order.

10) The word is guaranteed to be found inside the character grid if you search in all (vertical, horizontal or diagonal) directions.



Your program is expected to output the final modified version of the character grid where all the words in the list are substituted with "#" in the character grid and the remaining letters are left as is. Similar to input format, each row of the modified character grid will be printed in distinct rows separated with newline character ('\n') including the last row as output.


Sample Run

----------

Input:

AWESOMEA

DEKTTADR

DZLZQUOC

RPEYRMDL

EEAEAPRY

SFFNQBDA

SSFTMASN

AWESOGER

5

ADDRESS

STUDY

LEAF

ROMAN

AWESOME



Output:

#######A

#EKT#AD#

#Z#ZQ##C

#P#YR##L

#E#E#PR#

#F##QBDA

#SFTMASN

AWESOGER



Explanation of Sample Run:

The following character grid is input by the user:

AWESOMEA

DEKTTADR

DZLZQUOC

RPEYRMDL

EEAEAPRY

SFFNQBDA

SSFTMASN

AWESOGER



The number of list of words is 5

The list of words are:

ADDRESS

STUDY

LEAF

ROMAN

AWESOME



The row and column numbers of the character grid are written below to follow the explanations, clearly.


0 1 2 3 4 5 6 7
0 A W E S O M E A
1 D E K T T A D R
2 D Z L Z Q U O C
3 R P E Y R M D L
4 E E A E A P R Y
5 S F F N Q B D A
6 S S F T M A S N
7 A W E S O G E R






1. The letters of "ADDRESS" are found in the zeroth to the sixth row, all in column 0. These letters are substituted with the "#" character. Then, the modified character grid becomes as follows:

#WESOMEA

#EKTTADR

#ZLZQUOC

#PEYRMDL

#EAEAPRY

#FFNQBDA

#SFTMASN

AWESOGER



2. The letters of "STUDY" are found in the diagonal of (0,3),(1,4),(2,5),(3,6),(4,7) where the numbers in the parenthesis represent (row, column) numbers, respectively. These letters are substituted with the "#" character. Then, the modified character grid becomes as follows:

#WE#OMEA

#EKT#ADR

#ZLZQ#OC

#PEYRM#L

#EAEAPR#

#FFNQBDA

#SFTMASN

AWESOGER



3. The letters of "LEAF" are found in the second to the fifth row, all in column 2. These letters are substituted with the "#" character. Then, the modified character grid becomes as follows:

#WE#OMEA

#EKT#ADR

#Z#ZQ#OC

#P#YRM#L

#E#EAPR#

#F#NQBDA

#SFTMASN

AWESOGER



4. The letters of "ROMAN" are found in the diagonal of (1,7),(2,6),(3,5),(4,4),(5,3) where the numbers in the parenthesis represent (row, column) numbers, respectively. These letters are substituted with the "#" character. Then, the modified character grid becomes as follows:

#WE#OMEA

#EKT#AD#

#Z#ZQ##C

#P#YR##L

#E#E#PR#

#F##QBDA

#SFTMASN

AWESOGER



5. The letters of "AWESOME" are found in the zeroth to sixth column, all in row 0. These letters are substituted with "#" character. Notice that 'S' in row 0 is used both for the words "AWESOME" and "STUDY". Also, 'A' at (0,0) is used both for the words "ADDRESS "and "AWESOME". Since there are 5 words, there is no word remaining to find in the character grid. Hence, your program should print the final version of the grid given below on the screen, where each row will be separated with a newline character ('\n') including the last row.



#######A

#EKT#AD#

#Z#ZQ##C

#P#YR##L

#E#E#PR#

#F##QBDA

#SFTMASN

AWESOGER

Love Life Problem Solution

Given a binary matrix of size M * N. You are given H and V where H denotes the number of horizontal cuts and V represents number of vertical cuts. You need to find whether you can make H and V amount of cuts such that each submatrix formed after the cuts will have equal number of 1. E.g.

4 5
1 1 1 1 1
0 0 1 1 1
0 1 1 1 1
1 0 1 1 1
Given H=1 and V=3, we can make 1st horizontal cut after 2nd row and 3 vertical cuts after 2nd, 3rd and 4th column such that each of the sub matrix will have equal number of 1s.

| ----------------|
| 1 1 | 1 | 1 | 1 |
| 0 0 | 1 | 1 | 1 |
| ----------------|
| 0 1 | 1 | 1 | 1 |
| 1 0 | 1 | 1 | 1 |
| ----------------|