kulkarniaks007
BAN USER1. Get the list of friends for the current customer.
2. Create Hashmap with productId as key and its count as value.
3. For each friend get list of products purchased by him/her.
4. Put the product id in hashmap if the productid is not already present. If already present increment the count by 1.
5. Now After all the friends and products are finished create maxHeap using the HashMap.
Time Complexity : O(no of friends * no. of products)
Space Complexity : O(no. of unique product Ids *2) = (no. of unique product Ids)
2 is multiplied because 1 for hashmap and 1 for max heap.
public static int getTotalNumberOfOccurences(String target, String source)
{
int[] targetCharacterCount = new int[256];
for(int i=0;i<target.length();i++)
{
targetCharacterCount[target.charAt(i)]++;
}
int totalCount = 0;
boolean[] sourceCharacter = new boolean[256];
for(int i=0;i<source.length();i++)
{
if(!sourceCharacter[source.charAt(i)])
{
totalCount = totalCount+targetCharacterCount[source.charAt(i)];
sourceCharacter[source.charAt(i)] = true;
}
}
return totalCount;
}
Yup. I also thought about the same solution. Use max heap that will hold min k elements. The size of the heap would remain n. Also deletion and insertion in heap on average case is O(1). So it would be very efficient.
- kulkarniaks007 March 16, 2014public static String replace(String replacer,String inp)
{
String[] str=inp.split(" ");
inp="";
for(int i=0;i<str.length;i++)
{
if(i!=str.length-1)
str[i]=str[i]+replacer;
inp=inp+str[i];
}
return inp;
}
You can't use extra space....as mentioned in the question
- kulkarniaks007 January 21, 2013I have used C# and the complexity is O(n)
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace TestDemo
{
class Program
{
static void Main(string[] args)
{
Console.WriteLine("Enter the sequence of Integer's and press 0 to end it");
List<int> numbers=new List<int>();
string inp;
do
{
inp = Console.ReadLine();
numbers.Add(Convert.ToInt32(inp));
} while (inp != "0");
int[] arr = numbers.ToArray();
Array.Sort(arr);
int max1 = arr[arr.Length - 1];
int max2 = arr[arr.Length - 2];
int max3 = arr[arr.Length - 3];
Console.WriteLine("Max Numbers:" + max1 + " " + max2 + " " + max3);
int sum = 0; int l = 0;
for (l = 1; l < arr.Length - 3; l++)
sum = sum + arr[l];
float avg =(float) sum / (l-1);
Console.WriteLine("Avg of rest:" + avg);
}
}
}
I somewhat agree with your comment. I think a hashmap with key as the Keyword and Value as List of Ads that have that keyword would be a good data structure over here.
- kulkarniaks007 April 09, 2014HashMap<KeyWord,List<Ads>>;
You can get list of all Ads with a specific keyword in O(1). If you have multiple keywords you can get all the K keywords in O(k) and then we need to iterate over the list to make sure it does not contain duplicates. So, I think the overall complexity would be O(k*n) where n is the number of unique Ads. If anyone can knows a better solution please comment.