## Software Developer Interview Questions

- 6of 6 votes

AnswersYou are given a matrix with N rows and N columns. Elements in matrix can be either 1 or 0. Each row and column of matrix is sorted in ascending order.

Find number of 0-s in the given matrix.

Example:`0 0 1 0 1 1 1 1 1 Answer: 3 0 0 0 0 Answer: 4`

Update: Expected complexity is O(log(N)). The best I've seen in comments is still O(N).

- emb June 26, 2016 in United States

Update2: Alright, guys, sorry for a bit of trolling. Obviously this is not possible to do faster than O(N). Here is why: take a diagonal (N, 1), (N-1, 2), ... (1, N). Suppose input matrix has all 0's above this diagonal and all 1's under this diagonal. So only diagonal elements vary. Clearly, diagonal elements do not depend on each other. So we have to analyze each diagonal element which is O(N).

Nice job, @gen-y-s :)| Report Duplicate | Flag | PURGE

Google Software Developer Algorithm - 0of 0 votes

AnswerGiven M nodes and at most one outgoing edge from any node. Given Q operations where an operation is either

- lifeenergy999 June 19, 2016 in India

i) 1 Z where Z represent the source node, print the terminal node if a coin travels through edges. In case, if node Z lies in a cycle, print LOOP. 1 is the operation type

ii) 2 Z where Z represents node for which the outgoing edge is removed and 2 is operation type.

Operations are performed in order in which they are given.

M <= 3*10^5, Q <= 3*10^5

Input

First line contains integer M.

Second line contains M integers, where ith integer represents outgoing edge from ith node. If outgoing edge is 0, that means there is no outgoing edge from this node.

Third line contains integer Q followed by Q lines where each line is either 1 Z, or 2 Z where Z is node number. Nodes are 1-indexed.

This question was asked in coding test. Can somebody please help me with this problem with the given constraints?| Report Duplicate | Flag | PURGE

Software Developer Algorithm - 1of 1 vote

AnswersWrite a class to take in a large arbitrary number, also provide a function to increment the number. The number will be passed on as an array of integers.

- pushpinder2751 June 17, 2016 in United States| Report Duplicate | Flag | PURGE

Google Software Developer Algorithm - 0of 0 votes

Answergiven an arraylist of say 50 lac entries and an empty queue, Design a multi-threading bases system which can copy the items in arraylist in a queue parallely

- avidwaj June 12, 2016 in India

How many threads can be spawned based on what criterion ? Basically the interviewer wanted to know how to implement an algorithm where we can design number of threads to be spawned ?| Report Duplicate | Flag | PURGE

Oracle Software Developer design - 1of 1 vote

AnswersWrite a program that takes an integer and prints out all ways to multiply smaller integers that equal the original number, without repeating sets of factors. In other words, if your output contains 4 * 3, you should not print out 3 * 4 again as that would be a repeating set. Note that this is not asking for prime factorization only. Also, you can assume that the input integers are reasonable in size; correctness is more important than efficiency.

- xankar June 07, 2016 in United States

Eg: PrintFactors(12) 12 * 1 6 * 2 4 * 3 3 * 2 * 2| Report Duplicate | Flag | PURGE

Linkedin Software Developer Algorithm - 0of 2 votes

AnswersA robot on a plane has 2 types of commands:

1. move forward by X units (X is integer 0 <= X <= 10000 )

2. rotate by X degrees (X is integer in range [-180, 180] )

A robot looks like`def robot(commands): while True: for command in commands: execute(command)`

Given a list of commands (of size <= 10000) tell if it's possible to build a wall around the robot such that he will never touch it.

Example:

- emb June 06, 2016 in United States`[move(10), rotate(180), move(10)] -> answer is yes [move(10), rotate(45), move(10), rotate(-45), move(10), rotate(45)] - answer is no`

| Report Duplicate | Flag | PURGE

Google Software Developer Brain Teasers - 2of 2 votes

AnswersYou are given a range [first, last], initially white. You need to paint it black.

For this purpose you have a set of triples

[(f, l, cost), ...] - where each triple means that you can paint range [f, l] for `cost` coins (limitations: cost is floating point >= 0, f, l, first, last are integers).

Find minimum cost needed to paint the whole range [first, last] or return -1 if it's impossible

Example:`[first, last] = [0, 5] and set of triples is [[0, 5, 10], [0, 4, 1], [0, 2,5], [2, 5, 1]]`

Clearly the answer is to take [0, 4, 1] and [2, 5, 1] - the total cost will be 2.

Another example:`[first, last] = [0, 5] triples are [[1,4, 10], [2, 5, 6]]`

answer is -1, because it's impossible to color whole range.

- emb June 05, 2016 in United States| Report Duplicate | Flag | PURGE

