interview practice
1.0.0
Wenn Sie in einem Unternehmen wie Google oder Amazon (und vielen anderen ...) ein Interview haben, von dem Sie wissen, dass sie technische Fragen stellen werden, sind Sie zu einem guten Ort gekommen, um sich vorzubereiten! In diesem Readme sind eine Reihe von Fragen der technischen Informatik aufgeführt, die alle in separaten Paketen/Klassendaten beantwortet werden. Jede Lösung kann auch eine zugehörige Demo -Datei enthalten, die eine Hauptklasse und Demo dieser Lösung enthält. Sie wird empfohlen, mit diesen herumzuspielen und alle Eckfälle zu erfahren!
Es ist nicht ohne Grund so organisiert! Es wird empfohlen, ein gutes Verständnis für verschiedene Datenstrukturen und -sassen und -suche zu haben, bevor sie zu allgemeinen Interviewproblemen übergehen. Dies sind Ihre Tools, um verschiedene Interviewprobleme zu verstehen und zu lösen. Alle Arten zu machen ist optional, aber es wird empfohlen, dass Sie ein gutes Verständnis für mindestens One O (NLOGN) haben.
Diese Readme wurde so konzipiert, dass sie einfach und schnell mit Control-F durchsucht. Wenn Sie schnell in die ReadMe irgendwohin springen möchten, suchen Sie einfach (mit Control-F) in quadratischen Klammern nach. Stellen Sie sicher, dass Ihre Suche nicht fallsempfindlich ist!
Schnelle Suchoptionen:
Wenn Sie Fehler in meinem Code finden und Fehler geben, versuchen Sie, sie als Übung zu reparieren! Sobald Sie der Meinung sind, dass Sie eine funktionierende Implementierung haben, schießen Sie mir eine Pull -Anfrage, ich schätze die freundliche Hilfe immer :) Wenn Sie Ideen für Dinge haben, die Sie hinzufügen möchten, zögern Sie nicht, sie zu codieren und mir eine Pull -Anfrage zu drehen. Bitte halten Sie Ihren Code sauber - sauberer Code oder keinen Code. Ich schätze immer wieder Hilfe und danke im Voraus :)
public Queue ( int maxSize )
public void enqueue ( int data )
public int dequeue ()
public int peek ()
public boolean isFull ()
public boolean isEmpty ()
public String toString () public StackQueue ()
public StackQueue ( Type [] list )
public void enqueue ( Type obj )
public Type dequeue ()
public boolean isEmpty () public LinkedList ()
public Node < Type > find ( Type data )
public int getLength ()
public void addDataAtHead ( Type data )
public void addNodeAtHead ( Node < Type > nextNode )
public Node < Type > deleteHead () throws ...
public String toString ()Tun Sie genau das Gleiche wie in Frage 2, verwenden Sie jedoch eine Doublelinkedlist. Sie benötigen eine neue Knotenklasse
Umgekehrt eine SinglylinkedList, sollte der Method -Header wie:
public void reverse () // put this method inside your LinkedList class public boolean cyclic () // put this method inside your LinkedList class public Stack ()
public Type pop ()
public void push ( Type data )
public Type peek ()
public String toString () public Heap ( int initialSize )
public Heap ( int [] initialValues )
public void add ( int integer )
public boolean delete ( int integer )
public int peek ()
public int pop ()
public boolean contains ( int integer )
public boolean isEmpty ()
public int size () public PriorityQueue ( int initialSize )
public PriorityQueue ( int [] list )
public void enqueue ( int data )
public int dequeue ()
public int peek ()
public boolean isEmpty () public BinarySearchTree ( Integer data )
public BinarySearchTree ()
public TreeNode find ( Integer searchKey )
public void insert ( TreeNode insertNode )
public boolean delete ( Integer searchKey ) // return true if object deleted, false if object not in list
public void inOrderTraversal ()
public void preOrderTraversal ()
public void postOrderTraversal ()
public TreeNode smallest ()
public TreeNode biggest ()Analysieren Sie die Geschwindigkeit für alle Arten mit Big-O-Notation. Programmieren Sie alle möglichen als statischen Methoden in einzelnen Klassen, die jeweils eine Hauptmethode haben, die die Sortierung testet
private static void bubbleSort ( int [] list ) private static void selectionSort ( int [] list ) private static void insertionSort ( int [] list ) private static void mergeSort ( int [] list ) private static void quickSort ( int [] list ) private static void shellSort ( int [] list ) private static void countingSort ( int [] list , int startRange , int endRange ) private static void radixSort ( int [] list ) private static void bucketSort ( int [] list ) private static void heapSort ( int [] list ) private static int binarySearchArray ( int [] list , int searchKey )[P1] Implementieren Sie die Fakultät rekursiv. Implementieren Sie es erneut, verwenden Sie diesmal die Schwanzrekursion. Was ist die Schwanzrekursion? Ist Java für die Schwanzrekursion optimiert?
[P2] Lösen Sie die berühmten Türme des Hanoi -Problems. Ist es Schwanz rekursiv? Warum oder warum nicht?
[P3] Angenommen, ich gebe Ihnen eine Reihe von Zahlen, sagen wir, sie repräsentieren die Aktienkurse und finden Sie mir das meiste Geld, das Sie an diesem Tag verdienen können, indem Sie eine einzelne Aktie kaufen und verkaufen. Wenn die Aktien den ganzen Tag sinken, sollten Sie mir den geringsten Geldbetrag finden, den ich an diesem Tag verlieren könnte. Der Methode -Header sollte aussehen wie:
private static int bestStockTrade ( int [] stockPrices ) throws ...[P4] Geben Sie ein Array von Ganzzahlen, z. B. [1, 2, 3, 4], ein Array zurück, bei dem Sie bei jedem Index das Ergebnis des Multiplizierens mit allen anderen Werten erhalten. Z.B. [1, 2, 3, 4] -> [2x3x4, 1x3x4, 1x2x4, 1x2x3]. Verwenden Sie keine Abteilung. Der Methode -Header sollte aussehen wie:
private static int [] productAllButMe ( int [] data ) throws ...[P5] Bei einer Reihe von Ganzzahlen können Sie das maximale Produkt durch Multiplizieren von 3 der Ganzzahlen erhalten. Der Methode -Header sollte aussehen wie:
private static int productOfThree ( int [] data ) throws ...[P6] Schreiben Sie eine Reihe von Zahlenpaaren, die eine Funktion schreiben und sehen, welche Teile der Zeitleiste abgedeckt sind. Z.B. Angesichts des Arrays von [(1,4), (2,7), (9,11), (1,3), (12,14)] -> [(1,7), (9,14)]. Sie könnten sich vorstellen, dass dies nützlich ist, wenn wir eine Liste aller Zeitplan für jeden Zeitpunkt hätten und sehen wollten, wann alle frei waren. Verwenden Sie für die tatsächliche Darstellung der Eingabe die folgende Klasse:
class Schedule {
public int startTime ;
public int endTime ;
public Schedule ( int startTime , int endTime ) {
this . startTime = startTime ;
this . endTime = endTime ;
}
@ Override
public String toString () {
return "(" + startTime + " , " + endTime + ")" ;
}
}Für den Methodenheader:
private static List < Schedule > scheduler ( List < Schedule > schedules )[P7] Angesichts einer Reihe von Personen, bei denen eine Person durch eine Startzeit und die Endzeit für ihre Arbeitsverschiebung dargestellt wird, geben Sie die kürzeste Liste der Personen zurück, bei denen diese Menschen während ihrer Schicht alle anderen Menschen sehen. Wenn diese Personen beispielsweise (1, 2), (2, 10), (5, 6) gegeben sind, sollten Sie zurückkehren (2, 10), weil diese Person während seiner Schicht alle anderen sieht. Wenn angegeben (1, 5), (4, 10), (2, 3), (11, 13) -> (1, 5), (11, 13). Verwenden Sie für die tatsächliche Darstellung der Person die folgende Klasse:
class Person {
public int startTime ;
public int finishTime ;
public Person ( int startTime , int finishTime ) {
this . startTime = startTime ;
this . finishTime = finishTime ;
}
@ Override
public String toString () {
return "(" + startTime + " , " + finishTime + ")" ;
}
}Für den Methodenheader:
private static List < Person > selectPeople ( List < Person > people ) throws ...[P8] Bei einer Reihe von ganzen Zahlen, bei denen es garantiert eine Nummer gibt, die nicht dupliziert wird, finden Sie diese Zahl. Beachten Sie, dass in dieser Liste der gekoppelten Nummern nur 1 Zahl kein Duplikat hat und jede andere Zahl eins und nur ein Duplikat hat. Mögliche Eingaben: [1, 2, 2, 3, 3, 4, 4], [2], [3, 7, 3] usw.
Für den Methodenheader:
private static int uncoupledInteger ( int [] list ) Extrapunkte: Können Sie es in konstantem Speicher und linearer Zeit tun?
[P9] Überprüfen Sie, ob die Zeichenfolge eine Zeichenfolge, die voller Grenzwerte ist, ausgeglichene Grenzwerte hatte. Die einzigen Grenzwerte, über die wir uns in diesem Problem Sorgen machen werden, sind Folgendes: [] {} (). Es gibt keine anderen Zeichen in dieser Zeichenfolge außer den Abgrenzern. Die folgenden Zeichenfolgen sind ausgeglichen und sollten wahr zurückgeben: "", "()", "{} () []", "([{}])". Die folgenden Zeichenfolgen sind nicht ausgeglichen und sollten false zurückgeben: "[", "{}}", "{{]}", "{[}]"
Für den Methodenheader:
private static boolean balancedDelimiters ( String delimiters ) [P10] Machen Sie eine Reihe von Ganzzahlen und eine Zielsumme eine Funktion, die trifft, wenn die Zielsumme eine Summe von zwei der Ganzzahlen im Array ist. Zum Beispiel sollte das Array [1, 2, 3, 4, -100, 0, 0] und das Ziel 5 true zurückkehren, da 4 + 1 = 5. Beachten Sie, dass die Antwort falsch zurückgibt, wenn das gleiche Array gegeben wurde, das Ziel jedoch 8 war. Sie können sich nicht selbst eine Ganzzahl hinzufügen, um das Ziel zu erzeugen. Sie müssen zwei separate ganze Zahlen finden. Beachten Sie, dass diese beiden getrennten Ganzzahlen den gleichen Wert haben könnten, z. Wenn das gleiche Array angegeben wurde, aber 0 als Ziel angegeben wurde, sollte es true zurückkehren, da es im Array zwei Ganzzahlen gibt, die auf 0 sind - die 0 im 5. Index und die 0 im 6. Index.
Für den Methodenheader:
private static boolean targetSummable ( int [] array , int target ) 
