## Algorithm Interview Questions

- 0of 0 votes
Calculate and replace repeated characters in a string with their number of occurrences.

Example :

aaaggbbbbc

3a2g4b1c

- 0of 0 votes
Sort elements by frequency, print the elements of an array in the decreasing frequency if 2 numbers have same frequency then print the one which came first.

- 0of 0 votes
Write a program which will bold the sub-string found in string (HTML Style).

`Example: string = "HelloWorld HelloWorld" substringList = ["el", "rl"] Make it like HTML Style:- NewString = "H<b>el</b>loWo<b>rl</b>d H<b>el</b>loWo<b>rl</b>d`

- 0of 0 votes
Given an array of integers, design an algorithm that moves all non-zero integers to the end of the array. Minimize the number of writes or swaps.

- 0of 0 votes
How to verify the string which contains alpha-bates,parenthesis and signglle/double quote

Ex: AB(CD{"GH"}) is valid

"A()B' is invalid

- 0of 0 votes
Implement multiple stacks using a single contiguous block of memory

- 0of 0 votes
Write an efficient solution to give the next best available slot in a parking lot given that you need to minimize the effort to park and exit from the lot.

- 0of 0 votes
Write a program to implement event bus

- 0of 0 votes
Design and implement a sender and receiver system where there can be multiple senders and receivers subscribed to Topics. Each event generated at sender should be received by all receivers subscribed to that topic. Bonus if you can implement group mechanism at receiver side where event is received by one of the receiver in group and received by all groups subscribed to that Topic.

- 0of 0 votes
Implement in-memory file system

- 0of 0 votes
In memory cache implementation which supports concurrent operations for PUT, GET and DELETE

- 0of 0 votes
Stream of news events come; Need to find top 5 news at any time. use suitable data structure as score of news can dynamically increase or decrease.

- 0of 0 votes
Implement thread safe generic typed hashmap.

- 0of 0 votes
Determine if a point is inside a 2D convex polygon

- 0of 0 votes
Design rubik’s cube and its operation (all rotations and checking final state)

- 0of 0 votes
Given an Array of N elements and Integer K, write a function that returns true if the sum of any 2 elements of Array is K, false otherwise.

- 0of 0 votes
Write code to decode strings. For example, String str = "3[a2[bd]g4[ef]h]", the output should be "abdbdgefefefefhabdbdgefefefefhabdbdgefefefefh".

My solution is as follows.`public class StringDecoder { public static void main(String[] args){ String s = "3[a2[bd]g4[ef]h]"; System.out.println(decode(s)); } public static String decode(String s){ if(s == null || s.length()==0) return s; int indexOfFirstNumber = findIndexOfFirstNumber(s); int indexOfFirstBracket = findIndexOfFirstBracket(s); int indexOfClosingBracket = findIndexOfClosingBracket(s, indexOfFirstBracket); if(indexOfFirstNumber == -1) return s; String subStr1 = s.substring(0, indexOfFirstNumber); String subStr2 = decode(s.substring(indexOfFirstBracket+1, indexOfClosingBracket)); String subStr3 = decode(s.substring(indexOfClosingBracket+1, s.length())); int duplicates = Integer.parseInt(s.substring(indexOfFirstNumber, indexOfFirstBracket)); StringBuilder sb = new StringBuilder(); sb.append(subStr1); while(duplicates>0){ sb.append(subStr2); duplicates--; } sb.append(subStr3); return sb.toString(); } public static int findIndexOfFirstNumber(String s){ int index = -1; for(int i=0; i<s.length(); i++){ char c = s.charAt(i); if(c>=47 && c<=58){ index = i; break; } } return index; } public static int findIndexOfFirstBracket(String s){ int index = -1; for(int i=0; i<s.length(); i++){ char c = s.charAt(i); if(c=='['){ index = i; break; } } return index; } public static int findIndexOfClosingBracket(String s, int indexOfBracket){ int index = -1; int numberOfBracket = 1; for(int i=indexOfBracket+1; i<s.length(); i++){ char c = s.charAt(i); if(c == '[') numberOfBracket++; if(c==']'){ numberOfBracket--; if(numberOfBracket==0){ index = i; break; } } } return index; } }`

- 0of 0 votes
Print first pair of mis-matching leaves (first pair as in in-order) given two pre-order traversal arrays of BSTs.

e.g.`For 5 4 8 2 4 6 9 Pre-order Sequence as [5,4,2,4,8,6,9] & 5 3 8 2 4 7 9 Pre-order Sequence2 as [5,3,2,4,8,7,9] Print “4, 3”.`

- 0of 0 votes
Randomly select one of the weighted items from a linked list. (you may only go through the list once)

e.g.

weight 1.6 -> weight 0.2-> ... -> weight 3.4

randomly select one item based on the weight. The higher the weight is, the more likely to be selected

- 0of 0 votes
Given a list L of numbers from 0 to n, and another number k = [0-9], find how many times k appears in L. If the target number in L is more than one digit, treat each digit separately. For example, k=0 appears twice in L = [0,10].

- 0of 0 votes
Given a list of system packages, some packages cannot be installed until the other packages are installed. Provide a valid sequence to install all of the packages.

e.g.

a relies on b

b relies on c

then a valid sequence is [c, b, a]

