## Algorithm Interview Questions

- 2of 2 votes
FB on-site two weeks ago last round of coding . (This problem is also in the internal question bank of G.)

There is a robot in a room. The initial location of the robot is unknown. The shape or area of the room is unknown.

You have a remote that could walk the robot into any of the four directions - up, left, down or right.

Here is the move method: boolean move(int direction), direction: 0, 1, 2, 3. If the robot hits the wall, the method returns false.

Otherwise returns true and the robot moves on to the direction given.

Find out the area of the room.

e.g.

X

XXX X

XXXXX 'X' marks the floor plan of the room.

A room like such has an area of 10.

- 0of 0 votes
Last Monday phone interview of G.

Given a vector/list of doubly linked list pointers (a pointer is the directed linkage of two nodes), count how many independent blocks of linked lists there are for the pointers given.

- 0of 0 votes
Find the first non repeating character in a string. For example if the input string "abcdeabc", non repeating character is "e"

- -1of 1 vote
Find if a mathematical string is balanced in terms of parenthesis. For example "(1+2)" is balanced and "(1+2" is not balanced.

- 1of 1 vote
You have a array with integers:

`[ 1, -2, 0, 6, 2, -4, 6, 6 ]`

You need to write a function which will evenly return indexes of a max value in the array.

In the example below max value is 6, and its positions are 3, 6 and 7. So each run function should return random index from the set.

Try to implement with O(n) for computation and memory.

Try to reduce memory complexity to O(1).

- 0of 0 votes
The number of valid combinations of a strings for given input array a[], where a=>1, z => 26, and 0 <= a[i] <= 9

{1,1,1} => {aaa, ak, ka} => 3

{1,1,0} => {aj} => 1

- 0of 0 votes
/* The objective of this exercise is to build a road network connecting every pair of cities.

Each city should be connected to each other city once.

*/

public class Program

{

/* Your function RoadBuilder should return a list of new roads required to be built,

if the existing roads are given by builtRoads and the total number of

cities is nCities. Roads should not connect cities to themselves.

*/

public static int[][] RoadBuilder(int nCities, int[, ] builtRoads)

{

//implement the function here

return new int[0][];

}

public static void Main()

{

int[, ] test1 = new int[3, 2]{{0, 1}, {1, 2}, {3, 2}};

Console.WriteLine(RoadBuilder(4, test1)); // expected result should be {{0,2}, {0, 3}, {1, 3}}

}

}

- 0of 0 votes
There are three row of houses. There are N houses in each row. Each house can be painted with three colors: red, blue and green. The cost of painting each house with a certain color is different. You have to paint all the houses with following constaints

No two adjacent houses in a row have the same color.

Houses in a column have three different colors

You have to paint the houses with minimum cost. How would you do it?

Note: The cost of painting house 1 red is different from that of painting house 2 red in any row. Each combination of house and color has its own cost.

- 0of 0 votes
Given a binary tree of integers, write code to store the tree into a list of integers and recreate the original tree from a list of integers.

Here's what your method signatures should look like (in Java):

List<Integer> store(Node root)

Node restore(List<Integer> list)

Example Tree:

5

/ \

3 2

/ / \

1 6 1

- 1of 1 vote
You are given set of strings, You have return anagrams subsets from it. An anagram set is that one where every string is an anagram of another string. If the subset contains only one string, don't include that in the result.

- 0of 0 votes
You are given a NxN boolean matrix, where matrix(i,j) will be one if 'i' is a parent of 'j' in a tree, otherwise, it is zero.

Construct this tree.

- 0of 0 votes
Design/Implement an LRU cache so that Read/Write/Find operation only takes constant time.

Now, Let's say, we will be considering the frequency as well. It means to keep the most used processes and in a case of the tie, use lease recently used to remove an element.

Now, as this new algorithm can cause many hits, or no new process will come to the cache if the last process of the cache has two hits., What can you do to prevent this, and how would you implement that.

- 0of 0 votes
Apple On-site at Cupertino

Team Data Warehousing

III. Given three letters ABC, where AB->C, AC->B, BC->A (sequence doesn’t matter). Get the length of the path to convert from a given string to a single character.

For example, “ABACB” goes to “ACCB” (based on AB ->C, convert s[1] and s[2] to C)

“ACCB” goes to “BCB” (based on AC->B)

“BCB” goes to “AB”

“AB” goes to “C”

