Ενδιαφέρουσα άσκηση σε C++ από μία εταιρεία

[Star_Light]

Για τον εργοδότη δεν με νοιάζει το θέμα είναι ότι ο διαγωνισμός δεν είναι ισοτιμος και απλα δεν μπορείς να το ξέρεις

 

 

Μα δεν σε εμποδισε κανεις να συνεργαστεις και εσυ με καποιον

Απο το σπιτι σου την κανεις!!!! Τελοςπαντων ενταξει ο καθείς οπως το βλεπει

εγω παντως αυτο το πραγμα δεν θα μπορουσα να το κανω μονος μου ουτε κατα διανοια...

θα δεχομουν την βοηθεια ενος φιλου... αν με παιρνανε και μετα εβλεπαν πως ειμαι ανεπαρκης

δεν νομιζω να με εδιωχναν θα μπορουσαν να με εκπαιδευσουν και λιγο!

[Aztec]

Εντάξει την άποψη μας λέμε no problem

[migf1]

Δυστυχώς δεν βρήκα ακόμα την ευκαιρία να διαβάσω προσεχτικά ούτε τον κώδικα του φίλου DiaVol ούτε την απάντηση της εταιρίας. Τους έκανα μονάχα ένα γρήγορο πέρασμα, αλλά προφανώς δεν φτάνει. Θα κάτσω να το διαβάσω προσεχτικά και αν έχω να σημειώσω κάτι θα επανέλθω.

 

Να δώσω κι εγώ συγχαρητήρια στο DiaVol όχι μόνο για την προσπάθεια, αλλά και για τον πολύ όμορφο στυλ γραφής στον κώδικά του.

 

Από τη γρήγορη ματιά που έριξα στην απάντηση της εταιρίας, δείχνει να συμφωνεί με την άποψη που εξέφρασα εξαρχής πως ότι γίνει πρέπει να γίνει inplace. Και πραγματικά αυτή είναι η ενδεδειγμένη προσέγγιση για speed-efficient κώδικα.

 

