gameboy1024
BAN USERTopological sort is essential for the second part sorting problem but I'm still thinking how to get the winner with only O(1) space.
If the data is a HashMap<Winner, Loser> then it's easy but if it's just a list of tuples: list(winner, loser) then I don't know how. Any idea?
Look at the assumption: "The following condition always hold"
- gameboy1024 February 02, 2015He didn't say the entries are top-level domains only.
- gameboy1024 January 20, 2015The problem is that to "look for collisions in each of the 100 hash tables" you need to either: use a distributed system and communicate between them or load/dump chunks to hard drive. In either case the cost of communication or disk r/w would be too great thus unimplementable.
- gameboy1024 January 20, 2015Hi,
Ok here's one optimization I found:
E.g. this can get rid of trying length 4 starting number for 10 in total, 5 for 24, 7 for 24, etc:
n digit number
m digit starting number
if n % m == 0
ok go on
else
number_of_occurrence = n / m
number_of_leftovers = n % m
if number_of_leftovers >= number_of_occurrence:
not ok
else
go on
But I thinks there are better solutions, also, I'm not sure if this is valid if we have the string long enough to hold consecutive numbers from n digits to n + 2 , +3, etc like 12345678910.....99100
- gameboy1024 January 19, 2015Hi,
Glad to hear the feedback.
I think you should ask your interviewer about the relation between the total length and the order of the number, otherwise starting from 1 to n or n down to 1 won't have any statistical influence on the complexity IMHO.
You do have a good idea to jump some numbers, but your solution, jumping non-factor and non-prime are incorrect. Imagine 999999 1000000 with length 13. The correct starting number would be of length 6 but you would have missed it. What we could do instead is for example stop at length/2.
Your understanding "aabcccdddd", in this context, should be a2b(1)c3d4
- gameboy1024 January 19, 2015A simple solution using recursion. The iteration version should be faster if you have time to develop, also using other languages than Python should be faster...
def verify(string, next_number, next_index, missing):
# If we are already at the end, we are done.
if next_index == len(string):
return missing
# If the next number is not what we expected
if string[next_index:next_index + len(str(next_number))] != str(next_number):
# If we already skipped some number, the input then is not valid.
if missing != None:
return None
# Else we try to skipped the number and try the next one.
return verify(string, next_number + 1, next_index, next_number)
# If it's a match we go on to the next one.
else:
return verify(string, next_number + 1, next_index + len(str(next_number)), missing)
string = "9989991001"
for l in xrange(1, int(len(string) / 2) + 1):
start = int(string[0:l])
missing = verify(string, start + 1, l, None)
if missing != None:
print missing
exit()
print "No missing number or more than one missing numbers"
Look at the question: Constrains: O(1) additional memory
- gameboy1024 January 18, 2015Hmm, seems to be a good application case for UnionFind.
en.m.wikipedia.org/wiki/Disjoint-set_data_structure
This sound like a simple web crawler.
I think the key point of question is
"We have one machine that has enough disk space but limited memory."
No matter what kind of data structure is used to store the data in memory, there must be a grabage-collector-alike job that periodically check for node/record that are stale(not written for a long time). So they can be dumped into file system to free the memory usage.
To avoid the duplication you could either check for existence when new node is created and load it if there is or create a mechanism to merge data when dumping into disk.
The solution should be extendable.
I would use Trie that stores everything, not only names.
The contact can be stored in a normal object. Some properties should be marked as "indexed" like name, phone number, company, and others "unindexed".
The Trie should then store more than just the name:
- First name
- Last name
- First + last
- Last + first
- Phone number
- Company
- Location
etc.
Leaves are pointers to the contact object. The Trie should be updated when contacts are added/modified/deleted.
Sorry this is not a good solution because it doesn't allow prefix search by phone number (entering 123 won't list 1234 and 1235).
- gameboy1024 August 21, 2014Complexity: One for loop means O(n) time complexity and no array needed means O(1) space complexity.
But,
Warning:
Try initiate a class where you only need static methods can give a very bad impression on your java proficiency.
I'm afraid it's not the conventional gray code.
The next five bit isn't a simple change of one bit but to get rid of the highest one and add a new one without duplicates.
Sorry, didn't pay attention.
Well, just do what the other said..
Do a reverse in O(n) time and O(1) space, then do what I posted.
Hopefully, still O(n) time and O(1) space
A no additional buffer solution:
Use two parsers, p1, p2;
int p1 = 0, p2 = 0
// this function parse through str from index p2 to find the index for next space
p2 = searchNextSpaceIndex(str, p2) - 1
while p2 != -1{
while p1 < p2 {
swap(str, p1++, p2--)
}
p1 = p2
p2 = searchNextSpaceIndex(str, p2) - 1
}
Complexity :
Time : O(n)
Space: O(1)
There are wiser solution to this:
Use recursive call as we can only add a 0 or 1 to the last four bits of the precedent number!
public static void main(String[] args) {
// I'm actually using more than i need (32 - 4 = 28) but 32 just to
// avoid the end case where we need to compare the last few bits and
// beginning bits
int[] result = new int[32];
// for simplicity, i just did the case that the first 5 bit = 00000,
// for all cases, just for (i = 0 to 0b11111), and do the recursive call
result[0] = 0;
// recursive call
// Warning: this actually print all numbers that meet the demand
// starting with 00000!
next(result, 1);
}
private static void next(int[] result, int index) {
// 31 = 11111 = 5 bits
// if we have arrived the last one and we form a circle
// i.e. the last 4 bit of result[31] == first 4 bit of result[0]
// then we found the number!
if (index == 32 && (result[31] & 0b1111) == (result[0] >> 1)) {
System.out.println("Number Found !");
int sum = 0;
// if it's even, then the last bit is 0, 1 otherwise
for (int i = 1; i < 28; i++) {
sum <<= 1;
sum += result[i] % 2;
}
System.out.println(sum);
System.out.println("00000" + Integer.toBinaryString(sum));
return;
}
// get the last 4 bits of the precedent number
int tmp = (result[index - 1] & 0b1111) << 1;
// see if we can add 0 or 1
boolean flag0 = true, flag1 = true;
for (int i = 0; i < index; i++) {
if (result[i] == tmp) {
flag0 = false;
}
if (result[i] == tmp + 1) {
flag1 = false;
}
}
// if we can add 0, just fill tmp, and do recursive call
if (flag0) {
result[index] = tmp;
next(result, index + 1);
}
// if we can add 1, just fill tmp + 1, and do recursive call
if (flag1) {
result[index] = tmp + 1;
next(result, index + 1);
}
}
Output is quite long:
For example the largest one starting with 5 bits 0:
Number Found !
131913257
00000111110111001101011000101001
@rahul
Yes, What I have as ReverseOrder is exactly the mirror version of inorder traversal. So the previousNode means:
1. In inorder traversal, every node left to previousNode is sorted! i.e. part of BST
2. In reversed inorder traversal, every node right to previousNode is not sorted so finding the min one actually means the next node to swap.
This is the key part why this would work. Well.. at least I suppose so.
@Diego Giagio
Let's see the input and output:
Input =
10,30,1
30,0,10
20,30,2
50,40,3
40,30,4
Output=
node 0: tree weight is 10
node 30: tree weight is 7
node 40: tree weight is 3
First, you didn't count in the X (the weight of a subtree for node X includes the own weight of X).
Second, node 30 has 3 children, the statement in the question is not exactly clear but I think node 30 should have a total weight of 20, not just the weight of its node40 branch.
I kinda have impression that this only works when we call leaf.getWeight first before their parent and won't work on branches either.
- gameboy1024 December 06, 2013Write code to overload the [] operator and you can literally rewrite the non-older-deletion version of vector in C++.
- gameboy1024 December 06, 2013
That's actually O(n^2), not O(n) time if you don't have a hashmap :)
- gameboy1024 February 03, 2015