## topcoder99

BAN USER- 0of 0 votes

AnswersDesign the autocomplete feature (ex:Google Suggest)

- topcoder99 in United States for Bing| Report Duplicate | Flag | PURGE

Microsoft Software Engineer / Developer Algorithm - 1of 1 vote

AnswersGiven a file, return the list of all the words which occurs exactly n times in the file

- topcoder99 in United States for Bing| Report Duplicate | Flag | PURGE

Microsoft Software Engineer / Developer Algorithm - 0of 0 votes

AnswersGiven a list of words, L, that are all the same length, and a string, S, find the starting position of the substring of S that is a concatenation of each word in L exactly once and without any intervening characters. This substring will occur exactly once in S..

- topcoder99 in United States

.

Example:.

L: "fooo", "barr", "wing", "ding", "wing".

S: "lingmindraboofooowingdingbarrwingmonkeypoundcake".

fooowingdingbarrwing.| Report Duplicate | Flag | PURGE

Facebook Software Engineer / Developer Algorithm - 0of 0 votes

AnswersYou are given a list of points in the plane, write a program that

- topcoder99 in United States

outputs each point along with the three other points that are closest

to it. These three points ordered by distance.

The order is less then O(n^2) .

For example, given a set of points where each line is of the form: ID

x-coordinate y-coordinate

1 0.0 0.0

2 10.1 -10.1

3 -12.2 12.2

4 38.3 38.3

5 79.99 179.99

Your program should output:

1 2,3,4

2 1,3,4

3 1,2,4

4 1,2,3

5 4,3,1| Report Duplicate | Flag | PURGE

Facebook Software Engineer / Developer Algorithm - 0of 0 votes

AnswersA sequence of numbers is called a zig-zag sequence if the differences

- topcoder99 in India

between successive numbers strictly alternate between positive and

negative. The first difference (if one exists) may be either positive

or negative. A sequence with fewer than two elements is trivially a

zig-zag sequence.

For example, 1,7,4,9,2,5 is a zig-zag sequence because the differences

(6,-3,5,-7,3) are alternately positive and negative. In contrast,

1,4,7,2,5 and 1,7,4,5,5 are not zig-zag sequences, the first because

its first two differences are positive and the second because its last

difference is zero.

Given a sequence of integers, sequence, return the length of the

longest subsequence of sequence that is a zig-zag sequence. A

subsequence is obtained by deleting some number of elements (possibly

zero) from the original sequence, leaving the remaining elements in

their original order| Report Duplicate | Flag | PURGE

Amazon Arrays - 0of 0 votes

AnswersGiven an array-based heap on n elements and a real number x, efficiently determine whether the kth smallest element in the heap is greater than or equal to x. Your algorithm should be O(k) in the worst-case, independent of the size of the heap.

- topcoder99 in India| Report Duplicate | Flag | PURGE

Amazon Software Engineer / Developer Algorithm - 0of 0 votes

Answerswrite an algorithm finding the no.of one bits from 1 to n,for given any n value.

- topcoder99 in India

complexity should be good

example:

1=1

2=10

3=11

4=100

5=101

6=110

.

.

if n=3 then ur answer is 4

if n=6 then ur answer is 9

Interviewer is looking for an algo in O(log N)time complexity| Report Duplicate | Flag | PURGE

Amazon Software Engineer / Developer Algorithm - 0of 0 votes

AnswersGiven an array of integers, find the longest subsequence of elements which monotonically increases. for ex. array = {1 4 8 2 5 7 3 4 6}, the longest subsequence = {1 2 3 4 6}

- topcoder99 in India

I have explained him about O(N^2) with O(1) space algorithm but the interview is expecting O(N log N). Could any one help me explaining the algorithm in detail ?| Report Duplicate | Flag | PURGE

Amazon Software Engineer / Developer - 1of 1 vote

AnswersYou are given 'n' appointments. Each appointment contains startime and

- topcoder99 in India

endtime. You have to retun all conflicting appointments efficiently

starttime and endtime can range from a few min to few years.| Report Duplicate | Flag | PURGE

Google Software Engineer / Developer Algorithm

Yes Swathi algorithm will fail.

I will extend the Swathi Algorithm:

Start scanning the array from left to right... Have an empty array/vector..

1) if the current element is greater than the next element then push the element on to the array..

2) else Using binary Search, find the element in the array and replace the number just greater than equal to the current element.

3) Whatever remains in the array/vector will be the maximum subsequence

It is O(N log N) time and O(N) space complexity

@Alex

Could you please explain the logic for n = 15?

Also I didnt get why the complexity is O(log N) in your case

@Anonymous

Could you please explain the algo given in wikepedia?

I meant O(N log N) time with O(N) Space Complexity

**CareerCup**is the world's biggest and best source for software engineering interview preparation. See all our resources.

@raja

- topcoder99 January 14, 2012You are right but using a trie requires a huge space complexity.

Is there any solution without using trie?