## Problem Solving Interview Questions

- 4of 4 votes
Given an integer array which represents the heights of adjacent vertical bars standing on the ground.

The width of each bar is 1. Now you have to pick two bars and remove all the remaining such that when

rain falls the water collected between two bars is maximum. Note that the distance between bars

remains the same after removing the remaining bars.

eg:

1. [10,5,6,12,14] ans: 30 (10*3)

2. [3 16 10 5 6 12 20 18] ans: 80 (16*(number of integers between 16 and 18)).

- 0of 0 votes
`import java.time.Duration; import java.time.LocalTime; import java.util.List; import java.util.Map; // Your goal is to write business logic for a very simple Restaurant booking system // You are encouraged to refactor exisiting code, create other classes, write helper methods etc // You also need to make sure that the implementation works correctly class Reservation { public String name; public int partySize; public LocalTime startTime; } class Table { public int tableNumber; public int maxPartySize; } class Restaurant { public List<Table> tables; public LocalTime openTime; public LocalTime closeTime; public Map<Integer, Duration> reservationDurationsPerPartySize; // Returns a Table if Reservation could be booked, null otherwise // Booking rules: // 1) Reservation could be made only when the Restaurant is open. // 2) Only one Reservation can be seatted a Table at any time. // 3) Reservation can be seatted only at a Table of the same or a bigger size. // 4) Reservation should stay on the same Table for the whole Duration. // 5) Reservation Duration is determined by PartySize. public Table bookReservation(Reservation reservation) { //TODO: } }`

- -1of 3 votes
You have L, a list containing some digits (0 to 9). Write a function answer(L) which finds the largest number that can be made from some or all of these digits and is divisible by 3. If it is not possible to make such a number, return 0 as the answer. L will contain anywhere from 1 to 9 digits. The same digit may appear multiple times in the list, but each element in the list may only be used once.

{{

Test cases

==========

Inputs:

(int list) l = [3, 1, 4, 1]

Output:

(int) 4311

Inputs:

(int list) l = [3, 1, 4, 1, 5, 9]

Output:

(int) 94311

}}

My Solution:

{{

package com.google.challenges;

import java.util.ArrayList;

import java.util.Arrays;

import java.util.Collections;

public class Answer {

public static int answer(int[] l) {

// Your code goes here.

ArrayList<Integer> list0 = new ArrayList<>();

ArrayList<Integer> list1 = new ArrayList<>();

ArrayList<Integer> list2 = new ArrayList<>();

int sum =0;

Arrays.sort(l);

for(int i = 0; i<l.length; i++){

if(l[i] % 3 == 0){

list0.add(l[i]);

}else if(l[i] % 3 == 1){

list1.add(l[i]);

}else{

list2.add(l[i]);

}

sum += l[i];

}

if(sum%3==0){

StringBuilder strNum = new StringBuilder();

for(int i = l.length-1; i >= 0; i--)

{

strNum.append(l[i]);

}

return Integer.parseInt(strNum.toString());

}else if(sum%3 == 1){

if(list1.size()>0){

Collections.sort(list1);

list1.remove(0);

}else if(list2.size() >= 2){

Collections.sort(list2);

list2.remove(1);

list2.remove(0);

}else{

return -1;

}

}else if(sum%3 == 2){

if(list2.size()>0){

Collections.sort(list2);

list2.remove(0);

}else if(list1.size() >= 2){

Collections.sort(list1);

list1.remove(1);

list1.remove(0);

}else{

return -1;

}

}

list0.addAll(list1);

list0.addAll(list2);

StringBuilder strNum = new StringBuilder();

Collections.sort(list0);

for(int i = list0.size()-1; i >= 0; i--)

{

strNum.append(list0.get(i));

}

return strNum.length() > 0 ? Integer.parseInt(strNum.toString()) : -1;

}

}

}}

But here I am able to pass 4 test cases out of 5. Therefore I am looking for scenario which is left to check.

Can someone help me?

- 0of 0 votes
Given a random function with equal probability of getting 1 or 0 ie 50% each. write a custom function which uses the above random function such that your function should return 1 with 75% probability and 0 with 25% probability

- 0of 0 votes
A planner wants to deign a city. A city having n points of interest and marked them from 0 - (n-1). Need to write two API:

public void buildRoad(int a, int b); // build road directly between a and b.

