## Software Developer Interview Questions

- 0of 0 votes

AnswersYou are given a rooted tree. The tree is not necessarily binary. The tree contains N nodes, labeled 1 to N. You are given the tree in the form of an array P[1..N] of size N. P[i] denotes label of the parent of node labeled i. For clarity, you may assume that the tree satisfies the following conditions.

- evostorm96 November 15, 2017 in India

The root of the tree is labeled 1. Hence P[1] is set to 0.

The parent of node T will always have a label less than T. Hence P[i] < i will always be true.

All nodes contain a mutable value (or, more simply, a variable), which is initially set to 0.

You are asked to perform several operations of the following type

ADD X Y: add Y to the value at node X.

ADDUP X Y: add Y to the value at node X. Then, add Y to the value at P[X] (i.e. the parent of X). The, add Y to the value at P[P[X]] (i.e. the parent of P[X]).. and so on, till you add Y to the value at root.

After you have performed all the given operations, you are asked to answer several queries of the following type

VAL X: print the value at node X.

VALTREE X: print the sum of values at all nodes in the subtree rooted at X (including X).

Input

The first line of input contains the number T, the number of test cases. Then follows the description of T test cases. The first line of each test case contains the numbers N, M and Q respectively (separated by single space character). N depicts the number of nodes. M depicts the number of operations you must perform. Q depicts the number of queries you must answer.

The next N lines contain a number each, depicting the array P[1..N]. Of course the number on the first such line is always 0.

The next M lines contain description of the respective operation. An operation will be either "ADD X Y" or "ADDUP X Y" (without the quotes). Please refer to the problem statement and sample I/O explanation for clarity on the meaning of the operations.

After the operations, the next Q lines contain description of the queries. A query will be either "VAL X" or "VALTREE X" (without the quotes). Please refer to the problem statement and sample I/O explanation for clarity on the meaning of the queries.

Output

Print the result of each query on a line by itself. Since the answer for some queries may be too large, please print the result modulo 1,000,000,007. Do not print any blank lines between test cases.

Constraints

1 ≤ T ≤ 10

1 ≤ N ≤ 50000

1 ≤ M ≤ 50000

1 ≤ Q ≤ 50000

1 ≤ X ≤ N

1 ≤ Y ≤ 50000

The input file will be smaller than 2 MB.

Sample Input

2

5 5 3

0

1

1

1

3

ADD 1 10

ADD 2 20

ADD 3 30

ADD 4 40

ADDUP 5 50

VAL 3

VALTREE 3

VALTREE 1

7 4 5

0

1

2

2

2

1

2

ADD 6 76

ADDUP 1 49

ADD 4 48

ADDUP 2 59

VALTREE 1

VALTREE 5

VAL 5

VALTREE 2

VAL 2

Sample Output

80

130

250

291

0

0

107

59

Explanation

In the first sample case, at the end of app the operations, the values at each of the nodes is as follows

1: 60

2: 20

3: 80

4: 40

5: 50

Also, the sum of the values of all the nodes in the subtree rooted at each of the nodes is as follows

1: 250

2: 20

3: 130

4: 40

5: 50| Report Duplicate | Flag | PURGE

Directi Software Developer - 0of 0 votes

AnswersYou are given a grid with 3 rows and N columns. Each cell in the grid contains the value 0 initially. You perform several operations of the following type on the grid

- evostorm96 November 15, 2017 in India

Pick a row, say r. Pick a start column and end column, say s and e. Of course 1 ≤ s ≤ e ≤ N. Now, set all values in the grid in row r, from column s to column e to 1.

After you perform all the operations, you wish to find subgrids in this grid (or rectangles, if you please) which contain only 1s. Most importantly, you wish to find the rectangle that has the largest area. Print the area of this rectangle.

Input

