## Recent Interview Questions

- 0of 0 votes
Objective: Write a function to find all the combinations of three numbers that sum to zero

Sample input:

[2, 3, 1, -2, -1, 0, 2, -3, 0]

Sample output:

2, -2, 0

1, -1, 0

3, -2, -1

3, 0, -3

3, 0, -3

- 0of 0 votes
write a function that has an int as input and return the equivalent String as an output

12 -> 'twelve'

4345 -> 'four thousand three hundred and forty-five'

7654567643 -> 'seven billion six hundred and fifty-four million five hundred and sixty-seven thousand six hundred and forty-three'

- -2of 2 votes
3, 5, 7, 9, 11, 13. Which is least like others?

- -3of 3 votes
3, 5, 7, 9, 11, 13. Which is least like others?

- 0of 0 votes
I was asked this during a recent interview.

Lucky number – a number is a lucky number if it comprises of combination of 4′s and 7′s.

For example , if 32 is the input number, the next nearest lucky number would be 44.

Similarly ,

43 -> 44

45 -> 47

1004 -> 4444

Input number can be of any digits.

Design an algorithm that will take any random number and return its next lucky number

- 0of 0 votes
In Byteland they have a very strange monetary system. Each Bytelandian gold coin has an integer number written on it. A coin n can be exchanged in a bank into three coins: n/2, n/3 and n/4. But these numbers are all rounded down (the banks have to make a profit).

You can also sell Bytelandian coins for American dollars. The exchange rate is 1:1. But you can not buy Bytelandian coins. You have one gold coin. What is the maximum amount of American dollars you can get for it?

Input The input will contain several test cases (not more than 10). Each testcase is a single line with a number n, 0 <= n <= 1 000 000 000. It is the number written on your coin.

Output For each test case output a single line, containing the maximum amount of American dollars you can make.

Explanation You can change 12 into 6, 4 and 3, and then change these into $6+$4+$3 = $13. If you try changing the coin 2 into 3 smaller coins, you will get 1, 0 and 0, and later you can get no more than $1 out of them. It is better just to change the 2 coin directly into $2. Pls suggest a better approach.

Here's My code:`import java.util.*; class Bytelandain { Vector v= null; Scanner sc = null; public Bytelandain() { v = new Vector(); sc = new Scanner(System.in); int i=1; String s =null; while (i<=10 ) { s = sc.nextLine(); if( s.equals("") ) break; int temp = Integer.parseInt(s); v.add(temp); i++; } for(i=0;i<v.size();i++) { showProfit((Integer)v.get(i)); } } public static void main(String args[]) { Bytelandain by = new Bytelandain(); } public void showProfit(int num) { System.out.println(computeValue(num)); } public int computeValue(int num) { int value = 0; if(num<=2) { return num; } value = getProfit(num,value); if(num >= value) { return num; } return value; } public int getProfit(int num,int value) { int sum; sum = value; sum = sum+ computeValue(num/2)+computeValue(num/3)+computeValue(num/4); return sum; } }`

- 1of 1 vote
Given a sequence of n random numbers: suppose: 1,5,7,3,...

and n-1 symbols of <,> in the given fashion:

_<_>_>_>.....

the task is to fill the blank best possible time complexity. (I solved upto O(nlogn))

- 0of 0 votes
Q1. Given array a[]={'a','n','u','b','h','a','v'}

You have to generate a[]={'v','a','h','b','u','n','a'} in the same array with space complexity O(1). You may use just one bit extra.

Q2. perform the same operation with the same constraints for

array a[]={'m','y',' ','n','a','m','e',' ','i','s',' ','a','n','u','b','h','a','v'}

Q3 Perform the same operation with same contraints to arrange the words in alphabetic order, ie the output array should be:

a[]={'a','n','u','b','h','a','v',' ','i','s',' ','m','y',' ','n','a','m','e'}

- 0of 0 votes
The input is a sequence x1,x2,...,xn of integers in an arbitrary order, and another sequence

a1,a2,..,an of distinct integers from 1 to n (namely a1,a2,...,an is a permutation of

1, 2,..., n). Both sequences are given as arrays. Design an 0(n logn) algorithm to order

the first sequence according to the order imposed by the permutation. In other words, for

each i, Xi should appear in the position given in ai. For example, if x = 17, 5, 1,9, and a =

3, 2, 4, 1, then the outcome should be x = 9, 5, 17, 1. The algorithm should be in-place, so

