Selmeczy, Péter
BAN USERCalling strlen(string) for each and every iteration is not very effective!
Call it once and use the value.
Why to use only one structure (tree/dict/whatever)? Why not use one per length? It can improve the searching a lot.
- Selmeczy, Péter April 28, 2015Have a binary array of 5x7 slots, and call the rand5 7 times, putting the result into the 1st, 2nd, etc 5-bit sub-array. This creates an equal distribution for all over the 35 slots, and if you think the other way (7-bit subarrays) the distribution is the same good (equal probablity) on those slots, too. So getting 7 values from rand5 will result in having 5 rand7 values in the array.
When a new rand7 value is needed get the number(s) from the 7-bit slots.
Do it 5 times - then all is used - so generate the array again.
Coding is left to the reader as an exercise :)
It is a very bad practice to name a local variable the same as the function it is within(main)
- Selmeczy, Péter October 16, 2014A few things already missed big time:
1. What if there are no numbers at all?
2. What if we do not know the number of numbers e.g. they are in a file?
3. The output does not look like the requested (e.g. no , between the numbers, and there isn't one at the end
To keep the minimum takes time!
When adding a new entry to the stack it is easy. But when removing - it is the hard nut.
To keep a heap - well, pop will remove the entry from the stack but heapify has a cost of O(log(N)) as far as I know. So pop is not O(1) then.
Did I miss something?
Global and static variables are initialized to zero prior program execution (if they do not have explicit initial value assigned to the like int x = 1;)
- Selmeczy, Péter August 15, 2013The only problem with this code is that it does not work :)
Why do you think that an address from the heap is above or below the address of the current stack? (Your guess on that the current stack is above any old stack is OK, but the opposite is not).
Furthermore what is the case with static variables? They are neither on heap, nor on stack, just sitting in some data segment (if the undelying model has "segment" at all)
And if we go a little bit further a variable that contains a reference to the heap is on the stack (or static)... I mean the variable itself. The address it contains is on the heap.
You should use that function by supplying the address of the variable, like isFromStack(&ptr) in your example.
- Selmeczy, Péter November 20, 20121. this is C++ and not C
2. no abstraction at all, there should be a function that performs the encryption/decryption AND a test-program to get these from the user and pass on to the function.
3. Buffered, binary read should be used, not lines - it is ways more effective
@Asperger
I think it was about having 1000000 digits...
It is ways bigger than bigint :)
Shallow copy: When the data in one data structure (usually class instance) is copied and created a new instance BUT only the top-level data is copied (e.g. the data belonging to the embedded references are not)
Deep copy: Object is copied in a way that all data in the references it contains (and all inside those references, etc. recursively) is copied.
E.g. if there is a class that contains 3 points (they are themselves class-instances) and a colour (not a class, just a simple enum) a shallow copy copies the referene to the 3 points and the colour creating a new instance of that class. However using this object and modifying the points data - it will modify the data in the original copy as well (well, the data that is referenced to) In this case only one new object created.
With a deep copy all three point-instances are copied by creating new instances, too, so making any change using this new object has no impact to the old object whatsoever. In this case 1+3 new objects are created.
If you try to understand algorithms and their complexity without mathematical background - it is a kind of mission impossible. Good luck with it - you gonna need it!
- Selmeczy, Péter November 02, 2012No-one will write you an intro like this here - lack of space :)
Get/buy and read this: Introduction to Algorithms [Student Edition] [Paperback] by T Cormen (Author), C Leiserson (Author), R Rivest (Author), C Stein (Author)
And it is worth to add that usually you pass the number of items in the array which is sizeof(theArray)/sizeof(theItem)
- Selmeczy, Péter October 30, 2012Errrr... 0xAAAA and 0x5555 are 16 bits, the question was for 32 bits
- Selmeczy, Péter October 25, 2012We can do it with 3 measurements
Let the balls be numbered with 1, 2, ..., 8
Compare 1&2 with 3&4
If they are equal then the fake one is in [5..8] and all in [1..4] are good ones.
If they are not equal then all in [5..8] are good ones and the fake one is in [1..4]
So with one measurement we surely have 4 good balls and a set of 4 that contains 3 good and the fake.
Compare two of the "wrong" set with two good ones (from the other set)
If they are equal - you have a set of two that contains the wrong one.
If they are not - same thing.
So for the 3rd measurements you have a set of two that contains the wrong one and 6 that are surely good.
Compare one out of the wrong set with a good one.
If they are equal - the remaining from the wrong set is the fake.
If they are not - well, you know which one is the good one, the other is the fake.
It is left to the reader to prove that it cannot be done with 2 measurements.
The interesting part is that knowing if the fake ball is heavier (or not) is helping a lot: you can do it using 2 measurements (3 vs 3 and then another one)
- Selmeczy, Péter October 23, 2012a[iReplace] = 48 + count;
vs
a[iReplace] = '\0';
Don't you feel that something is wrong with this?
A few comments:
1. Why don't you write a function to do it a make main a test-bed for it?
2. Why main is returning 1??? What is the return value of main supposed to be? (It is left to the reader to answer this question)
3. Why don't you handle/test for misformed texts? E.g. "alma"? This cannot be converted inspace.
4. Your code does not handle the case when a character appears more than 9 times.
It is either garbage or 0.
Depending on how this is evaluated: a[indx]=indx++;
The order is undefined, what is sure that after the statement indx is 1 (it was 0 before)
But if a[0] or a[1] is assigned to 0 (the old value of indx) - it is not defined.
So the a[1] - what is printed out - can be garbage or 0.
Yep, but...
If the character set is Unicode (what else in 2012?) than the constant on the O(1) is quite huge, to set up a 64K-size array to count is a significant amount of time, allocating and clearing this buffer should not be ignored.
Each non-empty item in the sheet is a triplet (row, col, data) and this is stored in an array.
This is not optimal for traversing/access but it is a solution.
These triplets can be extended to contain "ponters" (aka indexes in the array) to the next/previous/upper/lower cells as well.
And we can have a supporting array to the first cell of columns/rows.
It is a very good question to test if someone has heard about regular expressions - or even about more formal language theory!
And if yes does he/she have an idea how to write a program to process them - some knowledge of finite automata and their implementation.
Or just test if someone can use a regex library in a given environment.
Or just test if someone can really capture "float" as a specification. And how well he is handling the wrong-format cases - for testing jobs this is a brilliant question to ask!
Inserting where? Don't mix binary tree (each node can have max 2 child) and binary sort/search tree.
And it mostly depends on how it is implemented.
- Is it balanced or not?
- Is it stored with pointers or compactly stored in an array?
The size of the file does not really matter, supposed that one word easily fits into memory (e.g. can be read without problems into memory).
At least if the question is about creating a file with the same words in the same order as in the original file but lla sdrow era desrever.
If it is about reversing the order of the words - story different a is it :)
It is potentially dangerour to set char* nonwhite = s - 1;
It then points to a position that is practically an illegal address!
I know that because of the prefix increment this addressing won't happen but why are you afread of using postfix increments?
Calling strcat is killing the O(n)!
First it is reading to the end of the first string and then it it copying the 2nd string!
#include <stdio.h>
#define MAX_N 20
// don't bother with parameter passing
int matrix[MAX_N][MAX_N];
void Spiral(int n) {
int i, j;
if (n == 1) {
matrix[0][0] = 1;
} else if (n == 2) {
matrix[0][0] = 1; matrix[0][1] = 2; matrix[1][1] = 3; matrix[1][0] = 4;
} else {
Spiral(n-2);
// shift and increment
for (i=n-1; i>0; i--) {
for (j=n-1; j>0; j--) {
matrix[i][j] = matrix[i-1][j-1] + 4*(n-1);
}
}
// fill border around
j = 1;
for (i=0; i<n; i++) { // top
matrix[0][i] = j++;
}
for (i=1; i<n-1; i++) { // right
matrix[i][n-1] = j++;
}
for (i=n-1; i>0; i--) { // bottom
matrix[n-1][i] = j++;
}
for (i=n-1; i>0; i--) { // left
matrix[i][0] = j++;
}
}
}
void Dump(int n) {
int i, j;
for (i=0; i<n; i++) {
for (j=0; j<n; j++) {
printf("%3d", matrix[i][j]);
}
printf("\n");
}
printf("\n");
}
int main() {
int n;
for (n = 1; n<10; n++) {
Spiral(n);
Dump(n);
}
return 0;
}
Just draw the matrices and watch for the odd (1st, 3rd, 5th, etc) and evens (2nd, 4th, 6th, etc)
It is easy to see that the Nth is generated from the (N-2)th by three simple operations:
a. "shift" the (N-2)th matrix right and down by one
b. Add 4*(N-1) to each element of the shifted matrix
c. "Draw" the border "around" of the shifter (N-2)th matrix by filling it with 1, 2, 3... N, ... 4(n-1)
(a. and b. is interchangable if you like or can be done paralelly, c. should be done after them IF we are not creating a new matrix just let the old one grow)
I know that it is not a simple solution but a very nice inductive way to create those matrices and induction equals recursion :)
You can do it better with recursion, split the sequence, determine the longest increasing/decreasing sub-sequence and remember if the longest sub-sequence was at the beginning or ending of the sequence. And when "merging" the result just add the "longests" (ending of 1st+starting of 2nd forms a consequtive sub-sequence) or choose the max of them (otherwise).
- Selmeczy, Péter September 26, 2012In C you declare the type of an expression, not a variable.
const int *i; -> *i is an int, that cannot be modified
int const *i; -> same as before, no difference
int *const i; -> i is an int* and the pointer itself cannot be modified - but the content can! e.g. *i = 10; is absolutely valid
const int * const i; -> neither of the pointer, nor the content can be modified. [This only makes sense with initializing i to an existing address]
axecapone is right on it, b is advanced after the terminating 0-character! So the output is garbage or even a segmentation fault (reading memory that does not belong to the program)
- Selmeczy, Péter September 19, 2012It is C, you can assign, the compiler just shows a warning... Don't compile C code with C++ compiler.
- Selmeczy, Péter September 19, 2012Output: Kick the ass of the one who wrote those macros! Never ever write code that is doing like this (e.g. the name does not reflect what the function does).
- Selmeczy, Péter September 18, 2012You can write an extension method for arraylists, like ToStringX() [unfortunately you cannot override its ToString - at least I think so!]
But this one should work as cl.ToStringX()
public static string ToStringX(this ArrayList array)
{
string s = "[";
foreach (object obj in array)
{
ArrayList inner = obj as ArrayList;
if (inner != null)
{
s += inner.ToStringX() + " ";
}
else
{
s += obj.ToString() + " ";
}
}
return s+"]";
}
Nice requirement :) most probably impossible to meet, but you can try some not-very clever but working solutions, like get the next item on list-2 and search if this pointer is in list-1 (if found, this is a merging point). Surely works and it is a trivial solution. At least this is what I'd told him/her.
- Selmeczy, Péter September 18, 2012What about using plain text or XML - a sequence of 8-bit characters, ints and longs are sent as decimal numbers.
Plain and simple and does not need the knowledge of architectures (well, each side knows its own, but apart from that).
I know that this is not the most efficient way but the difference is not much (if you add padding)
If it is as in the example then there is no problem at all.
IF int arr[10]; would be a const array than the write access could fail - based on the operating system and memory allocation of the C compiler.
This is just not true. You can use an array as a pointer to the first item of it.
- Selmeczy, Péter July 19, 2012(number & k) > 0 should read as (number & k) != 0 [or simple (number & k) if in C] in all the codes above.
If the shifting puts the bit to the topmost bit in k than the result will be negative, but still non-zero.
C++ supports multiple inheritance of classes, Java (and C#) supports single inheritence of classes and multiple inheritance of interfaces.
When C++ added multiple-class inheritence pure OOP was thought to be "the" solution to everything.
In the meantime it was proven that class inheritance is good, but it ends up with tightly coupled systems. The more class inheritance you use, the more likely that one small change will have a huge impact on your entire system.
Loosely coupled inheritance - interfaces - are considered a much better option these days.
Why do you write this return((m==n)?true:false); ?
Why don't you write return m == n; ?
To avoid loops? So perhaps he/she was looking for a recursive solution (which is a hidden loop in anyway!) On the other hand to write recursion for this is kind of problems is overkill.
- Selmeczy, Péter February 15, 2012Bruce Eckel is having a Java book as well, search for Thinkin in Java.
- Selmeczy, Péter February 14, 2012I think the "trick" part of this question is to use the QUEUE operations (enqueue/dequeue) and you are not allowed to iterate through the linked list!
So the solution is that one step in the iteration should read the first-out entry (dequeue), compare and then enqueue it. After all items are examined the queue is in the same state as it was.
There are three cases when the static keyword can be applied, the first two are similar:
1. A variable declared (actually defined) as static outside of any block
In this case this variable has file-scope (can be only be accessed in the file where it is declared and after the declaration) and has storage allocated for the full lifetime of the program
2. A variable declared static in a block
In this case the usual block-scope applies but the life-time of the storage is the full life-time of the program
1&2: If the variables are not initialized their value is set to 0. If there is an initialization it must be constant and it is evaluated at compile time and the initial value is set to this.
3. A function is declared as static - it means that the function (which are by default have external linkage!) has file linkage only, so it cannot be from called outside of the file.
Some examples:
static int my_static; // file-global declaration (case 1)
can be accessed in the file, but declaring it as "extern int my_static;" and trying to use it in another file will result a linker error.
2.
void f() {
static int my_static = 0;
my_static++;
printf("Function is now called %d times\n", my_static);
}
3.
In file x.c:
static void f() {
// do something
}
In file y.c
extern void f();
...
f();
it will compile but when the object files from x.c and y.c are linked together there will be no extern f found.
- Selmeczy, Péter February 14, 2012Ooooops, one more thing: while(a[--j] == 1);
nicely decrementing j below 0...
Should add j>=0 &&
Sorry, but it is not fixed, the while (arr[begin]==0) begin++; loop nicely increments begin over the size...
while (begin < size && array[begin] == 0) should be the condition, and similar should be added to the 2nd loop (end >= 0 && ...)
In more detail: create an array (of ints) where each item contains the bits in the character that is indexing it (e.g. numBits['A'] = 2; etc)
- Selmeczy, Péter May 19, 2015Then it is just an indexing/adding per each character in the array.