CameronWills
BAN USER- 1of 1 vote
AnswersFrom the set of natural integer numbers
- CameronWills in United States
Let x = 1234 = {1, 2, 3, 4}
Let y = 2410 = {2, 4, 1, 0}
Write an algorithm to compute the rearrangement of x that is closest to y but still greater than y. Both x and y have the same number of digits.
So in the example above, the answer would be { 2, 4, 1, 3 } = 2413 which is greater than y = 2410 and closer than any other arrangements of x.
And whats the time complexity of this algorithm?| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm
Yes, it requires an bit array of size 2^32 = 512mb (assuming we're talking about 32 bit integers) . But this is a constant sized array regardless of the size of the input arrays A and B.
So this solution is O(1). a.k.a constant in space complexity.
As mentioned, this solution is only suitable for really large arrays A and B.
I agree, this probably the best/only O(1) space solution. This involves a very large (but constant) array of bits, where the bit value represents whether the corresponding number is present in array A. Then iterate through array B checking the corresponding positions in the bit array.
So assuming that we're using 32 bit integers, then the bit array has 2^32 bits = roughly 512 mb. This approach would achieve O(n) execution time and O(1) space. But this solution is only really valid when there is a very large number of elements in array A and B.
Aspect Oriented Programming.
#Winning
1. Load the items of the array A into a HashSet S. Each insert will take amortized O(1) time.
2. Iterate through the integers of array B and check if the HashSet contains the integer. Each lookup also takes O(1) time.
So the overall algorithm is O(n) time.
Its a variation on integer partition:
en.wikipedia.org/wiki/Partition_(number_theory)
And code to generate partitions here:
chinmaylokesh.wordpress.com/2011/01/26/partition-number-theory-ferrers-diagram/
Sounds like a game of Boggle.
1. Load the dictionary words into a Trie data structure.
2. Model the MxN matrix as a graph, each vertex representing a position in the matrix (a letter) and edges for the adjacent matrix positions. e.g. edges between (1,1) , (1,2), (2,2).
3. Starting from each vertex, traverse the graph with a depth first search, and check letters off in the Trie while traversing. Keeping track of 'visited' vertices to ensure the same letter isn't used multiple times. And prune paths where there is no matching letter / path in the Trie.
4. When a complete word in the Trie is found, output the word.
6,000,000 x 4 bytes = 22.8 Megabyte <- Not an issue for Memory?
- CameronWills November 08, 2012Assuming that File-1 and File-2 have no duplicates within themselves? And memory limitation is not a issue:
1. Iterate through File-2 adding each string to a HashMap and writing each string to File-3
2. Iterate through File-1, check if each string is present in the HashMap, if its not then write the string to File-3.
If memory is an issue, you could use a memory-mapped-file to store the HashMap strings.
A generic Hashtable / Hashmap in C#. Note that I'm using the out-of-the-box Object.GetHashCode() method to generate hashes. You could substitute a custom hash method if so desired..
Also this is not a thread safe implementation.
public class Hashtable<TKey, TValue>
{
private class Entry
{
public TKey Key;
public TValue Value;
public Entry Next;
public int Hashcode;
}
private const int MIN_CAPACITY = 16;
private Entry[] buckets;
private int count;
public Hashtable()
: this(MIN_CAPACITY)
{ }
public Hashtable(int capacity)
{
capacity = (capacity < MIN_CAPACITY) ? MIN_CAPACITY : capacity;
buckets = new Entry[capacity];
}
public void Add(TKey key, TValue value)
{
int hashcode = key.GetHashCode();
int targetBucket = (hashcode & int.MaxValue) % buckets.Length;
Entry ent = null;
// Search for existing key
for (ent = buckets[targetBucket]; ent != null; ent = ent.Next)
{
if (ent.Hashcode == hashcode && ent.Key.Equals(key))
{
// Key already exists
ent.Value = value;
return;
}
}
// Rehash if necessary
if (count + 1 > buckets.Length)
{
Expand();
targetBucket = (hashcode & int.MaxValue) % buckets.Length;
}
// Create new entry to house key-value pair
ent = new Entry()
{
Key = key,
Value = value,
Hashcode = hashcode
};
// And add to table
ent.Next = buckets[targetBucket];
buckets[targetBucket] = ent;
count++;
}
public TValue Get(TKey key)
{
Entry ent = Find(key);
if (ent != null)
return ent.Value;
return default(TValue);
}
public void Remove(TKey key)
{
int hashcode = key.GetHashCode();
int targetBucket = (hashcode & int.MaxValue) % buckets.Length;
Entry ent = buckets[targetBucket];
Entry last = ent;
if (ent == null)
return;
// Found entry at head of linked list
if (ent.Hashcode == hashcode && ent.Key.Equals(key))
{
buckets[targetBucket] = ent.Next;
count--;
}
else
{
while (ent != null)
{
if (ent.Hashcode == hashcode && ent.Key.Equals(key))
{
last.Next = ent.Next;
count--;
}
last = ent;
ent = last.Next;
}
}
}
private Entry Find(TKey key)
{
int hashcode = key.GetHashCode();
int targetBucket = (hashcode & int.MaxValue) % buckets.Length;
// Search for entry
for (Entry ent = buckets[targetBucket]; ent != null; ent = ent.Next)
{
if (ent.Hashcode == hashcode && ent.Key.Equals(key))
return ent;
}
return null;
}
private void Expand()
{
Rehash(buckets.Length * 2);
}
private void Rehash(int newCapacity)
{
// Resize bucket array and redistribute entries
int oldCapacity = buckets.Length;
int targetBucket;
Entry ent, nextEntry;
Entry[] newBuckets = new Entry[newCapacity];
for (int i = 0; i < oldCapacity; i++)
{
if (buckets[i] != null)
{
ent = buckets[i];
while (ent != null)
{
targetBucket = (ent.Hashcode & int.MaxValue) % newCapacity;
nextEntry = ent.Next;
ent.Next = newBuckets[targetBucket];
newBuckets[targetBucket] = ent;
ent = nextEntry;
}
}
}
buckets = newBuckets;
}
}
What does the contains function do? Depth first search?
Whats the time complexity of the contains function?
This is a recursive depth first search with backtracking.
Personally I do not believe this approach qualifies as Dynamic Programming (recursion is not dynamic programming).
This will not deliver the result in O(n) time...
On a side note, you could implement some pruning such that searches do not go any deeper than the length of the longest word in the dictionary.
I.e. Theres no point searching for dictionary words that are 20 characters long when the longest word in the dictionary is only 8 charactes long..
I was simply handling the example input provided. I'd be very surprised if someone can come up with an O(n) algorithm to handle all possible inputs / dictionaries. You would need to implement backtracing. Note that many interview questions are designed for the candidate to fail..
- CameronWills October 30, 2012Thats incorrect. It works fine for the example string provided "iamastudentfromwaterloo".
However this algorithm is greedy and would have problems if say "loo" was a dictionary word as well, and the desired sentence was supposed to be:
"i am a student from water loo"
this algorithm would still output:
"i am a student from waterloo"
public class TrieNode
{
private char key;
private Dictionary<char, TrieNode> children;
public TrieNode()
{ }
public TrieNode(char key)
{
this.key = key;
}
public TrieNode AddChild(char key)
{
TrieNode node = null;
if(children == null)
children = new Dictionary<char,TrieNode>();
if (children.ContainsKey(key))
return children[key];
else
{
node = new TrieNode(key);
children.Add(key, node);
}
return node;
}
public TrieNode GetChild(char key)
{
if (children != null && children.ContainsKey(key))
return children[key];
return null;
}
}
public class Trie
{
private TrieNode root = new TrieNode();
public void Add(string word)
{
TrieNode node = root;
for(int i = 0; i < word.Length; i++)
{
node = node.AddChild(word[i]);
}
}
public string AddSpaces(string sentence)
{
StringBuilder builder = new StringBuilder();
TrieNode node = root;
int i = 0;
while(i < sentence.Length)
{
char key = sentence[i];
node = node.GetChild(key);
if (node == null) // End of word, add space
{
builder.Append(" ");
node = root;
}
else
{
builder.Append(key);
i++;
}
}
return builder.ToString();
}
}
//-------------------------------------
static void Main(string[] args)
{
// dictionary of valid words
string[] dictionary = new string[] { "from", "waterloo", "hi", "am", "yes", "i", "a", "student" };
// add words to trie
Trie trie = new Trie();
for (int i = 0; i < dictionary.Length; i++)
{
trie.Add(dictionary[i]);
}
// get sentence with spaces
string withSpaces = trie.AddSpaces("iamastudentfromwaterloo");
Console.WriteLine(withSpaces); // outputs: i am a student from waterloo
Console.Read();
}
Tran, I'm talking about constructing a Trie (do a google search for 'Trie'), Trie is also know as a prefix tree. Its basically a tree that stores a single character at each node - while the root node is blank. Unlike binary-search-trees , tries have O(m) lookup time where m is the total number of characters in the word being searched for. Tries also have an O(m) insert time.
A path through a the Trie from the root node to a single leaf node, appending the character values along the path, would produce a word from the dictionary.
Simply use the 'merge' part of a merge sort.
- CameronWills December 07, 2012en.wikipedia.org/wiki/Merge_sort