Там не все так простоFlying Hen wrote:Как это? В Джаве буква это 16 bit unsigned int, примитив то есть.ZmeyeeD wrote: А буква и так - объект, если считать за букву юникодовский символ.
Согласно местным поверьям, у программистов зарплат в 150К не бывает, а в 2 раза больше, чем есть у меня сейчас -- это уже просто из области ненаучной фантастики. Так шта, по-любасу их контора нам не подойдет.valchkou wrote:А если они вам предложат в 2 раза больше, чем у вас есть сейчас ?
Неверно. Специалисты, которые в состоянии отличить точку следования от дырки в земле, на интервью таких вопросов на задают. А если вдруг и задают, то уж совсем не для того, чтобы проверить вас в роли живого лексически-синтаксического анализатора.ZmeyeeD wrote:Aга, именно такие специалисты по порядку операций задают на интервью вопросы типа
int a = 5;
int b = 6;
int c = a+++b--;
Чему равно с?
Вы вы и сами привели пример ситуации, в которой умение разбираться в таком коде является весьма полезным.ZmeyeeD wrote:И если бы только на интервью! Неделю назад переписывал код, написанный таким "специалистом" по порядку операций - ошибочка вошла в одном из ++-- и система падала случайным образом. Когда я спросил, "WTF, кто написал это", мне ответили, что этот "специалист" уже не работает в конторе.
Вы являетесь жервой некоего заблуждения. Не существует никакой разницы в производительности между `*++s` и парой `++s; *s;`. Оба варианта элементарнейшим образом делают одно и то же и, поэтому, при использовании любого уважающего себя компилятора, будут порождать одинаковый машинный код. Люди, которые пишут выражения вида `*s++` делают это не из соображений повышения производительности (от таких иллюзий избавляются еще в детском саду).ZmeyeeD wrote:Код должен быть понятным с первого взгляда, по возможности. Первоначальный код топикстартера с первого взгляда не понятен (и не ясно, что он делает, если нет комментариев). Приносить читаемость кода в жертву производительности там, где производительность модуля не критична (а это в большинстве случаев происходит) - нельзя.
с "aab" и "baa" работает одинаково?crypto5 wrote:perm(StringBuffer s, StringBuffer f) {
if(s.isEmpty()) {
print f;
}
for(int i = 0; i < s.size(); i ++) {
f.append(s.charAt(i));
s.deleteCharAt(i);
perm(s,f);
s.insert(f.last(), i);
f.removeLast();
}
}
main() {
perm(new StringBuffer(stroka), new StringBuffer());
}
Только что бы с правильной сложностью реализовать нужно с связными списками вроде возиться.
У меня подозрений нету.. Это псевдокод, доберусь до джавы/питона напишу на них.sergant wrote:в смысле правильности работы кода.
есть подозрение, что "baa" даст больше вариантов, чем "aab".
У меня нет плюсов проверить.
Code: Select all
#include <stdio.h>
void permute( char *s, int pos, int len )
{
char temp;
int i, j;
if ( pos == len - 1 )
printf( "%s\n", s );
else
{
permute( s, pos + 1, len );
for ( i = pos + 1; i < len; i++ )
{
for ( j = pos; j < i; j++ )
if ( s[j] == s[i] )
break;
if ( j == i )
{
temp = s[pos];
s[pos] = s[i];
s[i] = temp;
permute( s, pos + 1, len );
temp = s[pos];
s[pos] = s[i];
s[i] = temp;
}
}
}
}
main()
{
char s0[] = "abc";
char s1[] = "aab";
char s2[] = "baa";
permute( s0, 0, sizeof( s0 ) - 1 );
printf( "---\n" );
permute( s1, 0, sizeof( s1 ) - 1 );
printf( "---\n" );
permute( s2, 0, sizeof( s2 ) - 1 );
return 0;
}
$ ./a.out
abc
acb
bac
bca
cba
cab
---
aab
aba
baa
---
baa
aba
aabПризнаю, я был не прав, множество будет одинаково.crypto5 wrote:Ваш вариант намного лучше - он in place, учитывает повторяющиеся быквы и более быстрый чем мой, но я все еще продолжаю считать что у моего варианта на aab и baa множество пермутаций будет одинаково.
А я бы за такой как у Вас. Хотя бы потому что у него O(n), а у Вас нет.ZmeyeeD wrote:A за такой код
я бы прекращал интервью немедленно (если это только не кусок какого-нибудь супер-пупер embedded firmware чего-то-там, где памяти 128К а места на диске 2 МВ (но это явно не в данном примере). Это издевательство над тем, кто читает код (и дебагирует его).Code: Select all
for ( s1 = s2 = str; *s2; ) { table[*s1]++; while ( table[*++s2] ); *++s1 = *s2; }
Его код НЕ работает на Extended ASCII, только на base. Более того, только на строчках длиной менее 65536. Ваш, впрочем, тоже не работает на full Unicode.ZmeyeeD wrote: Код должен быть понятным. Ваше решение вызывает головную боль при остальных его недостатках (главный из которых - это работает только на Extended ASCII).
Не хотите помнить одной из всео-то пары дюжин базовых операций языка, на котором базированы все языки, на которых написано 99%+ кода в мире? no hire, даже на junior, даже на интерна бесплатного. Самому так писать не надо, но такой код бывает, и надо его уметь читать без словаря.ZmeyeeD wrote: Кстати, кто помнит порядок операций в?Code: Select all
*++s2
Я не помню и помнить не хочу. Если писать, то
(или в дрогом порядке, в зависимости от того, что правильно)Code: Select all
*s2; ++s2
И тут Вы не правы.ZmeyeeD wrote: Учитывая, что Set - это темплейт (если в терминах С++),
И тут Вы не правы. Ни темплеты ни классы сами по себе память не жрут (разве что во время компиляции).ZmeyeeD wrote: Иногда нет выхода - элементарно не хватает памяти (или места не диске) и приходится считать каждый байт. Тут уже не до темпейтов и классов.
QT - это C++, String <char> там нет, есть basic_string<char>, он же просто string.StrangerR wrote: Ну во первых, оный String <char> весьма кривой класс и половина народа пишет не на нем а на чем нибудь еще вроде QT. Я уж не помню почему мы в свое время от него отказались, но пришлось отказаться.
Обычно да. Но иногда избегать таки надо, при наличии полатформ, где нет достаточно стандартных компиляторов.Мальчик-Одуванчик wrote:Дураки как раз интуитивно стараются избегать применения расширенных возможностей С++, в том числе и шаблонов, низводя все до программирования в стиле "С с классами".
Это практически бинарный код. Если в байткоде инструкция iadd, то с лонгами и даблами она уже работать не будет. В этом, кстати, отличие Java bytecode от .NET VM и его CIL (за счет того, что последний нельзя эффективно интерпретировать).crypto5 wrote:Во первых у джавы насколько я знаю двухпроходной компиллер, во вторых в чем проблема использовать class файл для генерации нового класса? Они ж легко интроспектируются, это ж не бинарный оптимизированный код?IvanF wrote:Вы вообще java видели??? каким образом компилятор java найдет описание темплейта если он находится в другом файле??? перед тем как компилировать текущий java файл, все импорты должны быть уже откомпилированны в class файл и компилятор использует только их.crypto5 wrote:Непонятно при чем тут хедеры, вполне можно компилить по факту использования
Думаю что в теле класса ArrayList<T> не будет никаких iadd относящихся к ТRobinF wrote:Это практически бинарный код. Если в байткоде инструкция iadd, то с лонгами и даблами она уже работать не будет. В этом, кстати, отличие Java bytecode от .NET VM и его CIL (за счет того, что последний нельзя эффективно интерпретировать).crypto5 wrote:Во первых у джавы насколько я знаю двухпроходной компиллер, во вторых в чем проблема использовать class файл для генерации нового класса? Они ж легко интроспектируются, это ж не бинарный оптимизированный код?IvanF wrote:Вы вообще java видели??? каким образом компилятор java найдет описание темплейта если он находится в другом файле??? перед тем как компилировать текущий java файл, все импорты должны быть уже откомпилированны в class файл и компилятор использует только их.crypto5 wrote:Непонятно при чем тут хедеры, вполне можно компилить по факту использования
AndreyT wrote:Неверно. Специалисты, которые в состоянии отличить точку следования от дырки в земле, на интервью таких вопросов на задают. А если вдруг и задают, то уж совсем не для того, чтобы проверить вас в роли живого лексически-синтаксического анализатора.ZmeyeeD wrote:Aга, именно такие специалисты по порядку операций задают на интервью вопросы типа
int a = 5;
int b = 6;
int c = a+++b--;
Чему равно с?
Вы вы и сами привели пример ситуации, в которой умение разбираться в таком коде является весьма полезным.ZmeyeeD wrote:И если бы только на интервью! Неделю назад переписывал код, написанный таким "специалистом" по порядку операций - ошибочка вошла в одном из ++-- и система падала случайным образом. Когда я спросил, "WTF, кто написал это", мне ответили, что этот "специалист" уже не работает в конторе.
Вы являетесь жервой некоего заблуждения. Не существует никакой разницы в производительности между `*++s` и парой `++s; *s;`. Оба варианта элементарнейшим образом делают одно и то же и, поэтому, при использовании любого уважающего себя компилятора, будут порождать одинаковый машинный код. Люди, которые пишут выражения вида `*s++` делают это не из соображений повышения производительности (от таких иллюзий избавляются еще в детском саду).ZmeyeeD wrote:Код должен быть понятным с первого взгляда, по возможности. Первоначальный код топикстартера с первого взгляда не понятен (и не ясно, что он делает, если нет комментариев). Приносить читаемость кода в жертву производительности там, где производительность модуля не критична (а это в большинстве случаев происходит) - нельзя.
Люди, которые пишут подобные выражения либо считают, что это в данном кокретном случае лучше (в т.ч. выразительнее и удобочитаемее), либо считают, что именно так всегда и надо писать на С, ибо это "C way". Вторая категория - это, без сомнения, заблудшие овечки, которых надо срочно спасать. Что касается первой категории, то при определенном уровне профессионализма эти люди соврешено правы, в том числе и с точки зрения удобочитаемости. Нет никаких сомнений в том, что удобочитаемость предполагает некий оптимальный уровень компакности/краткости, отклонение от которого в любую сторону приводит к менее читаемому коду. Подобные фичи языка С, будучи применнными в уместной степени в уместных конетекстах, существенно повышают выразительность и удобочитаемомть кода, а не понижают ее.
Ну и что? Компилятору это не известно, зато извстно, что там уже скомпилированый код.crypto5 wrote:Думаю что в теле класса ArrayList<T> не будет никаких iadd относящихся к ТRobinF wrote:Это практически бинарный код. Если в байткоде инструкция iadd, то с лонгами и даблами она уже работать не будет. В этом, кстати, отличие Java bytecode от .NET VM и его CIL (за счет того, что последний нельзя эффективно интерпретировать).crypto5 wrote:Во первых у джавы насколько я знаю двухпроходной компиллер, во вторых в чем проблема использовать class файл для генерации нового класса? Они ж легко интроспектируются, это ж не бинарный оптимизированный код?IvanF wrote:Вы вообще java видели??? каким образом компилятор java найдет описание темплейта если он находится в другом файле??? перед тем как компилировать текущий java файл, все импорты должны быть уже откомпилированны в class файл и компилятор использует только их.crypto5 wrote:Непонятно при чем тут хедеры, вполне можно компилить по факту использования
Code: Select all
#include <stdio.h>
#include <stdlib.h>
/*
Your niece was given a set of blocks for her birthday,
and she has decided to build a panel using 3”×1” and 4.5”×1" blocks.
For structural integrity, the spaces between the blocks must not line up
in adjacent rows.
For example, the 13.5”×3” panel below is unacceptable,
vvv
#####|###|###|###| <<<
###|###|#####|###| <<<
#####|#####|#####|
^^^
because some of the spaces between the blocks in the first two rows line up
(as indicated by the dotted line).
There are 2 ways in which to build a 7.5”×1” panel,
2 ways to build a 7.5”×2” panel, 4 ways to build a 12”×3” panel,
and 7958 ways to build a 27”×5” panel.
How many different ways are there for your niece to build a 48”×10” panel?
The answer will fit in a 64-bit integer. Write a program to calculate the answer.
The program should be non-interactive and run as a single-line command
which takes two command-line arguments, width and height, in that order.
Given any width between 3 and 48 that is a multiple of 0.5, inclusive,
and any height that is an integer between 1 and 10, inclusive,
your program should calculate the number of valid ways
there are to build a wall of those dimensions.
Your program’s output should simply be the solution as a number,
with no line-breaks or white spaces.
*/
#define W1 30 // 1st block length multiplied by 10
#define W2 45 // 2nd block length multiplied by 10
#define MAX_COL (480 / W1) // 16
typedef unsigned long int64;
int width;
int hight;
typedef struct Pair
{
struct Row *entry; // pointer to matched row
struct Pair *next; // no comments
} Pair;
typedef struct Row
{
int bl[MAX_COL]; // containes list of blocks
int sp[MAX_COL]; // size needed to compare
int64 p_r; // completed pairs
int64 n_r; // next possible pairs
Pair *pair; // list of all matched rows
struct Row *next; // no comments
} Row;
void findCompatibility( void );
int PossiblePair( Row *sp1, Row *sp2 );
void permutations( int *, int, int );
Row *firstRow; // keeps start pointer
Row *curRow; // keeps current pointer
main( int argc, char **argv )
{
int i, j, len;
int *s;
int64 count;
/* verify input */
if ( argc != 3 )
{
printf( "Usage: %s {3..48} {1-10}\n", argv[0] );
exit( 1 );
}
else
{
width = atof( argv[1] ) * 10;
// I hate verify if hight is an integer
// I would better do atoi
hight = atof( argv[2] ) * 10;
if ( width < 30 ||
width > 480 ||
width % 5 ||
hight < 10 ||
hight > 100 ||
hight % 10 )
{
printf( "Error: parameters %s %s out of range\n", argv[1], argv[2] );
exit( 1 );
}
hight /= 10;
}
// our start row
curRow = firstRow = calloc( sizeof( Row ), 1 );
// temp row
s = calloc( sizeof( *s ), MAX_COL );
// find blocks that fit into the width
// i W1, j W2
// and store them in a list (firstRow)
for ( i = width / W2; i >= 0; i-- )
{
for ( j = width / W1; j >= 0; j-- )
{
if ( i * W2 + j * W1 == width )
{
// we found amount of each type
// to fit the space
// lets build the row
// W2 block first, then W1s
int c, k;
for ( c = 0, k = i; k; k-- )
s[c++] = W2;
for ( k = j; k; k-- )
s[c++] = W1;
// and find all permutes
permutations( s, 0, j + i );
}
}
}
// walls
count = 0;
if ( hight > 1 )
{
// build compatibilities of each row with others
findCompatibility();
// for each row
for ( i = 0; i < hight - 1; i++ )
{
// no "next possible" rows yet
for ( curRow = firstRow; curRow->next; curRow = curRow->next )
curRow->n_r = 0;
// we have initialized to 1 "completed rows" before
// through all found rows
for ( curRow = firstRow; curRow->next; curRow = curRow->next )
{
Pair *p;
for ( p = curRow->pair; p; p = p->next )
p->entry->n_r += curRow->p_r;
}
// save
for ( curRow = firstRow; curRow->next; curRow = curRow->next )
curRow->p_r = curRow->n_r;
}
// calculate amount of walls
for ( curRow = firstRow; curRow->next; curRow = curRow->next )
count += curRow->n_r;
}
// if hight == 1 amount of rows is amount of walls
else // if ( hight == 1 )
for ( curRow = firstRow; curRow->next; curRow = curRow->next )
count++;
// no even "\n" on output? ;)
printf( "%ld", count );
return 0;
}
/*
we compare each row with all the others
including compare a row with itself
I know that is not good, but from coding and performance
prospective we better keep it that way.
*/
void findCompatibility()
{
Row *cur = firstRow;
Row *tRow;
while ( cur->next )
{
tRow = firstRow;
while ( tRow->next )
{
if ( PossiblePair ( cur, tRow ) )
{
// so, curRow and tRow match
// lets add the link
Pair *t_p = cur->pair;
Pair *new_p = calloc( sizeof( Pair ), 1 );
new_p->entry = tRow;
if ( t_p )
{
while ( t_p->next )
t_p = t_p->next;
t_p->next = new_p;
}
else
{
cur->pair = new_p;
}
}
tRow = tRow->next;
}
cur = cur->next;
}
}
/*
returns 0 if 2 rows not compatible
otherwise return 1
keep in mind rows do not contain last block
*/
int PossiblePair( Row *sp1, Row *sp2 )
{
int i, j;
for ( i = 0; sp1->sp[i]; i++ )
for ( j = 0; sp2->sp[j]; j++ )
if ( sp1->sp[i] == sp2->sp[j] )
return 0;
return 1;
}
/*
Recursive!
finds all the possible permutes like
abc -> abc, acb, bac, bca, cab, abc
and check for duplicated elements so
aab -> aab, aba, baa
*/
void permutations( int *s, int pos, int len )
{
int temp;
int i, j;
if ( pos == len - 1 )
{
temp = 0;
// create N-1 blocks in a row
// if we don't keep last block
// it will be easier to find matched rows later
for ( i = 0; i < len - 1; i++ )
{
curRow->bl[i] = s[i];
temp += s[i];
curRow->sp[i] = temp;
}
curRow->next = calloc( sizeof( Row ), 1 );
curRow->p_r = 1;
curRow = curRow->next;
}
else
{
permutations( s, pos + 1, len );
for ( i = pos + 1; i < len; i++ )
{
for ( j = pos; j < i; j++ )
if ( s[j] == s[i] )
break;
if ( j == i )
{
temp = s[pos];
s[pos] = s[i];
s[i] = temp;
permutations( s, pos + 1, len );
temp = s[pos];
s[pos] = s[i];
s[i] = temp;
}
}
}
}