public boolean isRoadExist(int a, int b); // Check if there is any road connectivity exist between a & b (either directly or indirectly) then return TRUE else FALSE.

The solution should be in O(log n). You can first try in O(n).

- 0of 2 votes
Write all jumbled number which is >0 && <N, where N is provided by the user.

A jumbled number is a number whose neighbour digit (either left or right) max differ by 1 value.

e.g.:

8987 is a jumbled number.

13 is not a jumbled number.

123456 is a jumbled number.

287 is not jumbled number.

- 0of 0 votes
You have a guy who is walking on a street with "X" doors on one side

(say left side).From the third round, He has to walk "X" rounds to and

fro( from point A, starting point to B, ending point).

So he walks "X" times from A to B, and back "X" times.

First two rounds he just walks to and fro.

Every time he walks he closes the particular doors corresponding to

the number of the round of his walk, starting from the third round. So

at the third round, he closes the third door, sixth door, ninth door,

.... upto

"X", if "X" is a multiple of 3,

"X-1", if "X-1" is a multiple of 3

AND

"X-2", if "X-2" is a multiple of 3

Then he walks till the "X" door. This he does for every round, till

the "Xth" round.

So, if X is 300, he walks upto the 300th door, closes the 300th door

and returns.

If X is 400, he closes upto 399th door, goes till the 400th door and returns.

If X is 500, he closes upto 498th door, goes till the 500th door and returns.

While returning, he just does nothing. He just returns to where he

started i.e. POINT A.

Likewise for the fourth round, where he close doors that are multiples

of 4 i.e. 4, 8, 12, 16, etc till X (Similar calc as in the 3rd round,

except that we consider multiples of 4 here).

And so on till the "Xth" round.

I.E.

This continiues till "X" rounds. So, from 3 to X rounds. Note that we

have not included 1st and 2nd rounds.

Problem here is:

Write the code in any language of your choice to find:

What is the minimum number of the round where he would not have to close any door?

- 0of 0 votes
System design of high traffic eCommerce website including inventory

- 0of 0 votes
Implement a solution nth_largest( array, n ) that takes in an array of arbitrary size and returns the nth largest element.

`Eg. array = [1, 8, 4, 5, 9, 7, 2, 10, 44, 55, 67] nth_largest( array, 2) = 55 nth_largest( array, 5) = 9`

- 0of 0 votes
Write a program to print all permutations of a given string.

- 0of 0 votes
Given the X Y coordinates, width and length of 2 rectangles. Implement a function which returns "True" if the 2 rectangles intersect otherwise returns "False". The first 2 values represent the X Y coordinates, the following 2 represent the width and length.The last 4 values represent the second rectangle. The "8" values should be read from console and the result should be printed to console. Test input "1 1 1 1 -1 -1 3 3"

- 0of 0 votes
A delivery boy wants to deliver some items on his way from office to home. You need to find the optimized path he should take from office to home and deliver all his deliveries on his way.

It is 101 X 101 grid. Office, home , delivery points are represented via coordinated (x,y) where 0 <= x <= 100, 0 <= y <= 100.

distance between two points (x1, y1) and (x2,y2) is computed as |x1 - x2| + |y1 - y2|

You need to find the optimized path from office to home covering all delivery locations and return the optimized path length as output.

You will be given the input in the 2 lines

first line - N (no. of delivery locations)

second line - (x,y) coordinates of office, followed by home, followed by all N delivery locations.

3

0 0 100 100 20 30 50 50 70 70

output: The length of the optimized path taken.

For above input, the output is 200

- 3of 3 votes
Given 4 teams and 3 gamedays, create an algorithm such that each team plays another team every gameday and by the end of the 3 game days each team should have played one game with every other team.

