VillageMonkey
BAN USER- 0of 0 votes
AnswersLarge shared HDD is synced with Cloud Server. HDD contains same files multiple times by different users. How does the cloud server manage duplicates. It can't store all the duplicates. Duplicates may not be differ by file name. Discuss algorithm.
- VillageMonkey in India| Report Duplicate | Flag | PURGE
Amazon Software Development Manager Algorithm
1) Get the file 1 size in bits and create a bitmap of that size and initialize to zero.
2) Read file1 and from file 1, read all integers.
if(bitmap[file1[i]] is not set then -> bitmap[file1[i]] = 1.
else //common numbers in same file. so no action.
3) Now read from integers from file 2.
Check the bitmap created by file1 for the number.
if it is already set then print as common element.
otherwise dont print.
time: O(Number of entries in file1+file2)
space: O(size(file1))
1) Find the middle of the linked list using two pointers.
2) Reverse the linked list from the middle(second half).
3) Now two pointers, 1st one from start of list, 2nd one from middle of list.
Compare the list elements by moving pointers each time by one.
Check for palindrome property.
Fill array b with entries s.t. b[0] = a[1]-a[0] .... b[n-1] = a[n]-a[n-1].
Now apply Kadane's Sub sequence sum algorithm on B and Find the indices.
Time O(n), Space O(n).
1. Find Kth Element from Beginning. Store the pointer.
2. Using Kth Element, find kth element from last(two pointers)
3. Swap these pointers.
4. At every step, check for length traversed till is < n, otherwise raise error
sorry bitmap of size 2^32 is needed. Creation of bitmap of size file1 wont work.
- VillageMonkey June 08, 2012