interviews #1

[Volkan Uzun]

netten buldugum veya kendi interviewlarimda karsilastigim bazi sorulari tek tek yazmaya ve ilgi olursada toplayip tek makale yapmak isterim cevaplariyla.
soruyu sorup sonra digerlerinden cevap beklicem, ve sonrada dogru cevabi her beraber buluruz.
dedigim gibi ilgi olursa devam ederim :)
ilk iki soru :
--------------------
1. single linked listi terse ceviren function i yazin
2. istanbulda kac km yol var.

[Euclides]

2. istanbulda kac km yol var.
bu soru hileli mi ? :D

[Volkan Uzun]

yoo degil microsoft interviewlerde cok sik cikan soru tipi. dogru cozumden cok nasil gidilecegi onemli
los angelesta kactane benzin istasyonu var gibi bir soru.

[sckz]

kac km yol mu var.. nasıl oluyor o ? hadi kac benzin istasyonu nu anlarım da.. bu garip bi soru..

[Volkan Uzun]

ok bu tip soruyla ilk defa karsilasan icin ornek bir cozum, dedigim gibi tam dogru olmasi gerekmiyor, algoritmik dusunce bekliyorlar.
cozumlerden biri su olabilir mi :
istanbul nufusu 15 milyon
bir aile 4 kisi, o zaman yaklasik 4 milyona yakin aile var
her aile bir dairede yasiyor
bir binada yaklasik 8 daire var ( 4 katli varsayiyorum )
o zaman 500,000 bina var
her bianin onunden arkadasindan yol gecer
bir bina genisligi 20 metre olsak
500,000 * 20 /1000 = 10,000 km
2 tarafli = 5000 km yol.
bunun gibi.
peki sckz, benzin istasyonunu nasil bulursun :)

[sckz]

tek tek sayarım.. 8).. bence daha kolay :hiohahoha

aslında kastetmek istedigim o degildi.. km yi biz birşeyin adet ini bulmak icin kullanmayız.. uzunluk icin kullanırız.. kac km yol var demek biraz garip geldi de.. belki de yanılıyorum dur..

[Volkan Uzun]

single linked list soruus ?

[sckz]

single linked list şu mu oluyor : sadece tek bi yönü gösteren işaretçi si olan linked list mi.. yani tuttuğumuz yapi icinde sadece sonraki elemanı gösteren işaretçi var (onceki ni gosteren yok).. bu mudur single linked-list.. bildigim kadarıyla stl deki list böle deil.. çünkü iteratoru çift yönlü hareket edebiliyor..

su an uykuluyum sabah sacmalamadan daha duzgun cevaplar verebilirim sanırım..

[Volkan Uzun]

evet single list budur
herkes kendinden sonrakini gosteriyor.
en sondaki null i gosteriyor.
bu tip sorularda kelimeler cok onemli
mesela function demisim, buraya gelen parametre cok onemli. ayrica linked listenin ortasindan bir yerden bisi gondersemde calismali programin
mesela
1,2,3,4,5,6,7,8,9,10 olsun
pointer olarak 5. adresinide gondersem
10,9,8,7,6,5,4,3,2,1 cikartsin :)

[sckz]

şimdi bu mülakatta olaya stl karıstırmaya izin var mı.. (gerci olsa ne guzel olur reserve() var)

template <class T>
singleLinkedList<T> my_reverse(singleLinkedList<T> & cevrilecek)
{
singleLinkedList<T> tersHali;
copy(cevrilecek.rbegin(), cevrilecek.rend(), back_inserter(tersHali));
/* ya da copy(cevrilecek.begin(), cevrilecek.end(), front_inserter(tersHali)); */
return tersHali;
}

böle bişey i mülakatta versek kabul ederler mi ? 8).. (dikkat stl işin içine stl girmiş olsa bile.. burda isimleri geçen şahıslar (sınıflar, nesneler vs vs) hayal ürünüdür..)

sonradan degistirme :
ilk copy cok aptalca oldu.. rbegin(), rend() kullanabilmek icin iki yone de isaretci olmalı...

