Interview Forespørgsler til C / C / Java

[comp_freak]

Kan nogen venligst post programmeringsprocessen spørgsmål, de stod overfor under interviewet?Jeg tror det vil hjælpe medlemmer, som jeg og andre forberedelser til software relaterede interviews.

Der er bøger og website til rådighed for interviewet, men jeg vil alligevel gerne medlemmer til at sende deres spørgsmål.

 

[ITpro]

Interview Spørgsmål - Microsoft (Algoritmer og programmering)
Algoritmer og Programmering

1.Da en rektangulaer (cuboidal for puritans) kage med et rektangulært fjernes (uanset størrelse eller orientering), hvordan ville du tage den resterende del af kagen i to lige store halvdele med en lige snit af en kniv?

2.Du har givet et array indeholder både positive og negative heltal og kræves til at finde sub-array med den største sum (O (N) a la KBL).Skriv en rutine i C for ovennævnte.

3.Da en bred vifte af størrelse N, hvor hvert nummer er mellem 1 og N, afgøre, om der er nogen dubletter i det.Du har lov til at ødelægge den matrix, hvis du vil.[Jeg endte med at give omkring 4 eller 5 forskellige løsninger til dette, hver angiveligt bedre end de andre].

4.Skriv en rutine at tegne en cirkel (x ** 2 y ** 2 = r ** 2) uden at gøre brug af alle flydende komma beregninger overhovedet.[Denne ene havde mig stak i temmelig lang tid, og jeg for første gang gav en løsning, der havde floating point beregninger].

5.Da kun putchar (ingen sprintf, itoa osv.) skrive en rutinemæssig putlong at udskriver en usigneret længe i decimalgrader.[Jeg gav den indlysende løsning at tage% 10 og / 10, som giver os decimalværdi i omvendt rækkefølge.Dette kræver en bred vifte siden er vi nødt til at udskrive det i den rigtige rækkefølge.Intervieweren ikke var også glad og bedt mig om at give en løsning, som ikke behøvede array].

6.Giv en linje C udtryk for at teste, om et nummer er en effekt på 2.[Nr. sløjfer tilladt - det
er en simpel test.]

7.Da en række tegn, som udgør en sætning i ord, giver en effektiv algoritme til at vende rækkefølgen af ordene (ikke tegn) i den.

8.Hvor mange punkter er der på kloden, hvor ved at gå ved en mil syd, en mile øst og én mil nord du når det sted, hvor du startede.

9.Giv en meget god metode til at tælle antallet af dem i en "n" (fx 32) bit nummer.

ANS.Anført nedenfor er enkle løsninger, finde en løsning, der gør det i log skridt.

Iterativ

funktion iterativecount (usignerede int n)
begynd
int count = 0;
while
begynd
count = n & 0x1;
n>> = 1;
ende
tilbagevenden tæller;
ende

Sparsomme Count

funktion sparsecount (usignerede int n)
begynd
int count = 0;
while
begynd
count ;
n & = (n-1);
ende
tilbagevenden tæller;
ende

10.Hvad er de forskellige måder at gennemføre en tilstand, hvor værdien af x kan være enten et 0 eller 1.Tilsyneladende hvis da ellers løsning har et spring, når skrevet på samlesteder.if (x == 0) y = a ellers y = b Der er en logisk, aritmetiske og en datastruktur løsning på ovennævnte problem.

11.Tilbageførselsforretninger en sammenkædet liste.

12.Indsætte i en sorteret liste

13.I en X's og 0 spil (dvs. TIC TAC TOE) hvis du skriver et program til dette give en hurtig metode til at generere de bevæger sig ved computeren.Jeg mener det bør være den hurtigste måde muligt.

Svaret er, at du har brug for at lagre alle mulige konfigurationer af bestyrelsen og i bevægelse, der er forbundet med dette.Så er det koges ned til blot at få adgang til det rette element, og få den tilsvarende flytte for det.Gøre nogle analyse og gøre nogle mere optimeringsforslag i oplagring, da det ellers bliver umuligt at skaffe den nødvendige oplagring i en DOS-maskine.

14.Jeg fik to linjer forsamlings-kode, som har fundet den absolutte værdi af en række lagret i to's supplere form.Jeg var nødt til at erkende, hvad koden gjorde.Pretty simple, hvis du kender nogle forsamling og nogle fundaes om antallet repræsentation.

15.Giv en hurtig metode til at formere sig en række med 7.

16.Hvordan ville det gå om at finde ud af, hvor på at finde en bog i et bibliotek.(Du ved ikke, præcis hvordan de bøger er organiseret på forhånd).

17.Forbundet liste manipulation.

18.Tradeoff mellem tid brugt på at teste et produkt og komme ind i markedet først.