you cannot use an additional array.

- 2of 2 votes
Given a random generator rand(5) which generates numbers between 0 to 4. How do u generate numbers between 0 to 6, I.e. Implement rand(7).

- 2of 2 votes
Car parking problem. An array given represents actual order of cars need to be parked. Like for example order is 4,6,5,1,7,3,2,empty. If cars are parked in some order like empty,1,2,3,7,6,4,2. Some person needs to get them into correct order, list out all instructions to the person to get in correct order with least number of swaps.

- 0of 0 votes
Given a list of tuples representing intervals, return the range these intervals

covered.

e.g:

[(1,3), (2,5),(8,9)] should return 5

- 0of 0 votes
Consider a game of chess where there is a special queen which has the powers of a Queen as well as a Knight. For eg. in the following arrangement, squares marked with 'x' are in the attackzone of the special queen and the ones marked '0' are in the safe zone:

x O O x O O x

O x x x x x O

O x x x x x O

x x x Q x x x

O x x x x x O

O x x x x x O

x O O x O O x

Your task is to determine the number of ways in which you can place M such queens on a MxM chess board so that they are in equilibrium i.e. they are placed such that no queen is in the attack zone of the other.

Assume M<15. If you need coordinates to identify each square, you can assume that the top-left square is marked (1,1) and the bottom right square is marked (M,M).

- 0of 0 votes
Find x^y where y can be float. Any good algorithm for that?

- 0of 0 votes
You type www.yahoo.com on the browser . But it will display

nothing or blank page.what is the problem?How will you resolve/

- 1of 1 vote
given a N x N matrix find the no. of times a word is present in that matrix. constraints you can move in 3 directions from one cell 1. forward , 2. down 3. diagonal . Find all teh occurance of all the word

forward means right (x+1,y)

down mean (x,y+1)

diagonal means (x+1,y+1)

it can be done with BFS. {search the no. of occurance of a given word example "sachin" in the whole NxN matrix}

w | s | r | t | g | g|

a | a | c | h | i | n |

k | c | h | u | j | j |

o | h | i | n | y | q |

in this sachin can be found out 3 times.

- 0of 0 votes
I was asked this an interview at amazon and could not complete this. can I get some help?

am just totally blocked on this. I know what to do but I am having difficulty manipulating the tree. please help.

I am trying to delete and node from an BST. I am able to lookup and find the parent and store it an tree.

package com.test.binarytree;

public class BinaryTreeDelete {

private Node root;

//create null binary tree

public BinaryTreeDelete(){

root = null;

}

//delete

public void delete(int target){

root = delete(root, target);

}

public Node delete(Node node, int target){

NodeWithParent temp = lookupFindParent(root, null, target);

if( node == null){

return null;

}

else{

if( node.left == null || node.right == null) //leaf node

{

//WHAT DO I DO HERE

//temp.parent.left = null;

//temp.parent.right = null;

//return null;

}

if( node.left != null && node.right == null ) //one child only on left

{

//WHAT DO I DO HERE

}

if( node.right != null && node.left == null ) //one child only on right

{

//WHAT DO I DO HERE

}

if( node.left != null && node.right != null ) //two children

{

//WHAT DO I DO HERE

}

}

return null;

}

private NodeWithParent lookupFindParent(Node node, Node parentNode, int target){

if( node == null ){

return null;

}

if( node.data == target){

return new NodeWithParent(node, parentNode);

}

else if( node.data > target ){

parentNode = node;

return lookupFindParent(node.left, parentNode, target);

}

else{

parentNode = node;

return lookupFindParent(node.right, parentNode, target);

}

}

//insert

public void insert(int data){

root = insert(root, data);

}

public Node insert (Node node, int data){

if(node == null){

node = new Node(data);

}

else{

if( data <= node.data ){

node.left = insert(node.left, data);

}

else{

node.right = insert(node.right, data);

}

}

return node;

}

//print tree

public void printTree(){

printTree(root);

System.out.println();

}

//print tree

private void printTree(Node node) {

if (node == null) return;

// left, node itself, right

printTree(node.left);

System.out.print(node.data + " ");

printTree(node.right);

}

//node class

public static class Node{

Node left;

Node right;

int data;

Node(int newNode){

data = newNode;

left = null;

right = null;

}

}

//node class

public static class NodeWithParent{

Node current;

Node parent;

NodeWithParent(Node current, Node parent){

this.current = current;

this.parent = parent;

}

}

public static void main(String[] args) {

BinaryTreeDelete bt = new BinaryTreeDelete();

//insert with inserts - tree increases on right if inserted in order

bt = new BinaryTreeDelete();

bt.insert(5);

bt.insert(3);

bt.insert(7);

bt.insert(1);

bt.insert(4);

bt.insert(6);

bt.insert(9);

bt.printTree();

//bt.delete(3);

//bt.delete(4);

//bt.delete(6);

bt.delete(9);

//bt.delete(5);

bt.printTree();

}

}