The first line of input contains a number T, the number of test cases. The first line of each test case contains the number N and M respectively, separated by a single space. N is the number of columns in the grid. M is the number of operations you perform on the grid. Each of the next M lines contain three integers R, C1 and C2 respectively to describe the operation. R is the row in which the operation is performed. C1 and C2 are the start and end columns respectively. You may assume that 1 ≤ C1 ≤ C2 ≤ N.| Report Duplicate | Flag | PURGE

Directi Software Developer - 0of 0 votes

AnswersImplement zad-off-chu sequence for LTE eNodeB in c language?

- subhraprakash79 November 14, 2017 in United States| Report Duplicate | Flag | PURGE

Qualcomm Software Developer C - -2of 2 votes

AnswersThere was given total physical energy H and total distance D. Five pace information speed and corresponding physical energy was given. Find the minimum time that is required in order to complete total distance D making sure that some of the physical energy does not exceed H

- sonuanand2007 November 11, 2017 in India| Report Duplicate | Flag | PURGE

Samsung Software Developer - 0of 0 votes

AnswersRobot hand movement

- akira November 08, 2017 in United States

Given a (1) string message (consisting of only upper case alphabets), and (2) width of keyboard, output the movements required by an automated robot hand to print out the string message.

The robot hand can move right, left, up or down. It cannot move diagonally.

Ex 1:

String message: “HI”

Width: 26

Output: R8, T, R1, T

Ex2:

String message: “HELLO”

Width: 13

Output: R8, T, L3, T, R7, T, T, D1, L10, T| Report Duplicate | Flag | PURGE

Software Developer Algorithm - 0of 0 votes

AnswersGiven a set of strings (denoting URLs), like:

- lkjhgfdsa October 27, 2017 in United States

1. abc.pqr.google.com

2. pqr.google.com

3. pqr.google.net

4. yahoo.com

5. abc.yahoo.com

etc...

find an efficient way to find out how many times a particular string appears as a substring. For e.g., given the above set of strings, "google.com" appears twice; ".com" appears four times, "pqr.google.com" appears twice, and so on.

Follow up: How would you do this, if the input was no longer a URL (So, "abc.pqr.google.com" and "pqr.abc.google.com", both are valid)?| Report Duplicate | Flag | PURGE

Google Software Developer - 2of 2 votes

Answersnode {

- ajay.raj October 23, 2017 in United States

node * left, * right;

}

Given a list of node to determine whether the node in the list can form a valid binary tree. several points of judgment

1. need to ensure that all left, right pointer point to the node inside list

2. no cycle

3. All node must be connected

Boolean isValidTree(List<Node> list){}| Report Duplicate | Flag | PURGE

Facebook Software Developer - 1of 1 vote

AnswersGiven a matrix of N * M, given the coordinates (x, y) present in a matrix,

- ajay.raj October 23, 2017 in United States

Find the number of paths that can reach (0, 0) from the (x, y) points with k steps (requires exactly k, k> = 0)

From each point you can go up, down, left and right in four directions.

For example, the following matrix:

----------

0 0 0 0 0

0 0 0 0 0

0 0 0 0 0

0 0 0 0 0

(x, y) = (1, 1), k = 2, the output is 2| Report Duplicate | Flag | PURGE

Facebook Software Developer - 0of 0 votes

AnswersGiven a non-negative integer n, check if it is possible to build a pyramid of '*' and empty spaces where first row has one '*' and second has three '*' and so on.

- akira October 19, 2017 in United States

For example-

Input: n =4 Output: True

Explanation : The pyramid can be build

*

***

Input: n = 9 Output: True

Explanation : The pyramid can be build

*

***

*****

Input: n = 6 Output: False

Explanation : The pyramid cannot be build as last row will be incomplete

*

***

**| Report Duplicate | Flag | PURGE

Nutanix Software Developer Algorithm - 0of 0 votes

AnswersalphaAndarabic

- howard25330 October 13, 2017 in United States

given a set of character, ex: 'A' 'B' 'C',

each char have its representative number:

A = 1, B = 13, C= 110;

when the char next to current index is smaller than current we add ex: CBA = 110+13+1

