Recent questions tagged linked-list / GATE Overflow for GATE CSE

2 votes

1 answer

211

Semaphores:
Assume that you have a semaphore associated with each item on a doubly linked list. Using No other synchronization primitive, What is the fewest number of semaphore that you must acquire for any operation (lookup, insert, delete) ?

Assume that you have a semaphore associated with each item on a doubly linked list. Using No other synchronization primitive, What is the fewest number of semaphore that ...

mcjoshi

1.2k views

mcjoshi asked Oct 11, 2016

5 votes

3 answers

212

GATE Overflow | Data Structures | Test 1 | Question: 24
You are given a linked list, $L$ of $n$ integers, and another linked list, $P$, of $k$ integers where $k <<< n$. $L$ is sorted in ascending order but $P$ is not necessarily sorted. The operation $\text{print_lots}(L,P)$ will ... space is available) ______________ ? $\Theta(n)$ $\Theta(n \log k)$ $\Theta(n k)$ $\Theta (n k\log k)$

You are given a linked list, $L$ of $n$ integers, and another linked list, $P$, of $k$ integers where $k <<< n$. $L$ is sorted in ascending order but $P$ is not necessari...

Arjun

1.0k views

Arjun asked Oct 10, 2016

4 votes

2 answers

213

GATE Overflow | Data Structures | Test 1 | Question: 2
For a singly linked list where each node has a pointer to a data array as well as a next pointer, what would be the worst case time complexity to delete an intermediate node $x$ (given a pointer to it)? $O(n)$ $O(1)$ $\Omega(n)$ $O(\log n)$

For a singly linked list where each node has a pointer to a data array as well as a next pointer, what would be the worst case time complexity to delete an intermediate n...

Arjun

1.5k views

Arjun asked Oct 10, 2016

2 votes

1 answer

214

GATE Overflow | Data Structures | Test 1 | Question: 1
The following C function takes a singly-linked list of integers as a parameter and rearranges the elements of the list. The function is called with the list containing the integers 1,2,3,4,5,6,7 in the given order. What will be the contents of the list after the function completes ... 2,1,3,4,5,6,7 2,1,4,3,6,5,7 1,3,2,5,4,7,6 2,3,4,5,6,7,1

The following C function takes a singly-linked list of integers as a parameter and rearranges the elements of the list. The function is called with the list containing th...

Arjun

552 views

Arjun asked Oct 10, 2016

3 votes

2 answers

215

GATE Overflow | Algorithms | Test 1 | Question: 18
Time complexity of the optimal algorithm to interchange the $m^{th}$ and $n^{th}$ elements of a singly Linked List is $\Theta(m+n)$ $\Theta(m)$ when $m\geq n$ otherwise $\Theta(n)$ $\Theta(m)$ if $m \leq n$ otherwise $\Theta(n)$ $\Theta(m+ \min (m,n))$

Time complexity of the optimal algorithm to interchange the $m^{th}$ and $n^{th}$ elements of a singly Linked List is $\Theta(m+n)$$\Theta(m)$ when $m\geq n$ otherwise $...

Bikram

611 views

Bikram asked Oct 4, 2016

3 votes

2 answers

216

linked list
Two linked lists having n and m elements are stored in sorted order. What is the worst case complexity of program to print common elements of two lists ? $\begin{align*} &A. \ \ O(n) \\ &B. \ \ \text{max}(m,n) \\ &C. \ \ \text{min}(m,n) \\ &D. \ \ m+n \end{align*}$

Two linked lists having n and m elements are stored in sorted order. What is the worst case complexity of program to print common elements of two lists ?$\begin{align*} &...

Vishal Goyal

713 views

Vishal Goyal asked Sep 26, 2016

0 votes

1 answer

217

UGC NET CSE | August 2016 | Part 2 | Question: 21
Consider an implementation of unsorted single linked list. Suppose it has its representation with a head and a tail pointer (i.e. pointers to the first and last nodes of the linked list). Given the representation, which of the following ... linked list. Deletion of the front node of the linked list. Deletion of the last node of the linked list.