Google Software Developer Algorithm - 3of 3 votes

AnswersGiven an array of length N and an integer K, sort the array as much as possible such that no element travels more than k positions to its left - an element however can travel as much as it likes to its right.

- testing@123 June 01, 2016 in United States| Report Duplicate | Flag | PURGE

Google Software Developer Algorithm - 1of 1 vote

Answersgiven 2 strings A and B. generate all possible solutions when B is merged in A.

- JerryGoyal May 22, 2016 in India

Ex: A = "hey"

B: "sam"

then solutions are :

heysam,hseaym,hesaym,sahemy etc.

notice that order should be the same for both of strings while merging.| Report Duplicate | Flag | PURGE

Google Software Developer Algorithm - 0of 0 votes

Answers/*

- xankar May 12, 2016 in United States

Prison cell question

In a kingdom there are prison cells (numbered 1 to P) built to form a straight line segment. Cells number i and i+1 are adjacent, and prisoners in adjacent cells are called "neighbors." A wall with a window separates adjacent cells, and neighbors can communicate through that window.

All prisoners live in peace until a prisoner is released. When that happens, the released prisoner's neighbors find out, and each communicates this to his other neighbor. That prisoner passes it on to his other neighbor, and so on until they reach a prisoner with no other neighbor (because he is in cell 1, or in cell P, or the other adjacent cell is empty). A prisoner who discovers that another prisoner has been released will angrily break everything in his cell, unless he is bribed with a gold coin. So, after releasing a prisoner in cell A, all prisoners housed on either side of cell A - until cell 1, cell P or an empty cell - need to be bribed.

Assume that each prison cell is initially occupied by exactly one prisoner, and that only one prisoner can be released per day. Given the list of Q prisoners to be released in Q days, find the minimum total number of gold coins needed as bribes if the prisoners may be released in any order.

Note that each bribe only has an effect for one day. If a prisoner who was bribed yesterday hears about another released prisoner today, then he needs to be bribed again.

Task: find the minimum amount of gold we need to bribe the prisoners so that the chosen prisoners can be released without causing cell destruction.

Input example:

8 cells, 1 prisoner has to be released. The prisoner to be released is the 3rd one.

|1|2|3|4|5|6|7|8|

7 gold coins

another example:

20 cells, 3 prisoners to be released: 3, 6 and 14

|1|2| |4|5| |7|8|9|10|11|12|13| |15|16|17|18|19|20|

release prisoner 3: 19 gold coins

release prisoner 6: 16 gold coins

release prisoner 14: 13 gold coins

release 14: 19 gold coins

release 6: 12 gold coins

release 3: 4 gold coins

input:

number of cells

prisoners that need to be released

output:

least number of gold coins we need to give

*/| Report Duplicate | Flag | PURGE

Amazon Software Developer Brain Teasers - 2of 2 votes

AnswersWrite a method to count the number of 2s between 0 and n.*

- xankar May 12, 2016 in United States| Report Duplicate | Flag | PURGE

Amazon Software Developer Coding - 0of 0 votes

AnswersDesign an algorithm to figure out if someone has won in a game of tic-tac-toe.

- xankar May 12, 2016 in United States| Report Duplicate | Flag | PURGE

Amazon Software Developer Coding - 0of 0 votes

AnswersDesign a hashMap in Java. Implement put, get, remove, resize methods.

- xankar May 10, 2016 in United States| Report Duplicate | Flag | PURGE

Uber Software Developer Algorithm - 0of 0 votes

Answers1) Narrate an instance you optimized or improved a software design.

- xankar May 10, 2016 in United States

2) Given a chance how would you re-think some of the design aspects?| Report Duplicate | Flag | PURGE

Uber Software Developer Behavioral - 0of 0 votes

AnswerDesign a Twitter feeds API. How would you actually connect it from a mobile? What happens behind the Twitter network? how do the Trends get published? From where does Twitter get the information for a particular trend(Eg: #Obama, #nfl) and publish it out? What protocol does it use? How do you connect to Twitter API? How does Twitter handle multiple connections?

- xankar May 10, 2016 in United States| Report Duplicate | Flag | PURGE

Uber Software Developer Software Design - 0of 0 votes

Answers1) Describe your most proudest project, least proudest project

- xankar May 10, 2016 in United States

2) Most inpiring teammate, what did he do?

3) Most awesome manager? Why was he so good?| Report Duplicate | Flag | PURGE

Uber Software Developer Behavioral - 0of 0 votes

AnswersGiven a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

- xankar May 10, 2016 in United States

For example, given

s = "leetcode",

dict = ["leet", "code"].

Return true because "leetcode" can be segmented as "leet code".| Report Duplicate | Flag | PURGE

