## Senior Software Development Engineer Interview Questions

- 0of 0 votes
Given a dependency list of libraries (where an item is: library X depends on library Y) generate a list describing the order in which libraries should be loaded.

Additional request: detect circular dependencies.

- 1of 1 vote
Design the (content) search autocomplete feature on Kindle

- 0of 0 votes
A paper consists of a series of consecutive numbers from 1 up to 2^n values. For example,

For case 2^1, content of the paper is,

1 2

For case 2^2, content of the paper is,

1 2 3 4

For case 2^3, content of the paper is,

1 2 3 4 5 6 7 8

There will be n number of commands for 2^n case. Below are the commands,

L – Fold the paper from Left edge to Right edge

R – Fold the paper from Right edge to Left edge

After performing the n number of commands, there will be a single number in all layer of paper, you need to write down the numbers in all layers when you see the paper from upside of it.

Please provide an efficient algorithm.

Example:

Content of the paper (2^3):

1 2 3 4 5 6 7 8

Commands: LRL

Output:

5 4 1 8 7 2 3 6

- 0of 0 votes
Suppose you have two arrays of objects. How would you find the common elements among them? How would you optimize the solution to avoid additional space?

- 0of 0 votes
Implement Priority Queue

- 0of 0 votes
Implement Least Recently Used Cache for IPAddress lookup. Assume max cache size is 1000 but it should scale well with larger number

Key of the cache is server name and value is IPAddress.

- 1of 1 vote
Given a string left rotate it by given number of times with O(n) solution

- 1of 1 vote
Given a array where each element is maximum +-k index away from it's sorted position, find an algorithm to sort such array.

- 1of 1 vote
Implement cycle detection for a spreadsheet with the characteristics outline below. Your solution should include working data structures to represent the spreadsheet and operate on a "entire" spreadsheet to indicate which cells have circular dependencies.

Spreadsheet

The spreadsheet is a collection of cells within a 2-D space of columns and rows. Columns are defined with a letter and rows are defined by a number. You can assume an upper limit of 26 columns for simplicity.

Cell values are either a number (long or double) or an expression containing numbers, operators, and references to other cells (i.e. B2 means the second column [B] and second row [2]). You can ignore the parsing of expressions for this exercise. Instead, your solution can define the data you will work with after expressions have been parsed.

Cycles

A cycle occurs when a cell refers to itself either directly or indirectly via an expression.

- 0of 0 votes
You have a coffee shop with say, a 1000 flavors of coffee. You always face a customer query asking for a certain number of coffee flavors that are closest matches to what they are drinking. Write a function which would take a coffee flavor and find a certain

number of closest flavor matches in terms of flavor.

- 0of 0 votes
You have a requirement where a user searches for a search term, which could be say, the title of a movie

and you need to find the title and then show a description of the movie. How would you implement it. Describe the data structures used. If you were going to host this service on a single machine with 250 MB of RAM while you need to handle, say 10 GB of data, how would you do this?

- 0of 0 votes
There are N pots. Every pots has some water in it. They may be partially filled . Every pot is associated with overflow number O which tell how many minimum no. of stones required for that pot to overflow. The crow know O1 to On(overflow no. for all the pots). Crow wants some K pots to be overflow. So the task is minimum number of stones he can make K pots overflow in worst case.

Array of overflow no--. {1,...On}

Number of pots--n

No of pots to overflow-- k

Let say two pots are there with overflow no.s {5,58}, and crow has to overflow one pot(k=1). So crow will put 5 stones in pot with overflow no.(58), it will not overflow, then he will put in pot with overflow no.(5), hence the total no. of stones to make overflow one pot is=10.

What are the best algorithm to do it?

- 1of 1 vote
Implement a program to reverse the linear linked list in pairs. it should handle both even number of nodes and odd number of nodes. if odd number of nodes, the last node will be the last node after reversion.

Do not move the data in the nodes. Do manipulate node pointers/references. the nodes themselves need to be manipulated, not just the data in the nodes.

For example, if the initial linear linked is,

1->2->3->4->5

after reverse it should be,

2->1->4->3->5