Consider an implementation of unsorted single linked list. Suppose it has its representation with a head and a tail pointer (i.e. pointers to the first and last nodes of ...

makhdoom ghaya

2.1k views

makhdoom ghaya asked Sep 24, 2016

0 votes

1 answer

218

Linked Lists
Q)The below code returns decimal value of binary linked list int val(struct Node *head) { struct Node *p = head; int val2= 0; while (p!= NULL) { XYZ;//fill the contents of XYZ p = p→next; } return val2; } What is XYZ in above code ? Please provide a sound explaination too.

Q)The below code returns decimal value of binary linked list int val(struct Node *head) { struct Node *p = head; int val2= 0; while (p!= NULL) { XYZ;//fill the contents o...

Manikant Kumar

584 views

Manikant Kumar asked Sep 23, 2016

0 votes

1 answer

219

Linked_List
To insert a node at the end of double linked list we need to modify two pointers right??But answer given is one pointer. can someone clarify?

To insert a node at the end of double linked list we need to modify two pointers right??But answer given is one pointer.can someone clarify?

cse23

568 views

cse23 asked Sep 9, 2016

3 votes

1 answer

220

Recurrence relation in constructing balanced tree from linked list and array
Consider the following algorithm to build a balanced search tree from a sorted sequence. * Make the mid-point of the sequence the root of the tree * Recursively construct balanced search trees from elements to the left and right of the ... O(n) 2- O(n log n) 3- O(n2) 4- Depends on the contents of the original sequence

Consider the following algorithm to build a balanced search tree from a sorted sequence.* Make the mid-point of the sequence the root of the tree* Recursively construct b...

dd

2.8k views

dd asked Aug 23, 2016

1 votes

1 answer

221

Linked list
How does this code return Nth the node from the end of the linked list in one pass? Node * GetNthNode ( Node* Head , int NthNode ) { Node * pNthNode = NULL; Node * pTempNode = NULL; int nCurrentElement = 0; for ( pTempNode = Head; pTempNode != NULL; ... nCurrentElement - NthNode > 0) { pNthNode = pNthNode ->pNext; } } if (pNthNode ) { return pNthNode; } else return NULL; }

How does this code return Nth the node from the end of the linked list in one pass?Node * GetNthNode ( Node* Head , int NthNode ){ Node * pNthNode = NULL; Node ...

Anushka Basu

524 views

Anushka Basu asked Jul 29, 2016

2 votes

1 answer

222

UGC NET CSE | December 2013 | Part 2 | Question: 22
If the queue is implemented with a linked list, keeping track of a front pointer, which of these pointers will change during an insertion into an non-empty queue? Neither of the pointer change Only front pointer changes Only rear pointer changes Both of the pointer changes

If the queue is implemented with a linked list, keeping track of a front pointer, which of these pointers will change during an insertion into an non-empty queue?Neither ...

go_editor

7.0k views

go_editor asked Jul 25, 2016

3 votes

2 answers

223

Amazon Interview question on Linked list
Given a linked list : 1->2->3->4->5->6, make the following changes 1->6->2->5->3->4 What would be the most effiicient way to make this change?

Given a linked list :1->2->3->4->5->6,make the following changes1->6->2->5->3->4What would be the most effiicient way to make this change?

sh!va

2.4k views

sh!va asked Jul 21, 2016

1 votes

2 answers

224

UGC NET CSE | September 2013 | Part 2 | Question: 12
The efficient data structure to insert/delete a number in a stored set of number is Queue Linked list Doubly linked list Binary tree

The efficient data structure to insert/delete a number in a stored set of number isQueueLinked listDoubly linked listBinary tree

go_editor

4.6k views

go_editor asked Jul 20, 2016

4 votes

7 answers

225

ISRO2014-49
Consider a single linked list where $F$ and $L$ are pointers to the first and last elements respectively of the linked list. The time for performing which of the given operations depends on the length of the linked list? Delete the first element of the list Interchange the first two elements of the list Delete the last element of the list Add an element at the end of the list

Consider a single linked list where $F$ and $L$ are pointers to the first and last elements respectively of the linked list. The time for performing which of the given op...

go_editor

16.0k views

go_editor asked Jul 1, 2016

5 votes

2 answers

226

How to Trace the recursion ?
Can Someone explain either Tree or Stack method to trace out this recursion ? What is the output of this Program ?

Can Someone explain either Tree or Stack method to trace out this recursion ?What is the output of this Program ?

shekhar chauhan

1.5k views

shekhar chauhan asked Jun 28, 2016

5 votes

3 answers

227

ISRO2008-72
Which of the following operations is performed more efficiently by doubly linked list than by linear linked list? Deleting a node whose location is given Searching an unsorted list for a given item Inserting a node after the node with a given location Traversing the list to process each node

Which of the following operations is performed more efficiently by doubly linked list than by linear linked list?Deleting a node whose location is givenSearching an unsor...

go_editor

14.7k views

go_editor asked Jun 13, 2016

2 votes

1 answer

228

ISRO2008-71
The time required to search an element in a linked list of length n is $O(\log_2 n)$ $O(n)$ $O(1)$ $O(n^2)$

The time required to search an element in a linked list of length n is$O(\log_2 n)$$O(n)$$O(1)$$O(n^2)$

go_editor

18.0k views

go_editor asked Jun 13, 2016

14 votes

2 answers

229

ISI2015-PCB-CS-3a
Consider a linked list containing $n$ nodes, where each node contains two pointers $ptr1$ and $ptr2$. For each node, $ptr1$ points to the next node of the list. Describe how pointer $ptr2$ should be set up for each node so that you will be able to locate the $i$-th node from the start node in the list traversing no more than $[\log\: i] + [i/2]$ nodes.

Consider a linked list containing $n$ nodes, where each node contains two pointers $ptr1$ and $ptr2$. For each node, $ptr1$ points to the next node of the list. Describe ...

go_editor

1.8k views

go_editor asked May 29, 2016

8 votes

1 answer

230

CMI2012-B-07
We use the notation $[x1,x2,...,xn]$ to denote a list of integers. $[]$ denotes the empty list, and $[n]$ is the list consisting of one integer $n$. For a nonempty list l, $head(l)$ returns the first element of $l$, and $tail(l)$ returns the list ... (tail(l)) then return g(tail(l)) else return(false) When does $f(l)$ return the value true for an input $l$? Explain your answer.

We use the notation $[x1,x2,...,xn]$ to denote a list of integers. $[]$ denotes the empty list, and $[n]$ is the list consisting of one integer $n$. For a nonempty list l...

go_editor

1.1k views

go_editor asked May 23, 2016

2 votes

0 answers

231

CMI2011-B-07a
A finite sequence of bits is represented as a list with values from the set $\{0,1\}$-for example, $[0,1,0], [1,0,1,1], \dots [ \: ]$ denotes the empty list, and $[b]$ is the list consisting of one bit $b$. For a nonempty list $l, \text{ head}(l)$ returns the first ... g2(n) if (n == 0) then return(0) else return f2(g2(n-1),g1(n)) endif What is the value of $g2(7)$ and $g2(8)$?

A finite sequence of bits is represented as a list with values from the set $\{0,1\}$—for example, $[0,1,0], [1,0,1,1], \dots [ \: ]$ denotes the empty list, and $[b]$ ...

go_editor

397 views

go_editor asked May 20, 2016

1 votes

0 answers

232

CMI2010-B-07a
A finite sequence of bits is represented as a list with values from the set {0,1}—for example, [0,1,0], [1,0,1,1], . . . . [ ] denotes the empty list, and [b] is the list consisting of one bit b. The function $length(l)$ returns the length (number of ... tail(t)),mystery2(s,tail(t)))) endif What is the value of $length(mystery2(s,t))$ in terms of $length(s)$ and $length(t)$?

A finite sequence of bits is represented as a list with values from the set {0,1}—for example, [0,1,0], [1,0,1,1], . . . .[ ] denotes the empty list, and [b] is the...

go_editor

443 views

go_editor asked May 19, 2016

5 votes

2 answers

233

ISRO-2013-4
The following steps in a linked list p = getnode() info(p) = 10 next (p) = list list = p result in which type of operation? Pop operation in stack Removal of a node Inserting a node Modifying an existing node

The following steps in a linked listp = getnode() info(p) = 10 next (p) = list list = presult in which type of operation?Pop operation in stackRemoval of a nodeInserting ...

makhdoom ghaya

6.7k views

makhdoom ghaya asked Apr 25, 2016

0 votes

4 answers

234

How to manipulate the given linked list in the following manner in O(n) time ?
If we are given a linked list then we have to manipulate such that even indexed node are arranged together and odd indexed nodes are arranged together after even indexed nodes for instance the given linked list is 1-->2-->3-->4-->5-->6 , so the op should be 2-->4-->6-->1-->3-->5

If we are given a linked list then we have to manipulate such that even indexed node are arranged together and oddindexed nodes are arranged together after even indexed n...

radha gogia

962 views

radha gogia asked Apr 7, 2016

97 votes

6 answers

235

GATE CSE 2016 Set 2 | Question: 15
$N$ items are stored in a sorted doubly linked list. For a delete operation, a pointer is provided to the record to be deleted. For a decrease-key operation, a pointer is provided to the record on which the operation is to be performed. An algorithm performs the following operations ... together? $O(\log^{2} N)$ $O(N)$ $O(N^{2})$ $\Theta\left(N^{2}\log N\right)$

$N$ items are stored in a sorted doubly linked list. For a delete operation, a pointer is provided to the record to be deleted. For a decrease-key operation, a pointer is...

Akash Kanase

34.4k views

Akash Kanase asked Feb 12, 2016

2 votes

2 answers

236

Linked list

Sourabh Kumar

3.0k views

Sourabh Kumar asked Jan 31, 2016

1 votes

1 answer

237

MadeEasy Test Series: Programming & DS - Linked Lists
Here, what will be the Head->Next , I am confused is it first element 50 or second element 29.

Here, what will be the Head->Next , I am confused is it first element 50 or second element 29.

Pradip Nichite

751 views

Pradip Nichite asked Jan 22, 2016

1 votes

0 answers

238

Linked allocation
A program has just read the $12^{th}$ disk block using linked allocation. If it next want to read the $5^{th}$ disk block, then the number of disk blocks must the program already read to reach the $5^{th}$ disk block ________.

A program has just read the $12^{th}$ disk block using linked allocation. If it next want to read the $5^{th}$ disk block, then the number of disk blocks must the program...

Sourabh Kumar

427 views

Sourabh Kumar asked Jan 22, 2016

0 votes

1 answer

239

linked list
What does the following function do for a given Linked List with first node as head? void fun1(struct node* head) { if(head == NULL) return; fun1(head->next); printf("%d ", head->data); } will it print 5-4-3-2-1 or 4-3-2-1 if i/p is 1-2-3-4-5?Will the last 5 get printed or not , due to return;

What does the following function do for a given Linked List with first node as head?void fun1(struct node* head){ if(head == NULL) return; fun1(head->next); prin...

chat28

5.4k views

chat28 asked Jan 21, 2016

0 votes

1 answer

240

Given the unordered linked list as a queue, what operations would take O(1) time?
My doubt is that the single list queue is the form : 1->2->3->4->5->6->7->8->9->NULL with 1 as the rear node and 9 as the front node. Also, in a queue, addition ... I just want to confirm whether my answer was right or the answer given. Source : testbook.com live test on 3rd January, 2016

My doubt is that the single list queue is the form : 1->2->3->4->5->6->7->8->9->NULL with 1 as the rear node and 9 as the front node. Also, in a queue, addition takes fro...

Utk

615 views

Utk asked Jan 4, 2016

tags	tag:apple
author	user:martin
title	title:apple
content	content:apple
exclude	-tag:apple
force match	+apple
views	views:100
score	score:10
answers	answers:2
is accepted	isaccepted:true
is closed	isclosed:true