Linked List Problems from Cracking the Coding Interview

[sinhaaman]

Solve all questions on CTCI. DON'T Skip any.

[emmcold]

@sinhaaman Do you have the questions from the new version of the Cracking the coding interview book?

[emmcold]

Problem 2.1. a) method CTCIprob21a(); Problem 2.1. b) If a temporary buffer is not allowed, then I will have a double loop, I will keep one pointer at the beginning of the linked list (first element) and run one loop and the second pointer with the second loop with the second element and I will move the pointer until the end of the loop. CTCIprob21b(); Return the kth element from the back- CTCIprob22(int k){

[sinhaaman]

@emmcold yes, I have the new version of the book (version 6). I was looking at your commits for example, f468bae1b097f85e6adcb1de8fe883a39ed010bd . Can you please check comments on that commit?

[emmcold]

@sinhaaman I need help with the problem 2.4 I don't understand it. :(

[emmcold]

@sinhaaman I need help with this; /**

• Sum lists (the forward version)
• e.g. 7+1+6 and 5+9+2 to 2+1+9
• Solution: Reverse the two linked list and use the above approach.
• Solution 2: USe a stack. */ How do we solve this problem? I have these ideas, but how else?

[sinhaaman]

There is no need to reverse the linked list. You have to add the linked list in the forward direction.

1. Iterate through the bigger list (you can call the length function in advance to know the length of the two list).
2. Then, Use sum and carry approach, sum = something and carry = something.
3. Modify the content of the bigger linked list, with this sum and carry approach.
4. In the end if the value of carry is 1, then add another node in the end of linked list with the data 1.

[emmcold]

@sinhaaman will my ideas of reverse work? And if not, why?

[emmcold]

p.s. @sinhaaman I don't understand your algo up. :(

[emmcold]

@sinhaaman can you check the other solutions from the cracking the coding interview.

Currently 2 problems are unsolved there:

• [x] Partition problem(2.4) as I don't understand the problem.
• [x] Forward sum of the linked list nodes.

[sinhaaman]

@EmiraZiberi yes, your ideas will work for the forward sum problem.

[sinhaaman]

In question number 2.4, it says that you are given a linked list. 3 -> 10 -> 6 -> 1 -> 7 -> 20 ->5 ->NULL

and you are given an integer n. You need to partition the linked list in such a manner that the first part contains the elements less than n. e.g. consider the two partition around n=5 3 -> 1 -> NULL (Linked List having elements less than 5) LIST 1 10 -> 6 -> 7 -> 20 -> 5 ->NULL (Liked List having elements greater than or equal to 5). LIST 2

Now let's append LIST 2 to LIST 1 we get: 3 -> 1 -> 10 -> 6 -> 7 -> 20 -> 5 ->NULL

This is the expected result from your code.

Let me know if you need more explanation.

[emmcold]

@sinhaaman then why should i use the approaches you mentioned earlier? :grin:

[emmcold]

The solution is: * Solution: Reverse the two linked list and use the above approach.