- 1of 1 vote
Implement a function that checks if the given binary tree is binary search tree(BST). Use tree operations to solve this. do not try solving by pre-order traversal of the tree and then checking if the array is sorted.

instead, traverse the tree for checking if it is BST.

- 0of 2 votes
Write a function that takes two arguments one array of integers that ranges between 0 and 9 and second the target sum(again integer). It produces all permutations strings of the input digits that equals the target sum.

For example, if input is array 2, 3, 5 and target sum is 10, then the output should be:

22222 because 2+2+2+2+2 = ,10

2323 as 2+3+2+3 = 10

3232

55

2233

3322

532

235

352

etc.,

- -1of 3 votes
Write a function which returns the number of times the digit "1" appears in a number which is generated from raising 11 to the Nth power where N is passed in as an input parameter. The range of N is 0 to 1,000.

Be sure to unit test your solution.

For instance, If N is 3, the number is 1331 and the function returns 2.

If N is 5, the function returns 3.

If N is 10, the function returns 1 and so on.`public int solution(int N) { ... }`

You have 30 minutes to complete the problem.

- 0of 0 votes
I was given 90 minutes to complete this test.

I didn't understand how the sample test cases arrived at their return output. Can anyone explain?

================

Approximate Matching (Coding)

You are given 3 strings: text, pre_text and post_text. Let L be a substring of text.

For each substring L of text, we define pattern_score as follows:

* pre_text_pattern_score = highest n, such that first n characters of L are equal to the last n characters of pre_text and occur in the same exact order.

* post_text_pattern_score = highest n such that last n characters of L are equal to the first n characters of post_text and occur in the same exact order.

* pattern_score = pre_text_pattern_score + post_text_pattern_score

For example, if L = "nothing", pre_text = "bruno", and post_text = "ingenious", then

* pre_text_pattern_score of L is 2 because the substring "no" is matched, and

* post_text_pattern_score is 3 because the substring "ing" is matched.

* pattern_score is 5 = 2 + 3

Your program should find a non-empty substring of text that maximizes pattern_score.

* If there is a tie, return the substring with the maximal pre_text_pattern_score.

* If multiple answers still have a tied score, return the answer that comes first lexicographically.

Complete the definition of function string calculateScore(string text, string prefix,string suffix)

Constraints:

* text, pre_text, and post_text contain only lowercase letters ('a' - 'z')

* 1 <= |text| <= 50

* 1 <= |pre-text| <= 50

* 1 <= |post-text| <= 50

(where |S| denotes the number of characters in string S)

* It is guaranteed that an answer will always exist; i.e. there will always be a substring in text that matches either at least one character at the end of pre-text or at least one character at the beginning of post-text.

Sample case #1

text: "nothing"

prefix: "bruno"

suffix: "ingenious"

Returns: "nothing"

Sample case #2

text: "ab"

prefix: "b"

suffix: "a"

Returns: "b"

- 1of 1 vote
This is design question. Starts with small data size and then goes with bigger data size

Design an application to retrieve the value for a key as fast as possible. The data given to you doesnt change.

You are given a data file of 1GB. Its key value data with key being bytes[]. What would be your application design.

Now assume the data set is 1 TB or greater how would you change your application design.(Distributed is a possibility).

Now assume the keys are very small. What are your optimizations.

- 0of 0 votes
You are given a list of strings

/flapp/server/apache

/d/apps

/d/apps/pub

/flapp

/flocal/firms

/d/sw/java

/d/sw/orcl/jdbc

The filtered strings shoud be

/flapp

/d/apps

/d/sw/java

/d/sw/orcl/jdbc

/flocal/firms

You have to identify the problem/requirement and provide solution that can work for any input with similar pattern.

- -1of 1 vote
It started with simple behavioral questions like, why facebook, cultural fit questions etc. They asked simple question.

`You are at latest version of committed code. assume one branch of code. Code version is in sorted order. It is corrupted with bug. You have fun isBug(VerNumber) which returns True or False. Find the version in which bug was introduced?`

This can be solved with linearly checking each version or modified binary search. Person asked to write test cases? This is where i struggled. how do you write test case for this question? Do you guys use framework syntax or something else?

- 1of 1 vote
Given row on N house, each is marked either R or B. And each house having some gems. You have to collect gems from these house with some constraint:

