Recent Interview Questions
 0of 0 votes
Given 3 sorted arrays. Find(x,y,z), (where x is from 1st array, y is from 2nd array, and z is from 3rd array), such that x<y<z.
x = element(s) from array 1
y= element(s) from array 2
z = element(s) from array 3
I can have more than 1 elements from each array. But at least 1 from each array is mandatory and elements from .
Need to find the number of such sequences.
 0of 0 votes
You are given a String S of length N. Now, a good subsequence is one that can be represented in the form (a raised to the power i) (b raised to the power j) (c raised to the power k) where i≥1, j≥1 and k≥1. For example ,if i=2, j=1, k=3, it represents the string aabccc. In short, a good subsequence is a subsequence that first consist of
i ′a′ characters, followed by j ′b′ characters, followed by k′c′ characters, where i≥1, j≥1 and k≥1
Now, you need to find the number of good subsequences of String S. As the number of such subsequences could be rather large, print the answer Modulo
(10 raised to the power 9) + 7.
Note: Two subsequences are considered different if the set of array indexes picked for the 2 subsequences are different.
Input : abcabc
Output : 7
Explanation
Valid sub sequences are(1based indexing):
{1,2,3}
{1,2,6}
{1,5,6}
{4,5,6}
{1,2,5,6}
{1,4,5,6}
{1,2,3,6}
 0of 0 votes
scenario: Many Ethernet switches are present, on which we want to run the test on. connection between several links to our traffic generator and various ports of the different switches is established.The physical ports we use may vary between the different switches.
Test: We need an easy way to reference port settings that apply to every switch, irrespective of the physical port to which the traffic generator is connected.
required to code in Java or python or tcl script.
asked in second round of cisco
 0of 0 votes
Harry is trying to climb a pole. He climbs the pole in terms of hops. The height of the pole is k. Harry at a time can make a hop of:
1.) 1 unit
2.) n units
Find the minimum number of hops Harry would need to reach the top of the pole.
No constraints were mentioned by can be done in O(1) without any extra space.
 1of 1 vote
How to solve google technical errors?
 0of 0 votes
If a string is matched to any filter, it is in the black list, otherwise not.
Design a data structure and implement following two functions.
addFilter(filter)
isInBlackList(string)
filters are in the form of
“a*b”
“abc”
“aa*b”
having at most one star, which matches 0 or more chars.
 0of 0 votes
Design a system that will let multiple sellers upload their products to Amazon seller's programs
 0of 0 votes
Tell me about a time you pushed your developer to take a risk
 0of 0 votes
Design the architecture for advertisement platform where N number of advertiser can display their ad on M number of websites.
 0of 0 votes
We have 52 week price list for a stock S. Suppose that during this period, we want to buy 100 stocks of S and sell all of them at a later day (within the 52 week window). We want to know when should we have bought and sold in order to make maximum profit. (If there is no profit making scenario, then it should be reported).
Example, for a small 4 week window: P1 = 14, P2 = 6, P3 = 7, P4 = 11 Then the output should be "Buy on 2 and sell on 4". Short selling is not allowed.
How can you best classify the type of the algorithm? (Greedy or Divide & Conquer or Dynamic Programming, etc..)
 0of 0 votes
Given a list of stocks with their respective market capitalizations. The stock’s market cap are updated every minute based on its trading in the market. I have a strategy that wants a list of top 10 highest capped stocks in the market. This query can happen multiple times during the day.
Question: What would be the most appropriate data structure that can be used to efficiently implement the list of stocks? Discuss pros/cons of various data structures. Please briefly explain your answer.
 1of 1 vote
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.length1; 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
You have a cycled doubly linked list (meaning there is a cycle and each node has prev() and next() method).
You can set/check the value of each node in the list to be 0/1 (method setValue(0/1) getValue())
Find how many elements there are in the list.
You start from the some node and you don’t know the status of the nodes value, could be any combination of 1’s and 0’s)..
 0of 0 votes
Look at the following sequence:
3, 5, 6, 9, 10, 12, 17, 18, 20....
All the numbers in the series has exactly 2 bits set in their binary representation. Your task is simple, you have to find the Nth number of this sequence.
1 <= T <= 10^6
1 <= N <= 10^14
I tried to implement it as follows but it is giving me wrong answer for some hidden cases.#include <cmath> #include <cstdio> #include <vector> #include <iostream> #include <algorithm> using namespace std; #define MAX 10000 #define MOD 1000000007 long long int m[MAX+1]; long long int sum; long long int binary_search(long long int n) { long long int low=0,high=MAX,mid; while(low<high) { mid=low+(highlow+1)/2; if(m[mid]<=n) low=mid; else high=mid1; } return low; } int main() { m[0]=1; for(long long int i=1;i<=MAX;i++) m[i]=m[i1]+i; long long int n,k,l; int t; scanf("%d",&t); for(int test=0;test<t;test++) { scanf("%lld",&n); k=binary_search(n); //cout<<m[k]<<" "; l=nm[k]; cout<<((1<<k+1)%MOD+(1<<l)%MOD)%MOD<<"\n"; } return 0; }
 0of 0 votes
