## Software Engineer / Developer Interview Questions

- 0of 0 votes
You are given an array of integers and a number K. You have to find the any continue sub-array whose elements sum is K. Please note that, the array may have positive, negative, and zeros as its element.

The desired complexity is O(N).

Example:

Input: [7 0 9 -10 0 789], K = 0

Output: Array from index 1 to Index 1.

Input: [1 2 3 5 -10] K = 0

Output: Array from Index 1 to Index 4.

If K = -2, Output would have been SubArray from Index 2 to Index 4.

- 0of 0 votes
You are given an integer array. You have to return/print an array where kth element of this array is the multiplications of all the elements from 0 to k-1 and from k+1 to n-1.

Example

input: [1 2 5 6]

output: [60 30 12 10]

- 0of 0 votes
You are given a BST of integers and an integer K. You have to find the smallest greater integer then K in the BST.

Ex`40 --- 50 --- 80 | | | 45 20 --- 30 | | 10 K = 35 Output: 40`

- 0of 0 votes
We define a k-subsequence of an array as follows

1) it is a subsequence of consecutive elements in the array

2) the sum of the subsequence's elements s, is evenly devisible by k(i.e. s % k == 0)

Given an integer and input array, find out the number of k-subsequences.

Example: k=3 and array be [1 2 3 4 1]

Output: 4 ({1 2},{1,2,3},{2,3,4},{3})

- 0of 0 votes
You are given an array with duplicates. You have to sort the array with decreasing frequency of elements. If two elements have the same frequency, sort them by their actual value in increasing order.

Ex: [2 3 5 3 7 9 5 3 7]

Output: [3 3 3 5 5 7 7 2 9]

- 0of 0 votes
You are given two string (like two statements). You have to remove all the words of second string from first string and print the remaining first string. Please maintain the order of the remaining words from the first string. You will be only removing the first word, not all occurrence of a word.

Example: Str1 = "A Statement is a Statement", Str2 = "Statement a"

Output: "A is Statement"

- 0of 0 votes
You are given an integer, print its 4th least significant bit

- 0of 0 votes
You are given a rotated sorted array of size N. You have to search a given number into it.

Example: [4,6,8,14,90,-9,-2,0,3], Search -2.

- 0of 0 votes
You are given an array of words. from each word, you make a chain, in that, you remove one char at a time and you remove that char only when the remaining word is present in the input array.

For Example, if the input is {a, b, ab, ac, aba}

then the possible chains are

from 'a', there is no chain, the chain it 'a' itself (of length 1)

similarly, from 'b', the chain length is 1 one (length is defined by the number of words in the chain)

now from 'ab', there are two possibilities which are ({ab -> b when you remove a},{ab -> a when you remove b}). So the max length is 2 here

now from 'ac', we only have one possibility which is ({ac -> a when we remove c}), because, when we remove 'a', we left with 'c' which is not present in the input.

Now, you have to find the length of the biggest such chain.

Input: array of words

Output: length of the biggest such chain.

- 0of 0 votes
Friends have transitive property where if A is the friend of B, and B is the friend of C then A is also the friend to C. Like that we make friend circle.

You have to find the number of such circles in a given list of friends

You are given a NxN matrix, where columns of each row will have either 'N' or 'Y', where 'N' represents not a friend and 'Y' represents Yes, they are friends.

Example :

YNY

NYN

YNY

The output is 2({0,2},{1}), as the 0 and 2 are friends of each other and 1 is another friend who is neither friend with 0 nor with 2.

- 0of 0 votes
Q1. You are given a binary search tree (with unique values) and two values. You need to find their lowest common ancestor. (Expected Complexity O(log(n)) + O(1))

Q2. Now let's assume the tree has duplicates, and when a duplicate number come, the insertion logic chooses left node. (Expected Complexity O(log(n)) + O(1))

Q3.Now let's assume the input tree is a binary tree instead of the binary search tree.(Expected Complexity O(n) + O(1))

- 0of 0 votes
You are given a vector of integers. You have to delete the odd numbers from it.

Expected complexity is O(N) Time and O(1) space

- 0of 0 votes
You are given an unsorted binary array.