19.Hvad at teste for givet, at der ikke er tid nok til at afprøve alt, hvad du vil.

20.Først nogle definitioner på dette problem: a) en ASCII-tegn er en byte lange og de mest signifikante bit i byte er altid'0 '.b) En Kanji tegn to bytes lange.Det eneste er karakteristisk for et Kanji karakter er, at i sin første byte de mest signifikante bit er'1 '.

Nu får du en bred vifte af et tegn (både ASCII og Kanji) og et indeks i array.Indekset peger på starten af nogle tegn.Nu skal du skrive en funktion til at gøre en tilbagetasten (dvs. slette karakter inden for de givne indeks).

21.Slet et element fra en dobbelt knyttet liste.

22.Skriv en funktion til at finde dybden af et binært træ.

23.Da to strygere S1 og S2.Slet fra S2 alle de tegn, der optræder i S1 også og endelig skabe et rent S2 med de relevante tegn slettet.

24.Antages det, at sluserne er den eneste grund skyldes som blokeringer kan forekomme i et system.Hvad ville der være en idiotsikker metode til at undgå blindgyder i systemet.

25.Tilbageførselsforretninger en sammenkædet liste.

Ans: Mulige svar --

iterativ loop
Curr-> next = prev;
prev = Curr;
Curr = næste;
næste = Curr-> næste
endloop

rekursiv reverse (ptr)
if (ptr-> næste == NULL)
tilbagevenden ptr;
temp = reverse (ptr-> næste);
temp-> next = ptr;
tilbagevenden ptr;
ende

26.Skriv en lille leksikalsk analysator - intervieweren gav møntefterligninger.udtryk som "a * b" osv.

27.Ud over kommunikation koste, hvad der er den anden kilde til ineffektivitet i RPC?(svar: sammenhæng switche, overdreven buffer kopiering).Hvordan kan du optimere kommunikation?(ans: kommunikere gennem delt hukommelse på samme maskine, omledning kernen _ A Univ. af
Wash thesis)

28.Skriv en rutine, der udskriver en 2-D array i spiral orden!

29.Hvordan er læsere-forfattere problemet løst?- Ved hjælp af semaforer / ada ..osv.

30.Måder at optimere symbol tabellen oplagring i compilers.

31.En gåtur gennem gennem symbol tabel funktioner, lookup () gennemførelse osv. - intervieweren var på Microsoft C holdet.

32.En version af "Der er tre personer XYZ,
hvoraf den ene altid ligger" ..mv.

33.Der er 3 myrer ved 3 hjørner af en trekant, de tilfældigt begynde at gå i retning af et andet hjørne ..hvad er sandsynligheden for, at de ikke kolliderer.

34.Skriv en effektiv algoritme og C-koden til shuffle en pakning af kort ..denne ene var en feedback-proces, indtil vi kom op med en uden ekstra lagerplads.

35.Den if (x == 0) y = 0 mm.

36.Nogle mere bitvise optimeringsforslag på samleprocesser plan

37.Nogle generelle spørgsmål om Lex, Yacc osv.

38.Da en række t [100], der indeholder tal mellem 1 .. 99.Returnere overlappes værdi.Prøv både O og O (n-kvadrat).

39.Da en række tegn.Hvordan ville du vende det.?Hvordan ville du vende det uden brug af indeksering i array.

40.Da en sekvens af tegn.Hvordan vil du konvertere de små bogstaver tegn til store bogstaver.(Prøv at bruge bit vektor - løsninger gives i C-lib-typec.h)

41.Fundamentals af RPC.

42.Da en sammenkædet liste, som er sorteret.Hvordan vil u insertet i sorteret måde.

43.Da en sammenkædet liste Hvordan vil du vende det.

44.Giv en god datastruktur for at have n køer (n ikke fast) i en begrænset hukommelse segment.Du kan have nogle data-struktur særskilt for hver kø.Prøv at bruge mindst 90% af hukommelsesplads.

45.Må en bredde første traversal i et træ.

46.Skrive kode for at vende en sammenkædet liste.

47.Skriv, effektiv kode til ekstraktion unikke elementer fra en sorteret liste over array.f.eks (1, 1, 3, 3, 3, 5, 5, 5, 9, 9, 9, 9) -> (1, 3, 5, 9).

48.Da en bred vifte af heltal, finde contiguous sub-array med den største sum.

ANS.Kan gøres i O og O (1) ekstra plads.Scan array fra 1 til n.Husk det bedste sub-array set hidtil, og det bedste sub-array sluttede i i.

49.Da en bred vifte af længde N indeholder heltal mellem 1 og N, afgøre, om den indeholder nogen dubletter.

ANS.[Er der en O tid løsning, der kun bruger O (1) ekstra plads og ikke ødelægger den oprindelige array?]