[Volkan Uzun]

hayir structure dusun yada class
linked lisste.
mesela struct list;
list->next sonrakini gostersin.

[sckz]

Daha önce yazdığım aptalca bişiye bi takım eklemeler yaptım ama yine biçok hata vardır.. çünkü ben yazdım :

(ilgili fonksiyon ters_cevir (biliyorum cok basit oldu ama elimden bu kadar geliyo gecenin bu vakti.. zaten tek gozum acık bakıyorum monitore) (senin verdigin bazı sartlara uymuyor))

SingleLinkedList.h :
#include <iostream>

template <class T>
class Link
{
public :
T veri;
Link * sonraki;
};

template <class T>
class SingleLinkedList
{
public :
SingleLinkedList() : bas_(NULL), son_(NULL), elemanSay_(0) {}
~SingleLinkedList();

void sona_ekle(T veri);
void basa_ekle(T veri);
size_t kac_tane();
void goster(); // bu fonksiyonu kullanan Eşşektir (sınıfın amacına aykırı)..
T operator [] (int n); // bu fonksiyonu kullanan daha da bi Eşşektir..
void ters_cevir();
protected :
Link<T> * bas_;
Link<T> * son_;
size_t elemanSay_;
};

template <class T>
SingleLinkedList<T>::~SingleLinkedList()
{
Link<T> * simdiki = bas_;
Link<T> * sonraki = NULL;
while (simdiki)
{
sonraki = simdiki->sonraki;
delete simdiki;
simdiki = sonraki;
}
}

template <class T>
void SingleLinkedList<T>::sona_ekle(T veri)
{
Link<T> * newLink = new Link<T>;
newLink->veri = veri;
newLink->sonraki = NULL;
if (NULL == bas_)
{
bas_ = newLink;
son_ = newLink;
}
else
{
son_->sonraki = newLink;
son_ = newLink;
}
++elemanSay_;
}

template <class T>
void SingleLinkedList<T>::basa_ekle(T veri)
{
Link<T> * newLink = new Link<T>;
newLink->veri = veri;
newLink->sonraki = bas_;
bas_ = newLink;
if (NULL == son_)
{
son_ = newLink;
}
++elemanSay_;
}

template <class T>
void SingleLinkedList<T>::goster()
{
Link<T> * simdiki = bas_;
while (simdiki != NULL)
{
std::cout << simdiki->veri << ' ';
simdiki = simdiki->sonraki;
}
}

template <class T>
size_t SingleLinkedList<T>::kac_tane()
{
return elemanSay_;
}

template <class T>
T SingleLinkedList<T>::operator [] (int n)
{
Link<T> * simdiki = bas_;
while (n--) simdiki = simdiki->sonraki;
return simdiki->veri;
}

template <class T>
void SingleLinkedList<T>::ters_cevir()
{
size_t indis = kac_tane();
T * dizi = new T[ kac_tane() ];
Link<T> * simdiki = bas_;

while (simdiki)
{
dizi[kac_tane() - indis--] = simdiki->veri;
simdiki = simdiki->sonraki;
}

indis = kac_tane();
simdiki = bas_;

while (simdiki)
{
simdiki->veri = dizi[--indis];
simdiki = simdiki->sonraki;
}

delete [] dizi;
}

gonul.cpp :
#include <iostream>
#include "SingleLinkedList.h"
using namespace std;

int main()
{
SingleLinkedList<int> gonul;
for (int f=0; 10 != f; ++f)
gonul.sona_ekle(f * 2);
gonul.goster();
cout << endl;

for (int f=0; 10 != f; ++f)
gonul.basa_ekle(f * -2);

gonul.goster();
cout << endl;

for (int f=0; 20 != f; ++f)
cout << gonul[f] << ' ';
cout << endl;

gonul.ters_cevir();

for (int f=0; 20 != f; ++f)
cout << gonul[f] << ' ';
cout << endl;
return 0;
}

[myavuzselim]

Teh sckz benden once yazmis :)
#include <iostream>
using namespace std;