Find the given doubly linked list is palindrome or not.
 0of 0 votes
Optimization Game
Currently, Monk is playing a unique kind of strategy game called optimisation game.
In this game we are provided with an array containing integral numbers.
Now all these numbers represent the count of their respective index power of 2.
The goal of the game is to minimize the total sum of the count of the array by converting lower powers of 2 into their higher powers
i.e. for example (2)*2^1 = (1)*2^2.
Note that we can extend the array beyond the final index i.e. N−1 too in case it optimizes our result.
Please see the below example for more understanding.
Let the number of elements given in the initial array be 3. Consider the array to be [1,2,0].
It means that 2^0 has count = 1, 2^1 has count = 2, 2^2 has count = 0.
Now, we can convert (2)*2^1 into (1)*2^2 as 2^1∗2 = 2^2. We get the new array as [1,0,1].
Now the total sum is 1+0+1=2 which is the required minimum value obtained at the end of the game as we can't reduce it any further.
Input:
First line will contain the number of test cases as T.
For each of the test case, N will be given in the first line and N integers will be given in the second line.
Output:
Output the minimum value obtained after playing the optimization game in a separate line for each test case.
Constraint:
1≤T≤5
1≤N≤10^5
0≤A[i]≤2∗10^9
Sample Input
2
3
1 2 1
2
2 1
Sample Output
2
1
Explanation
In the second case we have A[0]=2, A[1]=1. We can convert A[0] into A[1] and then finally (1+1=2) A[1] into A[2]. Thus, the final array shall be : [0,0,1]. Hence, the answer is 1.
 0of 0 votes
On google search, how to enable key word auto completion after a few letters typed.
Followup: How to rank the words if they are weighted by frequency?
 1of 1 vote
Cross the street
ABC Company is involved in the logistics business.
The company has many outlets and stockyards in a city. The city is like an
N
×
M
N×M grid. We consider a single cell of the given grid to be a single block in the city. The stockyard is at the upperleft corner and the outlet is located in the lower right corner. Everyday, one of the employees has to travel from the upper left to the lower right corner for supplies. Each block in the city has a height, where the height of the block located at position (i,j) in the grid is equal to
A
[
i
]
[
j
]
A[i][j]. The company wants to change the heights of some of the blocks, so that the employee can enjoy a highspeed drive from the stockyard to the outlet. But this change comes at a certain cost.
Specifically, if they change a block height from x to y, then they must pay exactly

x
−
y

x−y dollars. Please help them find the minimum cost, such that by spending that specific amount, they can get a path from stockyard to the outlet with all blocks along the path having the same height.
In a single move, the employee can move from a block to any of its adjacent blocks. Note that during this journey, the employee is allowed to move in all four directions, fulfilling the condition that he never goes out of the grid at any point in time.
Input :
First line contains two positive integers N and M  number of rows and columns in the city. Then, N lines follow, each containing M integers, where the
j
t
h
jth integer on the
i
t
h
ith line denotes
A
[
i
]
[
j
]
A[i][j].
Output :
The first and only line of output should contain minimum cost.
Constraints :
1<= N, M <=100
1<= height of blocks <=100
Sample Input
5 5
1 1 1 1 1
9 9 9 9 1
1 3 3 3 1
1 9 9 9 9
1 1 1 1 1
Sample Output
6
Explanation
Optimal path taken by the employee will be : (1,1) > (1,2) > (1,3) > (1,4) > (1,5) > (2,5) > (3,5) > (3,4) > (3,3) > (3,2) > (3,1) > (4,1) > (5,1) > (5,2) > (5,3) > (5,4) > (5,5) The height of each block along this path can be changed to
1
1, at a total cost of
6
6. There is no way to get a cost less than this.
 0of 0 votes
Alex has recently decided to learn about how to design compilers. As a first step he needs to find the number of different variables that are present in the given code.
So Alex will be provided N statements each of which will be terminated by a semicolon(;). Now Alex needs to find the number of different variable names that are being present in the given statement. Any string which is present before the assignment operator denotes to a variable name.
Input Format: :
The first line contains a single integer N
Each of the next N lines contains a single statement.
It is guaranteed that all the given statements shall be provided in a valid manner according to the format specified.
Output Format: :
Print the number of different variable name that are present in the given statements.
Sample Input
2
foo = 3;
bar = 4;
Sample Output
2
Explanation
Foo and Bar are only two variables used inside the statements so answer is 2.
 0of 0 votes