- 0of 0 votes
Q: Find the absolute paths to all directories with image files, given a file system that looks like this. The subdirectory is one indent over.

`/usr /local profile.jpg /bin config.txt dest.png /rbin image.gif /sys /re /tmp pic.jpg ..... ……`

- 0of 0 votes
Q: List all comments in the given segment of codes. It's pretty tricky since there is a lot of things to be considered, especially the escape characters.

- 0of 0 votes
Given two strings needle and haywards that contains ASCII characters,write an algorithm to output a list of 0-based indices of the occurances of all anagrams of needle in haystacks

- 0of 0 votes
Given a list of list of positive integers, find all pairs of list which are having more than 3 elements overlapping.

What is the complexity.

- 1of 1 vote
down vote

favorite

Consider the following series:

A := 1

B := A*2 + 2

C := B*2 + 3 and so on...

Write a program that:

-outputs the number corresponding to a given letter;

-given a string of letters like 'GREP', computes the sum of the numbers corresponding to all the letters in the string (i.e., G + R + E + P), as given by the above series; and

-given a large number (that would fit into a standard 32-bit integer), finds the shortest string of letters corresponding to it. You may use a greedy approach for the last part. Compute the values of the numbers corresponding to letters as and when required and DO NOT pre-compute beforehand and store them in a data structure.

- 0of 0 votes
What is the smallest number *n* by which the given number *x* must be divided to make it into a perfect square?

`n = find_number( x )`

- 0of 0 votes
2.{{ Query the sum of all the data values in a given rectangle (x1,y1) ~(x2, y2).

int querySum(int x1, int y1, int x2, y2) {}}}

- 0of 0 votes
{{Given a two dimensional grid that stores data as integers with the size of N*M, implement write and query functions which supports:

1. Write the given value to designated coordination (x, y).

void write(int value, int x, int y) {}

}}

- 0of 0 votes
Running with Bunnies

====================

You and your rescued bunny prisoners need to get out of this collapsing death trap of a space station - and fast! Unfortunately, some of the bunnies have been weakened by their long imprisonment and can't run very fast. Their friends are trying to help them, but this escape would go a lot faster if you also pitched in. The defensive bulkhead doors have begun to close, and if you don't make it through in time, you'll be trapped! You need to grab as many bunnies as you can and get through the bulkheads before they close.

The time it takes to move from your starting point to all of the bunnies and to the bulkhead will be given to you in a square matrix of integers. Each row will tell you the time it takes to get to the start, first bunny, second bunny, ..., last bunny, and the bulkhead in that order. The order of the rows follows the same pattern (start, each bunny, bulkhead). The bunnies can jump into your arms, so picking them up is instantaneous, and arriving at the bulkhead at the same time as it seals still allows for a successful, if dramatic, escape. (Don't worry, any bunnies you don't pick up will be able to escape with you since they no longer have to carry the ones you did pick up.) You can revisit different spots if you wish, and moving to the bulkhead doesn't mean you have to immediately leave - you can move to and from the bulkhead to pick up additional bunnies if time permits.

In addition to spending time traveling between bunnies, some paths interact with the space station's security checkpoints and add time back to the clock. Adding time to the clock will delay the closing of the bulkhead doors, and if the time goes back up to 0 or a positive number after the doors have already closed, it triggers the bulkhead to reopen. Therefore, it might be possible to walk in a circle and keep gaining time: that is, each time a path is traversed, the same amount of time is used or added.

Write a function of the form answer(times, time_limit) to calculate the most bunnies you can pick up and which bunnies they are, while still escaping through the bulkhead before the doors close for good. If there are multiple sets of bunnies of the same size, return the set of bunnies with the lowest prisoner IDs (as indexes) in sorted order. The bunnies are represented as a sorted list by prisoner ID, with the first bunny being 0. There are at most 5 bunnies, and time_limit is a non-negative integer that is at most 999.

For instance, in the case of

[

[0, 2, 2, 2, -1], # 0 = Start

[9, 0, 2, 2, -1], # 1 = Bunny 0

[9, 3, 0, 2, -1], # 2 = Bunny 1

[9, 3, 2, 0, -1], # 3 = Bunny 2

[9, 3, 2, 2, 0], # 4 = Bulkhead

]

and a time limit of 1, the five inner array rows designate the starting point, bunny 0, bunny 1, bunny 2, and the bulkhead door exit respectively. You could take the path:

Start End Delta Time Status

- 0 - 1 Bulkhead initially open

0 4 -1 2

4 2 2 0

2 4 -1 1

4 3 2 -1 Bulkhead closes

3 4 -1 0 Bulkhead reopens; you and the bunnies exit

With this solution, you would pick up bunnies 1 and 2. This is the best combination for this space station hallway, so the answer is [1, 2].

Test cases

==========

Inputs:

(int) times = [[0, 1, 1, 1, 1], [1, 0, 1, 1, 1], [1, 1, 0, 1, 1], [1, 1, 1, 0, 1], [1, 1, 1, 1, 0]]

(int) time_limit = 3

Output:

(int list) [0, 1]

Inputs:

(int) times = [[0, 2, 2, 2, -1], [9, 0, 2, 2, -1], [9, 3, 0, 2, -1], [9, 3, 2, 0, -1], [9, 3, 2, 2, 0]]

(int) time_limit = 1

Output:

(int list) [1, 2]