Ex [0 1 1 0 0 1 0 1 1 1 1 0 0 1 0 0 1]

and a number K, which represents the number of swap operations allowed on this binary array.

you need to find out the maximum length continuous subarray that can be generated using K many swaps.

Ex if K = 3 in above case

[0 1 1 0 0 1 0 1 1 1 1 0 0 1 0 0 1] => [0 1 1 0 0 1 1 1 1 1 1 0 0 0 0 0 1] => [0 1 1 0 1 1 1 1 1 1 1 0 0 0 0 0 0] => [0 0 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0]

so the answer is 9.

- 0of 0 votes
You are given a binary matrix whose each row is sorted. that means each row will have zeros at front and ones at the back. You need to find out the row which contains a maximum number of ones.

Ex :`[0 0 0 0 0 0 0 1 1 1 1 1] [0 0 0 0 1 1 1 1 1 1 1 1] [0 0 0 0 0 0 1 1 1 1 1 1] [0 0 0 0 0 0 0 0 0 1 1 1] [0 0 0 0 0 0 0 1 1 1 1 1] [0 0 0 0 1 1 1 1 1 1 1 1]`

Ans : second row and sixth with 8 ones. you will print [2,8] and [6,8];

Update : Required complexity O(M+N) + O(1) only.

- 0of 0 votes
Implement a stack that in addition to push and pop has a function that returns the min value of the stack.

I came up with a O(logn) solution, but he wanted a O(1) for the whole algorithm.

- 0of 0 votes
Problem statement

Given a set of hotels and its guests reviews, sort the hotels based on a list of words specified by a user. The criteria to sort the hotels should be how many times the words specified by the user is mentioned in the hotel reviews.

Input

The first line contains a space-separated set of words which we want to find mentions in the hotel reviews.

The second line contains one integer M, which is the number of reviews.

This is followed by M+M lines, which alternates an hotel ID and a review belonging to that hotel.

Output

A list of hotel IDs sorted, in descending order, by how many mentions they have of the words specified in the input. If the count is same, sort according to the hotel IDs.

- 0of 0 votes
Given an array of integers:

1. rearrange the array such that all non-zero members appear on the left of the array (order is not important)

2. return the number of non-zero members

e.g. [1,2,0,5,3,0,4,0] => [1,2,5,3,4,0,0,0] and return 5. The non-zero array members can be in any order.

- 0of 0 votes
One question containing multiple questions

1) Define the structure of a function which takes an array of size n as input and returns True or False.

2) Write a function which takes an array as input and returns a string containing all the elements separated by a comma.

Ex : [0, -45, 9, 10] => "0,-45,9,10";

3) Write a function which takes two arrays ass input, and returns minimum common element in them.

Ex : [0, -90, 45, 10, 4], [4, 8, 90, 45] => 4

4) Now let's say, the function takes an array of arrays, and each array is sorted. now, returns their first common element.

Ex : [0, -90, 45, 10, 4], [4, 8, 90, 45], [-1, -3, -5, -7, 10, 4], [24, 35, 78, -90, 56, 4] => 4

- 1of 1 vote
You are given an array of integers both negative and positive.

Print the maximum continuous sum of the array and if all the elements are negative, print the smallest of them.

Ex : [-20, -5, -2, -9] :> -2(-2)

Ex : [20, -19, 6, 9, 4] :-> 20(20)

Ex : [10, -3, 4, -2, -1, 10] -> 18 (10, -3, 4, -2, -1, 10)

Thanks velu007 for pointing out the mistake

- 1of 1 vote
Define a graph using Adjacency list where node and graphs are different entities, for example, Node is a struct/class and graph is set of nodes.

The graph is an acyclic directed graph(may be a forest not necessarily connected).

Write an assignment copy constructor for this graph.

Please note that the copy constructor should create a new copy of the graph, including all its edges and vertices. Interviewer called this deep copy.

- 0of 0 votes
* Definition for a binary tree node.

* public class TreeNode {

* int val;

* TreeNode left;

* TreeNode right;

* TreeNode(int x) { val = x; }

* }

Given an array of Binary Tree Node, check if all of these nodes can form a binary tree?