- -1of 1 vote
C++ Program that uses Linked List to display an Address Book (Name, Address, and Phone number)

Note:phone numbers format: (xxx)-xxx-xxxx

Address should ..street...City...State...Zip

- 0of 0 votes
Given a list of interval , find the maximum overlapping interval. For ex if input is (0,5) (2,9) (8,10) (6,9) then ans is 8,10.

- 0of 0 votes
Given a tree T of nodes such that each node contains a number. A set of nodes is a Largest independent set of T (i.e. there can be no common edge between the elements). Use dynamic programming to solve this.

No recursion only loops and table must be used, you can recurse through the tree to fill some initial values in the table

- 0of 0 votes
Write an efficient algorithm to the situation.There are 8 cubicles in a room. In each cubicle, there are 8 computers.

There are a total of 60 members.

Constraint#1 - A team can contain a minimum of 2 members and a maximum of 6 members.

Constraint#2 - In every cubicle, not more than 1 computer can be unallocated.

Constraint#3 - All team members of a team must be in the same cubicle.

- 0of 0 votes
Write an algorithm for maintaining the situation.There are 8 cubicles in a room. In each cubicle, there are 8 computers.

There are a total of 60 members.

Constraint#1 - A team can contain a minimum of 2 members and a maximum of 6 members.

Constraint#2 - In every cubicle, not more than 1 computer can be unallocated.

Constraint#3 - All team members of a team must be in the same cubicle.

- 0of 0 votes
You have a complete graph with N vertices. You know that all edges have a cost of A and you are given a set of K edges whose cost is B. Find the shortest (cheapest) path from node 0 to node N - 1.

0 < N, K < 500k

1 < A, B < 500k

- 0of 0 votes
There are at most eight servers in a data center. Each server has got a capacity/memory limit. There can be at most 8 tasks that need to be scheduled on those servers. Each task requires certain capacity/memory to run, and each server can handle multiple tasks as long as the capacity limit is not hit. Write a program to see if all of the given tasks can be scheduled or not on the servers?

Ex:

Servers capacity limits: 8, 16, 8, 32

Tasks capacity needs: 18, 4, 8, 4, 6, 6, 8, 8

For this example, the program should say 'true'.

Ex2:

Server capacity limits: 1, 3

Task capacity needs: 4

For this example, program should return false.

Got some idea that this needs to be solved using dynamic programming concept, but could not figure out exact solution.

- 0of 0 votes
I attended a telephonic round for appstore testing and successfully cleared this round. Following was the 2nd question(apart from tell me abt yourself,etc):

Give all testcases for creating and renaming a folder in a parent directory, say c drive

- 1of 1 vote
I attended a telephonic round for appstore testing and successfully cleared this round. Following was the First question(apart from tell me abt yourself,etc):

Give me all possible test cases for gmail registration page.

- 0of 0 votes
give me the code for :

Given a string say "I am a human being" the output should reverse all letters of each word but not the whole string as such.

Eg: O/p should be "I ma a namuh gnieb"

I somewhat wrote the code, but i was asked what if there are extra spaces etc.

(i am able to write the code sitting at my desktop at one short but there front of interviewer i am struggling. Need to build up my confidence)

let me know the best and optimised way of writing this code.

Also i suggest people to aviod using inbuilt functions as much as possible

My Answer is as below in perl`#i want the reverse of the letters of all words in a string #eg Input is "I am a human being" then o/p shud be "I ma a namuh gnieb" $str="I am a human being"; @arr=split(' ',$str); print @arr; for($i=@arr-1;$i>=0;$i--) { $_=@arr[$i]; ####intead of above for loop if we use foreach(@arr) then it will reverse the whole string @word=split('',$_); { foreach $n (@word) { unshift(@final,$n); } } } print "\n @final \n";`