template<class T>
class LinkedList {

struct ListItem {
ListItem(T t) : content(t), next(0) {}
~ListItem() {}

T content;
ListItem* next;
};
int size;
ListItem* first;
ListItem* last;

public:
LinkedList() : size(0), first(0), last(0) {}
~LinkedList() {
if (size==0) return;

for(ListItem* i=first; i!=last; ) {
ListItem* next = i->next;
delete i;
i = next;
}
delete last;
first = last = 0;
}

void add(T t) {
if (first == 0) {
first = last = new ListItem(t);
}
else {
last->next = new ListItem(t);
last = last->next;
}
size++;
}

void reverse () {
if(size < 2) return;
ListItem* i1 = first;
ListItem* i2 = first->next;
i1->next = 0;
while(i2) {
ListItem* temp = i1;
i1 = i2;
i2 = i2->next;
i1->next = temp;
}
ListItem* temp = first;
first = last;
last = temp;
}

void print() {
ListItem* i = first;
while(i) {
cout << i->content << ", " << flush;
i = i->next;
}
cout << endl;
}
};


int main() {
LinkedList<int> list;
for(int i=1; i<=10; i++)
list.add(i);
list.print();
list.reverse();
list.print();
return 0;
}

[neurorebel]

#include <stdio.h>
#include <malloc.h>

typedef struct tagNode {
int iData;
tagNode *pNextNode;
} Node;

void AddNodeToEnd(Node *pRoot, int data)
{
if (pRoot == NULL)
return;
Node *pNode = pRoot;
while(pNode->pNextNode != NULL)
pNode = pNode->pNextNode;
pNode->pNextNode = (Node *)malloc(sizeof(Node));
pNode->pNextNode->iData = data;
pNode->pNextNode->pNextNode = NULL;
}

void FreeLL(Node *pRoot)
{
if (pRoot == NULL)
return;
Node *pNode = pRoot, *pTemp;
while (pNode != NULL)
{
pTemp = pNode->pN!xtNode;
free(pNode);
pNode = pTemp;
}
}

void DispLL(Node *pRoot)
{
if (pRoot == NULL)
return;
Node *pNode = pRoot;
while (pNode != NULL)
{
printf("%d ", pNode->iData);
pNode = pNode->pNextNode;
}
printf("\n");
}

Node *GetLastNode(Node *pRoot)
{
Node *pNode = pRoot;
while(pNode->pNextNode != NULL)
pNode = pNode->pNextNode;
return pNode;
}

void ReverseLL(Node **ppRoot)
{
if (ppRoot == NULL || *ppRoot == NULL || (*ppRoot)->pNextNode == NULL)
return;
Node *pNode = *ppRoot, *pPivot = GetLastNode(*ppRoot),
*pPrev, *pTemp, *pLast;

while(pNode->pNextNode != pPivot)
{
pTemp = pNode;
while(pNode->pNextNode != pPivot)
{
pPrev = pNode;
pNode = pNode->pNextNode;
}
pLast = GetLastNode(pNode);
pLast->pNextNode = pNode;

pPrev->pNextNode = pPivot;
pNode->pNextNode = NULL;

pNode = pTemp;
}

pLast = GetLastNode(pNode);
pLast->pNextNode = pNode;
pNode->pNextNode = NULL;
*ppRoot = pPivot;
}

int main()
{
Node *pRoot = (Node *)malloc(sizeof(Node));
pRoot->iData = 0;
pRoot->pNextNode = NULL;
int i;
for (i = 1; i < 10; i++)
AddNodeToEnd(pRoot, i);
DispLL(pRoot);
ReverseLL(&pRoot);
DispLL(pRoot);
FreeLL(pRoot);
}

:dahi:

[neurorebel]

istanbul 7 tepeyse, her tepenin olduğu bölgeyede tahmini 500km *asfalt* yol düşse ben derim ki 3500km yol vardır herhal...

[neurorebel]

mesela
1,2,3,4,5,6,7,8,9,10 olsun
pointer olarak 5. adresinide gondersem
10,9,8,7,6,5,4,3,2,1 cikartsin
bu olayı görmemişim yaw... tüh...