50.Sorter en vifte af størrelse n indeholder heltal mellem 1 og K, givet en midlertidig bunden heltal array af størrelse K.

ANS.Compute kumulative tæller for heltal i hjælpeansatte array.Nu scanner den oprindelige array, roterende cykler![Kan nogen ord denne mere pænt?]

* 51.En vifte af størrelse k indeholder heltal mellem 1 og n.Du får en ekstra bunden vifte af størrelse n.Komprimere den oprindelige array ved at fjerne dubletter i det.Hvad hvis k <<n?

ANS.Kan gøres i O (k) tid
dvs. uden initialisering af hjælpeansatte array!

52.En vifte af heltal.Summen af de array vides ikke at overflow et heltal.Compute summen.Hvad nu, hvis vi ved, at heltal er i 2's komplement form?

ANS.Hvis numre er i 2's komplement, en almindelig søger loop gerne for (i = total = 0; i <n; samlede = array [i ]); vil gøre.Ikke nødvendigt at se efter overflow!

53.En række af tegn.Bytte om på rækkefølgen af ordene i den.

ANS.Skriv en rutine at vende et tegn array.Nu kalder det for givet array og for hvert ord i den.

* 54.En vifte af heltal størrelse n.Generere en tilfældig permutation af array, da en funktion rand_n (), der returnerer et heltal mellem 1 og n, begge dage inklusive, med lige stor sandsynlighed.Hvad er det forventede tidspunkt for din algoritme?

ANS."Forventet tid" skulle ringe en klokke.Til beregning af en tilfældig permutation, bruge standard algoritme for scanning array fra n downto 1, swapping i'te element med en ensartet tilfældige element <= i'te.At beregne en ensartet tilfældigt heltal mellem 1 og k (k <n), kalder rand_n () gentagne gange, indtil den returnerer en værdi i det ønskede interval.

55.En lang række henvisninger til (meget lang) strenge.Find henvisninger til de (lexicographically) mindste og største strenge.

ANS.Scan array parvis.Husk største så langt og mindste så langt.Sammenlign det største af de to strenge i den nuværende par med største så langt for at opdatere den.Og den mindste af de nuværende par med den mindste så langt for at opdatere den.For i alt <= 3n / 2 strcmp () opkald.Det
er også den nedre grænse.

56.Skriv et program til at fjerne dubletter fra et sorteret array.

ANS.int remove_duplicates (int * p, int størrelse)
(
int nuværende Indsæt = 1;
for (nuværende = 1; aktuelle <size; aktuelle )
if (p [aktuelle]! = p [indsæt-1])
(
p [indsæt] = p [aktuelle];
nuværende ;
indsætte ;
)
Elsenuværende ;

tilbagevenden indsætte;

)

57.C (hvad der er virtuel funktion? Hvad sker der, hvis der opstår en fejl i konstruktøren eller destructor. Diskussion om fejlhåndtering, skabeloner, unikke funktioner i C . Hvad er anderledes i C , (sammenlign med Unix).

58.Givet en liste over numre (fast liste) Nu gives enhver anden liste, hvordan kan du effektivt finde ud af, om der er nogen som helst element i den anden liste, der er et element i den første liste (fast liste).

59.Givet 3 linjer på samlefabrik kode: find det gør.Det var for at finde absolutte værdi.

60.Hvis du er på en båd og du kaster en kuffert, Will niveauet for vand stige.

61.Udskriv et heltal, der kun bruger putchar.Prøv at gøre det uden at bruge ekstra lagerplads.

62.Skriv C-koden til (a) at slette et element fra en sammenkædet liste (b) kører en sammenkædet liste

63.Hvad er forskellige problemer enestående for distribuerede databaser

64.Erklære en void pointer ANS.void * ptr;

65.Foretag de pointer afstemt med en 4 byte grænse på en effektiv måde ANS.Tildele pointer til en lang række, og antallet med 11 ... 1100 tilføje 4 til antallet

66.Hvad er en langt pointer (i DOS)

67.Hvad er en afbalanceret træ

68.Da en sammenkædet liste med følgende ejendom node2 er overladt barn af node1, hvis node2 <node1 andet, det er den rigtige barn.

OP
|
|
OA
|
|
OB
|
|
OC

Hvordan kan du konvertere de ovenfor forbundet liste til form uden at forstyrre ejendommen.Skriv C-kode for det.

OP
|
|
OB
/ \
/ \
/ \
O?O?

afgøre, hvor gøre A og C gå

69.Beskriv filsystemet layout i UNIX OS

ANS.beskrive boot blok, super blok, inodes og data layout

70.I UNIX, er filerne fordeles sammenhængende blokke af data

ANS.nej, de kan være fragmenteret

Hvordan er den fragmenterede data holdes styr på

ANS.Beskriv den direkte blokke og indirekte blokke i UNIX-filsystem

71.Skriv en effektiv C-koden til 'tr' program.'tr' har to kommandolinje argumenter.De er begge strenge af samme længde.tr lyder en inddatafil, erstatter hver karakter i den første streng med de tilsvarende karakter i den anden streng.f.eks.'tr abc xyz' erstatter alle 'A's med »X's,' b's ved 'y's og så videre.ANS.
a) har en vifte af længde 26.
sætte 'x' i array element corr til 'a'
sætte 'y' i array element corr til 'b'
sætte 'z' i array element corr til 'c'
sætte 'd' i array element corr til 'd'
sættes »e« i array element corr til 'e'
og så videre.