- 0of 0 votes
How would you convert a row number on Excel to a label? Rows are labeled alphabetically with letters added on once the alphabet has been fully used. (Ex. row # 5 is labeled E, row # 27 is labeled AA, row # 28 is AB, row # 53 is BA and so forth) What would the row label be for a large number, such as 1500?

- 0of 0 votes
Design a train system which suggests shortest path and transfer needed to reach from source to destination. What can be the optimization.

For example:

A system may have 10 trains from t1 to t10.

There are total 100 stops in the system s1 to s100.

Each train has fixed set of stops. You could allow to change and transfer train of source and destination does not cover using just 1 train.

What all can be APIs, data structure, optimizations scalable option.

- 0of 0 votes
You are planning a big programming conference and have received many proposals which have passed the initial screen process but you're having trouble fitting them into the time constraints of the day -- there are so many possibilities! So you write a program to do it for you.

The conference has multiple tracks each of which has a morning and afternoon session.

Each session contains multiple talks.

Morning sessions begin at 9am and must finish by 12 noon, for lunch.

Afternoon sessions begin at 1pm and must finish in time for the networking event.

The networking event can start no earlier than 4:00 and no later than 5:00.

No talk title has numbers in it.

All talk lengths are either in minutes (not hours) or lightning (5 minutes).

Presenters will be very punctual; there needs to be no gap between sessions.

Note that depending on how you choose to complete this problem, your solution may give a different ordering or combination of talks into tracks. This is acceptable; you donâ€™t need to exactly duplicate the sample output given here.

Test input:

Writing Fast Tests Against Enterprise Rails 60min

Overdoing it in Python 45min

Lua for the Masses 30min

Ruby Errors from Mismatched Gem Versions 45min

Common Ruby Errors 45min

Rails for Python Developers lightning

Communicating Over Distance 60min

Accounting-Driven Development 45min

Woah 30min

Sit Down and Write 30min

Pair Programming vs Noise 45min

Rails Magic 60min

Ruby on Rails: Why We Should Move On 60min

Clojure Ate Scala (on my project) 45min

Programming in the Boondocks of Seattle 30min

Ruby vs. Clojure for Back-End Development 30min

Ruby on Rails Legacy App Maintenance 60min

A World Without HackerNews 30min

User Interface CSS in Rails Apps 30min

Test output:

Track 1:

09:00AM Writing Fast Tests Against Enterprise Rails 60min

10:00AM Overdoing it in Python 45min

10:45AM Lua for the Masses 30min

11:15AM Ruby Errors from Mismatched Gem Versions 45min

12:00PM Lunch

01:00PM Ruby on Rails: Why We Should Move On 60min

02:00PM Common Ruby Errors 45min

02:45PM Pair Programming vs Noise 45min

03:30PM Programming in the Boondocks of Seattle 30min

04:00PM Ruby vs. Clojure for Back-End Development 30min

04:30PM User Interface CSS in Rails Apps 30min

05:00PM Networking Event

Track 2:

09:00AM Communicating Over Distance 60min

10:00AM Rails Magic 60min

11:00AM Woah 30min

11:30AM Sit Down and Write 30min

12:00PM Lunch

01:00PM Accounting-Driven Development 45min

01:45PM Clojure Ate Scala (on my project) 45min

02:30PM A World Without HackerNews 30min

03:00PM Ruby on Rails Legacy App Maintenance 60min

04:00PM Rails for Python Developers lightning

05:00PM Networking Event

- 0of 0 votes
Not sure what topic this falls under.

"Improve metrics on the system."

Intentionally vague requirement to see how I ask questions. In my case, it ended up being a discussion about making database queries faster.

- -1of 1 vote
You are a prince of the kingdom of Kireet.

You are handsome and brave.

While you are studying in London, you fall in love with a girl who turns out to be a princess of Tikrit.

The term ends and you return home.

Somehow it becomes public that you the prince of Kireet is in love with the princess of Tikrit.

The kingdoms of Kireet and Tikrit are enemies since time immemorial.

A prince of Kireet taking a Tikrit princess as bride is something unheard of.

The princess is forced not to leave Tikrit.

Your job is to rescue the princess.

However, there are certain conditions that you should be aware of before you embark upon this journey.

You know that the princess is somewhere in the city of Bagore, the capital of Tikrit.

You know that she uses a smartphone.

But, her phone number is changed and you don't know the new number.

You have been removed from her contact list in facebook and your account blocked.

However, she is able to receive and read all your mails on gmail and your messages on facebook through your other facebook account.

But her firewall blocks her every attempt to reply to your mail/message.

Only her closest friends know of her where-abouts and they are asked not to divulge this information to anyone who asks for it.

However, you were able to hack into her school website and get the emails and phone numbers of some of her friends.

You even know the phone number of her father and the location of palace is known to all.

But you know that she may not be in the palace.

You somehow manage to sneak into Bagore.

Once there, you are totally anonymous. Nobody knows who you really are.

Your job is to find out the where the princess is.

Use any technology you want. Use any other resources at your hand.

Use all your spying skills and intellect.

You need to find out where the princess is.

- 1of 1 vote
Given a sorted array of integers, using the same array, shuffle the integers to have unique elements and return the index.

Sample input : [3, 3, 4, 5, 5, 6, 7, 7, 7]

Sample output : [3, 4, 5, 6, 7, X, X, X, X]

In this case, it returns an index of 4.

The elements in the array after that index is negligible (don't care what value it is).

- 0of 0 votes
Design the backend system for a website like HackerRank

- 0of 0 votes
Implement a MessageBroker which accept messages from Publisher and deliver to Subscriber.

To begin with start with single Publisher and Subscriber. But design it in such a way to scale up to many publisher and subscriber associated with a Single Broker.

Take Performance and parallel processing into consideration.

- 3of 3 votes
Find longest substring with "m" unique characters in a given string.

input: aabacbeabbed

output:

4 (aaba) for 2 unique characters

6 (aabacb) for 3 unique characters

- 1of 1 vote
Create a maze.

- -1of 1 vote
You're the guard of a prison, you want to keep an eye on the most dangerous prisoner. Each prisoner has a danger rank of his own and a group of friends (who also have danger ranks). You'll need to go through the prison and find out the prisoner who has the highest danger rank (his own + all his friends)

- -1of 1 vote
You're the guard of a prison, you want to keep an eye on the most dangerous prisoner. Each prisoner has a danger rank of his own and a group of friends (who also have danger ranks). You'll need to go through the prison and find out the prisoner who has the highest danger rank (his own + all his friends)

- 0of 0 votes
You're the guard of a prison, you want to keep an eye on the most dangerous prisoner. Each prisoner has a danger rank of his own and a group of friends (prisoners, who also have danger ranks). The guard has a list of prisoners with their corresponding danger ranks and he also has a list of the friends of each of the prisoners in the prison.

The danger rank is computed as follows: Prisoner 1 has a danger value of 5, his friends are Prisoner 2 and Prisoner 5, who have danger values of 3 and 4 respectively. So the danger value of Prisoner 1 is 5+3+4 = 12.

There could be any number of prisoners. Whichever prisoner has the highest value is the most dangerous(computed using the above method).

Friendship can be assumed to be symmetric.

Come up with an efficient algorithm to find the most dangerous prisoner?

The solution I came up with runs in quadratic time.

A hash table which has the Prisoner as Key and list of his friends as value

Compute the sum of danger rank of all friends one key at a Time. (n * N)

Maintain a max count and update it as necessary.

I believe there is a solution for this problem having better time complexity than O(N^2).

- 1of 3 votes
design and implement a calculater that can calculate expressions like:

+ 2 4

* 8 ( + 7 12)

( + 7 ( * 8 12 ) ( * 2 (+ 9 4) 7 ) 3 )

(PS:all items are space delimetered.)

Example answers

+ 2 4 => 2 + 4 = 6

* 8 ( + 7 12) => 8 * ( 7 + 12 ) = 152

( + 7 ( * 8 12 ) ( * 2 (+ 9 4) 7 ) 3 ) => 7+8*12+2*(9+4)*7+3 = 148

- 1of 1 vote
Design a TinyURL like Service.

- 1of 1 vote
Take a list of integers (left to right order) and return an integer of the number of identical binary trees that can be created from the same list.

Input: [10, 8, 15, 6, 9, 4, 5]

Output: 24

Input: [12, 6, 19, 15, 5]

Output: 6

Input: [44, 46, 48, 50, 52, 54, 56, 58, 60, 62, 64]

Output: 1

I wrote a brute-force 'solution', creating a binary tree for each permutation of the list (with the same root as Input list) and compared each to the binary tree from the Input list. For large input lists (length > 10), my 'solution' is useless.

- 1of 1 vote
Colorful Number:

A number can be broken into different sub-sequence parts. Suppose, a number 3245 can be broken into parts like 3 2 4 5 32 24 45 324 245. And this number is a colorful number, since product of every digit of a sub-sequence are different. That is, 3 2 4 5 (3*2)=6 (2*4)=8 (4*5)=20 (3*2*4)= 24 (2*4*5)= 40

But 326 is not a colorful number as it generates 3 2 6 (3*2)=6 (2*6)=12.

You have to write a function that tells if the given number is a colorful number or not.