CareerCup

What position is to be stored for repeated numbers?

In the example 13413124,

the positions of 1: 0, 3, 5
the positions of 3: 1, 4

...etc...

We need to store any repeated number only once? Or do we have to store each occurance separately along with the positions?

we could use array of structure. In this the index of the array will be the number and the structure will contain the list of all the numbers.

struct List
{
int position;
struct List *next;
};

struct List repeatedList[10];

Maintain a 2D array of integers: Initialize all elements to 0.The first column contains the element and the subsequent column contains the location. The location field is made up of bits. Thus, if we have a string like 111231..., do
a[0][0] = 1, a[0][1] = 0|position (0 or with position). Thus, a[0][1]=1. i.e. bits --> (0000000....1)

For the next 1 in the string, we do...
a[0][1] = 1 | position
a[0][1]=3 (bits->0000....11)

And so on...

Have an array of size 10 of lists

node* digits[10];

each time you find a digit just call

insert(digits[digit], position_of_digit);

package com.badal.HashTable;

import java.util.*;

public class HashTable2 {

public static void main(String [] args){
Hashtable<Character,ArrayList<Integer>>hashtable=new Hashtable<Character, ArrayList<Integer>>();

String test="1234512345";

for(int i=0;i<test.length();i++){
Character s=test.charAt(i);

if(hashtable.containsKey(s)){
// update the position
hashtable.get(s).add(i);
}else{
// create the key
ArrayList<Integer> positions=new ArrayList<Integer>();
positions.add(i);
hashtable.put(s, positions);

}

}

// print the hash table
for(Character key:hashtable.keySet()){
System.out.println(key+" = "+hashtable.get(key));

}

}

}

Hashtable, using linkedlist to handle conflicts

i hope its again a simple thing, if we know before hand what different numbers we have otherwise we just need to take vector or some kindda thing which help us keeping information dynamically.


//for simplicity it is assumed that numbers are from 1 to n and
//and are known which all numbers are there in the given array
Now what we can do

make an 'array' of size n, initialized to '0'
for each 'number'
read the 'number'.
given_array's[current index]<-array[number]
array[number]<-current index
end for

//hey we made a link list of each number with headers in the //array[], is it okay

Question is not clear because it was not mentioned - position counts from the right to left or left to right, and/or like 1st, 10th, 100th? I am not understanding.

Jackie's answer is kewl,
Hashtable = Number, linkedlist of position
so if we have 111
answer:
For first 1,
Hashtable.Add(1, 0) where 1 is number, and 0 is position
for second 1
Check 1 in hashtable
if found
Modify position, and add node to that
so it'll be Hashtable 1, 0->1
for third 1
it'll be Hashtable 1, 0->1->2

Instead of linked list, we can simply put string also
for first 1
hashtable 1, "0"
for second
hashtable 1, "0,1"
for third
hashtable 1, "o,1,2"

hope this helps

Thinking on line of bits... We just need to store the position so take an integer value for each digit and set the bits accordingly...

what to we need to achieve here? access speed or min space?

We need to use a linkedlist to store the positions of each number. And since we know that there are only ten numbers (1,2,3,4,5,6,7,8,9,0) we can use an array of size 10 instead of a hashtable. Hashtables are usually preferred when you do not the the number of key value pairs you would be storing. Each element in the array would be a linkedlist holding positions of the array index.

Count Sort