Uber Software Developer Algorithm - 0of 0 votes

AnswersWrite a function that takes a string representing as value in roman numbers and returns it as an integer.

- joey April 28, 2016 in United States`Implement the following /** * * romanNumber("III") = 3 * romanNumber("IV") = 4 */ int romanNumber(String roman) { // ... }`

| Report Duplicate | Flag | PURGE

Linkedin Software Developer Algorithm - 0of 0 votes

AnswersWrite a function that takes a number and returns the square root

- joey April 28, 2016 in United States`Implement the following double sqrt(double d) { // ... }`

| Report Duplicate | Flag | PURGE

Linkedin Software Developer Algorithm - 0of 0 votes

AnswersGiven a stream of characters (e.g. acacabcatghhellomvnsdb) and a list of words (e.g. ["aca","cat","hello","world"] ) find and display count of each and every word once the stream ends.(Like : "aca" : 2 , "cat" : 1 , "hello" : 1 , "world" : 0 ).

- badebhaiyya April 16, 2016 in United States| Report Duplicate | Flag | PURGE

Booking.com Software Developer Algorithm - 8of 8 votes

AnswersYou are given a graph, some edges are black, some are red. Find a spanning tree with one restriction: if we take some node as root, every path from it to some leaf node must consist of alternating red-black-red-black edges. That is, no path from root to leaf must contain sequential black-black edges or red-red edges.

- emb April 12, 2016 in United States

You are guaranteed that such spanning tree exists.| Report Duplicate | Flag | PURGE

Google Software Developer Algorithm - -1of 1 vote

AnswersProvide a function that allow to compare two strings lexicography, having in mind that these words may contain digraphs (two letters together represents a single one i.e in Spanish ch is a single character ).

- urodba April 07, 2016 in United States

This in order to be able to sort a list of words.| Report Duplicate | Flag | PURGE

Google Software Developer Sorting - 0of 0 votes

AnswersThere are N coins with coordinates (x, y) where x >0 and y >0

- emb April 02, 2016 in United States

You start at (0, 0) and you can only do steps of form (dx, dy) where dx >0 and dy > 0

Print the maximum number of coins that you can collect.

Clarification: you can do as many moves as you wish, the point is to collect maximum number of coins. If you are located at position (a, b) you may jump to position (a+dx, b+dy) for all dx > 0 and dy > 0

@krbchd: Your algorithm may output incorrect values. Suppose there are points (5, 7), (5, 8), (5, 9) for y coordinates LIS will output 7, 8, 9, however since these points are on the same x axis, you can choose only one of them.| Report Duplicate | Flag | PURGE

Facebook Software Developer Algorithm - 0of 0 votes

AnswersFind all the customers who spent >2 minutes on Page "XYZ" & purchased

- LoneStarTexxan March 22, 2016 in United States

>2 items of cofffee_X && gave a review of >3

Objects given:

class PageView {

private String URL;

private String customerID;

private Integer timeSpent;}

class Purchase {

private String productID;

private String customerID;

private Integer itemsPurchased;}

class Review {

private String productID;

private String customerID;

private Integer reviewPoints;}| Report Duplicate | Flag | PURGE

Software Developer Data Structures - 1of 1 vote

Answers#define mysizeof(x) (char*)(&x+1)-(char*)(&x)

- jkl March 20, 2016 in India

//why casting is done to char* for mysizeof

// casting it to void also works| Report Duplicate | Flag | PURGE

HCL Software Developer C - 9of 9 votes

AnswersGiven a packed file with 1Tb of 64-bit doubles (first 8 bytes are first double, next 8 bytes are next, etc) find the exact value of median. For simplicity assume the number of doubles is odd.

- emb March 19, 2016 in United States

You can't modify the file and you have only 8Gb of free memory.

Update: you may use no more than two passes through file and your algorithm shouldn't rely on some nature of file - it should work in all cases.| Report Duplicate | Flag | PURGE

Google Software Developer Coding - 0of 0 votes

