## Algorithm Interview Questions

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

- 0of 0 votes
You are given an array of words. from each word, you make a chain, in that, you remove one char at a time and you remove that char only when the remaining word is present in the input array.

For Example, if the input is {a, b, ab, ac, aba}

then the possible chains are

from 'a', there is no chain, the chain it 'a' itself (of length 1)

similarly, from 'b', the chain length is 1 one (length is defined by the number of words in the chain)

now from 'ab', there are two possibilities which are ({ab -> b when you remove a},{ab -> a when you remove b}). So the max length is 2 here

now from 'ac', we only have one possibility which is ({ac -> a when we remove c}), because, when we remove 'a', we left with 'c' which is not present in the input.

Now, you have to find the length of the biggest such chain.

Input: array of words

Output: length of the biggest such chain.

- 0of 0 votes
VMWare Standard Online Screen

3rd Question Given an array of strings and a long description about the formatting of IPv6 and IPv4 (it took me more than 5 minutes to read the description). Write a function to find if a string is IPv4 or IPv6 address or neither.

4th Question Given an integer array, whenever a duplicate number is found, you may increment it (++). Find the minimum sum of the numbers in the array by keep incrementing the dups until all the numbers are unique.

- 1of 1 vote
VMWare Standard Online Screen

The Online Assessment was called something like Life Cycle Challenge-qpan.

There are 4 questions in total given 60 minutes. The problem description was unexpectedly long that it takes 5 minutes just to read a question.

1st Question Design a function to create BST. Given an integer array, insert the integers into the binary search tree and print all the steps taken.

2nd Question Given an integer, print the index of all the positions in which the binary bit is 1 in order.

- 0of 0 votes
Given a count and maxvalue, write a program to return count number of unique random integers between 0 and maxvalue.

- 2of 2 votes
Facebook Senior Engineer On-site 2017

1st Round

Question 1: Binary tree to doubly linked list.

Question 2: Read 4 (Given the read4 API, read an entire file)

2nd Round

Culture fit. No coding.

3rd Round

Question: System Design POI (Point of Interest. Given a point, find things within a radius).

Lunch

4th Round

Question 1: Decode way

Question 2: Random max index

5th Round

Question: System design + component-wise design on download manager

- 2of 2 votes
5th Round

Open-ended question What happens when you type a url in the browser and hit enter?

Second question Given an array of integers, print all the numbers that meet the following requirement - when the number is greater than every number on its left and smaller than every number on the right.

- 0of 2 votes
interviewed by senior engineer

Question Given two strings s1 and s2, combine the characters in the strings and maintain the sequence of characters

Follow-up If s1 has a length of m and s2 has a length of n, how many ways the strings could be merged. Figure out the formula F(m, n) = ?

- 0of 0 votes
Given a list of files. Return all the unique lines from all files.

- 0of 0 votes
You are given an unsorted binary array.

Ex [0 1 1 0 0 1 0 1 1 1 1 0 0 1 0 0 1]

and a number K, which represents the number of swap operations allowed on this binary array.

you need to find out the maximum length continuous subarray that can be generated using K many swaps.

Ex if K = 3 in above case

[0 1 1 0 0 1 0 1 1 1 1 0 0 1 0 0 1] => [0 1 1 0 0 1 1 1 1 1 1 0 0 0 0 0 1] => [0 1 1 0 1 1 1 1 1 1 1 0 0 0 0 0 0] => [0 0 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0]

so the answer is 9.

- 0of 0 votes
You are given a binary matrix whose each row is sorted. that means each row will have zeros at front and ones at the back. You need to find out the row which contains a maximum number of ones.

Ex :`[0 0 0 0 0 0 0 1 1 1 1 1] [0 0 0 0 1 1 1 1 1 1 1 1] [0 0 0 0 0 0 1 1 1 1 1 1] [0 0 0 0 0 0 0 0 0 1 1 1] [0 0 0 0 0 0 0 1 1 1 1 1] [0 0 0 0 1 1 1 1 1 1 1 1]`

Ans : second row and sixth with 8 ones. you will print [2,8] and [6,8];

Update : Required complexity O(M+N) + O(1) only.

- -2of 2 votes
Find the coordinates of the rectangle which is parallel to axis and has minimum area.