So it takes 4 steps to change the given string into a single character.

If a given string cannot be resized to 1 character, such as “AAA” or "ABACABB", return -1.

- 0of 0 votes
Apple On-site at Cupertino

Team Data Warehousing

There were 6.5 rounds in total, that 0.5 on package negotiation with the HR and the remaining rounds with 2 managers and 4 engineers.

Only three pure coding questions were asked.

I. Use a stack to sort given data.

II. Given an array with positive integers only, find the MIN integer that is missing from the array.

- 0of 0 votes
You are given an array of values, (not necessary integers or positives) and a value. You have to print all the pairs whose sum is given value. Write a general method which can accept integers, float, doubles, long, or any other thing where this make sense.

- 0of 0 votes
You are given an array of stock prices, You have to return maximum profit one can make when buying once and selling once. Consider, you are buying one stock only.

- 0of 0 votes
You are given set of strings, you have to print out the could of each distinct patterns. Please consider anagrams as same pattern and even the char count does not matter.

Ex:

abbba

ab

ba

abcd

abdc

adbc

aabddc

output:

ab: 3

abcd: 4

- 0of 0 votes
Implement pow(x, n)

- 1of 1 vote
Pick three numbers a, b, c from an array of integers to get the maximum product a * b * c.

Began with the O(N^3) solution. Then the interviewer give clues on optimization by sorting the array.

- 0of 0 votes
Jamie is walking along a number line that starts at point 0 and ends at point n. She can move either one step to the left or one step to the right of her current location , with the exception that she cannot move left from point 0 or right from point n. In other words, if Jamie is standing at point i,she can move to either i-1 or i+1 as long as her destination exists in the inclusive range [0,n]. She has a string ,s , of movement instruction consisting of the letters 1 and r , where 1 is an instruction to move one step left and r is an instruction to move one step right.

Jamie followed the instructions in s one by one and in order .For Example if s=‘rrlr’,she performs the following sequence of moves :one step right ->one step right ->one step left -> one step right .Jamie wants to move from point x to point y following some subsequence of string s instruction and wonders how many distinct possible subsequence of string s will get her from point x to point y. recall that a subsequence of a string is obtained by deleting zero or more characters from string .

it has four parameters

A String , s giving a sequence of eduction using the characters l( i.e. move left one unit ) and r (i.e. move right one unit)

An integer n, denoting the length of the number line.

An integer x, denoting jamie’s starting point on the number line

An integer y , denoting Jamie’s enidng point on the number line.

The function must return an integer denoting the total number of distinct subsequence of string s that will lead Jamie from point x to point y as this value cab be quite large .

Sample Input

rrlrlr

6

1

2

out put =7

- 0of 0 votes
Q 2. You are given a chess game board of size NxN. You have find out positions(i,j), where you can place N queens so that, none of the queens can kill each other without making their first move.

- 1of 1 vote
Q 1. You are given an array of integers, contains positive, negative and zeros. You have to written subarray whose sum is maximum in this array.

Desired Complexity is O(N) + O(1)

- 0of 0 votes
You have given a tree, where each node can have multiple children. You have to find if the tree has a cycle or not.

Ex`A / \ / \ B C / | \ | \ D E F E H | B`

This tree has a cycle from B -> E -> B.

Please note that you only know the nodes that you have traveled in the tree, so at the beginning, you will only know that there is a root node and nothing else about any other node.

The followup question was to print the cycle in the tree if found.

- 1of 1 vote
Find sets of values in array whose sum is equal to some number.

- 0of 0 votes
Q 7. You are getting a stream of integers, You have to find the median of these in real time(or with minimum complexity).

- 0of 2 votes
Amazon SDE 2 On-site (1 of 4 Rounds)

In a file system stored a large amount of user’s browsing data, including the urls that the user visited. Design a function that outputs the longest common path of all the urls.

Having finished the code, I was asked to analyze the complexity.

- 0of 0 votes
find the isomorphic pairs of string !!

a string is said to be isomorphic if its each alphabets can be replaced by another alphabet

for ex "abca" and "zxyz" are isomorphic but "abca" and "pqrs" is not isomorphic

conditions :

1 - A character can be replaced by itself. for ex "abcd" and "pbfg" are isomorphic .

2- No two characters can be replaced by same character . for ex "abcd" and "bbcd" are not isomorphic .

- -1of 1 vote
Sorry had to remove this question

- 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 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.