AnswersGiven an array of numbers, find the longest alternating subsequence. That is, a subsequence [a1, a2, a3, ..., ak] where a1 > a2, a3 < a2, a4 > a3, ... or vice versa (Graphically looks like /\/\/\... or \/\/\/\....

- emb March 19, 2016 in United States| Report Duplicate | Flag | PURGE

Google Software Developer Algorithm - 0of 0 votes

AnswersJack love playing games, Gluttonous snake( an old game in Nokia era) is one of his favorite. However, after playing gluttonous snake so many times, he finally got bored with the game, so he changed the rules:

- mirrorme March 12, 2016 in United States

Rule 1: Write a code to find the Max sum path in a grid (2-D array), with dimension with n rows and m column (1<=n,m<=500)

Rule 2: In the 2D Array, each cell (elements) contains a value v in the array is from (-1<=v<=99999)

Rule 3. You can start from any position of the leftest column (border) of the array to the rightest(border) column of the array to calculate the Max Sum path.

Rule 4. You can move up, right, down, and CAN'T move left, and can visit each element only one time.

Rule 5.If the element is -1, it means the path is blocked, and you can't go through the path (calculate it in the sum), you have to choose other path to calculate the sum.

For example, if a 4*4 array grid

{{-1,3,2,1}

{2,-1,2,4}

{2,2,-1,3}

{4,2,1,2}};

The max sum path is : (from grid[4][0])

4-->up-->2-->left-->2-->down-->2-->left-->

1-->left-->2-->up-->3-->up-->4-->up-->1

and the sum is 4+2+2+2+1+2+3+4+1 =21

Thank you

Here is my code, I am new in Java and there is still lots of improvements

import java.util.*;

public class MainClass {

public static void main(String[] args) {

@SuppressWarnings("resource")

Scanner rowDimension = new Scanner(System.in);

System.out.print("Enter the number of rows: ");

int firstInput = rowDimension.nextInt();

@SuppressWarnings("resource")

Scanner columnDimension = new Scanner(System.in);

System.out.print("Enter the number of columns: ");

int secondInput = columnDimension.nextInt();

//Input two number to generate 2D Array

Integer [][] array = new Integer[firstInput][secondInput];

//The purpose of the array is check the wall (cell value = -1)

boolean [][] visited = new boolean[firstInput][secondInput];

//Use Math.random() to generate the cell of the array

int[][] randomTable = new int[firstInput][secondInput];

for (int row = 0; row < firstInput; row++) {

for (int column = 0; column < secondInput; column++) {

// multiply by 1000000 to get a number between 0 and 99999

randomTable[row][column] = (int)(Math.random() * 1000000 -1);

System.out.print(randomTable[row][column] + " ");

}

System.out.println();

}

//Start form the left-down location of grid

int i = firstInput-1, j = 0;

visited[i][j] = true;

double sum = array[i][j];

while(true)

{

int max = -1;

int maxi = 0, maxj = 0;

//Case1 : choose path: UP

if(i-1 >= 0 && i-1<= firstInput-1 && j>=0 && j<= secondInput-1 && array[i-1][j] != null && array[i-1][j]>max && !visited[i-1][j])

{

max = array[i-1][j];

maxi = i-1;

maxj = j;

}

//Case2 : choose path: Down

if(i+1 >= 0 && i+1<= firstInput-1 && j>=0 && j<= secondInput-1 &&array[i+1][j] != null && array[i+1][j]>max && !visited[i+1][j])

{

max = array[i+1][j];

maxi = i+1;

maxj = j;

}

//Case3 : choose path: Right

if(i >= 0 && i<= firstInput-1 && j+1>=0 && j+1<= secondInput-1 && array[i][j+1] != null && array[i][j+1]>max && !visited[i][j+1])

{

max = array[i][j+1];

maxi = i;

maxj = j+1;

}

i = maxi;

j = maxj;

visited[i][j] = true;

sum += max;

//To the destination : Right-Up location of the grid

if(i == 0 && j == secondInput-1)

break;

}

System.out.println(sum);

}

}| Report Duplicate | Flag | PURGE

TATA Consultancy Services Software Developer Java - 0of 0 votes

AnswersA flipping rule is given as a follows: Consider a series of positive integer. Take three numbers in the series next to each other. On applying the flipping rule to these numbers, the right most number will go to the left most number position and the other two numbers will move one position to the right at the same time. The rule can be applied to any three numbers present next to each in the series and can be applied as many times as needed.

- Info.Dubey March 03, 2016 in India

Given n as the number of element in the original series, elements of the original series and a target series of a numbers, figures out if the target series can be created by flipping numbers of the original number and output the word “POSSIBLE” followed by the number of times the flipping rule has to be applied. In case, the target series cannot be formed, output the word “IMPOSSIBLE”.

Example :

For a series with 4 elements in it, 1 3 4 2 a new series = 4 3 2 1 can be formed by applying flipping rule as follows, From the table below we can say the output is POSSIBLE 3.

Steps

Series

The three Numbers Flipped

Resultant Series

1

1 3 4 2

1 3 4

4 1 3 2

2

4 1 3 2

1 3 2

4 2 1 3

3

4 2 1 3

2 1 3

4 3 2 1

Example input

Example OutPut

4 1 3 4 2 4 3 2 1

POSSIBLE 3

6 1 2 3 4 5 6 6 5 4 3 2 1

IMPOSSIBLE| Report Duplicate | Flag | PURGE

Infosys Software Developer C++

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

Open Chat in New Window