Ehsan
BAN USERI have a background in electrical engineering and telecommunications and very interested in computer science and programming puzzles.
A recursion works but when you are adding the next character, you have to check for the "constraints". In this case, making sure that the last two character of the sequence are either equal or at least one of them equal to the new character you are adding.
public class AllStrings {
public static void PrintAll(int length) {
char_arr = new char[length];
pos = 0;
PrintSeq();
}
private static void PrintSeq() {
if (pos == char_arr.length) {
for (int i = 0; i < char_arr.length; i++)
System.out.print(char_arr[i]);
System.out.println();
}
else {
if (IsValid('a')) {
char_arr[pos++] = 'a';
PrintSeq();
pos--;
}
if (IsValid('b')) {
char_arr[pos++] = 'b';
PrintSeq();
pos--;
}
if (IsValid('c')) {
char_arr[pos++] = 'c';
PrintSeq();
pos--;
}
}
}
private static boolean IsValid(char a) {
if (pos < 2)
return true;
else
return !((a != char_arr[pos - 1]) && (a != char_arr[pos - 2]) && (char_arr[pos - 1] != char_arr[pos - 2]));
}
private static char[] char_arr;
private static int pos = 0;
}
This looks like a typical language detection problem for a Turing Machine.
Code:
public class SubStringFinder {
public static int GetSubStrLog(String main_str, String sub_str) {
int pos_main = 0;
while (pos_main < main_str.length()) {
int pos_sub = 0;
while(sub_str.charAt(pos_sub++) == main_str.charAt(pos_main++))
if (pos_sub == sub_str.length())
return pos_main - sub_str.length();
pos_main -= (pos_sub - 1);
}
return -1;
}
}
Sample:
public static void main(String[] args) {
// TODO code application logic here
String main_str = "This is thethethe maithe mai the main string.";
String sub_str = "the main";
int pos = SubStringFinder.GetSubStrLog(main_str, sub_str);
if (pos > -1)
System.out.println("Found the sub-string at position " + Integer.toString(pos) + ".");
else
System.out.println("Not found.");
}
Output:
Take "n" as the limit for "Rs. 300".
u1 = number of calls by person 1 = n + k1.
u2 = number of calls by person 2 = n + k2.
R = Rate in Rs/call
p1 = price paid by person 1 = 425 = 300 + k1 * R => k1R = 125
p2 = price paid by person 2 = 925 = 300 + k2 * R => k2R = 625
Result1: k2 = 5 k1 and 6k1 * R = 750
Total calls = 1400 ==> n + k1 + n + k2 = 2n + 6k1 = 1400
Result2: n + 3k1 = 700
u = calls by one person = 2n + 6k1 = 1400
p = price by one person = 300 + (n + 6k1) * R = 1550 ==> n * R = 1550 - 750 - 300 = 500
Result3: n * R = 500
Result1 & Result 3 => Result 4: k1 / n = 125 / 500
Result2 & Result4 => (1 + 125 / 500 * 3) * n = 700 ==> n = 500
You need a stack too keep track of the order of brackets.
public class CheckBracketConsistency {
public static boolean Validate(CharStream cs) {
Stack<Character> stack = new Stack<Character>();
Integer position = 0;
Character expected = 0;
while (cs.hasNext()) {
switch (cs.next()) {
case '(':
stack.push(')');
break;
case ')':
expected = stack.pop();
if (expected.compareTo(')') != 0) {
System.out.print("Expected " + expected.toString() + " at index " + position.toString() + ".");
return false;
}
break;
case '[':
stack.push(']');
break;
case ']':
expected = stack.pop();
if (expected.compareTo(']') != 0) {
System.out.print("Expected " + expected.toString() + " at index " + position.toString() + ".");
return false;
}
break;
default:
// Unknown character
return false;
}
position++;
}
return stack.empty();
}
}
Sample running code:
public class CareerCup {
/**
* @param args the command line arguments
*/
public static void main(String[] args) {
// TODO code application logic here
CharSequence[] cs = new CharSequence[3];
cs[0] = new CharSequence("(([]([]))");
cs[1] = new CharSequence("([)]");
cs[2] = new CharSequence("()(([]))([()])");
for (int i = 0; i < 3; i++) {
System.out.print("Checking sequence " + Integer.toString(i) + "...\n");
if (! CheckBracketConsistency.Validate(cs[i]))
System.out.println("The input sequence is invalid. Might have left some paranthesis open.");
else
System.out.println("The input sequence is valid.");
}
}
}
Output:
Checking sequence 0...
The input sequence is invalid. Might have left some paranthesis open.
Checking sequence 1...
Expected ] at index 2.The input sequence is invalid. Might have left some paranthesis open.
Checking sequence 2...
The input sequence is valid.
BUILD SUCCESSFUL (total time: 0 seconds)
Make your class/object implement the Comparable interface. See documentation.
Ex.
public class Object1 implements Comparable{
@Override
public int compareTo(Object o) {
if (o.getClass().getName().compareTo("something1") == 0) {
// do something
return 0; // or whatever
}
else if (o.getClass().getName().compareTo("something2") == 0) {
return 0; // or whatever
}
return -1;
}
// Or override again
public int comapreTo(Object3 o) {
return 0;
}
}
This question sounds very vague to me.
What do you mean by convex hull? As far as I know, "convex hull" is more of an operator rather than an object, i.e., convex hull of a set is the smallest convex set covering the set.
Intersection of two convex sets is also convex. So if you know an algorithm which gives you the points inside a convex set, just apply it to the intersection.
From a computational point of view, lets approximate the convex set using a convex polyhedron, i.e, assume the set is defined as
S = {x | A x <= b} for some A and b.
Now for two different sets you get two different A and b. Say A1 and A2 and b1 and b2.
Then
S1 \cap S2 = {x | A1 x \le b1 and A2x <= b2} = {x | [A1; A2] [x; x] <= [b1; b2]}
= {x | [A1; A2] [I, 0; I; 0] x \le [b1 b2]}
which is another polyhedron with A = [A1; A2] \times [I, 0; I, 0] and b = [b1; b2].
BTW, unless your polyhedron is trivial, there are infinite points in it.
I took a similar approach by using a Map and Linked List. In the map, I store a pointer to the linked list object corresponding to the URL. If the same page is visited twice, the address is used to find the object in the list, remove it, and re-insert it at the head.
Also, you can always obtain the last "N" pages by traversing through the list from the head down.
Here is the C++ code:
#pragma once
#include <string>
#include <map>
#define nullptr 0
using namespace std;
class URLHistory
{
public:
URLHistory(void) {
url_list_head = nullptr;
};
~URLHistory(void) {
//delete the list (not implemented)
};
void Insert(string url) {
if (url_map[url] == 0) {
// This is a new URL
URLList* ulist = AddToList(url);
url_map[url] = ulist;
}
else {
// We had already visited this page. Just bring it to the front
URLList* ulist = url_map[url];
if (ulist == url_list_head)
return;
ulist->prev->next = ulist->next;
if (ulist->next)
ulist->next->prev = ulist->prev;
delete ulist;
ulist = AddToList(url);
url_map[url] = ulist;
}
};
// Returns the top N (most recent)
string* TopN(int N) {
string* top_N = new string[N];
URLList* plist = url_list_head;
unsigned int pos = 0;
while(plist != nullptr) {
top_N[pos++] = plist->url;
plist = plist->next;
};
return top_N;
};
public:
class URLList {
public:
URLList(string url_, URLList* prev_, URLList* next_) {
url = url_;
next = next_;
prev = prev_;
};
string url;
URLList* next;
URLList* prev;
};
private:
URLList* AddToList(string url) {
URLList* ulist = new URLList(url, nullptr, url_list_head);
if (url_list_head)
url_list_head->prev = ulist;
url_list_head = ulist;
return url_list_head;
}
private:
URLList* url_list_head;
map<string, URLList*> url_map;
};
And a sample usage:
string visited_url[10] = {"A", "B", "C", "D", "E", "A", "B", "A", "X", "A"};
URLHistory history;
for (int k = 0; k < 10; k++) {
history.Insert(visited_url[k]);
string* top_6 = history.TopN(6);
for (int j = 0; j < 6; j++)
cout << top_6[j] << "|";
cout << endl;
}
Output:
A||||||
B|A|||||
C|B|A||||
D|C|B|A|||
E|D|C|B|A||
A|E|D|C|B||
B|A|E|D|C||
A|B|E|D|C||
X|A|B|E|D|C|
A|X|B|E|D|C|
I guess, and not sure yet, that the following algorithm works.
int[] path = GetPath(); // From (0,0) to (N - 1, N - 1)
boolean good_path = PathCrossesGreyNode(path);
while (good_path == false) {
AddCostToPath(path); // for any edge on this path, increase the edge cost by a constant
path = GetPath();
good_path = PathCrossesGreyNode(path);
}
As mentioned earlier, the complexity is exponential. The reason is that the implementation is memory less, so you keep evaluating the same terms over and over.
Let's assume cost of calculation for comparison and addition is "1" unit.
Then if T(n) is the computation cost, we have
T(n) = T(n - 1) + T(n - 2) + 2 = 2 T(n - 2) + T(n - 3) + 4 > 2 * T(n - 2) > 4 * T(n - 4) > 8 T(n - 6) > ... > 2^k T(n - 2 * k) = theta(2^{n / 2}).
For "n = 1000000000" and "r = 2" you get
r = 0 => answer = 1000000000 (no over flow)
r = 1 = > answer = -743309312 which is an overflow but undetected.
Overall this is a very good approach since you are doing one product and one division in each iteration and naturally, it covers almost all supported pairs of values.
In O(k) space and O(k^2) time (k^2 = O(n * min(k, n - k)).
Assume k < n /.2, i.e., min(k, n - k) == k is true
The goal is to do the integer division first to make sure we can have the largest possible numbers without throwing an overflow.
public int nChoosek(int n, k) {
// Do division first
// We are evaluating N * (N - 1) * ... * (N - k + 1) / (k * (k - 1) * .... * 1).
// Numerator values (N, N - 1, ...)
int[] C = new int[k];
for (int i = 0; i < k; i++)
C[i] = N - i;
for (int i = 0; i < k; i++) {
// i + 1 is a denumerator value, i.e., i + 1 = 1, 2, ..., k
for (int j = 0; j < k; j++) {
// Find an element from numerator which divides (i + 1)
if (C[j] % (i + 1) == 0) {
C[j] = C[j] / (i + 1);
break;
}
}
}
// Now do product
int result = 1;
for (int i = 0; i < k; i++) {
if (i < (k - 1)) {
if (result > (1000000 / C[i + 1]))
return -1; // This would be an overflow anyway
}
result *= C[i];
}
return result;
}
Step 1:
Scan the array from index 0 -> (N - 1) and keep track of the maximum value seen up to each index. Let's call it (max_value_seen) and it is initialized to the smallest value. At index i, if A[i] >= max_value_seen, then do two things:
1- max_value_seen = A[i]
2- potential_q[i] = true.
Where "potential_q" is an array of length N of booleans initialized to all false. When you say potential_q[i] = true, it means that index "i" is a potential candidate for "q" since it satisfies the first constaint, i.e., for all k < i, A[i] >= A[k].
Step 2:
Scan the array in reverse order and do the opposite, i.e., keep track of min value. Let say the min value is stored in "min_value_seen". At index j, do the following
if (A[i] <= min_value_seen) {
min_value_seen = A[i];
if (potential_q[i] == true)
return i;
}
If A[i] < min_value_seen, then for any j > i, A[j] \ge A[i]. Then if A[i] is a potential Q from previous section, we know that A[i] \ge A[k] for all k < i. As a result, Q = i is a solution.
Full code:
public class FindSubIndex {
public FindSubIndex(int[] A) {
this.A = A;
}
public int GetQ() {
boolean[] pot_q = new boolean[A.length];
pot_q[0] = true;
int max_value_seen = min_val;
for (int i = 0; i < A.length; i++) {
if (A[i] > max_value_seen) {
pot_q[i] = true;
max_value_seen = A[i];
}
}
// if for some i, pot_q[i] = false, then Q cannot be i.
int min_value_seen = max_val;
if (pot_q[pot_q.length - 1])
return A.length - 1;
for (int i = 0; i < A.length; i++) {
int rev_index = A.length - i - 1;
if (A[rev_index] < min_value_seen) {
min_value_seen = A[rev_index];
if (pot_q[rev_index])
return rev_index;
}
}
return -1;
}
private int[] A;
private int min_val = -(int) Math.pow(2, 32);
private int max_val = (int) Math.pow(2, 32);
}
class Program {
public static void Main(String arg[]) {
int[] A = new int[]{....}.
int Q = (new FindSubIndex(A)).GetQ();
System.out.print(Q);
}
I will first introduce my method, then give you java code.
Method:
Time Complexity for "MxN" matrix: O(min(M, N)^2 max(M, N))
Algorithm (take M < N):
We will read rows 1-by-1. We have a register which is an array of integers of length "N". Call it sum_zero.
When reading row "r" of matrix update "sum_zero" as:
if (matrix[r][c] == 0)
sum_zero[c]++;
else
sum_zero[c] = 0;
,i.e., I am finding the number of consecutive zeros in column "c" up to row "r".
The rest of the method is described in an example.
Assume we have "5" columns and have read 3 rows. First of all, sum_zero[c] < 4 for all c.
Assume we have
sum_zero = {0, 1, 2, 1, 0}
.
This means the part of matrix we have read so far has been like
{1, ,0 ,0 ,0, 1}
{X, ,1 ,0 ,1 ,X}
{X, ,X, ,1, ,X, ,X}
Note that value of "X" does not matter. So in this case, we have a rectangle of size "1x3" and one of size "2x1". To find the rectangle, all we need is the array sum_zero.
To Do:
Go through array sum zero and look for a continuous run of values larger than "k". Let's say we found L[k] as the largest run. Then, we have a rectangle with dimensions "(k + 1) x L[k]".
When reading row "k", the maximum value of sum_zero[c] is k + 1. So we need to check "k" numbers. This is done in O(k x N).
Since we are repeating the sequence for "k = 1, 2, ..., M", the overall time complexity is
O(N x M^2) and if we are smart, we choose M < N.
This is actually a cubic time for square matrices, which might not be good. But for sure the optimal time complexity is \theta(N^2) so this is not really that bad.
Java Code: (I would like to thank "Mike" for preparing the array (input). I copied it from his code above)
// Class MaxRectangle.java
package careercup;
public class MaxRectangle {
public MaxRectangle(int[][] A) {
matrix = A;
nrows = A.length;
ncolumns = A[0].length;
}
public int GetMaxRectArea() {
int max_area = 0;
int[] sum_zero = new int[ncolumns];
for (int c = 0; c < ncolumns; c++)
sum_zero[c] = 0;
for (int r = 0; r < nrows; r++) {
for (int c = 0; c < ncolumns; c++)
if (matrix[r][c] == 0)
sum_zero[c]++;
else
sum_zero[c] = 0;
// decide
int new_max_area = GetMaxArea(sum_zero, r);
if (new_max_area > max_area)
max_area = new_max_area;
}
return max_area;
}
private int GetMaxArea(int[] sum_zero, int r) {
// Look for longest run of value "k + 1"
int area_to_report = 0;
for (int k = 0; k < r; k++) {
int longest_run = 0;
int this_run = 0;
boolean saw_same = false;
for (int c = 0; c < ncolumns; c++) {
if (saw_same){
// we have been counting a run
if (sum_zero[c] > k)
this_run++;
else {
// end of this run
saw_same = false;
if (this_run > longest_run)
longest_run = this_run;
}
}
else {
// check if a new run is starting
if (sum_zero[c] > k) {
this_run = 1;
saw_same = true;
}
}
}
int new_area = longest_run * (k + 1);
if (new_area > area_to_report)
area_to_report = new_area;
}
return area_to_report;
}
int[][] matrix;
int nrows, ncolumns;
}
// class Program.java
// Nothing special. Just initiating the input and calling the algorithm. Big "thank-you" to Mike for writing the input in a nice reusable format. :)
public class Program {
public static void main(String[] args) {
int[][] input = GetMatrix();
MaxRectangle max_rect = new MaxRectangle(input);
int max_area = max_rect.GetMaxRectArea();
System.out.println("Maximum area in a rectangle of zeros is " + Integer.toString(max_area));
}
private static int[][] GetMatrix() {
int input[][] = { { 0,0,0,1,1,1,1,1,1,0,0,0,1,1 },
{ 1,1,1,0,0,0,1,0,1,1,1,1,1,0 },
{ 1,1,0,0,0,1,1,1,1,1,1,1,0,0 },
{ 0,0,1,1,1,1,0,0,0,0,1,1,1,1 },
{ 0,0,1,1,0,0,0,0,1,1,0,0,0,0 },
{ 1,1,0,0,0,1,0,0,0,0,0,1,1,0 } };
return input;
}
}
It depends on OS. For 64-bit systems it is technically possible, on some machines/OS, to have a very large heap memory until your program thrashes, i.e., start paging since you have exceeded the RAM limit.
So theoretically I would say as large as you wish, but no point going (much) above RAM since everything will get slow.
Input: Matrix "A" (given above)
Idea: You can look at your matrix as a graph where each element on the matrix "A" is a vertex.
There might be an edge between vertex A[i][j] and A[i + 1][j] (bottom) or A[i][j] and A[i][j + 1] (right).
For instance, the following function determines if there is an edge from (r, c) to (r, c + 1) (RIGHT):
// the following lines are in the header file "snake_length.h"
int HasRightPath(int r, int c)
{
if (!((c + 1) < max_n_col))
return 0;
return ((matrix[r][c + 1] - matrix[r][c]) *
(matrix[r][c + 1] - matrix[r][c])) < 2;
}
.
Let's define a BinaryTree structure to represent a vertex (for convenience, not optimal space wise)
int matrix[3][5] = {{1, 3, 2, 6, 8}, {-9, 7, 1, -1, 2}, {1, 5, 0, 1, 9}};
int max_n_row = 3;
int max_n_col = 5;
int max_rank = 0;
typedef struct BinaryTree {
BinaryTree* right; // Point to the vertex on the right
BinaryTree* bottom;
int row; // row index of this vertex (not necessary, just for readable code)
int column; // similar to above for column
int rank; /* Rank: distance from this vertex to the end of the longest
path originating (or similarly, involving) this vertex.
*/
int matrix_value; // Value of the matrix at this vertex (not neceassry again since we already have the matrix)
} BinaryTree;
BinaryTree bt_matrix[3][5]; // Graph vertices
First, we need to initialize the graph, e.g., every vertex should be connected to its right and bottom neighbors (if any)
int InitTree()
{
// Connecting the vertices
int r, c;
for (r = 0; r < max_n_row; r++)
{
for (c = 0; c < max_n_col; c++)
{
BinaryTree dummy = {0, 0, r, c, 0, matrix[r][c]};
memcpy(&bt_matrix[r][c], &dummy, sizeof(BinaryTree)); // Initialize this vertex
if (HasRightPath(r, c))
bt_matrix[r][c].right = &bt_matrix[r][c + 1]; // Connect to right vertex
if (HasBottomPath(r, c))
bt_matrix[r][c].bottom = &bt_matrix[r + 1][c]; // Connect to bottom vertex
}
}
return 0;
}
Next, we need to find the rank of each vertex:
IDEA: Rank(A[i][j]) = max(Rank(A[i][j].right, A[i][j].bottom)) + 1.
int Rank(struct BinaryTree* bt)
{
if (bt == 0)
return 0;
if (bt->rank == 0)
{
int rank_right = Rank(bt->right);
int rank_bottom = Rank(bt->bottom);
bt->rank = (rank_right > rank_bottom) ? rank_right : rank_bottom;
bt->rank += 1; // To count the vertex itself
};
return bt->rank;
}
Find the rank for all the vertices in O(nm) time. Store the maximum which will be the length of longest snake (length of a snake = number of vertices involved ==> always positive).
int FindRanks()
{
int r, c;
for (r = 0;r < max_n_row; r++)
for (c = 0;c < max_n_col; c++)
{
int rank = Rank(&bt_matrix[r][c]);
if (max_rank < rank)
max_rank = rank;
};
return max_rank;
}
At this stage, we are done unless you want to find paths of certain rank, e.g., max rank. Since we have already loaded a lot of info in our BinaryTree structure, we can easily do this recursively.
int Print(int rank)
{
int count = 0;
int r, c;
for (r = 0; r < max_n_row; r++)
{
for (c = 0;c < max_n_col; c++)
{
if (bt_matrix[r][c].rank == rank)
{
int path[100];
PrintSubTree(&bt_matrix[r][c], path, 0);
count++;
};
}
}
return count;
};
void PrintSubTree(BinaryTree* bt, int* path, int pos)
{
path[pos] = bt->matrix_value;
if ((bt->right == 0) && (bt->bottom == 0))
{
// End of a route (snake)
int i = 0;
printf("Path of length %d: ", pos + 1);
for (i = 0; i <= pos; i++)
printf("%d ", path[i]);
printf("\n");
return;
};
if ((bt->right != 0) && (bt->bottom != 0))
{
// Route branching in two directions.
if (bt->right->rank >= bt->bottom->rank)
PrintSubTree(bt->right, path, pos + 1);
if (bt->bottom->rank == bt->right->rank)
PrintSubTree(bt->bottom, path, pos + 1);
}
else if (bt->right != 0)
PrintSubTree(bt->right, path, pos + 1);
else
PrintSubTree(bt->bottom, path, pos + 1);
}
Sample code:
#include <stdio.h>
#include "snake_length.h"
int main()
{
InitTree();
printf("Max length for a snake = %d\n", FindRanks());
Print(max_rank);
getc(stdin);
return 0;
}
Output:
Max length for a snake = 5
Path of length 5: 3 2 1 0 1
A few notes:
1- This is obviously not a good way to "print" a path since two different path might look the same
2- You can use function "Print(int)" for other path lengths
Your question is too general to be interpreted "correctly".
Every third element of an <<array>> means indices "3k" for k > -1.
The example you gave me is a linked list with sentinel (ring).
However, the nature of the problem is the same. I don't think you can do it in O(1). But I don't have a proof.
First assume the "Partitioning" problem:
Assume "A" is unsorted and choose its p-th location as the "pivot". Assume A[p] = a and "a" is the i-th smallest element of A. Then, a partitioning over "p" yields a reordering of A such that "a" is located at the i-th location, and any element located at j < i is smaller than "i" (an consequently, the ones at j > i are larger).
This is done in O(n) where n is the length of A.
Quick sort is nothing but a series of recursive calls to partitioning
QuickSort(A, p)
{
i = Partition(A, p);
QuickSort(A[1..i - 1], p1);
QuickSort(A[i + 1....n], p2);
};
The important question is how to choose "p". The answer is "randomly and uniformly". The average performance of QuickSort for uniformly chosen "p" is optimal, e.g., O(n.log(n)) time.
Worst-case however, is O(n^2) which occurs with O(1 / n!) chance when "p" is selected uniformly in each recursive call.
For me, the question is not quite clear, but this is "an" answer to it (what exactly is "whatever that happens to...")
class A {
void ReceiveMessage(Message m)
{
/* Do Something with it! */
};
};
class B {
A* a_instance; // An instance of A
// Link to an instance of A
B(A* x) {
a_instance = x;
};
/* DO SOMETHING */
void DoSomething()
{
// something
Message m;
// m <- whatever you want to tell A.
UpdateA(m);
};
void UpdateA(Message m) {
a_instance->ReceiveMessage(m);
};
};
A a;
B b(&a);
B.DoSomthing();
Hash (functions) is a transform from a "Key"-space to the subset of natural numbers {0, 1, ..., N - 1} where "N" is the size of the underlying array. Hashtables deploy hashing to provide O(1) insertion and look-ups in the data structure.
Assume a set of keys "K" and an underlying array "A" with size "N". Name the table "T". Then in calling "T[k]", the program does:
1- Uses the hash function on key F(k)--->n.
2- Looks in "A[n]" and returns the corresponding value with key "k".
If evaluating "F(k)" is O(1), then you have got yourself a DS with O(1) look-up/insertion.
Problem is that things are not quite easy. For any hash function you use, there are many streams of input data which cripple the performance (E.g., assume your key is an unsigned int and the hash function is simply F(k) = k mod N. For k = 1, N + 1, .... you end up at the second location of array.)
To resolve the collisions in hash function you could do the following two:
1- Implement another DS at each array location, e.g., Linked Lists.
2- When the array is almost full (> 50%), double up it size.
For both scenarios there is O(N) time complexity, but I prefer the latter since it is a one time thing and maybe less dependent on how well you have tuned your hashing function to the type of input.
As for the second question why ArrayList is not used, I am not certain but I am not sure even if LinkedLists are common anymore. The first idea is that LL are easy to implement and lower cost and you don't need dedicated memory, e.g., you allocate on-the-go. However, for an AL, there is a fixed-length underlying array which adds to the cost, e.g., your hash table would need exactly "NM" memory where "M" is the size of AL. This is a waste for some bins with lower number of keys.
Also, read the following post on why LL are not common in .NET (Stackoverflow - could not put the link)
"what-data-structure-is-used-to-implement-the-arraylist"
O(2^n) is pretty simple. I think this problem is "NP-complete".
Model:
Solve the following integer equations over binary variables:
a_1 x_1 + a_2 x_2 + ... + a_n x_n = S (S = half the sum)
x_1 + x_2 + ... + x_n = n / 2 (n = even)
Code in C++:
bool get_weighted_half(int* a, int* x, int pos, int sum_left, int choice_left)
{
// Picked too much
if (sum_left < 0)
return false;
// Picked enough!
if (choice_left == 0)
{
// Picked too little
if (sum_left > 0)
return false;
else
// Picked right size, right amount!
return true;
}
if (pos == -1)
// Nothing left!
return false;
// Not done yet...
x[pos] = 1;
if (get_weighted_half(a, x, pos - 1, sum_left - a[pos], choice_left - 1))
return true;
// x[pos] = 1 does not work
x[pos] = 0;
return (get_weighted_half(a, x, pos - 1, sum_left, choice_left));
}
For an input array
int a[8] = {1, 2, 3, 4, 5, 6, 7, 8};
int x[8] = {0};
int pos = 7, sum_left = 18, choice_left = 4;
get_weighted_half(a, x, pos, sum_left, choice_left);
the output will be
1, 2, 7, 8
Which is a solution, and not unique.
- Ehsan August 30, 20133) This is a crude implementation:
Company* top_companies[10]; \\ Pointer to members of Set 1 (I included the 10th company in Set(1)). This is going to be a sorted array where comparison is based on Company.load.
Company* all_companies = new Company[N]; // Set of all companies = Set(1) U Set(2)
Company* MaxInSet2; // Pointer to company with max load in the low-(N-10) companies.
void OnCompanyLoadReceived(Event e)
{
Company* c = e.PtrToCompany; // Find the company whose load is changed
c->load += e.load; // Update load
// If the company load has become large enough to join the top 10
if (c->load > top_companies[9]->load)
{
c = InsertNewCompany(c);
// "c" is inserted in top_10 and the company which is kicked out is returned. If "c" WAS already in top 10, nullptr is returned
};
if (c != nullptr)
{
// the initial company, or some other company does not belong to top 10
if (c->load > MaxInSet2->load)
{
MaxInSet2 = c;
};
}
}
As I look again, the pointer to maximum is not necessary. All we care is the top 10. When a company changes in load, we just need to compare it with top 10.
As you said, it scales badly with number of top companies. Maybe for large enough such number, a balanced binary tree is a solution.
2) You are right. At first I was thinking of sorted array implementation and I did not notice you solution.
1) What I meant was something like this:
order = {1, 2, 3, 4, 5};
load = {0, 0, 0, 0, 0};
if load for some company changes, e.g., company "3", then
order = [1, 2, 3, 4, 5];
load = [0, 0, 10, 0, 0];
After sort we swap load[2] and load[0]. Do the same for order.
load = [10, 0, 0, 0, 0];
order = [3, 1, 2, 4, 5];
Now order[0] refers to the company with maximum load.
However, this is useless since we could define an array of Company objects already including all the information.
1) Searching is O(1). You can assume you keep a separate array to keep the company index and apply any modification on the trade load array on the index array as well. Then the i-th position of the trade-load is the i-th largest, and the i-th position of the index array, is the company index.
2) True. But each new modification (if arbitrary) requires O(log(n)) comparisons to determine the position.
3) <<<On a separate note>>> I guess we don't even need to have a heap for this application. Divide the companies into two sets: Set(1) = {top 9}, Set(2)={Other companies}. Keep a pointer to the company in Set(2) with maximum trade load at this time.
Event: A company "X" changes in trade load:
Let:
Y = max{Set(2)}, Z = arg min{Set(1)}
A) X is in Set(2):
A-1) X < Y ==> Do nothing.
A-2) (X > Y) & (X < Z) ==> max{S(2)} = X.
A-3) X > Z ==> Add X to array of top 10. Drop Z from the array. Let max{Set(2)} = Z.
B)
The X = Y (also in Set(2))
B-1) Y > Z ==> Set max{S(2)} = &Z. Add to position of Z. Reorder top 9.
B-2) Y < Z ==> Do nothing.
C)
X is in Set(1)
C-1) A simple reorder under 9 swaps. No change to Set(2).
Then, the time complexity of each modification would be O(1).
This approach works if trade load change at each instance is a non-negative number.
You are right. Search and max-10 are O(1) since it is sorted. But the sorting after modifying one company is O(n) which is not good.
But a combination of sorted array and heap might help. If we assume "N = the number of companies" and N >> 10, then you could imagine a sorted array of length 9 and a heap of length N - 9 with "extract-max".
Now if the load for a company changes, if it already belongs to the top 9, then it is at most "9" swaps to re-sort. If it belongs to 10'th company, then we compare the max of heap with the min of array. Then if necessary, in one swap, we could change the "max" of heap with min of array and in at most 9 swaps re-order array. If the company is already in the heap, then it is O(log(N - 9)). So the time complexity is max(10, c log(N)) swaps.
Another approach by using maps. Assume we keep track of cumulative sum of array. If there is a subsequence starting from index n1 to n2 summing to zero, then the cumulative sum is equal at n1 and n2. Just need to remember the locations.
map<int, vector<int>> locs;
int cs = 0;
locs[0]=0;
for (int i = 0; i < N; i++)
{
cs += arr[i];
locs[cs].push_back(i);
}
/// now go over map to identify subsequence
for (auto it = locs.begin(); it != locs.end(); ++it)
{
List_sequences(it->second);
}
list_sequences
simply prints sub sequences based on starting indices. For instances, the cumulative sum meets value "2" at indices 4, 8, 120, the there are three sub sequences: 4-8, 8-120, 4-120.
Time : O(N + M)
Space: O(N)
M = Total number of subsequences
A recursive implementation.
Idea: Pick one element of the set. If it is larger than given "sum" value, drop it. Otherwise, recursively proceed with two cases:
1- Picking this number-> call the function for the set minus this number and "sum - number"
2- No picking this number -> call the function for the set minus this number and "sum"
You could expedite the process by bounding (I didn't). E.g., when calling the function, make sure the smallest number in the remaining numbers is smaller than "sum",e.g.,
{6, 7, 8, 11, 12} , sum = 10 ==> No solution! no need to check all possibilities.
It can be expedited by utilizing some bounding function, e.g., at each call look for the smallest remaining value and if it is larger than
#include <vector>
using namespace std;
vector<vector<int>> all_solutions;
vector<int> current_solution;
void find_k_sum(vector<int>& numbers, int sum2)
{
// If there is no numbers in the list, and sum2 == 0, save current solution
if (numbers.size() == 0)
{
if (sum2 == 0)
all_solutions.push_back(current_solution);
return;
}
// If there is a solution including the last element of the vectors
int newnumber = numbers[(numbers.size() - 1)];
numbers.pop_back();
if (sum2 >= newnumber)
{
current_solution.push_back(newnumber);
find_k_sum(numbers, sum2 - newnumber);
current_solution.pop_back();
};
// Now consider the case the new number is not picked
find_k_sum(numbers, sum2);
numbers.push_back(newnumber);
}
I was wondering if O(n) algorithm is possible.
Assume the input is a sequence of length "n" with numbers chosen from the set {1,2,3,...,n}.
Let's assume there is an algorithm which goes through f(n) elements of the array and has "S" states. From state Si, we observe the input and based on its value we can go to another state Sj. After "f(n)" observations, we have tried at S^f(n) routes. If at some point we conclude that the remaining sequence is acceptable, then the algorithm terminates.
There is a total of n^n sequences. We must be able to differentiate between any two sequence so S^f(n) >= n^n. if f(n) = O(n), then S = Omega(n) and therefore, log2(S) = Omega(log(n)). If S = O(1), then f(n) = Omega(n log(n)).
I am not sure if my argument is correct, but my conclusion is that we either need O(log(n)) memory, or O(nlog(n)) iterations.
Nice solution. Your answer is almost correct. It is not trivial to find the exact value of expectation esp. for the case with replacement.
There is a minor flaw (in my opinion) in your argument. Mathematically speaking, the problem involves choosing a random number "m" and then finding the number of picks which follows until we obtain a number less than "m", e.g., "k" picks. For each "m", we have a specific distribution for "k". Then, the answer would be to calculate E[k|m] for fixed "m" with respect to "k", and then find the expected value of the result with respect to "m".
You are instead finding E[k|E[m]] which is different from E[E[k|m]].
Another perspective is that the function you have above is nonlinear in "K" that is another reason why you shouldn't put K / 2 and solve the problem.
Assume f(n) returns the index. Here is the O(log(n)) algorithm. I would like to go ahead and blindly claim that O(1) does not exist. :)
int f(int n)
{
int k_new = 1, k_old = 1;
while(k_new <= n)
{
k_new = round(k_old * 1.5)
k_old = k_new;
}
return k_old;
}
Example:
n = 11;
step1: k_old = 1, k_new = 1;
step 2: k_old = 1, k_new = 2;
step 3: k_old = 2, k_new = 3;
step 4: k_old = 3, k_new = 5;
step 5: k_old = 5, k_new = 8;
///step 6: k_old = 8, k_new = 12'
f(11) = k_old = 8.
A0 = [*1 2 3 *4 5 6 *7 8 9 *10 11]
A1 = [*2 3 5 *6 8 9 *11]
A2 = [*3 5 8 *9]
A3 = [*5 8]
A4 = [8]
I marked the numbers which are removed in next iteration with "*"
Short answer: 2 + O(1 / n).
Reason: Note that picking a larger number is as probable as picking a smaller number. For large n, picking the same number has a chance of 1 / n. So ignore it. Then, at each pick you might pick a larger number with probability 1 / 2 and a smaller number with probability 1 / 2. Therefore, the average number of picks in both cases is almost 2.
This approximation is shaky if n is not large, e.g., n = 2, 3, 4.
NOTE: Also, there is a technical problem with current question.
If you are looking for a number less than the initial pick you should note that if the first pick is "1", there is no way to find a smaller number. Then, the average number of picks will be infinity.
Method 1: O(n log(n)) for arrays
Too complicated to code but leads to O(n log n) for arrays
Start with an array A = [a1 b1 a2 b2 a3 b3 a4 b4 .... ak bk]
where ai and bi are subarrays of positive and negative numbers.
assume ni = len(ai) and mi = len(bi)
Observation:
[a1 b1] --> [b1 a1] in O(max(ni, mi)) which is obtained by repeatedly swaping the first, second, ... elements.
For ni = mi it is obvious. For ni > mi, do it for the first mi, then ignore the first mi since they are in place, do it [ni - mi, mi] positive ones and put them in order. Repeat until you finish after ni swaps.
So recursively do this:
Take [a1 b1 a2 b2] -> [b1 a1 a2 b2] -> [b1 b2 a1 a2]
this is done in max(n1, m1) + max(n1 + n2, m2) < 2n1 + n2 + m1 + m2
For k pairs of [ai bi], we find k / 2 new pairs pairs.
Reapeat the procedure. Note that in the second run, your new value of n1 is (n1 + n2) from previous step.
The same for m1.
For k pairs we need the time complexity T(k) = k / 2 * (2n1 + n2 + m1 + m2) + T(k / 2).
Put averages here: (E[ni] = E[mi] = n / k.
ET(k) = k / 2 * (5 n / k) + ET(k / 2) = 2.5 n + ET(k / 2).
For k / 2, the sizes of ni and mi are doubled. So we have
ET[k] = 2.5 n + 2.5 n + .... + 2.5 log2(k) times.
Then ET[k] = O(nlog(k)).
Finally, average over "k". Note that k is O(n) for random arrays. Therefore, the overall complexity = O(n log(n))
Repeat it for all the k / 2 pairs.
////////////////////
Method 2: For arrays, simple code O(n^2)
void special_sort(int* arr, int length)
{
// Sweep from back to front
// If a number is negative and its previous number is positive, swap them
// continue sweeping until no swaps are made
bool swapped = false;
while(swapped)
{
swapped = true;
for (int k = length - 1; k > -1; k--)
{
if (k > 0)
{
if (arr[k] < 0)
{
if (arr[k - 1] > 0)
{
int tmp = arr[k - 1];
arr[k - 1] = arr[k];
arr[k] = tmp;
swapped = false;
}
}
}
}
}
}
Method 3: Data stored in linked list O(n)
struct LinkedList {
int value;
LinkedList* next;
};
LinkedList* special_sort(LinkedList* arr)
{
// If the first element is not negative, insert a negative number
// Set pos_last_neg as pointer to the first elemnt of array
// Sweep through the list (using pointer pos)
// if the number is negative and pos != pos_last_neg->next, move the element at pos to pos_last_neg;
LinkedList* head = new LinkedList;
head->value = -10000000;
head->next = arr;
LinkedList* last_neg = head;
LinkedList* pos = head->next;
LinkedList* prev = last_neg;
while(pos != nullptr)
{
if (pos->value < 0)
{
if (prev != last_neg)
{
// There are some positive elements in between
LinkedList *p1 = pos;
prev->next = pos->next;
pos->next = last_neg->next;
last_neg->next = pos;
last_neg = pos;
pos = prev->next;
pos = prev->next;
continue;
}
}
prev = pos;
pos = pos->next;
}
return head->next;
}
void main()
{
LinkedList* head = GetLinkedListFromArray({......});
PrintList(head);
head = special_sort(head);
PrintList(head);
}
This, in its most general form, seems like a CSP, or SAT problem. I would go for the standard branch and prune/bound.
Each work Wi has a payoff of Ti. If two works overlap then they cannot be chosen together
One way to formulate:
Maximize T1 W1 + T2 W2 + .... + T5 W5
Subject to: not(W1 & W2) = true
not(W2 & W3) = true
not(W2 & W4) = true
not(W2 & W5) = true
not(W3 & W5) = true
This is a rough sloppy implementation without bounding.
function payoff = solve(k, w)
if (k > N)
p = get_pay_off(w)
if (p > pmax)
pmax = p;
wmax = w;
end
return p;
end
w[k] = 1;
p1 = solve(k + 1, w);
w[k] = 0;
p2 = solve(k + 1, w);
return (max(p1, p2))
end
You can add a bounding method to make the algorithm faster. This is usually obtained by relaxing the binary variables and solving the LP to obtain the upperbound. If the upper bound on payoff is less than best solution so far, our assumption for wk is wrong or there is no solution.
- Ehsan August 22, 2013Nice approach, but:
1- You are assuming a set of "M" words is given to you. The question says, "you are given a test function to determine whether a given word is in the dictionary."
2- Given the "test function" you do not need the graph. Start from the given word of length "L". Check all the possibilities of dropping a letter (L - 1) and put a vertex for each valid case. Repeat until the graph is made. It seems like L! but it will be less.
The idea is that if you are given a word with "L" letters, there is at most 2^L - 2 words of length < L. Including the given word and the "null" string, 2^L (total number of subsets of a set with "L" elements).
So the initial step in you algorithm should be to build a graph with O(2^L) nodes, and run the algorithm. This takes O(2^L). The DFS and BFS also take O(2^L) so the complexity is O(2^L).
To compare it with a simple recursive algorithm we should note that through recursion we check for repeated words, (i.e., in "restated" dropping "r" then "d" or "d" then "r" is the same). So the complexity is O(L!) >> O(2^L).
Also, the time complexity of O(2^L) is quite nicely compatible with the predictions from information theory. We know that the entropy of English alphabet is somewhere around 1.5 bits per character, i.e., there is a total of 2^(1.5 L) words of length "L". Since we are looking for the ones made with the given "L" letters, the complexity should be less, but not super-exp in "L".
I wonder if this problem is "NP"-complete in size of input.
The code above looks correct. I am still posting the java version I wrote using a similar approach. The recursive implementation is in fact dynamic programming.
Sample usage:
Output:
- Ehsan December 02, 2013