## Senior Software Development Engineer Interview Questions

- 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}

- 0of 0 votes
Components of computer systems often have dependencies -- other components that must be installed before they will function properly. These dependencies are frequently shared by multiple components. For example, both the TELNET client program and the FTP client program require that the TCP/IP networking software be installed before they can operate. If you install TCP/IP and the TELNET client program, and later decide to add the FTP client program, you do not need to reinstall TCP/IP.

For some components it would not be a problem if the components on which they depended were reinstalled; it would just waste some resources. But for others, like TCP/IP, some component configuration may be destroyed if the component was reinstalled.

It is useful to be able to remove components that are no longer needed. When this is done, components that only support the removed component may also be removed, freeing up disk space, memory, and other resources. But a supporting component, not explicitly installed, may be removed only if all components which depend on it are also removed. For example, removing the FTP client program and TCP/IP would mean the TELNET client program, which was not removed, would no longer operate. Likewise, removing TCP/IP by itself would cause the failure of both the TELNET and the FTP client programs. Also if we installed TCP/IP to support our own development, then installed the TELNET client (which depends on TCP/IP) and then still later removed the TELNET client, we would not want TCP/IP to be removed.

Write a program to automate the process of adding and removing components. To do this we will maintain a record of installed components and component dependencies. A component can be installed explicitly in response to a command (unless it is already installed), or implicitly if it is needed for some other component being installed. Likewise, a component, not explicitly installed, can be explicitly removed in response to a command (if it is not needed to support other components) or implicitly removed if it is no longer needed to support another component.

I found a reference to this problem online.. Check this for i/o details. This is the exact same problem

http://www.cs.cornell.edu/Info/Courses/Spring-98/CS211/assgts/assgt3/assgt3.pdf

- 0of 0 votes
Write a program to find first 20 elements with high density

- 1of 1 vote
/* In "the 100 game," two players take turns adding, to a running

total, any integer from 1..10. The player who first causes the running

total to reach or exceed 100 wins.

What if we change the game so that players cannot re-use integers?

For example, if two players might take turns drawing from a common pool of numbers

of 1..15 without replacement until they reach a total >= 100. This problem is

to write a program that determines which player would win with ideal play.

Write a procedure, "Boolean canIWin(int maxChoosableInteger, int desiredTotal)",

which returns true if the first player to move can force a win with optimal play.

Your priority should be programmer efficiency; don't focus on minimizing

either space or time complexity.

*/

Boolean canIWin(int maxChoosableInteger, int desiredTotal) {

// Implementation here. Write yours

}

- 0of 0 votes
Check if tree is BST.