koden
while (! eof)
(
c = GETC ();
putc (array [c - 'a']);
)

72.hvad der er disk interleaving

73.hvorfor er disk interleaving vedtaget

74.givet en ny disk, hvordan kan du bestemme, hvilke interleaving er den bedste a) give 1000 læse operationer med hver type interleaving fastlægge den bedste interleaving fra statistikker

75.tegne grafen med resultater på en akse og »n« på en anden, hvor 'n' i 'n' i n-vejs disk interleaving.(et vanskeligt spørgsmål, skal besvares omhyggeligt)

76.Jeg var en C kode, og blev bedt om at finde ud af fejlen i det.Fejlen var, at han erklærede et objekt lokalt i en funktion, og forsøgt at returnere pointer til den pågældende genstand.Da formålet er lokale til den funktion,
er det ikke mere eksisterer efter retur fra funktionen.Viseren derfor er ugyldig udenfor.

77.A real life problem - En firkantet billede skæres i 16 firkanter, og de er blandet.Skriv et program for at omarrangere 16 firkanter for at få den oprindelige store kvadrat.

78.
int * a;
char * c;
* (a) = 20;
* c = * a;
printf ( "% c", * c);

Hvad er output?

79.Skriv et program til at finde, om en given m / c er big-endian eller lille-endian!

80.Hvad er et flygtigt variable?

81.Hvad er omfanget af en statisk funktion i C?

82.Hvad er forskellen mellem "malloc" og "calloc"?

83.struct n (int data; struct n * næste) node;
node * C * t;
c-> data = 10;
t-> next = NULL;
* c = * t;
hvad er virkningen af den sidste erklæring?

84.Hvis du
er fortrolig med?operatør x?y: z
du ønsker at gennemføre, at der i en funktion: int betingelse (int x, int y, int z), der kun bruger ~,!, ^, &, , |, <<,>>
Nej, hvis erklæringer, eller sløjfer eller noget andet , blot de erhvervsdrivende og den funktion bør korrekt tilbagevenden y eller z baseret på værdien af x.Du kan bruge konstanterne, men kun 8 bit konstanterne.Du kan kaste alt, hvad du ønsker.Du ikke skal bruge ekstra variabler, men i sidste ende, vil det egentlig ikke sagen
ved hjælp VARS bare gør tingene renere.Du bør være i stand til at reducere din løsning til en enkelt linje i den sidste ende selv om det kræver ikke ekstra VARS.

85.Du har en abstrakt computer, så bare glemme alt, hvad du ved om computere,
er dette en kun gør hvad jeg er ved at fortælle dig, det gør.Du kan bruge så mange variabler, som du har brug for, er der ingen negative tal, alle numre er heltal.Du kender ikke størrelsen af heltal, de kunne være uendeligt stort, så du kan ikke regne med truncating på et hvilket som helst punkt.Der er ingen sammenligninger tilladt, ikke hvis udtalelser eller lignende.Der er kun fire operationer, kan du gøre på en variabel.
1) Du kan indstille en variabel til 0.
2) Du kan indstille en variabel = en anden variabel.
3) Du kan tilvækst en variabel (kun 1), og det
er en post tilvækst.
4) Du kan sløjfe.Så hvis du skulle sige loop (v1) og v1 = 10, din sløjfe ville henrette 10 gange, men værdien i v1 ikke ville ændre så den første linje i loop kan ændre værdien af v1 uden at ændre antallet af gange De sløjfe.
Du er nødt til at gøre 3 ting.
1) Skriv en funktion, som decrements af 1.
2) Skriv en funktion, at fratrække en variabel fra en anden.
3) Skriv en funktion, der deler en variabel af en anden.
4) Se om du kan gennemføre alle 3 bruger højst 4 variabler.Betydning, du ikke gør funktion kræver nu, at du får makroer.Og på de fleste kan du få 4 variabler.Begrænsningen virkelig kun gælder for kløft, de øvrige 2 er let at gøre med 4 VARS eller derunder.Division på den anden side er afhængig af den anden 2 funktioner, så, hvis subtrahere kræver 3 variabler, derefter kløft kun har 1 variabel uændret efter en opfordring til at trække fra.Dybest set bare gøre din funktion opkald til reduceres og trække fra, så du passerer din VARS i ved henvisning, og du kan ikke erklære nogen nye variabler i en funktion, hvad du passerer i er alt, hvad det bliver.