- 0of 0 votes
Suppose you have a stream of (timestamp, tag) events. You need to filter this stream (online), leaving only events with tags that haven't been already encountered in the last X seconds.

- 0of 0 votes
Given an array of integers:

1. rearrange the array such that all non-zero members appear on the left of the array (order is not important)

2. return the number of non-zero members

e.g. [1,2,0,5,3,0,4,0] => [1,2,5,3,4,0,0,0] and return 5. The non-zero array members can be in any order.

- 1of 1 vote
You are given an array of integers both negative and positive.

Print the maximum continuous sum of the array and if all the elements are negative, print the smallest of them.

Ex : [-20, -5, -2, -9] :> -2(-2)

Ex : [20, -19, 6, 9, 4] :-> 20(20)

Ex : [10, -3, 4, -2, -1, 10] -> 18 (10, -3, 4, -2, -1, 10)

Thanks velu007 for pointing out the mistake

- -1of 1 vote
--

- -1of 3 votes
Find the frequency of a number in array in less than bigo n time

Array 1,2,2,3,4,5,5,5,2

Input 5

Output 3

Array 1,1,1,1,

Input 1

Output 4

Keep in mind less than bigo n

Thanks

- 0of 0 votes
Delhi Route Traffic Optimizer

Traffic congestion is an annoying issue in Delhi, the capital of India. Every morning thousands of people drivea residential area to the International Technology Park (ITPL). There are various routes one can take to reach ITPL and each route takes its own time making some routes faster than the others. People obviously take faster routes which causes congestion on those roads too. Congestion results into increased travel time, air pollution and wastage of fuel. As a Traffic commissioner of Delhi, you are asked to optimize the traffic by putting toll to various roads so that resultant cost of every route (driving time cost and toll cost) ends up the same. This has to be done in such a way that any driver pays toll only once no matter which route he/she takes.roads have one-way traffic and there is no cycle in any of the routes. You need to create a toll plan for a given road layout.

The toll plan must adhere to following rules:

1. Toll should be levied in such a way that perceived cost (base road cost and toll cost) remains same forroads.

2. The tolls should be levied such that the total cost for each route is minimized.

3. A route cannot have more than one toll.

4. In case of multiple solutions for a route, add toll to a road that is closer to destination.

In some use cases, it might be impossible to impose tolls that satisfy the above conditions.

http://qa.geeksforgeeks.org/11340/delhi-route-traffic-optimizer

- 1of 1 vote
Given some email ids, and a similarity function which says whether two email ids are similar, determine all the sets of email ids that are similar to each other.

- 0of 0 votes
You have a string consisting of open and closed parentheses, but parentheses may be imbalanced.

Make the parentheses balanced and return the new string.

- 1of 1 vote
Given a list of URLs entered by a user write a program to print unique and most recently used URLs. For example if user entered the following: -

1. google.com

2. yahoo.com

3. wsj.com

4. google.com

The output should be :-

1. google.com

2. wsj.com

3.yahoo.com

- 0of 0 votes
Given a movie X that the user had watched, write an algorithm to suggest more movies to the user. How to display the other movies based on same genre?

- 2of 2 votes
Given a sorted array, find all the numbers that occur more than n/4 times.

- 0of 0 votes
How to Design an Meeting scheduler

- 0of 2 votes
How to randomly select a number in an array?

array: [15, 2, 4, 5, 1, -2, 0]

Follow-up:

Given a second array freq where freq[i] represents the occurrence of the ith number in array, how to randomly select a number in array based on the frequency.

Extra requirement:

Could you complete the selection in a single-pass(go through each array only once)?

- 1of 5 votes
In school a student gets rewarded if he has an attendance record without being absent for more than once or being late for 3 times continuously.

Given a student's attendance record represented by a string with 3 possible characters 'L'(Late), 'A'(Absent), 'O' (On time),

check whether the student qualifies for the reward.

e.g.

@INPUT (String) "OLLAOOOLLO"

@RETURN (Boolean) False

The student does not qualify for reward because "LLA" means he was late for 3 times in a row.

@INPUT (String) "OLLOAOLLO"

@RETURN (Boolean) True

Follow-up:

If known the length of the attendance string is n, how many possible ways there is to attend school and make sure you get the reward.