## Recent Interview Questions

- 0of 0 votes
Imagine a room full of people, with only 1 celebrity in the room. Celebrity is defined as a person who does not know anyone, but everyone knows him/her. Write a method who will take array of people and a person as input and return boolean if the person is a celebrity or not.

- 0of 0 votes
A bus has to travel from A to B and the distance is d miles. There are many gas stations between A and B.

The bus has initially g gallon of gas in tank. 1 gallon of gas travels 1 mile.

Gas stations have inforamtion of remaining distance from station to destination b and max gas that can be filled from the station.

Find the minimum number of stops for bus without running out of gas ever.

eg: gas = 10 , distance = 20

gasStation[] = {{16,3}, {10, 7}, {14, 11},{11, 5}, {7, 6}}

o/p = 1

If bus stops at the stop{14,11} that is 14 miles away from destination and fills 11 gallon then it can reach destination with 1 gallon spare.

It can also stop as {16,3} and {10,7} but its 2 stops and at destination it runs out of gas.

Similarly {11, 5}, {7, 6} has 2 stops but has 1 gallon spare at destination.

- 2of 2 votes
Feb On-site Google

DP Problem. Given the length and width of a matrix, get the number of paths from bottom-left to bottom right.

You may only walk into those 3 directions ➡ (right) ↗ (upper-right) ↘ (lower-right) at each point.

Follow-up: optimize 2d DP to 1d DP of linear extra space.

Follow-up: what if some cells are blocked

System Design

Availability test/debug on distributed system. Discussed and drafted about failover, replication, NoSQL etc.

Interviewer seemed to be expecting more but time ran out.

- 2of 2 votes
Feb On-site Google

Print all numbers satisfying the expression 2^i * 5^i (where i, j are integers i >= 0 and j >= 0) in increasing order up to a given bound N.

2^i stands for power(2, i).

- 0of 0 votes
x={a,b,c}, y={p,q}, z={r,s}

Define a

Operation, x * y * z = {{a,p,r},{a,p,s},{a,q,r},{a,q,s}......{c,q s}}

Is to output all the results in the order of each subset, implementing a class iterator that has Next() and hasNext() methods

- 0of 0 votes
Give a tree-like graph that lets you find the maximum length from the leaf node to the leaf node. The input is an array of edges.

- 0of 0 votes
Last Man Standing

A king gathers all the men in the kingdom who are to be put to death for their crimes, but because of his mercy, he will pardon one. He gathers the men into a circle and gives the sword to one man. The man kills the man to his left, and gives the sword to the man to the dead man's left. The last man alive is pardoned.

With 5 men, the 3rd is the last man alive.

Write a program that accepts a single parameter: a number N that represents the number of criminals to start with. The program should output the number of the last two men alive.

Example #1: myProgram 5

would output:

5, 3

Example #2: myProgram 7

would output:

3, 7

- 0of 0 votes
Given the description of the ancient castle that contains years (e.g 910, 1111, 1560, 1809), centuries (X, XII, IX or 11th c, 15th c). The years and centuries might repeat many times.

Assume that the centuries are equals(e.g XI = 1000, XV = 1400, 16th c = 1500)

Find the first historical mention about the castle in the text if you know that the very first mention could not be under 601 year.

- 0of 0 votes
This is a word splitter program, I wanted to know the complexity of this program:

`String s = //"The quick fox jumped over a lazy dog"; "The Java language provides special support for the string " + "concatenation operator ( + ), and for conversion of other " + "objects to strings. String concatenation is implemented " + "through the StringBuilder(or StringBuffer) class and its " + "append method. String conversions are implemented through " + "the method toString, defined by Object and inherited by " + "all classes in Java."; int charLimit = 13; System.out.println("-------------"); char[] chars = s.toCharArray(); boolean endOfString = false; int start = 0; int end = start; while(start < chars.length-1) { int charCount = 0; int lastSpace = 0; while(charCount < charLimit) { if(chars[charCount+start] == ' ') { lastSpace = charCount; } charCount++; if(charCount+start == s.length()) { endOfString = true; break; } } end = endOfString ? s.length() : (lastSpace > 0) ? lastSpace+start : charCount+start; System.out.println(s.substring(start, end)); start = end+1; }`

- 0of 0 votes
Given a biased coin whose probability for Heads is 0.67 and Tails is 0.33, write an algorithm which will print the Heads and Tails with this probability.

- -1of 1 vote
To determine whether two people have kinship, all data structures need their own definition

- 0of 0 votes
Find the missing letters from a string if it doesn't create a pangram.

- 0of 0 votes
https://leetcode.com/problems/word-search/description/

Given a 2D board and a word, find if the word exists in the grid.

The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.

For example,

Given board =

[

['A','B','C','E'],

['S','F','C','S'],

['A','D','E','E']

]