98.Et tegnsæt, der er 1 og 2 byte tegn.Et tegn har 0 som første bit.Du skal bare holde akkumuleringsbetingelser tegnene i en buffer.Antag, at på et tidspunkt brugeren skriver en tilbagetasten, hvordan kan du fjerne tegnet effektivt.(Bemærk: Du cant lagre sidste tegn typebestemmes fordi brugeren kan skrive i vilkårligt mange backspaces)

99.Hvad er den enkle måde at tjekke, hvis summen af to usigneret heltal har resulteret i en overflow.

100.Hvordan får du repræsenterer en n-ary træ?Skriv et program til at udskrive knudepunkter i sådan et træ i bredden første ordre.

101.Skriv 'tr' program af UNIX.Påberåbes som

tr-str1-str2.Det lyder stdin og udskriver det ud til Stdout, erstatter hver forekomst af str1 med str2 .

f.eks tr-abc-xyz
at være og ikke at være <- input
til jer xnd ikke at ye <- output

Net-og Sikkerhedspolitiske

1.Hvordan bruger du RSA for både autentificering og hemmeligholdelse?

2.Hvad er ARP og hvordan fungerer det?

3.Hvad er forskellen mellem en switch og en router?

4.Nævn nogle routing protokoller?(RIP, OSPF mv.)

5.Hvordan gør man, autentificering med besked digest (MD5)?(Normalt MD bruges til at finde manipulation af data)

6.Hvordan får du implementerer et pakkefilter, der adskiller følgende tilfælde og udvælger første tilfælde og afviser anden sag.

i) En vært inde i corporate n / w gør en ftp anmodning uden vært og uden vært sender svar.

ii) en vært uden for netværket sender en ftp anmodning om at blive vært indeni.for pakkefilter i begge tilfælde kilden og destination felter vil se det samme.

7.Hvordan virker traceroute arbejde?Nu Hvordan virker traceroute sørg for, at pakken følger den samme vej, som en tidligere (med TTL - 1) sonde pakkekoblende gik i?

8.Forklar Kerberos-protokollen?

9.Hvad er digitale signaturer og smart cards?

10.Forskel mellem skønsmæssig adgangskontrol og obligatoriske adgangskontrol?

Java

1.Hvordan finder du på størrelse med en java objekt (ikke den primitive type)?

ANS.type stoebt det til strengen og finde sin s.length ()

2.Hvorfor er flere arv ikke i Java?

3.Thread t =
new Thread (); t.start (); t = null; nu hvad der vil ske med den oprettede tråd?

4.Hvordan er affaldsjournal indsamling gjort i java?

5.Hvordan kan du skrive et "ping" rutine i java?

6.Hvad er de sikkerhedsrestriktioner på applets?
Grafik