You can choose gems from any blue house but you have to choose even number of red house ( either from 2 Red houses or from 4 red houses)

each time you take gem from one house, you will multiply gems received with gems currently, you have.

You have to choose continuous houses.

You have to return start point and end point of house (remember this should be continuous )

- 5of 5 votes
you have given array of Size N and two numbers M, K. K is size of subarray and M is count of subarray.

You have to return sum of max M subarray of size K (non-overlapping)

N = 7, M = 3 , K = 1

A={2 10 7 18 5 33 0} = 61 — subsets are: 33, 18, 10 (top M of size K)

M=2,K=2

{3,2,100,1} = 106 - subsets are: (3,2), (100,1) 2 subsets of size 2

- 0of 0 votes
How can I represent the following in a data structure ?

<html><body><div><span>TEXT1</span><br/></div></body></html>

Do I do the same using a stack or create a tree for the same ?

- 0of 0 votes
Given an array A and an array B. Sort all the elements of A in the order of B. Sort the remaining elements.

e.g.

A = {4,2,7,6,8,9,1,3,2,5,6}

B = {6,3,4,1}

Output= {6,6,3,4,1,2,3,5,7,8,9}

- 0of 0 votes
Check if 2 link lists merge or not. If yes, return the 1st common node.

- 0of 0 votes
Check if an integer is a power of 2 or not.

- 0of 0 votes
Input a matrics, print the elements one by one:right->left down->left->up. The 1st line is the matrics size, then follows the matrics elements. Ex:

5 3

1 2 3 4 5

6 7 8 9 10

11 12 13 14 15

First loop:

starts from the top left '1';

1: to right, print 1,2,3,4,5

2: to left down, print 9,13

3: to left, print 12,11

4: to up, print 6 ('1' has been print, ignore)

Second round:

1: to right, print 7,8

2: no more elements to print

So the elements should be:

1,2,3,4,5,9,13,12,11,6,7,8

- 0of 0 votes
Implement algo for ls command in unix. You have n ordered file names with you. You have to print file names in column then in rows.

e.g. I have 5 files

F1 F3 F5

F2 F4

Minimize on number of rows

Maximize on number of columns

Max Page Width possible P

Page width of any row = max width of all files in first column + max width of all files in second column + ... +max width of all files in last column

- 1of 1 vote
Asked at Walmart Labs

----------------------------------

There is a row of seats. Assume that it contains 15 seats adjacent to each other. There is a group of people who are already seating in that row randomly. i.e. some are sitting together & some are scattered.

Take the row as a String in java.

The seat which is occupied is marked with a character 'X' & which is not occupied is marked with a dot '.'

Now your target is to make the whole group sit together i.e. next to each other and without having any vacant seat between them in such a way that the total number of hops or jumps at the end of the grouping them together should be minimum.

Ok let me try to explain you in details.

Here is the row having 15 seats represented by the String (0, 1, 2, 3, ......... , 14) -

. . . . x . . x x . . . x . .

Now to make them sit together one of approaches is - . . . . . . x x x x . . . . .

Following are the steps to achieve this -

1 - Move the person sitting at 4th index to 6th index - Number of jumps by him = (6 - 4) = 2

2 - Bring the person sitting at 12th index to 9th index - Number of jumps by him = (12 - 9) = 3

------------------------------------------------------------------------------------------------------------------------------------------------------------

So now the total number of jumps made = ( 2 + 3) = 5 which is the minimum possible jumps to make them seat together.

There are also other ways to make them sit together but the number of jumps will exceed 5 & that will not be minimum.

For example bring them all towards the starting of the row i.e. start placing them from index 0. In that case the total number of jumps will be ( 4 + 6 + 6 + 9 ) = 25 which is very costly and not an optimized way to do this movement.

Now write an algorithm which will return the minimum number of jumps required to make them sit together.

- 0of 0 votes
find out the subset of an array of continuous positive numbers from a larger array whose sum of of the elements is larger in comparision to other subset. eg: {1,2 5 -7, 2 5} .The two subarrays are {1,2,5} {2,5} and the ans is {1,2, 5} as its sum is larger than{2,5}