## Algorithm Interview Questions

- 0of 0 votes
Assume there is no software like google maps. you are given a map of world. Suppose you are somewhere in the hyderabad.

You will have to figure out all the paths from your location to Hyderabad airport.

I have given DFS approach. But the problem is that by doing DFS, a path can cross boundaries of Hyderabad and go so long away from Hyderabad

airport. DFS will take some much time. How to solve this problem?

- 2of 2 votes
Convert a string with digits into a literal representation of the number like: 1001 to one thousand one

- 0of 0 votes
`We encode a string, s, by performing the following sequence of actions: Replace each character with its ASCII value representation. Reverse the string. For example, the table below shows the conversion from the string "Go VMWare" to the ASCII string "711113286778797114101": // Character G o V M W a r e // ASCII Value 71 111 32 86 77 87 97 114 101 // // We then reverse the ASCII string to get the encoded string 101411797877682311117. // // For reference, the characters in s are ASCII characters within the range 10 - 126 which include special characters. // // Complete the decode function in the editor below. It has one parameter: // encoded - A reversed ASCII string denoting an encoded string s. // // The function must decode the encoded string and return the list of ways in which s can be decoded. static Collection<String> decode(String encoded) { }`

- 2of 2 votes
Given the list of the numbers. In this list, there are the numbers from the Fibonacci sequence.

Write the algorithm that retrieves all the numbers which belong to the Fibonacci sequence of numbers.

- 2of 2 votes
Decompress string - string (s) followed by {n} denotes s repeating n times

"a(b(c){2}){2}d" decompresses to "abccbccd"

"((x){3}(y){2}z){2}" decompresses to "xxxyyzxxxyyz"

- 1of 1 vote
Write a function that takes two numbers as strings and returns the result as a string:

mul(l string, r string) : string

Assume the numbers might be too large to be parsed into a variable of any numeric type the language has.

- 0of 0 votes
/**

*

* Google OnSite Round 3

*

* Data structure for Task Dependency

* A task can start only after all its pre-requisites are done

*

* Code the methods addTask(preRequisiteTask, dependentTask)

* and

* getExecutionSequence()

*

*/

- 0of 0 votes
/**

*

* Google OnSite Round 2

*

* Input is an integer array A

* Return an array B such that B[i] = product of all elements of A except A[i]

*

*/

- 0of 0 votes
/**

*

* Google Telephonic Round 2

*

* Given any uppercase string. Report the starting index at which any valid permutation of

* ABCDEF starts. If not found, then report -1.

* Possible permutations of ABCDEF are ABCDFE, BCDAFE, FEDCAB etc (a total of 6! = 720 permutations)

*

*/

- 0of 0 votes
/**

*

* Google Telephonic Round 3

* Find the sum of all nodes stored in a tree

*

*/

- 0of 0 votes
/**

*

* Google Telephonic Round 3

*

* Convert an integer to base-3 equivalent

*

*/

- 0of 0 votes
/**

*

* Google Telephonic Round 1

*

* Given two strings - S1 and S2.

* Arrange the characters of S1 in same alphabetical order as the characters of S2.

* If a character of S1 is not present in S2 - such characters should come at the end of

* the result string, but make sure to retain the order of such characters

* Case sensitivity is irrelevant

* e.g. S1 = "Google", S2 = "dog"

* Output = "ooggle"

*

* e.g. S1 = "abcdedadf", S2 = "cae"

* Output = "caaebdddf"

*

*/

- 0of 0 votes
Minimum Continuous Subsequence: targetList & availabletTagsList are two lists of string.

Input:

targetList = {"cat", "dog"};

availableTagsList = { "cat", "test", "dog", "get", "spain", "south" };

Output: [0, 2] //'cat' in position 0; 'dog' in position 2

Input:

targetList = {"east", "in", "south"};

availableTagsList = { "east", "test", "east", "in", "east", "get", "spain", "south" };

Output: [2, 6] //'east' in position 2; 'in' in position 3; 'south' in position 6 (east in position 4 is not outputted as it is coming after 'in')

Input:

targetList = {"east", "in", "south"};

availableTagsList = { "east", "test", "south" };

Output: [0] //'in' not present in availableTagsList

Note: targetList will contain Distinct string objects.

- -1of 1 vote
Given a list of characters, write a function to output a list of length of minimum non overlapping subsequences that can partition the input list.

For example:

Input : [a,b,c]

Output: [1,1,1]

Explanation: There are no repeated characters.

Input : [a,b,c,a]

Output: [4]

Explanation: The 'a' is repeated so one subsequence is between a to last a.

Input : [a,b,c,b,a,e,b,a,d,f,g,d,f,i,f,k,l,m,n,m,l]

Output: [8,7,6]

Explanation: max length from 1st 'a' to last 'a' is 8.

1st 'f' to last is 6 adding d to it = 7

so on

- 1of 1 vote
Michelle has created a word game for her students. The word game begins with Michelle writing a string and a number, K, on the board.

The students must find a substring of size K such that there is exactly one character that is repeated one;

in other words, there should be k - 1 distinct characters in the substring.

Write an algorithm to help the students find the correct answer. If no such substring can be found, return an empty list;

if multiple such substrings exist, return all them, without repetitions. The order in which the substrings are does not matter.

Input:

The input to the function/method consists of two arguments - inputString, representing the string written by the teacher;

num an integer representing the number, K, written by the teacher on the board.

Output:

Return a list of all substrings of inputString with K characters, that have k-1 distinct character i.e.

exactly one character is repeated, or an empty list if no such substring exist in inputString.

The order in which the substrings are returned does not matter.

Constraints:

The input integer can only be greater than or equal to 0 and less than or equal to 26 (0 <= num <= 26)

The input string consists of only lowercase alphabetic characters.

Example

Input:

inputString = awaglk

num = 4

Output:

[awag]

Explanation:

The substrings are {awag, wagl, aglk}

The answer is 'awag' as it has 3 distinct characters in a string of size 4, and only one character is repeated twice.

- 1of 1 vote
Google

1st round

Given a box with N balls in it, each ball having a weight, randomly choose pick one out base on the weight.

Input ball1-> 5kg, ball2 -> 10kg and ball3 -> 35kg,

then Prob(ball1 chosen) = 10%, Prob(ball2) = 20%,

Prob(ball3) = 70% ;

Follow-up:

Select a ball randomly based on weights. Once a ball is chosen, remove it. Next time select from the remaining balls. Go on until there is nothing left in the box.

- 2of 2 votes
Find whether string S is periodic.

Periodic indicates S = nP.

e.g.

S = "ababab", then n = 3, and P = "ab"

S = "xxxxxx", then n = 1, and P = "x"

S = "aabbaaabba", then n = 2, and P = "aabba"

follow up:

Given string S, find out the P (repetitive pattern) of S.

- 1of 1 vote
Design a hit counter which counts the number of hits received in the past 5 minutes.

Each function accepts a timestamp parameter (in seconds granularity) and you may assume that calls are being made to the system in chronological order (ie, the timestamp is monotonically increasing). You may assume that the earliest timestamp starts at 1.

Example:

HitCounter counter = new HitCounter();

// hit at timestamp 1.

counter.hit(1);

// hit at timestamp 2.

counter.hit(2);

// hit at timestamp 3.

counter.hit(3);

// get hits at timestamp 4, should return 3.

counter.getHits(4);

// hit at timestamp 300.

counter.hit(300);

// get hits at timestamp 300, should return 4.

counter.getHits(300);

// get hits at timestamp 301, should return 3.

counter.getHits(301);

Follow-up:

Due to latency, several hits arrive roughly at the same time and the order of timestamps is not guaranteed chronological.

Follow up 2:

What if the number of hits per second could be very large? Does your design scale?

- 1of 3 votes
Round3 Google

For N light bulbs , implement two methods

I. isOn(int i) - find if the ith bulb is on or off.

II. toggle(int i, int j) - i <= j. Switch state (switch on if it's off, turn off if it's on) of every bulb in range i to j.

All bulbs are off initially.

- 2of 2 votes
/**

* Google

* Given a list of non-negative numbers and a target integer k,

* write a function to check if the array has a continuous subarray of size at least 2 that sums up to the multiple of k, that is, sums up to n*k where n is also an integer.

**/

- 3of 3 votes
Amazon

Given an ArrayList of Nodes, with each Node having an ID and a parent ID, determine whether the List is given in preorder.

- 2of 2 votes
Google

Given an array a[] and an integer k, a[i] means flower at position a[i] will blossom at day i. Find the first day that there are k slots between two blooming flowers.

- 1of 1 vote
Google

Given a string that represents time like "15:31", find the next time that is formed by the numbers in the string(a number can be used more than once). For "15:31", the answer should be "15:33".

- 1of 1 vote
Twitter

Create a simple stack which takes a list of elements.

Each element contains a stack operator (push, pop, inc) and a value to either push/pop or two values, n and m,

which increment the bottom n values by m.

Then print the topmost value of the stack after every operation. If the stack is empty, print "empty"

- 1of 1 vote
Print words in order which are occurring once in huge document. The RAM size 100MB and file size 10 GB.

Example: I am good. You are good.

Answer : I am You are

Note : It's not datastructure problem where we can simply make use of LinkedHashMap. The file size is going to be huge.

- 2of 2 votes
DropBox Dec 2017

Congrats to Brian landing @DropBox

Round 3：

Develop an web crawler API, find all sub-sites reachable from a given URL.

Given this method - vector<string> getURLs(string url);

Comparison of DFS vs BFS in the scenario

Follow up：

Support multi-thearding.

Round 4：

Build an ID allocator. Max ID value is given as MAX. Allocate IDs from 0 to MAX.

Must be able to handle when an ID gets released.

Must be able to handle exceptions.

Follow-up: Improve time/space efficiency.

Optimal approach:

Segment tree + bit map.

Looking for interview experience sharing and coaching?

Visit aonecode.com for private lessons by FB, Google and Uber engineers

ONE TO ONE real-time coaching on SYSTEM DESIGN, ALGORITHMS, and mock interviews.

Feel free to email us aonecoding@gmail.com with any questions. Thanks!

- 0of 0 votes
Given a List determine if contiguous elements of the List sum to an input number. For example: Array/List [6 5 3 2 1 7], and input number 8. The numbers 5 + 3 = 8. Or suppose an input number 10, the elements of the list 2 + 1 + 7 = 10.

- 0of 0 votes
N different couple go to cinema with 2N different seats. They take their place randomly. You could make swap operations. Write a code for given input what is the minimum number of swap operations for sitting all couples with their partners? Additionally, be sure that no one swaps more than 2 times.

- 0of 0 votes
Create an algorithm to compare two database.

- 0of 0 votes
Algorithm to compare two database.