- 0of 0 votes
give me a code to find all anagrams or combnations of a given work.

Say if the word given was "hello"

then

hel

he

hell

leho

lleho

and so on

- 1of 1 vote
Given an array say [0,1,2,3,5,6,7,11,12,14,20]

given a number say 5.

Now find the sum of elements which sum to 5

eg:2+3=5, 0+5=5 etc.

I guess the interviewer wanted all possible combinations eg 0+2+3=5, etc

- 0of 2 votes
A very interesting Question to be done in C or C++ as platform:

Given two input files.

Input file1.csv

Each line in the file describes a websites.

The first field is unique identifier for the site, the second field is the minimum amount in cents, the third field is a string that is the site’s URL:

2181, 320, abc.com

3288, 450, pqr.com

9662, 567, xyz.com

2675, 721, lmn.com

6434, 500, rst.com

8123, 5000, jjj.com

Input file2.csv

Each line in the file describes an ad. The first field is a 32bit unsigned integer which is the unique identifier for the ad , the second field which is the maximum amount in cents the ad is willing to pay to show on a site, the third field specifies the number of sites the ad wants to display on, followed by the site_ids of the sites.

9822, 450, 3, 2181, 9662, 66434

3421, 897, 3, 2675, 9662, 3288

8961, 342, 1, 9662

7623, 2000, 3, 2181, 2675, 9662

all integr fields are 32bit unsigned integer

In the above example, ad 9822 is willing to play on 3 sites(abc.com, xyz.com and rst.com) and pay a maximum amount of 450 cents. WAP that decides the appropriate ad by applying the following rules

1. An ad can be shown on this site only if the site is in the list of sites that the ad is interested in.

if no ad id found for a ite, then no ad is returned

2. The ad that is returned is chosen an auction thats is called second price auction. For ads to qualify for the second price auction,

auction for a site their bid_price should be greater than or equal to the reserve_price of the

site. The winner of the auction is the ad that has the maximum bid_price among these ads, and this

winning ad pays the second highest ad’s bid_price. For instance, if two ads with bid_price 500

and 600 are competing for a site that has a reserve_price of 400, then the ad that bid 600 wins,

but pays 500 (the second highest ad’s bid price).

3. In case of a tie between two or more ads, the ad with the lower ad_id wins and pays it’s

bid_price. In case, the auction has only one ad that qualifies, then that ad wins and pays

reserve_price of that site.

4. In case there are no ads that qualify for the auction for a site either because no ad expresses interest

in playing on that site or because none of the ads have bid_price greater than or equal to

reserve_price of that site then no ad is returned.

Your server should accept input file path,first.csv and the second.csv as

arguments and wait for input. The input is the site_id and the adserver should return the ad_id of the ad that wins the second price auction and price the ad pays for the display. An input of 1 ends the program. example:

$ ./adserver sites.csv ads.csv

2675

7623 897

3288

3421 450

6434

0 0

9999

0 0

8123

0 0

1

$

DIRECTIONS:

1. The code should compile at least on

http://www.compileonline.com/compile_cpp_online.php

2. Please note that will test your program on larger input files with 20K+ sites and

20K+ ads.

3. You have 1.5 hour to solve the problem, test and submit your solution. Your goal is to provide a working solution at least. You may submit additional code later if you think you can make it work better or faster.

For starters If I were to do this in Java:

Algo:

Step1: I/O

Store both the File Paths from STD IN

Take the SITE_ID as Input Then

Step 2: Pre Processing

Site_Map:

Create a Dictionary/HashMap of All the Site_ID and their Price

Ad_Map:

Create a Dictionary/HashMap of All the Ad_ID and the Ammount they Have

Site_to_Ad Map:

Create a Dictionary/HashMap of All the Site_ID and the Ad_IDs Interested to be on them.

Step 3: Auction Method

Iterate through the Site_to_Ad Map.

Fetch the Amount for Each ad_id from the Ad_Map

Compare it against the min price and if greater store it in a variable along with the ID. Fetch the Next ID and IF it is Higher, Replace and put this value in the variable. If there is a draw, compare the two ap_ids and store the one that has min ad_id value.

If min bid is not reached or if there are no ad_id values for that site, return no ad.

Add Constraints to the Auction block.

I believe in c++ we would use Dictionaries to achive this as we have HashMap in Java, can someone help m with the syntax.