musfiqur
BAN USERThis java code is definitely O(n).
LinkedList<Integer> list1=new LinkedList<Integer>();
LinkedList<Integer> list2=new LinkedList<Integer>();
LinkedList<Integer> list3=new LinkedList<Integer>();
Random r=new Random();
for(int i=0;i<10;i++){
list1.add(r.nextInt(20));
list2.add(r.nextInt(20));
}
Collections.sort(list1);
Collections.sort(list2);
int currentindex1=0,currentindex2=0;
while(currentindex1<list1.size()&¤tindex2<list2.size()){
int x=list1.get(currentindex1);
int y=list2.get(currentindex2);
if(y==x){
currentindex1++;
}
else if(x<y){
list3.add(x);
currentindex1++;
}
else{
currentindex2++;
}
}
System.out.println(list1);
System.out.println(list2);
System.out.println(list3);
}
Here is the C# code for the same:
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace Algorithms
{
class Program
{
static void Main(string[] args)
{
ArrayList arraylist1 = new ArrayList();
ArrayList arraylist2 = new ArrayList();
//Initialze with random values between 0-10
Random r = new Random();
for (int i = 0; i < 10; i++)
{
arraylist1.Add(r.Next(20));
arraylist2.Add(r.Next(20));
}
arraylist1.Sort();
arraylist2.Sort();
LinkedList<int> list1 = new LinkedList<int>();
LinkedList<int> list2 = new LinkedList<int>();
for (int i = 0; i < arraylist1.Count; i++)
{
list1.AddLast((int)arraylist1[i]);
}
for (int i = 0; i < arraylist1.Count; i++)
{
list2.AddLast((int)arraylist2[i]);
}
LinkedList<int> list3 = new LinkedList<int>();
LinkedListNode<int> x = list1.First;
LinkedListNode<int> y = list2.First;
while (x != null && y != null)
{
if(x.Value.Equals(y.Value)){
x = x.Next;
}
else if (x.Value.CompareTo(y.Value) > 0)
{
y = y.Next;
}
else
{
list3.AddLast(x.Value);
x = x.Next;
}
}
foreach (int m in list1){
Console.Write(m+" ");
}
Console.WriteLine();
foreach (int m in list2)
{
Console.Write(m + " ");
}
Console.WriteLine();
foreach (int m in list3)
{
Console.Write(m + " ");
}
Console.ReadKey();
}
}
}
If there is no problem in using additional data structure, I would use a treemap <<value, linkedlist of nodes>> . For some value ->key, node will be linked to the linked list. Since it is a treemap, values will be sorted. So after checking all values, and stroing them in the treemap, we can simply output the nodelist in order.
- musfiqur September 01, 2012We need a size-bounded minheap. Because everytime we encounter a newword, we have to evict the entry with the minimum count. If the number of entry (in this case 10) grows, then hashtable can be used. Otherwise, hashtable is of no use. Here is the code:
import java.util.ArrayList;
public class Mostfrequentwords {
/*There is a big file of words which is dynamically changing.
We are continuously adding some words into it.
How would you keep track of top 10 trending words at each moment ?
*/
private ArrayList<WordEntry> heap;
private int maxsize=10;
public Mostfrequentwords(){
heap=new ArrayList<WordEntry>();
}
public void setMaxSize(int maxsize){
this.maxsize=maxsize;
}
private int Heap_minimum(){
return heap.get(0).getCount();
}
private int Heap_extract_min(){
int min=heap.get(0).getCount();
heap.set(0, heap.get(heap.size()));
heap.remove(heap.size());
min_Heapify(0);
return min;
}
private void min_Heapify(int i) {
// TODO Auto-generated method stub
int l=2*i;
int r=2*i+1;
int smallest=i;
if(l<heap.size() && heap.get(l).getCount()<heap.get(i).getCount()){
smallest=l;
}
else{
smallest=i;
}
if(r<heap.size() && heap.get(r).getCount()<heap.get(i).getCount()){
smallest=r;
}
else{
smallest=i;
}
if(smallest!=i){
swap(i,smallest);
min_Heapify(smallest);
}
}
private void swap(int x,int y){
WordEntry temp=heap.get(x);
heap.set(x,heap.get(y));
heap.set(y,temp);
}
private int getWordIndex(String word){
for(int i=0;i<heap.size();i++){
if(heap.get(i).getWord().equals(word)){
return i;
}
}
return -1;
}
private void min_Heap_Insert(String newword){
//check if the word exist
int newWordIndex=getWordIndex(newword);
WordEntry wordentry;
//if does not exist create a new one
if(newWordIndex==-1){
wordentry=new WordEntry(newword);
if(heap.size()==maxsize){
//we have to find the maximum one and evict it
if(wordentry.getCount()>=heap.get(0).getCount()){
heap.set(0,wordentry);
}
else{
//do not do anything
}
}
//there is place for addition of word
else{
heap.add(wordentry);
}
int i=heap.size()-1;
while(i>0 && heap.get(i/2).getCount()>heap.get(i).getCount()){
swap(i/2,i);
i=i/2;
}
}
//else get the index of the word
else{
wordentry=heap.get(newWordIndex);
wordentry.increasecount();
min_Heapify(newWordIndex);
}
}
public void addWord(String word){
min_Heap_Insert(word);
}
public void outputHeap(){
System.out.println("Heap entries:");
for(int i=0;i<heap.size();i++){
System.out.println("Word:"+heap.get(i).getWord()+":Count="+heap.get(i).getCount());
}
}
private class WordEntry{
private int count;
private String word;
public WordEntry(String x){
word=x;
count=1;
}
public void increasecount(){
count++;
}
public String getWord(){
return word;
}
public int getCount(){
return count;
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
String []words={"Test1","Test2","Test3","Test4","Test1","Test2","Test5","Test6","Test5"};
Mostfrequentwords mostfrequentwords=new Mostfrequentwords();
mostfrequentwords.setMaxSize(3);
for(int i=0;i<words.length;i++){
mostfrequentwords.addWord(words[i]);
mostfrequentwords.outputHeap();
}
}
}
public boolean isRepeatedSubstring(String s){
int i,j,k,m;
for(i=1;i<s.length();i++){
int count=0;
for(j=0,k=i;j<s.length()-i;j++,k++){
if(s.charAt(k)==s.charAt(j)){
count++;
}
else{
count=0;
}
if(count>=2){
//check if the a substring of length=count from k exist
if (k-j==count)
return true;
}
}
}
return false;
}
Here is the a possible solution for this:
void Lineararrange(int X[]){
this.X=X;
int i=0,j=0;
int m=X.length-1,n;
while(i<X.length){
//Increase i as long as found negative
while(X[i]<0 && i<X.length)i++;
//Set j=i+1
j=i+1;//X[j] is either 0 or positive
//increase j as long as another negative is not found
while(j<X.length && X[j]>=0){j++;}
//if j=length finish
if(j>=X.length){
break;
}
//else swap with X[i],increase i
else{
int temp=X[i];
X[i]=X[j];
X[j]=temp;
}
}
//Now we have all negative to the left of i
while(m>0){
//Decrease m as long as found positive
while(X[m]>0 && m>0)m--;
//Set n=m-1
n=m-1;//X[n] is either 0 or negative
//decrease n as long as another positive is not found
while(n>=0 && X[n]<=0 ){n--;}
if(n<=0){
break;
}
//if n=0 finish
//else swap with X[m],decrease m
else{
int temp=X[m];
X[m]=X[n];
X[n]=temp;
}
}
//Now we have all positive to the right of m
output();
}
public void output(){
for(int i=0;i<X.length;i++){
System.out.print(X[i]+",");
}
}
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.StringTokenizer;
import java.util.TreeMap;
public class Anagram {
private String inputtext;
public Anagram(String inputtext) {
this.inputtext = inputtext;
}
public static String sortString(String s) {
char cs[] = s.toLowerCase().toCharArray();
Arrays.sort(cs);
return new String(cs);
}
public String getOutput() {
String output = "";
// Create a hashmap of <String, ArrayList<String>>
HashMap<String, ArrayList<String>> list = new HashMap<String, ArrayList<String>>();
// Sort each word of inputtext
StringTokenizer st = new StringTokenizer(inputtext, ",. ");
while (st.hasMoreTokens()) {
String word = st.nextToken();
// at the sorted result as key and store the word in the ArrayList
String sortedkey = sortString(word);
// System.out.println(word+"-"+sortedkey);
if (!list.containsKey(sortedkey)) {
ArrayList<String> listofAnagrams = new ArrayList<String>();
listofAnagrams.add(word);
list.put(sortedkey, listofAnagrams);
} else {
ArrayList<String> listofAnagrams = list.get(sortedkey);
if (!listofAnagrams.contains(word)) {
listofAnagrams.add(word);
}
}
}
// after the result is complete check the arralist length and if the
// output is more than 1 output them
for (ArrayList<String> anagrams : list.values()) {
if (anagrams.size() > 1) {
for (String s : anagrams) {
output += s + " ";
}
output += "\n";
}
}
return output;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Anagram anag = new Anagram(
"Parts of the world have sunlight for close to 24 hours during summer. Dan went to the north pole to lead an expedition during summer. He had a strap on his head to identify himself as the leader. Dan had to deal with the sun never going down for 42 consecutive days and his leadership strap soon became a blindfold. He wondered what kind of traps lay ahead of him.");
System.out.print(anag.getOutput());
}
}
How it is like merge sort? In merge sort , you merge two sorted arrays. How this is like merge sort?
- musfiqur February 17, 2013