[myavuzselim]

bu olayı görmemişim yaw... tüh...
Ben gormemezlikten geldim :)

(gormezlikten (http://www.dilimiz.gen.tr/dilbilgisi/yapi/) demek lazimmis)

[Euclides]

mesela function demisim, buraya gelen parametre cok onemli. ayrica linked listenin ortasindan bir yerden bisi gondersemde calismali programin
mesela
1,2,3,4,5,6,7,8,9,10 olsun
pointer olarak 5. adresinide gondersem
10,9,8,7,6,5,4,3,2,1 cikartsin :)
Eğer double linked takılsaydık tamamda, single linked bir listede list head olmadan tüm elemanlara ulaşmamız pek mümkün değil.

[Sabahi]

Soz konusu list circular linked list olmasin sakin?

[RaiST]

Eğer double linked takılsaydık tamamda, single linked bir listede list head olmadan tüm elemanlara ulaşmamız pek mümkün değil.

eet herkesın gozunden kacmıs :)
5.ciyi gonderırse, cevirme fonk.larınız maksimum
10->9>8>7>6>5 i olusturabilecek


: circular olması ile ilgili mesajı atlamısım

[Euclides]

evet single list budur
herkes kendinden sonrakini gosteriyor.
en sondaki null i gosteriyor.
bu tip sorularda kelimeler cok onemli
mesela function demisim, buraya gelen parametre cok onemli. ayrica linked listenin ortasindan bir yerden bisi gondersemde calismali programin
mesela
1,2,3,4,5,6,7,8,9,10 olsun
pointer olarak 5. adresinide gondersem
10,9,8,7,6,5,4,3,2,1 cikartsin :)
@Sabahi:
circular linked değil

[Sabahi]

InsertFirst(1).....InsertFirst(10) deyip
Sonrada Listenin sonundan 10 taneyi silsek cok mu uckagit olur?

[sckz]

Ben gormemezlikten geldim(senin verdigin bazı sartlara uymuyor)Ben öle..
Eğer double linked takılsaydık tamamda, single linked bir listede list head olmadan tüm elemanlara ulaşmamız pek mümkün değil.Bunun da bilincindeydim aslında.. rbegin(), rend() olayına benziyo çünkü..

[sckz]

@neurorebel :

while(pNode->pNextNode != NULL)
pNode = pNode->pNextNode;
bu kısım biraz garip.. çünkü sona eleman eklemek eleman sayısını baglı olarak degisecek..

birde bu satır :

pNode->pNextNode = (Node *)malloc(sizeof(Node));
pNode->pNextNode->iData = data;
tamam C de okhe de.. C++ da garip bi satır..

@myavuzselim : bak ben bu yapı ya ctor koymayı akıl edemedim..

@sckz : ne bu şimdi.. şimdi sen kod mu yazdın.. hayır yani sen buna kod mu diyorsun.. ya bırak allah aşkına,, ya.. ya bu da kod mu,, ya.. kodun kolu bacağı kopukk.. aradaki bi kaç şey bağlı olsa nolur.. olum sckz, senin yerinde olsam bırakırım si plas plas öğrenmeyi.. sen bu kafayla.. oo hooo.. neyse işimiz var senle..

[sckz]

@sckz : ne bu şimdi.. şimdi sen kod mu yazdın.. hayır yani sen buna kod mu diyorsun.. ya bırak allah aşkına,, ya.. ya bu da kod mu,, ya.. kodun kolu bacağı kopukk.. aradaki bi kaç şey bağlı olsa nolur.. olum sckz, senin yerinde olsam bırakırım si plas plas öğrenmeyi.. sen bu kafayla.. oo hooo.. neyse işimiz var senle..len dingil.. adammı oldun olum, üç kuruş c++ bilgisiyle..

[mr1yh1]