1.Skriv en funktion til at kontrollere, hvis to rektangler defineret som nedenfor overlap eller ej.struct rekte (int toppen, bot, venstre, højre R1, R2;

2.Skriv en SetPixel (x, y)-funktion, da en pointer til bitmap.Hver pixel er repræsenteret ved 1 bit.Der er 640 pixels i hver række.I hvert enkelt byte, mens bits er nummererede højre til venstre, pixels er nummererede fra venstre til højre.Undgå multiplications og spaltninger at forbedre deres resultater.

Databaser

* 1.Du, en designer ønsker at måle disk trafik dvs få et histogram viser den relative hyppighed af I / O /
sekund for hver disk blok.Bufferen pulje har b buffere og bruger LRU udskiftning politik.Disken block størrelse og buffer pool blokere størrelser er de samme.Du får en rutinemæssig int lru_block_in_position (int i) som returnerer block_id af blokken i den
i'te position på listen over blokke forvaltes af LRU.Antag position 0 er det hotteste.Du kan gentagne gange kalder denne rutine.Hvordan vil du få histogrammet du ønsker?

Tips og svar

1.Simpelthen gøre histogram [lru_block_in_position (b-1)] hyppigt ...Samplingfrekvensen bør ligge tæt på disken I / O-sats.Det kan justeres ved at huske den sidste blok ses i position b.Hvis samme, fald frekvens; hvis forskellig, stige med eksponentielle henfald osv. Og naturligvis tage sig af overflow i histogrammet.

Semaforer

1.Gennemføre en multiple-læser-single-skribent låse givet et sammenligne-og swap instruktion.Læsere ikke kan overhale venter forfattere.

Computer Architecture
1.Forklar, hvad der er DMA?
2.Hvad er pipelining?
3.Hvad er superscalar maskiner og vliw maskiner?
4.Hvad er cache?
5.Hvad er cache sammenhæng, og hvordan er det fjernet?
6.Hvad er skrive tilbage og skrive gennem cachelagrer?
7.Hvad er anderledes pipelining farer og hvordan skal de fjernes.
8.Hvad er forskellige stadier i et rør?
9.Forklare mere om filial forudsigelse i kontrollere bekæmpelse af farer
10.Giv eksempler på data farer med pseudo-kode.
11.Hvordan kan du beregne antallet af sæt givet sin måde og størrelse i en cache?
12.Hvordan er en blok fundet i en cache?
13.Resultattavle analyse.
14.Hvad er miss straf og give dine egne idéer til at fjerne det.
15.Hvordan kan du forbedre cache ydeevne.
16.Forskellige løse transportformer.
17.Computer aritmetiske med to's supplerer.
18.Om hardware og software interrupts.
19.Hvad er bus påstand og hvordan kan du fjerne det.
20.Hvad er aliasing?
21) Hvad er forskellen mellem en låsen og en flip flop?
22) Hvad er den race rundt tilstand?Hvordan kan det løses?
23) Hvad er formålet med cachen?Hvordan er det brugt?
24) Hvad er de typer af hukommelse forvaltning?Lagt efter 9 minutter:0.Classic: Hvis en bjørn vandreture en mil syd
og drejer til venstre og vandreture en mile mod øst og derefter vender tilbage igen og vandreture en mil nord og ankommer til sin oprindelige holdning, hvad der er farven på bjørnen.

ANS.Farven på bjørnen er trivielle.De mulige løsninger for at det er interessant.Ud over de trivielle Nordpolen, der er yderligere kredse nær Sydpolen.Tror det.

* 1.Da en rektangulaer (cuboidal for puritans) kage med et rektangulært fjernes (uanset størrelse eller orientering), hvordan ville du tage den resterende del af kagen i to lige store halvdele med en lige snit af en kniv?

ANS.Join the centre af den oprindelige og den fjernede rektangel.Det virker for cuboids også!BTW, jeg har fået mange spørgsmål spørger, hvorfor en horisontal skive tværs midt vil ikke gøre.Bemærk de "enhver størrelse eller orientering" i spørgsmålet!Ikke får boxed i ved den måde, du klippe din fødselsdagskage

<img src="http://www.edaboard.com/images/smiles/icon_smile.gif" alt="Smile" border="0" />

Tænk ud af kassen.

2.Der er 3 kurve.en af dem har æbler, en har appelsiner, og den anden har blanding af æbler og appelsiner.Etiketterne på deres kurve altid løgn.(dvs. hvis etiketten siger appelsiner, du er sikker på, at den ikke har appelsiner kun, det kunne være en blanding) Opgaven er at vælge en kurv og du kun vælge en frugt af den, og derefter korrekt mærke alle de tre kurve.

HINT.Der er kun to kombinationer af udlodninger, hvor alle varekurvene have forkerte etiketter.Ved at udvælge en frugt fra en mærket blandingen, er det muligt at fortælle, hvad de to andre kurve have.

3.Du har 8 bolde.En af dem er defekt og vejer mindre end andre.Du har en balance at måle bolde mod hinanden.I 2 vejninger Hvordan finder du det defekte en?

4.Hvorfor er et mandehul dække runde?

HINT.Diagonalen i et kvadrat hullet er større end i siden af en forside!

Suppleant svar: 1.Runden dækker kan transporteres af en person, fordi de kan rulles på deres kant.2.En rund dække behøver ikke roteres, så det passer i et hul.

5.Hvor mange biler er der i USA?

6.Du har en person der arbejder for dig for syv dage og en guldbarre til at betale dem.Guld bar er opdelt i syv tilsluttet stykker.Du skal give dem et stykke af guld i slutningen af hver dag.Hvis du er kun tilladt at foretage to pauser i guld bar, hvordan kan du betale din arbejdstager?

7.Et tog forlader Los Angeles på 15mph overskriften for New York.En anden tog blade fra New York på 20mph udgiftsområde for Los Angeles på samme spor.Hvis en fugl, der flyver på 25mph, blade fra Los Angeles på samme tid som toget og flyver frem og tilbage mellem de to tog, indtil de kolliderer, hvor langt vil fuglen har rejst?

HINT.Tænk relativ hastighed på togene.