Συνήθως όμως (θα έλεγα πάντα εφόσον μιλάμε για real-life εφαρμογές) το inplace συνεπάγεται χρήση κάποιου (ή κάποιων) data-structure, το οποίο κατά κανόνα "γεμίζει" με πληροφορίες σε πραγματικό χρόνο κατά το parsing. Η ανάκτηση των πληροφοριών συνήθως (πάλι) γίνεται σε 2ο χρόνο, αλλά είναι ταχύτατη λόγω του ότι πλέον είναι οργανωμένη και καταχωρημένα ειδικά για να μπορεί να ανακτηθεί ταχύτατα (συνήθως σε O(1) με τη βοήθεια κάποιου hash-table, στον οποίον έχει γίνει hashed κατά το parsing.

 

Παρεμπιπτόντως τα 128Mb που αναφέρει πως έχουν στη διάθεσή τους είναι... απειρο-τεράστιος χώρος για τη συγκεκριμένη δουλειά, αλλά προφανώς όπως επίσης αναφέρει στην απάντησή της, χρησιμοποιείται για ένα κάρο δουλειές.

 

Όπως και να έχει, η "καρδιά" του implementation είναι το inplace parsing και αμέσως μετά η επιλογή του/των data-structures που θα χρησιμοποιηθούν (και πως και πότε θα χρησιμοποιηθούν).

 

Αφιέρωσα περίπου 45 λεπτά για να γράψω σε C μια ρουτίνα για inplace parsing ενός και μόνο command-set, σύμφωνα με τα command-sets που αναφέρει η εκφώνηση, η οποία επιστρέφει ένα ResType struct (συνειδητά δεν επιστρέφω δείκτη, γιατί εστίασα στο να φτιάξω τη ρουτίνα πρώτα). Tην παραθέτω ακριβώς όπως μου βγήκε ως 1ο draft χωρίς σχόλια, χωρίς καλλωπισμούς, κλπ, κλπ, για όποιον ενδιαφέρεται να της ρίξει μια ματιά.

 

Στο τέλος της, έχω βάλει σε σχόλιο τη γραμμή:

 

>
	/* ret.cs = hashmap[ csstr ] */

επειδή η C δεν παρέχει έτοιμα hashmaps, ενώ η C++ παρέχει μέσω της STL. Το csstr είναι ένα c-string που γεμίζει δυναμικά κατά το inplace parsing, και στο τέλος ισούται με ένα από τα command-set-strings που δίνει η εταιρία ως σχόλια στον ορισμό του CommandSet_t. Έχοντας φτιάξει ένα hash-table indexed με αυτά τα strings, η παραπάνω γραμμή επιστρέφει σε O(1) το κατάλληλο CommandSet_t value, προς εκχώρηση στο πεδίο: ret.cs.

 

Επίσης, κάνω το αυθαίρετο assumption πως κάθε command-token μπορεί να είναι είτε αρχικό, είτε ενδιάμεσο, είτε τελικό. Κάτι που δεν ισχύει, γιατί στα παραδείγματα το S χρησιμοποιείται άλλοτε ως αρχικό κι άλλοτε ως ενδιάμεσο token στα command-sets. Στον πίνακα mtokens, που περιέχει τα ενδιάμεσα tokens, το έχω αντικαταστήσει με το Χ. Επειδή αυτό συμβαίνει μονάχα για το S, μπορεί να διαχειριστεί ως special-case (δεν το έχω κάνει).

 

 

 

>
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#include <ctype.h>

#define MAX_TOKSIZE	(8+1)			// "SEQUENCE"
#define MAX_PARAMS	4
#define MAX_CSSTRSIZE	(15+1)

#define MAX_STOKENS	5
#define MAX_MTOKENS	6
#define MAX_ETOKENS	7

/**
*  Command codes as returned by the parser when a given command is identified
*/
typedef enum CommandSet {
   	csUnknown	= 0,
   	csSceneGo	= 1,			// SCENE*GO
   	csSceneTGo	= 2,			// SCENE*T*GO
   	csSceneTLGo	= 3,			// SCENE*T*L*GO
   	csSceneNu	= 4,			// SCENE*NU
   	csSceneNd	= 5,			// SCENE*ND
   	csSceneUp	= 6,			// SCENE*UP
   	csSceneDn	= 7,			// SCENE*DN
   	csSceneSt	= 8,			// SCENE*ST
   	csSequenceGo	= 9,			// SEQUENCE*GO
   	csSequenceSt	= 10,			// SEQUENCE*ST
   	csSetSlaveChan	= 11,			// S*C*L*GO
   	csSetPackChan	= 12,			// P*C*L*GO
   	csSetPackDmx	= 13,			// P*D*L*GO
   	csSetModuleChan	= 14,			// M*D*C*L*GO
   	csSetButtonState = 15			// P*B*S*\r\n, P*B*S*GO

} CommandSet_t;

typedef struct ResType {
CommandSet_t	cs;
int		params[ MAX_PARAMS ];
} ResType;

/* -------------------------------------------------------
*
* -------------------------------------------------------
*/
bool str_in_arrstr( const char *str, char *const *arrstr, const int arrlen )
{
register int i = 0;
if ( !str || !arrstr )
	return false;

for (i=0; i < arrlen; i++)
	if ( !strcmp(str, arrstr[i]) )
		return true;
return false;
}

/* -------------------------------------------------------
*
* -------------------------------------------------------
*/
int advance_param( char *start, char *token )
{
int i = 0;

if ( !start || !token )
	return 0;

while ( *start && *start != ',' && isdigit( *start ) && i < MAX_TOKSIZE )
{
	*token++ = *start++;
	i++;
}
*token = 0;

return i;
}

/* -------------------------------------------------------
*
* -------------------------------------------------------
*/
int advance_token( char *start, char *token, char *csp )
{
int i = 0;

if ( !start || !token )
	return 0;

while ( *start && *start != ',' && !isdigit( *start ) && i < MAX_TOKSIZE )
{
	*token++ = *csp++ = *start++;
	i++;
}
*token = 0;

return i;
}

/* -------------------------------------------------------
*
* -------------------------------------------------------
*/
ResType getResult( const char *atstart, const int maxlen )
{
ResType ret = { csUnknown, {0} };
char	*stokens[ MAX_STOKENS ] = {"M", "P", "S", "START", "SEQUENCE"};
char	*mtokens[ MAX_MTOKENS ] = {"B", "C", "D", "L", "X", "T"};
char	*etokens[ MAX_ETOKENS ] = {"GO", "DN", "UP", "NU", "ND", "ST", "\r\n"};
char	token[ MAX_TOKSIZE ]	= {'\0'};
char	csstr[ MAX_CSSTRSIZE ]  = {'\0'};
int	i=0, j=0;
char	*cp = NULL, *csp = NULL;
bool	started = false, isstok = false, ismtok = false, isetok = false;
int	iparam = 0;

if ( !atstart || maxlen < 1 )
	goto ret_unknown;

cp = (char *)atstart;
csp = csstr;
started = false;
i = j = iparam = 0;
while ( i < maxlen && *cp != ',' )
{
	/*
	 * start reading the token
	 */

	j = advance_token( cp, token, csp ); 
	if ( j == 0 ) {
		puts("*** error: garbage found or invalid pointer used");
		goto ret_unknown;   	/* invalid token */
	}

	isetok = str_in_arrstr(token, etokens, MAX_ETOKENS);
	if ( isetok )
	{
		if ( !started ) {
			puts("*** error: end of command that never started");
			goto ret_unknown;
		}
		printf( "\ntoken = %s\n", token );
		printf( "csstr = %s\n", csstr);
		return ret;
	}

	ismtok = str_in_arrstr(token, mtokens, MAX_MTOKENS);
	if ( ismtok )
	{
		if ( !started ) {
			puts("*** error: mid of command that never started");
			goto ret_unknown;
		}
	}
	else
	{
		isstok = str_in_arrstr(token, stokens, MAX_STOKENS);
		if ( started && isstok ) {
			puts("*** error: invalid command (started twice)");
			goto ret_unknown;
		}

		if ( !started && isstok )
			started = true;
		else if ( !isstok ) {
			puts("*** error: invalid token found");
			goto ret_unknown;
		}
	}

	printf( "\ntoken = %s\n", token );

	cp += j;
	csp += j;
	i += j;

	/*
	 * start reading the token's parameter
	 */

	j = advance_param( cp, token );
	if ( j == 0 ) {
		puts("*** error: invalid parameter or invalid pointer");
		goto ret_unknown;   	/* invalid parameter */
	}

	ret.params[ iparam ] = atoi( token );
	printf( "param[ %d ] = %d\n", iparam, ret.params[ iparam ] );
	iparam++;

	cp += j;
	i += j;

	*csp++ = '*';
	printf( "csstr = %s\n", csstr );

 }

/* ret.cs = hashmap[ csstr ] */
return ret;

ret_unknown:

ret.cs = csUnknown;
return ret;
}

/* -------------------------------------------------------
*
* -------------------------------------------------------
*/

int main( void )
{
char *inputdata     	= "S2C34L871GO,S32C89L100GO,S923C49L510GO";
//	char *inputdata     	= "S2C34L871GO";
int inputlen        	= strlen( inputdata );

printf( "input   : %s\n", inputdata );
printf( "inputlen: %d\n", inputlen );
getResult( inputdata, inputlen );

system("pause");
exit( EXIT_SUCCESS );
}

 

 

Ο κώδικας και άναρχος είναι, και μεγάλος, ενδεχομένως να περιέχει bugs και σίγουρα δεν είναι στα στάνταρ που θέτει η απάντηση της εταιρίας για δυναμική προσαρμογή σε γραμματικές, δίνει όμως μια 1η ιδέα περί inplace parsing.

 

Την κάνω για σπίτι, άργησα

Επεξ/σία 21 Ιανουαρίου 2012 από migf1

[Star_Light]

H χρηση της goto δεν ειναι επικύνδινη migf1?

[defacer]

Επί προσωπικών (συγκαλυμμένων) επαναλαμβανόμενων () επιθέσεων δεν απαντώ._

 

Λυπάμαι αν το βλέπεις έτσι. Δε σε ξέρω και δεν έχω τίποτα να κερδίσω από το να καταφέρομαι προσωπικά εναντίον σου, άρα μάλλον κάτι άλλο συμβαίνει.

 

Το συμπέρασμα που βγαίνει είναι ότι θα πρέπει να είσαι προσεκτικός με τον μανάβη σου, τίποτε περισσότερο και τίποτε λιγότερο από αυτό.

 

Σ' αυτό συμφωνώ, αλλά πρακτικά είναι λίγο δύσκολο να εφαρμοστεί αυτή η συμβουλή. Εδώ έχουμε μια περίπτωση οn/off: ή στέλνεις υποβολή (την καλύτερη που μπορείς), ή δεν στέλνεις.

 

Και αμα σχεδον σιγουρα ολοι αυτοι ειναι καλύτεροι απο σενα γιατι ψάχνουν υπαλλήλους?

 

Το πόσο καλοί είναι δεν έχει να κάνει με το αν θέλουν κι άλλους στην ομάδα τους ή όχι. Τώρα για το αν και κατα πόσο είναι καλύτεροι απο σένα θα σου πω το εξής: όσο καλύτερος είναι κάποιος (εμείς στη συγκεκριμένη συζήτηση) τόσο μεγαλύτερη επίγνωση έχει του πόσα πράγματα δεν ξέρει και του πόσο περιθώριο βελτίωσης υπάρχει.

 

Με άλλα λόγια, αν υποθέσουμε ότι υπάρχει μια αντικειμενική κλίμακα του πόσο σφιχτό αγγούρι είναι ο καθένας, το παλικάρι που είναι του 2 θα σου πεί ότι είναι 6 και το παλικάρι του 8 θα σου πεί επίσης ότι είναι 6. Food for thought.

 

Defacer εγω διαφωνω κάθετα με τον συγκεκριμένο τρόπο. Θα σου εξηγήσω. Ποιος μου λέει εμένα ότι αυτός που έγραψε την άσκηση την εγραψε μόνος και δεν είχε βοήθεια. Μπορεί να μην ήταν βοήθεια κώδικα αλλά απλά μια κατευθυνση απο έναν πολύ έμπειρο ποια προσέγγιση να ακολουθήσει.

 

Φυσικά και μπορεί να συμβεί αυτό, αλλά δεν μας ενδιαφέρει γιατί δεν πρόκειται να σε προσλάβουν μόνο από τον κώδικα που θα στείλεις. Εννοείται πως θα υπάρξει interview και όποιος έχει κάνει interview σε σοβαρή εταιρία στο εξωτερικό ξέρει πως σ' αυτό είναι σίγουρο ότι θα σε φτάσουν στο σημείο που θα πεις "δεν ξέρω". Οπότε εκεί φαίνεται ακριβώς πόσα απίδια βάζει ο σάκος.

 

Η δοκιμασία με τον κώδικα γίνεται απλά για να κόψει όλον αυτό τον κόσμο που θα κοβόταν έτσι κι αλλιώς στη συνέντευξη, χωρίς να χρειαστεί να περάσει από συνέντευξη (που είναι χρονοβόρα και κοστίζει).

[Star_Light]

Κανοντας λοιπον ενα summarize.

 

Με δεδομένη την άσκηση της ψευδής ή μη εταιρείας

 

Ποιο κατα την γνωμη σας ειναι το σημαντικοτερο ζήτημα για εναν προγραμματιστη σε ενα implementation - project ?

 

-Η πολυπλοκοτητα του αλγοριθμου που θα χρησιμοποιηθεί?

 

- Η διαχειριση της μνήμης ?

 

κάτι άλλο?

 

Δώστε μια γενική εικονα γιατι αν αρχισετε παλι με τους iterators και την STL θα χάσουμε τον μπούσουλα !!!

[ChRis6]

Μια γραμματικη που αναγνωριζει ( μερικες ) εντολες θα μπορουσε να ειναι :

 

S--> scene DIGITS go | scene DIGITS t DIGITS go

DIGITS --> DIGIT DIGITS | ε

DIGIT --> 1 | 2 | 3 | .....

 

Αντιστοιχα μπορουν να βγουν και αλλοι κανονες για να ικανοποιουνται οι υπολοιπες εντολες!

Το προβλημα ειναι οτι οι εναλλακτικοι κανονες του αρχικου συμβολου εχουν κοινο προθεμα( το SCENE) , οπως και οι υπολοιποι αν προστεθουν. Αρα δεν ειναι ευκολο να κανουμε parse διαβαζοντας ενα ενα τα συμβολα και να αποφασισουμε ποιος κανονας μας βολευει( θα πρεπει να κοιταζουμε πιο πολλα...).

 

Εναλλακτικα , μπορουμε να διαβαζουμε απο την εισοδο που δινεται στην processInput και να σχηματιζουμε δεξια μελη κανονων μεχρι να σχηματιστει το αρχικο συμβολο S.Λογικα με ενα σχετικα απλο αυτοματο στοιβας μπορουμε να το λυσουμε.

 

 

Με μια προχειρη ματια , δεν χρειαζεται καν να κοιταζουμε προπορευομενο συμβολο απο την εισοδο , κατι που φυσικα κανει τη δουλεια μας ακομα πιο ευκολη και φυσικα ΠΟΛΥ πιο γρηγορη.Ομως αν προσθεσουμε και τους υπολοιπους κανονες , μπορει να εχουμε καποιο προβλημα που το δεν το βλεπω αυτη τη στιγμη...

[Επισκέπτης]

Αρχικά θα ήθελα να σας ευχαριστήσω για τις απαντήσεις σας.

 

Την συγκεκριμένη εταιρεία την βρήκα μέσο recruiter (έτσι λειτουργούν συνήθως σε UK) και όταν η recruiter μου είπε ότι πρόκειται για embedded software development δεν ήμουν ιδιαίτερα θετικός αλλά..με έπεισε. Η εταιρεία σίγουρα δεν είναι fake και πρέπει μάλιστα να έχει πολύ αξιόλογο προσωπικό με αρκετούς "γνώστες" και προσφέρει πολύ καλά χρήματα (αν εξαιρέσουμε το γεγονός ότι βρίσκεται στο Λονδίνο όπου γενικά η ζωή είναι αρκετά ακριβή). Το να βάζουν τους υποψήφιους να λύσουν την άσκηση στέλνοντας την μαζί με το βιογραφικό τους είναι μια πολύ έξυπνη και αποτελεσματική προσέγγιση γιατί ναι μεν κάνουν έναν πρώτο ξεκαθάρισμα αλλά μπορούν επίσης να πάρουν και ιδέες από εναλλακτικές υλοποιήσεις (όχι απαραίτητα για όλη την άσκηση αλλά για τμήματα αυτής).

 

Δεδομένου του διαθέσιμου χρόνου που είχα έκανα ότι μπορούσα (η recruiter μάλιστα μου είπε ότι ο manager της εταιρίας της είπε ότι χρειάζεται 1-2 ώρες κάποιος για να λύσει την άσκηση !!!!!!!). Η αλήθεια είναι ότι διαβάζοντας κάποιος την εκφώνηση δεν μπορεί να καταλάβει ακριβώς τι ζητάνε. Για παράδειγμα θα μπορούσε να λέει εξαρχής ότι η υλοποίηση θα πρέπει να είναι O(1) ή O(log n) έτσι ώστε κάποιος που δεν έχει πολύ χρόνο να μην μπει καν στον κόπο να ασχοληθεί. Μία πρόταση μόνο αναφέρεται στο memory-constraint περιβάλλον και στο ότι θα δοκιμάσουν την λύση με string μεγέθους 1 MB.

 

Αυτό που αρχικά μου είχε κάνει αρνητική εντύπωση για την εταιρεία ήταν ότι δεν έδωσαν αρχικά καθόλου feedback. Η recruiter μου είπε απλά ότι ενώ η λύση ήταν καλή, υπήρχαν και καλύτερες. Αυτή η αντιμετώπιση δεν θα έλεγα ότι με ενθουσίασε για αυτό και τους έστειλα μετά απευθείας email ζητώντας feedback. Η απάντηση πάντως που μου έδωσαν αργότερα με κάλυψε πλήρως και κατάλαβα τι ζητούσαν και που έπρεπε να εστιάσω. Εγώ έδωσα ιδιαίτερη βάση στην πληρότητα (σωστή οργάνωση των κλάσεων, καθαρός κώδικας με σχόλια, documentation, test cases, integer ranges κτλ.) και όχι στην αποδοτικότητα/ταχύτητα εκτέλεσης.

 

Πάντως από την απάντηση που μου έδωσαν πάλι δεν μπορώ να πω ότι θα μπορούσα να κάνω μια υλοποίηση με O(1). Σίγουρα κάποια περιττά functions (strlen, strchr, memmove, memcpy) θα μπορούσαν να αποφευχθούν. Για παράδειγμα τώρα σκέφτηκα ότι για όλα τα commands θα μπορούσε να χρησιμοποιηθεί ένα patricia-trie (ή prefix-tree) data structure. Αυτό που δεν μπορώ να καταλάβω με τίποτα είναι πώς μπορεί να λυθεί η άσκηση χωρίς την χρήση buffer. Εάν δηλαδή γίνει κλήση της processInput() με 1 χαρακτήρα δεν πρέπει αναγκαστικά να υπάρχει ένας buffer για να τον κρατήσει μέχρις ότου γίνει η επόμενη κλήση?

 

πχ:

processInput("S", 1); // πού κρατάμε προσωρινά αυτόν τον χαρακτήρα;

...

processInput("CENE01GO", 8);

 

Εάν κάποιος έχει σκεφτεί πώς θα μπορούσε να γίνει σύμφωνα με τις προδιαγραφές που θέτει η εταιρεία ή έχει κάποια άλλη υλοποίηση θα χαιρόμουν πολύ να την συζητήσουμε.

 

Ευχαριστώ

[Star_Light]

1-2 ώρες?????

 

και πολυ βάζουνε!!!! Σε 5 λεπτάκια το χω ξεπετάξει

 

χα! Μπρικια κολλάμε? Πες εκει στα αγγλάκια πως ο κωδικας μου ειναι Ο Α Σ Η!

[migf1]

H χρηση της goto δεν ειναι επικύνδινη migf1?

Σε μη έμπειρα χέρια ή όταν χρησιμοποιείται σαν assembly ναι.

 

...

Εάν δηλαδή γίνει κλήση της processInput() με 1 χαρακτήρα δεν πρέπει αναγκαστικά να υπάρχει ένας buffer για να τον κρατήσει μέχρις ότου γίνει η επόμενη κλήση?

 

πχ:

 

Εάν κάποιος έχει σκεφτεί πώς θα μπορούσε να γίνει σύμφωνα με τις προδιαγραφές που θέτει η εταιρεία ή έχει κάποια άλλη υλοποίηση θα χαιρόμουν πολύ να την συζητήσουμε.

 

Ευχαριστώ

Δεν έχω δώσει τη δέουσα προσοχή στις ακριβείς προδιαγραφές της άσκησης (στο implementation που ζητάει εννοώ), ούτε στην απάντηση της εταιρίας. Είναι σίγουρο ότι επιβάλλει τέτοιου είδους συμπεριφορά ή π.χ. το αφήνει ελεύθερο να υποθέσεις πως μισοτελειωμένα ή scrambled command-sets γίνονται treat ως garbage, οπότε τα πετάς;

 

ΥΓ. Btw, στη ρουτίνα που ποστάρισα, το commented out hash retrieval πρέπει να είναι έξω από το loop... νομίζω δηλαδή ( το διόρθωσα).

 

Όσοι βαριούνται να το κάνουν compile, το ανέβασα και στο ideone που δείχνει το output του κώδικα στο τέλος της σελίδας.