sanal_programci bir Linkedlist tanımla diyor,
ama list'i değil nodu bekleyen bir fonksiyon istiyor..
bence orada bir yanlışlık var...
bende yazdım bitane :D template siz versiyon...
#include <iostream>
using namespace std;
class Node{
public:
Node *next;
int data;
Node( int _data ) { next=NULL ; data=_data;};
};
//bir single-way list
class List{
Node *first ;
Node *last ;
public:
List(Node* _first) { first = _first; last = first ; }
~List () {
while ( first ) {
Node *temp = first->next;
delete first;
first = temp;
}
}

void add(Node* node) { last->next = node; last = node; }

Node* begin() { return first ; };//bunu unutmamak lazim

void show (){
for( Node* i = begin(); i; i=i->next )
cout << i->data << "-" ;
}

void reverse(){
Node *before = first ;
Node *current = first ->next ;
Node *further = current->next ;
before -> next = NULL ;
for ( ;further ; before=current ,
current=further , further= further-> next )
current->next = before ;

current->next = before ; // sonuncu eleman
current = first;// kavramalar degisti
first = last ;// " "
last = current ;// " "
}
};

int main(){
List l ( new Node(1) );
for ( int i = 2 ; i <= 10 ; i++ )
l.add( new Node (i) );

cout<<"ilk liste :";
l.show(); cout<<endl;

l.reverse();
cout<<"son liste :";
l.show(); cout<<endl;
}

[neurorebel]

mr1yh1 güzel kod :)

[mr1yh1]

thanks :hey:
benimkinde hatalı kullanıma karşı önlem yok..( reverse de )myss nin ki daha sağlam..
hem Nodu listeye dahil etmesi template olarak kullanımı kolaylaştırıyor , daha iyi paketleme yapıyor..
ama listeye node mu eklenir, veri mi ?
benim sevdiğim tad node eklemek..
bir de reverse olayını daha anlaşılır hale getirmek için uğraştım..3 tane referans olmadan listede hem dolaşıp hem değişiklik yapılmıyor..

[Euclides]

Hep C++ yapacak değiliz ya birazda C yapalım değil mi ;)

#include <windows.h>
/* SONRADAN EK:
Eğer windows.h'yi eklemek istemiyorsanız
typedef unsigned long DWORD,*PDWORD;
satırını ekleyin */
#include <stdio.h>
#include <stdlib.h>
//:::::::::::::::::::::::::::::::::::::::::::::::::: :::::::::::::
void ReverseList(PDWORD *pListHead)
{
PDWORD pItem1,pItem2,pItem3;
pItem1 = *pListHead;
pItem2 = (PDWORD)*pItem1;
pItem3 = (PDWORD)*pItem2;
while(*pItem3 != 0)
{
*pItem2 = (DWORD)pItem1;
pItem1 = pItem2;
pItem2 = pItem3;
pItem3 = (PDWORD)*pItem3;
}
*pItem2 = (DWORD)pItem1;
*pItem3 = (DWORD)pItem2;
**pListHead = 0;
*pListHead = pItem3;
}
//:::::::::::::::::::::::::::::::::::::::::::::::::: :::::::::::::
void BuildList(PDWORD pList,int nCnt)
{
int i;
for(i = 0;i < nCnt;i += 2)
{
pList[i] = (DWORD)&pList[i+2];
pList[i+1] = i / 2 + 1;
}
pList[nCnt-2] = 0;
}
//:::::::::::::::::::::::::::::::::::::::::::::::::: :::::::::::::
void DumpList(PDWORD pList)
{
PDWORD pItem = pList;
while(*pItem != 0)
{
printf("%02X,",pItem[1]);
pItem = (PDWORD)*pItem;
}
printf("%02X\n",pItem[1]);
}
//:::::::::::::::::::::::::::::::::::::::::::::::::: :::::::::::::
int main(void)
{
PDWORD pListHead;
pListHead = (PDWORD)malloc(20*sizeof(DWORD));
BuildList(pListHead,20);
DumpList(pListHead);
ReverseList(&pListHead);
DumpList(pListHead);
return 0;
}
//:::::::::::::::::::::::::::::::::::::::::::::::::: :::::::::::::