word = "ABCCED", -> returns true,

word = "SEE", -> returns true,

word = "ABCB", -> returns false.

- 0of 0 votes
Write a word processor that can do left and right justification for a sample input of string type.

Here is an example:

This is a sample.This is a sample.This is a sample.

This is a sample.This is a sample.This is a sample.This is a sample.

Additional details:

* The left margin is 5 units.

* The right margin is 75 units.

* The input string is a single-spaced collection of words and punctuation.

* If the length of the word exceeds the right margin, then we must not break the word. Instead, we must print it on the next line and justify the existing line by adding more spaces to the middle of the line.

- 0of 0 votes
Given an integer n (say somewhere between 100 and 1000), you want to generate a random binary tree having exactly n nodes. You are only interested in the structure of the tree. Each structurally unique tree should ideally have the same chance of being generated.

- 1of 1 vote
Given a binary matrix, find if there is a path from the upper left corner to the lower right corner, meet the conditions each time the value of the cell must be different.

Follow up if there is a path with the same number of 0 and 1?

- 0of 0 votes
Given k numbers as strings. The numbers may be very large (may not fit in long long int), the task is to find sum of these k numbers.

Example

S1 = “100”

S2 = “10”

S3 = “1”

Return “111”

public string addNumbers(String[] nums){

}

- 0of 0 votes
A number is special if it is possible to remove some digits from it to get a number having 3, 5 or 6 only.

For example, 38597 is special since it is possible to remove digits 8, 9, 7 to get 35. You cannot remove all the digits.

You can remove digits from left, right or middle.

Write a program in C which given a number N, calculate how many divisors of N are special

- 0of 0 votes
Given the N*N matrix, find the given number in the matrix. All rows are sorted. And each row first element is less than the previous row last index.

input :

[1,3,5,7,9]

[11,13,15,16,20]

[21,22,23,24,25]

[30,32,35,40,45]

Given Num : 23

What is the best Optimal solution ? I have used BST but the interviewer asked to use any other which could do better in the above scenario.

- 0of 0 votes
Given the below input and ouput.

Input :

String[] input = {"hello", "world"};

output: (Higher count should come before and natural order)

hello : l=2, e=1,h=1,o=1

world: d=1,l=1,o=1,r=1,w=1

- 0of 0 votes
given an array of integers suppose 1234, print all groups of integer array possible of length upto n where n can be any number greater than zero

example for n=5

1,11,111,1111,11111,12341,22222,2222,222,22,2 etc

for n=3

1,11,123 etc

- 0of 0 votes
There is a process sequence that contains the start and end of each process. There is a query sequence asking how many processes are running at a certain point in time. Please return the query result of the query sequence.

Example

Given logs = [[1, 1234], [2, 1234]], queries = [2], return [2].

Explanation:

There are 2 processes running at time 2.

Given logs = [[1, 1234], [2, 1234]], queries = [1, 1235], return [1, 0].

Explanation:

There is a process running at time 1, and 0 processes running at time 1235.

- -1of 1 vote
Given:

R number of Red Cards

B number of Black cards

K

Cards needs to be placed in a circle. Start from a position and for

every K moves remove that card And

repeat the process until all the cards are eliminated.

Question: Position the cards such that the red cards are completely

eliminated before the blacks cards are selected for elimination.

- 0of 0 votes
Given a BST convert it into new Data Structure that satisfies following conditions:

1. every leaf node's left ptr point to its parent and right ptr points to the next leaf

2. every non leaf node's left ptr points to its parent and right ptr is NULL

3. return the head and print the new DS`example: 7 / \ 5 9 / \ \ 4 6 10 output: head->4->5->7 | ->6->5->7 | ->10->9-7`

with optimal time and space complexity

- 0of 0 votes
input: "kitten%20pic.jpg"

output: "kitten pic.jpg"

%20 -> ' '

%3A -> '?'

%3D -> ':'

modify your input in place.

no string library functions.

void Decode(char[] str)

- 0of 0 votes
Given a string T of length n, partition it in n' "phrases" (p1, p2, ..., pn'),

such that

pi = pj + c, for some j<i, where + is string concatenation and c is a character

p0 = ''

p1 = pj + c where j < 1

T = p1 + p2 + ... + pn'

For example:

T = aababcabcd = a + ab + abc + abcd

p1 p2 p3 p4

- 0of 0 votes
Print a binary tree in vertical order using singly linked list...

- 0of 0 votes
There are three threads and we want them to run

one after the other. How can we do that?

- 0of 0 votes
In a grid, you are given a position, and every location has some value.

find the shortest length so that you can touch to any boundary of the grid.

- 0of 0 votes
You are given a graph and an algorithm that can find the shortest

path between any two nodes

Now you have to find the second shortest path between same two nodes.