when the char next to current index is bigger than current we all the answer in prev will become minus sign(but not the last one) ABC -1 - 13 + 110 = 96;

calculate the number for each string input;| Report Duplicate | Flag | PURGE

Epic Systems Software Developer - -2of 6 votes

AnswersHow will you test "Hello world" program?

- gagan.ping October 12, 2017 in India| Report Duplicate | Flag | PURGE

Google Software Developer Algorithm - 0of 0 votes

AnswersHow to Design Netflix.(System Design)

- mayankesh911 September 30, 2017 in India| Report Duplicate | Flag | PURGE

Amazon Software Developer System Design - 0of 0 votes

AnswersHow to Design App-Store like google play.(System Design)

- mayankesh911 September 30, 2017 in India| Report Duplicate | Flag | PURGE

Amazon Software Developer System Design - 0of 0 votes

AnswersGiven an array of strings, find out in how many cases is any of the anagrams of the string at location i, a substring of the string at location i+1.

- lkjhgfdsa September 30, 2017 in United States

Test Case I: ["ab", "ab", "abc", "bca"]

Answer: 3

Test Case II: ["ab","aqb"]

Answer: 0| Report Duplicate | Flag | PURGE

Google Software Developer Algorithm - 0of 0 votes

AnswersGiven a target sum, populate all subsets, whose sum is equal to the target sum, from an int array.

- milincjoshi September 28, 2017 in United States

For example:

Target sum is 15.

An int array is { 1, 3, 4, 5, 6, 15 }.

Then all satisfied subsets whose sum is 15 are as follows:

15 = 1+3+5+6

15 = 4+5+6

15 = 15| Report Duplicate | Flag | PURGE

Google Software Developer - 0of 0 votes

AnswersGenarate and validate a magic matrix.A magic matrix is one in which the sum of every row,column,and every diagonal is same.One such matrix will be when every element in the matrix is same.generate and validate a magic matrix where every element is not the same

- prashant.tah September 27, 2017 in India| Report Duplicate | Flag | PURGE

Oracle Software Developer - 0of 0 votes

AnswersYou are given a stream of numbers which represent the stock prices of a company with timestamp. You need to perform some set of operations on the stream of data efficiently as below: 1. findStockPriceAtGivenTimeStamp(Timestamp) 2. deleteAndGetMinimumStockPriceForToday() Timstamp: 1 2 3 . 4 . 5 Prices: 12 34 4 . 1 . 18

- bholeNath September 18, 2017 in India| Report Duplicate | Flag | PURGE

Amazon Software Developer Data Structures - 0of 0 votes

AnswersWrite algorithm for java grep command for word matching in the following context.Given a file containing n words.Given a word w and a number k.Find k words in the file occuring before occurence of w.Assume that the average word size is m in the file

- prashant.tah September 12, 2017 in India

eg.

aaa

bbb

ccc

booking

alpha

beta

gamma

for k=3 and w = booking

the output should be [aaa,bbb,ccc,booking]

similarly for k =2 and w = beta

output should be [booking,alpha,beta]

Assume that the file size can grow very large

and try to get solution with space complexity lesser than O(n)

I suggessted solution for iterating through file until the word w is found and maintaiining a queue of size K

The time complexity of my solution was O(nm)

and space complexity was O(k) .Any answers to improve the time and space complexity

Apparently they were looking for a better implementation of grep| Report Duplicate | Flag | PURGE

Booking.com Software Developer Algorithm - 1of 1 vote

AnswersWe start with a list of Integers. We can remove a group of integers from the list if the all but one equals the remaining number. This removal operation can be performed in the remaining number of list until no more operations can be performed.

- ajay.raj September 07, 2017 in United States

Write a function which can accept an array of integers, and return the minimal number of remaining integers from performing this operation.

Example [1, 3, 5, 6] -> remove 1, 5, 6 , because 1 + 5 = 6, thus only [3] left, so return 1