Design classes to represent the following problem and solve the questions 1,2,3
A user might have some outstanding auto loan amount and you have 3 types of offers: personal loan, credit card and auto loan offers. You need to provide the user
with the following details:
1. Send user all the offers to the user
2. Send user all eligible offers (where minCreditScore < userCreditScore < maxCreditScore)
3. Send user all offers which satisfied 2) and where the (userOutStandingLoanAmount < maxOfferedAutoLoanAmount)
personalloan = [{
"personalloan": {
"id": 1,
"provider": "Avant",
"term": 36,
"minimumCreditScore": 300,
"maximumCreditScore": 700,
"maximumAmount": 10000
}
}, {
"personalloan": {
"id": 2,
"provider": "Prosper",
"term": 24,
"minimumCreditScore": 600,
"maximumCreditScore": 700,
"maximumAmount": 5000
}
}]
creditcard=[{
"creditcard": {
"id": 2,
"provider": "CapitalOne",
"minimumCreditScore": 600,
"maximumCreditScore": 700
}
}, {
"creditcard": {
"id": 3,
"provider": "Chase",
"minimumCreditScore": 300,
"maximumCreditScore": 900
}
}]
autoloan = [{
"autoloan": {
"id": 1,
"provider": "CapitalOne",
"term": 36,
"minimumCreditScore": 300,
"maximumCreditScore": 700,
"maximumAmount": 10000
}
}, {
"autoloan": {
"id": 2,
"provider": "Blue Harbor",
"term": 24,
"minimumCreditScore": 600,
"maximumCreditScore": 700,
"maximumAmount": 5000
}
}]
 0of 0 votes
This is a twopart question.
Part one: Design one or more classes to represent the intersections and streets
in a city. Streets can be either oneway or twoway.
Part two: Using the classes from the previous question, determine whether there is a pair of intersections (A,B) such that there is exactly one route from A to B.
 0of 0 votes
1) Finish writing the below method: bookReservation(Reservation reservation)
2) You are free to add, modify, etc the following classes and methodimport 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) { //fill this method }
 0of 0 votes
I need to create a database that have five columns each entry is such that there can be repeated tuples in each column(No primary key).There will be no two same entries
There are 5 Methods that needs to be implemented
1. Create()  create the database
2. Add(string a,b,c,d,e)  Add single entries with 5 tuples(all strings)
3. Update (culumntype1, columnvalue1,culumntype2, columnvalue2)
 each entry having culumntype1 = columnvalue1 will be updated by columntype2=columnvalue2 and return total such eantries.
4. Delete (culumntype1, columnvalue1)
 each entry having culumntype1 = columnvalue1 will be deleted.and return total such eantries.
5. Search(culumntype1, columnvalue1)
 Search each entry having culumntype1 = columnvalue1 and return total such eantries.
How to implement in best possible way such that there can be 50,000 such entries?
 0of 0 votes
Design a system for implementation of stock market.
Buyer and seller case. stock server will receive buy request and sell request. A sell can be successful when it matches the quantity and price for same stock.
There will be many request for buyer and seller . Need to select the appropriate one.
Which data structure will be used ? how to handle concurrency issue?class diagram?
 0of 0 votes
Given an array arr and a number n, you have to find whether there exist a subset in arr whose sum is n. You have to print length of the subset.
1. There exists only one subset like that
2. All number in arr are positive
 1of 1 vote
Consider that the driver with one trip want to pick up some peoples in different locations like this:
String[] locations ={
"person1, person2, person3, person4, person5",
" person6, person7, person8, person9",
"person10, person11, person12",
"person13, person14, person15",}
in each location there are different choice, so write a code present all possible way to pick up people in the different locations. you can use every data structure needs.
 0of 2 votes
i want code of movie recommendation system using knn in java,python,c
 1of 1 vote
Find largest subarray?
 1of 1 vote
given preorder traversal [5,3,2,4,8,7,9] of a BST, how do we identify the leaf nodes without building the tree ?
@Anonymous Thanks for the reply!
Please try other use cases like, only single leaf node
 1of 1 vote
Java:
GENERAL INSTRUCTIONS: To get the half of the word that was inputted by the user, use division to divide into two and use substring method to specify its beginning and ending index.
OUTPUT FORMAT:
The output will be:
* First half of the entered word
* Last 2 letters (from the end)
* Second half of the entered word