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
@raja
- topcoder99 January 14, 2012You are right but using a trie requires a huge space complexity.
Is there any solution without using trie?