Public boolean canForm(TreeNode[] nodes){

}

- 0of 0 votes
Check if two given binary trees(expression trees with two characters 'a' and 'b' and obviously operators like +,-,*) are mathematically equivalent?

- -1of 1 vote
Given two strings representing very large integer numbers, find the Product. Do not use BigInt.

`using System; public class Program { public static void Main() { Console.WriteLine( GetProduct("18888888888888888888888888","19999999999999999999999999999999999999999999999999999999999")); } public static string GetProduct(string s1,string s2) { int digit1=0; int digit2=0; char[] str1=s1.ToCharArray(); char[] str2=s2.ToCharArray(); int carry; string[] result=new string[str1.Length]; string finalproduct=string.Empty; int padding=0; for(int i=str1.Length-1;i>=0;i--) { digit1=str1[i]-'0'; string resval=string.Empty; carry=0; int j; for(j=str2.Length-1;j>=0;j--) { digit2=str2[j]-'0'; int product=digit1*digit2+carry; carry=product/10; resval=resval+(product%10); } if(carry>0) { resval=resval+carry; } for(int k=0;k<padding;k++) { resval="0"+resval; } result[i]=resval; padding++; } int max=findMax(result); int count=0; int car=0; while(count<max) { int sum=0; for(int x=0;x<result.Length;x++) { if(count<result[x].Length) { sum+=result[x][count]-'0'; } } sum+=car; car=sum/10; int p=sum%10; finalproduct=p+finalproduct; count++; } finalproduct=car+finalproduct; return finalproduct.TrimStart('0'); } public static int findMax(string[] s) { int max=0; for(int i=0;i<s.Length;i++) { int len=s[i].Length; max=Math.Max(max,len); } return max; }`

}

- 0of 0 votes
Turtle is on a N * N grid, with N obstacles. The turtle can only move F orward one position

and can turn L eft or R ight. The grid has 4 directions N, E, W, S

Assuming that the initial position of turtle is 1, 1 (bottom left corner of the grid facing North) and

the grid has random obstacles in a few of its cells, given the movement instructions, find the

final position of turtle and printing the grid state will be an added plus. When there is an

obstacle, movement is not possible.

input :

FFFRRFLF

output:

2,3 E

- 3of 3 votes
`/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */`

Find if a given binary tree has duplicate sub trees.

followup:

Find all duplicate subtrees in a binary tree`For example, 1 / \ 2 3 / / \ 4 2 4 / 4 The following are two duplicate subtrees: 2 / 4 and 4 Therefore, return [ [2,4], [4] ].`

- 0of 0 votes
Given a diamond shape matrix, find the minimum path sum from top to bottom.

Each step you may move to adjacent numbers on the row below.`[ [2], [3,4], [6,5,7], [4,1,8,3], [2,5,4], [6,4], [1] ]`

- 0of 0 votes
Design a algorithm to initialize the board of Candy Crush Saga. With M x N board, Q types of candies. (Rules: no 3 for run after initialization, must contain at least one valid move at the beginning)

- 0of 0 votes
Given the weekly vacation numbers for various cities for an year (ie 12 * 4 = 48 weeks ) , design a tour which will maximize the number of vacations for a salesman. The salesman can choose to work in any city for the week , and can weekly change the city unlimited number of times , but has to remain in the city for the week . It's not necessary for the salesman to go to all cities , goal is to find the schedule which maximize the vacation for whole year. Input will be HashMap<string , int[48] vacation> where string is the city name and int[48] is city's vacation numbers for an year.

- -2of 2 votes
Consider a hotel where the guest is checked in and check out. Find a day when the maximum number of guests stay in a hotel.

example:

Input :

[

{check-in : 1, check-out 4},

{check-in : 2, check-out 5},

{check-in : 10, check-out 12},

{check-in : 5, check-out 9},

{check-in : 5, check-out 12}

]

Output : 5

- 0of 0 votes
Given number N, Find the least number of perfect square number sum needed to get N.

Example :

n=5 (4+1) i.e. 2

n=7 (4+1+1+1) i.e. 4

n=12 (4+4+4) i.e 3

n=20 (16+4) i.e. 2