8.Du har to krukker, 50 røde frisen og 50 blå frisen.En krukke vil blive pillet ved stikprøver, og derefter en marmor bliver plukket fra jar.Placere alle af skulpturerne i krukker, hvordan kan du maksimere chancerne for en rød marmor bliver plukket?Hvad er den præcise odds for at få en rød marmor bruger din ordningen?

9.Forestil dig, at du står foran et spejl, vender det.Forhøj din venstre hånd.Løft din højre hånd.Kig på dine overvejelser.Når du hæve din venstre hånd dine overvejelser gør hvad der synes at være sin højre hånd.Men når du hælde dit hoved op, dine overvejelser også gør, og ikke synes at hælde sit hoved ned.Hvorfor er det, at spejlet ser ud til at vende til venstre og højre, men ikke op og ned?

10.Du har 5 glas piller.Hver pille vejer 10 gram, undtagen for forurenet piller i en krukke, hvor hver pille vejer 9 gm.Da en skala, hvordan kan du fortælle hvor jar havde forurenet piller på blot en måling?

ANS.1.Markér de krukker med numrene 1, 2, 3, 4 og 5.
2.Tag 1 pille fra jar 1, tage 2 piller fra jar 2, tage 3 piller fra jar 3, tage 4 piller fra jar 4 og tage 5 piller fra jar 5.
3.Sætte dem alle på skalaen på en gang og tage måling.
4.Nu trækkes måling fra 150 (1 * 10 2 * 10 3 * 10 4 * 10 5 * 10)
5.Resultatet vil give dig den jar tal, som har forurenet pille.

11.Hvis du havde en uendelig forsyning af vand og en 5 Kvart og 3 Quart spand, hvordan ville du måle præcis 4 quarts?

12.Du har en spand gelée bønner.Nogle er røde,
andre er blå, og nogle grønne.Med dine øjne lukket, udvælge 2 i samme farve.Hvor mange har du til at få fat i for at være sikker på, at du har 2 af samme?

13.Hvilken vej skal nøglen igen i en bil døren for at låse den op?

14.Hvis du kan fjerne nogen af de 50 stater, som staten ville det være og hvorfor?

15.Der er fire hunde / myrer / personer på fire hjørner i et kvadrat med enhed afstand.På samme instant dem alle begynder at køre med enhed hastighed i retning af den person, på deres urretningen og altid vil køre i retning af dette mål.Hvor lang tid tager det for dem at mødes og hvor?

HINT.De vil mødes i midten, og den distance, der er af dem, er uafhængig af den vej, de rent faktisk tager (en spiral).

16.(fra Tara skur) En helikopter dråber to tog,
der hver på en faldskærm, på en lige uendelig jernbanelinjen.Der er en udefineret afstanden mellem de to tog.Hver ansigter samme retning, og efter landing, faldskærmen knyttet til hvert tog falder til jorden ved siden af toget og udskiller.Hvert tog har en mikrochip, der kontrollerer dens bevægelse.De jetoner, er identiske.Der er ingen måde for togene at vide, hvor de er.Du er nødt til at skrive koden i chip at gøre togene støder ind i hinanden.Hver linje kode tager en enkelt taktcyklus at fuldbyrde.
Du kan bruge følgende kommandoer (og kun disse);
MF - flytter toget frem
MB - flytter toget baglæns
IF (P) - betinget, der
er tilfredse, hvis toget er ved siden af en faldskærm.Der er ingen "og derefter" til dette, hvis erklæring.
GOTO

ANS.
A: MF
IF (P)
GOTO B
GOTO A
-----
B: MF
GOTO B
Forklaring: Den første linje simpelthen får dem væk fra faldskærme.Du har brug for at få de tog ud for deres faldskærme så tilbage toget kan finde forsiden togets faldskærm, skaber en særlig betingelse, der vil give det mulighed for at bryde ud af den kode, de begge nødt til at følge oprindeligt.De både sløjfe gennem A: indtil tilbage toget konstaterer forsiden togets faldskærm,
hvorefter den går til B: og bliver hængende i at sløjfe.De forreste toget har stadig ikke fundet en faldskærm, så det holder i en sløjfe.Fordi hver enkelt linje kode tager et "taktcyklus" at udføre, det tager længere tid at udføre en sløjfe end B loop derfor bagsiden tog (kører i B-loop) vil tage op til de forreste toget.
Knyttet lister

* 86.Under hvilke omstændigheder kan en slette et element fra et enkeltvis forbundet listen i konstant tid?

ANS.Hvis listen er cirkulær og der er ingen henvisninger til knudepunkter i listen fra andre steder!Bare kopiere indholdet af den næste node og slette de næste node.Hvis listen er ikke cirkulære, vi kan slette alle undtagen den sidste node bruger denne idé.I så fald, markere den sidste node som dummy!

