You are given an array of size 1001. The array contents are at random containing values from 1 to 1001. All element except one occurs only once in that array. Find the repeating element. Optimize for time and space complexity.
Write an algorithm for run-length encoding
How will you find the middle node of a linked list? Optimize for time and space.
How will you check whether a linked list has a loop?
Subscribe to:
Post Comments (Atom)
4 comments:
middle node in linklist:
middle_node(head)
temp1 <- head
temp2 <- head
while next(temp2) != NULL or next(next(temp2)) != NULL
temp1 <- next(temp1)
temp2 <- next(next(temp2))
return temp1
loop in linklist:
loop(head)
temp1 <- head
temp2 <- head
while temp2 != NULL
temp1 <- next(temp1)
temp2 <- next(temp2)
if temp1 = temp2
return TRUE
return FALSE
run-length encoding:
run_length()
step1:
cur_char <= prev_char <= Input
count <- 1
step2:
Repeat up to step 4 until no more characters for Input
step3:
cur_char <= Input
if prev_char = cur_char
count <- count + 1
else
write prev_char,count
count <- 1
step4:
prev_char <- cur_char
step5:
write prev_char,count
return
For d 1st 1,find d sum of all d array elements n subtract it from 1001*1002/2 i.e n*(n+1)/2.D duplicate element s d value u get
for the first here the snippet:
fun(n)
{
if n is even
result = (n ^ (n >> 1));
else
result = 0;
for(int i = 0;i < n;i++)
{
result = result ^ array[i];
}
return result;
}
Post a Comment