ur.devesh
BAN USER- 0of 0 votes
AnswersYou are given very huge file , with each line containing a single word. We have to give the count and word which is repeated most. I answer of using TRIE data structure to hold the word. I am reading a word at a time and incrementing the counter if i am getting the same word. I am keeping a global max count to keep the max count and the word. Complexity will be O(total letters in the file);
- ur.devesh in India| Report Duplicate | Flag | PURGE
Amazon SDE1 Algorithm - 0of 0 votes
AnswersGiven a binary search tree (BST) with each node having some value. You have to compute for each node the summation of all nodes whose value is greater than the current node.I have used the DFS kind of algorithm.
- ur.devesh in United StatesDictionary<node,bool> visited = new Dictionary<node,bool>(); int Traverse(node n ) { if(node.Right == null) if(node.Left != null && !visited(node.Left)) Traverse(node.Left); return node.value; node.Summation = Traverse(node.Right); if(node.Left != null && !visited(node.Left)) Traverse(node.Left); return node.Value + node.Summation; }
| Report Duplicate | Flag | PURGE
Amazon SDE1 Algorithm
Here is my solution in C#
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace AlgoSolution
{
class BSearch
{
static void Main()
{
int[] num = new int[] { 1 , 1 , 2 ,2 , 3 ,3, 4 };
Console.WriteLine(LowerBound(num, 4) + 1);
Console.WriteLine(UpperBound(num, 3) - 1);
}
static int LowerBound(int[] data, int num)
{
int min = 0;
int max = data.Length;
while (min < max)
{
int mid = min + (max - min + 1) / 2;
if (data[mid] < num)
{
min = mid;
}
else
{
max = mid - 1;
}
}
return min;
}
static int UpperBound(int[] data, int num)
{
int min = 0;
int max = data.Length;
while (min < max)
{
int mid = min + (max - min ) / 2;
if (data[mid] > num)
{
max = mid;
}
else
{
min = mid + 1;
}
}
return min;
}
}
}
i will divide the int val = totalCount % n and so the iteration will go till the n * val
int val = totalCount % n;
Stack<int> s = new Stack<int>();
for(int i = 1 ; i <= n * val ; n++
{ if(i % n == 0)
s.Push(num[i]);
while(s.Count() > 0 )
Console.WriteLine(s.Pop());
}else {
s.Push(num[i];
}
//For rest of the numbers
for(int i = val * n + 1 ; i < totalLength ; i++)
Console.writeLine(num[i]);
Take first one million integer and merge it with next file which will be total 2 million records and now sort it which will be nLog(N) less than 3 million .
- ur.devesh May 23, 2014Now pick the 1 million records from here and merge with the next file and repeat the process. At last you will have the 1 million sorted records.