[RaiST]

hadi bakalım bu sınavı geçtiniz. brainfuckla yazacak babayiğit varmı?:dahi:

[mr1yh1]

Euclides ,
senin C , C nin windows görmüş hali..

hem o while den nasıl çıktın ?

[Euclides]

Euclides ,
senin C , C nin windows görmüş hali..

hem o while den nasıl çıktın ?
Hyr canım, sadece şu tanımları yazmamak için windows.h'yi ekledim
typedef unsigned long DWORD,*PDWORD; //aslıdna sadece bunu kullanıyorum
typedef unsigned short WORD,*PWORD;
typedef unsigned char BYTE,*PBYTE;

bunları eklerseniz windows.h'yi eklemenize gerek kalmaz.

Hangi while ? Dump'daki mi ? Reversedeki mi ? (gerçi hoş 2Sinde aynı ama :) )
Kısaca 2'side listenin sonuna ulaşında çıkıyorlar.

[neurorebel]

Euclides, linked list yok orda maalesef...

[Euclides]

@neurorebel:
Orada linked list var...
BuildList fonksiyonuna biraz daha dikkat et

[neurorebel]

güzel linked listmiş :bravo: saman altından linked list yaparım demişsin direk heheh :) BuildList'i pek iyi okumadım en başta o yüzden de pListHead fazlasıyla array gibi geldi :1:

[Volkan Uzun]

ilk soru hakkinda bilgiye devam
ben adama ee basini bilmiyorum diye aynen sordum
o da demekki function 2 parametre alacak demisti
arkadaslar bunlari interview sorusu gibi dusunun, inanin bu hafta 4 firmayla gorustum
bir ucunu kapatip benim soru sormami bekliyorlar soru hakkinda.

[myavuzselim]

Peki 1.nin adresini bildikten sonra 5.nin adresini bilmeye ne gerek var?

[neurorebel]

single link list için kesinlikle 1. eleman lazım... Olmaz derim ben :iih: 2 parametre 3 parametre bişey farkettirmez... :yaaa:

[Volkan Uzun]

1. adresi bilindikten sonra 5.yi neden gerek var cunku nerde duracagini bilmek icin
ornek olarak gene
1,2,3,4,5,6,7,8,9,10 verildiyse size
ve 1, starter 5 de burda basla dendiyse
fonksiyon, 5 den baslayip ters cevirmeli
neyse bu soruya benim cevabimi yazarim :)
ama bu tip sorulara devam edicem bu hafta aldigim, sadece dikkat bnlarda sadece c++ sorulari degl c++ interview sorulari ve karsi taraftan bilgi almak icin cozume gecmeden once soru sormaniz bekleniyor
hemen cevap icin yazmaya baslamayin tam anlamadan

[mr1yh1]

bence o soruda ya yanlışlık ya da ciddi kasıt varmış..
çünkü o işlem listenin tümüne uygulanmazsa, ortadan başlanır ya da ortada durulursa liste kırılır, geri dönüşsüz
veri kaybı olur...

[Revne]

Kodunu yazmaktan cok aciklamak istiyorum yontemimi cunku suan saat gecenin 02:00 si...

listenin son elemanı belirlenir...
bu son eleman en basa gelene kadar listenin basındaki item bu son elemanın arkasına eklenir...
yani 1 2 3 4 5 ise
2 3 4 5 1
3 4 5 2 1
4 5 3 2 1
5 4 3 2 1 oluyor dimi :)

kolay gelsin..

[Revne]

Kodunu yazmaktan cok aciklamak istiyorum yontemimi cunku suan saat gecenin 02:00 si...

listenin son elemanı belirlenir...
bu son eleman en basa gelene kadar listenin basındaki item bu son elemanın arkasına eklenir...
yani 1 2 3 4 5 ise
2 3 4 5 1
3 4 5 2 1
4 5 3 2 1
5 4 3 2 1 oluyor dimi :)

kolay gelsin..


Kabul ediyorum salakca olmus...:iih:
Neyse forumdaki ilk mesajlarimdandi...