* 87.Da en enkeltvis knyttet liste, fastslå, om det indeholder en sløjfe eller ej.

ANS.(a) Begynd at vende listen.Hvis du når hoved, gotcha!der er en sløjfe!
Men dette ændrer listen.Så reverse listen igen.
(b) Opretholde to henvisninger,
som i første omgang pege på hovedet.Forhånd en af dem en node på et tidspunkt.Og den anden en, to noder på et tidspunkt.Hvis sidstnævnte overhaler den tidligere til enhver tid, der er en sløjfe!

p1 = p2 = hoved;

do (
p1 = p1-> next;
p2 = p2-> next-> next;
) Samtidig (P1! = P2);

88.Da en enkeltvis knyttet liste, udskrive indholdet i omvendt rækkefølge.Kan du gøre det uden brug af ekstra plads?

ANS.Start vende listen.Gøre det igen, trykning indholdet.

89.Da et binært træ med noder, udskrive værdierne i pre-order/in-order/post-order uden brug af ekstra plads.

90.Tilbageførselsforretninger en enkeltvis knyttet liste rekursivt.Funktionen prototype er node * reverse (node *);

ANS.

node * reverse (node * n)
(
node * m;

if (! (n & & n -> næste))
tilbagevenden n;

m = reverse (n -> næste);
n -> Næste -> Næste = n;
n -> next = NULL;
tilbagevenden m;
)

91.Da en enkeltvis knyttet liste, finde midten af listen.

HINT.Brug enkelt og dobbelt pointer hoppe.Opretholde to henvisninger,
som i første omgang pege på hovedet.Forhånd en af dem en node på et tidspunkt.Og den anden en, to noder på et tidspunkt.Når det dobbelte når udgangen, det indre er i midten.Dette er ikke asymptotically hurtigere, men synes at tage mindre skridt end at gå gennem listen to gange.

Bit-manipulation

92.Vende bits i en usigneret heltal.

ANS.

# define reverse (x) \
(x = x>> 16 | (0x0000ffff & x) <<16, \
x = (0xff00ff00 & x)>> 8 | (0x00ff00ff & x) <<8, \
x = (0xf0f0f0f0 & x)>> 4 | (0x0f0f0f0f & x) <<4, \
x = (0xcccccccc & x)>> 2 | (0x33333333 & x) <<2, \
x = (0xaaaaaaaa & x)>> 1 | (0x55555555 & x) <<1)

* 93.Compute antallet af dem i en usigneret heltal.

ANS.

# define count_ones (x) \
(x = (0xaaaaaaaa & x)>> 1 (0x55555555 & x), \
x = (0xcccccccc & x)>> 2 (0x33333333 & x), \
x = (0xf0f0f0f0 & x)>> 4 (0x0f0f0f0f & x), \
x = (0xff00ff00 & x)>> 8 (0x00ff00ff & x), \
x = x>> 16 (0x0000ffff & x))

94.

Compute the discrete log of an unsigned integer.

ANS.

#define discrete_log(h) \
(h=(h>>1)|(h>>2), \
h|=(h>>2), \
h|=(h>>4), \
h|=(h>> <img src="http://www.edaboard.com/images/smiles/icon_cool.gif" alt="Cool" border="0" /> , \
h|=(h>>16), \
h=(0xaaaaaaaa&h)>>1 (0x55555555&h), \
h=(0xcccccccc&h)>>2 (0x33333333&h), \
h=(0xf0f0f0f0&h)>>4 (0x0f0f0f0f&h), \
h=(0xff00ff00&h)>>8 (0x00ff00ff&h), \
h=(h>>16) (0x0000ffff&h))

If I understand it right, log2(2) =1, log2(3)=1, log2(4)=2..... But this macro does not work out log2(0) which does not exist! How do you think it should be handled?

* 95. How do we test most simply if an unsigned integer is a power of two?

ANS. #define power_of_two(x) \ ((x)&&(~(x&(x-1))))

96. Set the highest significant bit of an unsigned integer to zero.

ANS. (from Denis Zabavchik) Set the highest significant bit of an unsigned integer to zero
#define zero_most_significant(h) \
(h&=(h>>1)|(h>>2), \
h|=(h>>2), \
h|=(h>>4), \
h|=(h>> <img src="http://www.edaboard.com/images/smiles/icon_cool.gif" alt="Cool" border="0" /> , \
h|=(h>>16))

97. Let f(k) = y where k is the y-th number in the increasing sequence of non-negative integers with the same number of ones in its binary representation as y, eg f(0) = 1, f(1) = 1, f(2) = 2, f(3) = 1, f(4) = 3, f(5) = 2, f(6) = 3 and so on. Given k >= 0, compute f(k)