[48, 20, 1, 3, 4, 6, 9, 24] -> remove 3, 6, 9 , because 3 + 6 = 9, and remove 4, 20, 24, 48, because 4 + 20 + 24 + 48, thus only [1] left, so return 1

int left(int[] nums){

}| Report Duplicate | Flag | PURGE

Facebook Software Developer - 0of 0 votes

AnswersConsider an N*N game board, with a black and white pieces that can be placed on it. You are given a board with placed pieces around it in a random spots.

You need to implement a function that determines if a piece (black or white) is captured on a given coordination (x, y).

A piece is defined as captured by the following rules:

1. If all sides (up, down, left & right) contains an opposite piece that surrounds/blocking it.

2. If some of the sides are blocked (for example, right and down) and the other ones are out of bound (OOB defined for coords: x: <= 0, y: <= 0) it's considered as blocked.

3. If one of the sides is empty, it's free.

4. If one of the sides contains the same piece type, and that piece is not captured (by the rules above), it's free.

5. Note that pieces may be captured in a clustered way (related to #4).

For example, consider the following coordinates:

coord(1,1) = B

coord(1,2) = W

coord(2,1) = W`X | 1 | 2 1 | B | W 2 | W |`

For the given coordination 1,1 the result would be `captured` (true).

Another example, consider the following coordinates:

coord(2,2) = W

coord(2,3) = W

coord(3,1) = W

coord(3,2) = B

coord(3,3) = B

coord(3,4) = W

coord(4,2) = W

coords(4,3) = W`X | 1 | 2 | 3 | 4 | 5 | 2 | E | W | W | W | E 3 | W | B | B | B | W 4 | E | W | W | W | E`

For the given coordination 3,2 (or 3,3) the result would be `true` (captured).

If we would either remove one of the W coords (thus making it empty), or change it to be a B piece, the result would be `false` (not captured).

As basic primitive, you are provided with a function that translates coordination into its state:

- johanson1 September 06, 2017 in Netherlands`getState (x, y) == Black, White, Out Of Bound, Empty`

| Report Duplicate | Flag | PURGE

Booking.com Software Developer Algorithm - 1of 1 vote

AnswerExplain the Data Structure which is well suited to implement UNIX commands like PWD, LS, MKDIR, CD in an imaginary OS. No code required.

- neer.1304 September 04, 2017 in United States| Report Duplicate | Flag | PURGE

Cisco Systems Software Developer Data Structures - 0of 0 votes

AnswersUnsorted array and a position ‘P’. Return the element that is likely to come to the given location upon sorting the array. TC in O(n).

- neer.1304 September 04, 2017 in United States| Report Duplicate | Flag | PURGE

Cisco Systems Software Developer Algorithm - 0of 0 votes

AnswerA thief trying to escape from a jail has to cross ‘N’ walls each with varying heights. He climbs ‘X’ feet every time. But, due to the slippery nature of those walls, every times he slips back by ‘Y’ feet. Now the input is given as (N, {H1, H2, H3,….Hn}, X, Y}. Calculate the total number of jumps required to cross all walls and escape from the jail.

- neer.1304 September 04, 2017 in United States| Report Duplicate | Flag | PURGE

Cisco Systems Software Developer Algorithm - 0of 0 votes

Answerstransactions = [

- Pedro September 01, 2017 in United States

{"payee": "BoA", "amount": 132, "payer": "Chase"},

{"payee": "BoA", "amount": 827, "payer": "Chase"},

{"payee": "Well Fargo", "amount": 751, "payer": "BoA"},

{"payee": "BoA", "amount": 585, "payer": "Chase"},

{"payee": "Chase", "amount": 877, "payer": "Well Fargo"},

{"payee": "Well Fargo", "amount": 157, "payer": "Chase"},

{"payee": "Well Fargo", "amount": 904, "payer": "Chase"},

{"payee": "Chase", "amount": 976, "payer": "BoA"},

{"payee": "Chase", "amount": 548, "payer": "Well Fargo"},

{"payee": "BoA", "amount": 872, "payer": "Well Fargo"},

There are multiple transactions from payee to payer. Consolidate all these transactions to minimum number of possible transactions.

HINT: Consolidate transitive transactions along with similar transactions| Report Duplicate | Flag | PURGE

Google Software Developer - 0of 0 votes

AnswersDesign a space shooter program .

- anaghakr89 August 16, 2017 in United States for Nest Labs

Note: The game includes spaceship , bullets and asteroids. Spaceship rotates in 180 degree generating bullets. The position of the bullets gets updated after certain time period every time . No Need to write the code for collision detection

Basic code in expected . Not the entire working code.| Report Duplicate | Flag | PURGE

Google Software Developer - 0of 0 votes

AnswersGiven a list/array of "Assign" trees with integers, operators and variables, return the result of the requested "Result" tree expression.

Example:

- thetinysheep August 13, 2017 in United States`"Assign" / \ "x" "+" / \ 2 3 "Assign" / \ "y" "-" / \ 5000 30 "Assign" / \ "z" "*" / \ 50 x "Return" \ "-" / \ z "*" / \ 1 y`

| Report Duplicate | Flag | PURGE

Facebook Software Developer Trees and Graphs - 1of 3 votes

AnswersThe array of integers in given . The array indicates nothing but the heights of the cylinders. The robotic arm has two ends-> left and right.

- anaghakr89 August 07, 2017 in United States

The left end points to the left end of the cylinder array and right end searched for the cylinder with least height.

ex:

array = {4,5,6,7,1,2}

left end => index 0

right end =>index 0->n giving index 4 with min height

Now the entire block is rotated by 180 degree.

now the array = { 1, 7, 6, 5, 4, 2}

now the left end moves forward.

and right end will search from left index onwards till the end of the array

so left index = 1

right index => 1-> n giving index 5 as min. height

again do the block rotate .

Write the code for this particular algorithm.

However, there is one condition

1. If there are duplicates in the array then the final order of those duplicates should remain the same.

ex. If the cylinder with height 4 is appearing at index 3 and 5 in the initial array then the cylinder at index 3 should always appear before the one at index 5 in the final array.| Report Duplicate | Flag | PURGE

Google Software Developer - -1of 1 vote

AnswersThe array of integers in given . The array indicates nothing but the heights of the cylinders. The robotic arm has two ends-> left and right.

- anaghakr89 July 31, 2017 in United States

The left end points to the left end of the cylinder array and right end searched for the cylinder with least height.

ex:

array = {4,5,6,7,1,2}

left end => index 0

right end =>index 0->n giving index 4 with min height

Now the entire block is rotated by 180 degree.

now the array = { 1, 7, 6, 5, 4, 2}

now the left end moves forward.

and right end will search from left index onwards till the end of the array

so left index = 1

right index => 1-> n giving index 5 as min. height

again do the block rotate .

Write the code for this particular algorithm.

However, there is one condition

1. If there are duplicates in the array then the final order of those duplicates should remain the same.

ex. If the cylinder with height 4 is appearing at index 3 and 5 in the initial array then the cylinder at index 3 should always appear before the one at index 5 in the final array.| Report Duplicate | Flag | PURGE

Google Software Developer - 1of 1 vote

AnswersGenerate a random number with UNIFORM DISTRIBUTION between [0,n) where n is given and excluded list is given. The randomly generated number should belong to the range [0, n) but should be excluded from the given excluded list. For example, n = 10 and excluded list ={2,3,0} then the random number should be from {1,4,5,6,7,8,9} such that any number from the list {1,4,5,6,7,8,9} has UNIFORM probablility of occuring

- xyz July 31, 2017 in United States for NEST| Report Duplicate | Flag | PURGE

Google Software Developer

**CareerCup**is the world's biggest and best source for software engineering interview preparation. See all our resources.

Open Chat in New Window