Obiektywna odpowiedź:
Podczas gdy moja początkowa odpowiedź na to pytanie opierała się na moich doświadczeniach empirycznych jako wkrótce studenta CS oraz na mojej przewidywanej opinii o typach ludzi, z którymi chciałem pracować w dziedzinie CS. W rzeczywistości istnieje obiektywna odpowiedź (w odniesieniu do subiektywnych opinii stowarzyszeń obliczeniowych ACM SIGCSE i IEEE). Co 10 lat ACM i organy IEEE współpracują w ramach wspólnej publikacji, która szczegółowo przedstawia sugestie dotyczące programu studiów licencjackich z zakresu informatyki w oparciu o profesjonalną wiedzę o stanie branży komputerowej. Więcej informacji można znaleźć na stronie cs2013.org . Komitet publikuje raport końcowy zawierający listę rekomendacji programowych .
Mimo to nadal uważam, że moja lista jest całkiem dobra.
Oryginalna odpowiedź poniżej.
Co powinienem wiedzieć?
Minimum
Uważam, że biegły programista powinien posiadać wiedzę z zakresu informatyki na poziomie co najmniej licencjackim. Pewnie, możesz być skuteczny w wielu zawodach, mając tylko niewielki podzbiór informatyki, ze względu na solidną społeczność, na której opiera się CS, i zawężone ukierunkowanie większości profesjonalnych stanowisk. Ponadto wiele osób będzie dalej specjalizować się po studiach licencjackich. Nie uważam jednak, aby były pretekstem, aby nie być wtajemniczonym w podstawową wiedzę na temat CS.
Aby odpowiedzieć na pytanie tytułowe, oto, co powinien wiedzieć student studiów licencjackich (podstawa programisty) po ukończeniu studiów:
Struktury danych
- Reprezentacja danych maszynowych
- Jedynki, dopełnienie dwóch i powiązana arytmetyka
- Słowa, wskaźniki, zmiennoprzecinkowe
- Dostęp do bitów, przesuwanie i manipulowanie
- Połączone listy
- Tabele skrótów (mapy lub słowniki)
- Tablice
- Drzewa
- Półki na książki
- Kolejki
- Wykresy
- Bazy danych
Algorytmy
- Sortowanie:
- Sortowanie bąbelkowe (aby dowiedzieć się, dlaczego jest źle)
- Sortowanie przez wstawianie
- Scal sortowanie
- Szybkie sortowanie
- Sortowanie według stylu Radix, sortowanie zliczające i sortowanie kubełkowe
- Sortuj sterty
- Sortowanie Bogo i kwantowe (=
- Badawczy:
- Wyszukiwanie liniowe
- Wyszukiwanie binarne
- Głębokie pierwsze wyszukiwanie
- Szerokość Pierwsze wyszukiwanie
- Manipulacja ciągiem
- Iteracja
- Tree Traversal
- Lista Traversal
- Funkcje mieszania
- Konkretna implementacja tabeli mieszania, drzewa, listy, stosu, kolejki, tablicy i zestawu lub kolekcji
- Algorytmy planowania
- Przejście i manipulacja systemem plików (na poziomie i- węzła lub równoważnego).
Wzorce projektowe
- Modularyzacja
- Fabryka
- Budowniczy
- Singel
- Adapter
- Dekorator
- Flyweight
- Obserwator
- Iterator
- Stan [maszyna]
- Kontroler widoku modelu
- Gwintowanie i równoległe wzorce programowania
Paradygmaty
- Tryb rozkazujący
- Obiektowy
- Funkcjonalny
- Deklaracyjny
- Programowanie statyczne i dynamiczne
- Znaczniki danych
Teoria złożoności
- Przestrzenie złożoności
- Obliczalność
- Regularne, bezkontekstowe i uniwersalne maszyny Turinga kompletne języki
- Wyrażenia regularne
- Liczenie i podstawowa kombinatoryka
Poza
Aby przejść do pytania, o które pytasz w dalszej części pytania, jeśli znasz powyższe, powinieneś być w stanie łatwo zidentyfikować odpowiedni wzorzec, algorytm i strukturę danych dla danego scenariusza. Należy jednak pamiętać, że często nie ma najlepszego rozwiązania. Czasami może być konieczne wybranie mniejszego zła lub nawet wybranie jednego z dwóch równie realnych rozwiązań. Z tego powodu potrzebujesz ogólnej wiedzy, aby móc bronić swojego wyboru przed rówieśnikami.
Oto kilka wskazówek dotyczących algorytmów i struktur danych:
- Wyszukiwania binarnego można (i należy) używać tylko do posortowanych danych.
- Rodzaje stylów Radix są niesamowite, ale tylko wtedy, gdy masz sortowane skończone klasy rzeczy.
- Drzewa nadają się do prawie wszystkiego, podobnie jak Stoły Hash. Funkcjonalność tabeli skrótów można ekstrapolować i wykorzystać do rozwiązania wielu problemów kosztem wydajności.
- Tablice mogą być używane do tworzenia kopii zapasowych większości struktur danych wyższego poziomu. Czasami „struktura danych” to po prostu sprytna matematyka do uzyskiwania dostępu do lokalizacji w tablicy.
- Wybór języka może być różnicą między wyciąganiem włosów lub przejeżdżaniem przez problem.
- Tabela ASCII i tablica zawierająca 128 elementów tworzą domyślną tablicę skrótów (=
- Wyrażenia regularne mogą rozwiązać wiele problemów, ale nie można ich używać do analizowania HTML .
- Czasami struktura danych jest równie ważna jak algorytm.
Niektóre z powyższych mogą wydawać się bezmyślne, a niektóre mogą wydawać się niejasne. Jeśli chcesz, żebym zagłębił się bardziej szczegółowo, mogę. Ale mam nadzieję, że gdy napotkamy bardziej konkretne pytanie, takie jak: „Zaprojektuj funkcję, która liczy liczbę wystąpień każdego znaku w ciągu znaków”, możesz spojrzeć na wskazówkę dotyczącą tabeli ASCII i 128 elementów tworzących czysty ukryty skrót tabele odpowiedzi.
Opierając się na tych pomysłach, zaproponuję odpowiedź na problem z szafką opisany w twoim pytaniu.
Odpowiedz na problem związany z pytaniem.
To może nie być najlepsza odpowiedź na twoje pytanie, ale myślę, że jest to interesujące, które nie wymaga niczego zbyt złożonego. I z pewnością pokona złożoność czasową korzystania z kolejki lub stosu, które wymagają liniowego czasu, aby ustalić, czy szafka jest wolna, czy nie.
Masz 0-999 szafek. Teraz, ponieważ masz stałą liczbę szafek, możesz łatwo wyobrazić sobie funkcję haszującą bez kolizji w zakresie 0-999. Ta funkcja to po prostu h (x) = x mod 1000. Teraz [koncepcyjnie] zbuduj tablicę skrótów z kluczami całkowitymi i zawartością tablicy elementów 1000 jako wartości. Jeśli klient chce zarezerwować szafkę 78 do użytku, po prostu wstaw 78 do funkcji skrótu (zwracając 78), a następnie dodaj tę liczbę do podstawowego wskaźnika tablicy - przechowując prawdziwą wartość w miejscu wskazanym przez wartość przesunięcia . Podobnie, jeśli chcesz sprawdzić, czy 78 jest w użyciu, po prostu przeczytaj wartość przechowywaną w tej lokalizacji i sprawdź wartość true.
To rozwiązanie działa w trybie ciągłym dla wyszukiwania i przechowywania, w przeciwieństwie do przechowywania i wyszukiwania dziennika (n) w przypadku kolejki priorytetowej wspieranej przez drzewo binarne. Opis jest celowo obszerny, dzięki czemu można zobaczyć, że wyższe pojęcia sprowadzane są do wydajnego algorytmu.
Teraz możesz zapytać: co, jeśli muszę znać wszystkie dostępne szafki, czy kolejka priorytetowa nie byłaby lepsza? Jeśli w kolejce priorytetowej znajduje się k dostępnych szafek, iteracja nad wszystkimi z nich zajmie k kroków. Ponadto, w zależności od implementacji kolejki priorytetowej, może być konieczne przebudowanie kolejki priorytetowej, gdy spojrzysz na to wszystko ... co wymagałoby kroków k * log (k): (k <1000). W rozwiązaniu macierzowym musisz tylko iterować tablicę 1000 elementów i sprawdzić, które są otwarte. Możesz również dodać dostępną lub używaną listę do implementacji, aby sprawdzić tylko w czasie k.